Skip to content

Instantly share code, notes, and snippets.

@ckirkendall
Forked from bkyrlach/Lambda.scala
Last active December 11, 2015 09:48
Show Gist options
  • Save ckirkendall/4581826 to your computer and use it in GitHub Desktop.
Save ckirkendall/4581826 to your computer and use it in GitHub Desktop.
(ns lambda-calc.core)
;; THIS MACRO CREATES A LAMBDA THAT IS COMPATABLE WITH LAMBDA AS DEFINED IN
;; LAMBDA CALCULUS -> CURRIED NON-RECURSIVE
(defmacro f* [args & body]
(let [fsym (gensym "fn")
alist (for [n (range 1 (count args))]
(take n args))
curries (map #(do `(~(vec %) (partial ~fsym ~@%))) alist)]
`(fn ~fsym ~@curries (~args ~@body))))
;;LOGIC FUNCTIONS
(def TRUE (f* [a b] a))
(def FALSE (f* [a b] b))
(def AND (f* [p q] (p q p)))
(def OR (f* [p q] (p p q)))
(def NOT (f* [p a b] (p b a)))
(def IF (f* [p a b] (p a b)))
;;CHURCH ENCODING
(def SUCC (f* [n f x] (f (n f x))))
(def PRED (f* [n f x] ((n (f* [g h] (h (g f))) (fn [u] x)) (fn [u] u))))
(def ZERO (f* [f x] x))
(def ONE (f* [f x] (f x)))
(def TWO (SUCC ONE))
(def THREE (SUCC TWO))
(def ADD (f* [m n f x] (m f (n f x))))
(def SUB (f* [m n] ((n PRED) m)))
(def MULT (f* [m n f x] (m (n f) x)))
(def ZERO? (f* [n] (n (f* [x] FALSE) TRUE)))
(def EQUALS? (f* [m n] (AND (ZERO? (SUB m n)) (ZERO? (SUB n m)))))
(def GREATER? (f* [m n] (AND (NOT (ZERO? (SUB m n))) (ZERO? (SUB n m)))))
(def LESS? (f* [m n] (AND (ZERO? (SUB m n)) (NOT (ZERO? (SUB n m))))))
;Y COMBINATOR
(def Y (f* [f]
((f* [x] (x x))
(f* [x]
(f (fn [& args]
(apply (x x) args)))))))
;LIST OPERATIONS
(def NIL (f* [x] TRUE))
(def CONS (f* [x y z] (z x y)))
(def HEAD (f* [p] (p TRUE)))
(def TAIL (f* [p] (p FALSE)))
(def NIL? (f* [l] (l (f* [x y] FALSE))))
;;We have to use delay and @ here because clojure is not lazy
(def FILTER-HELPER
(f* [filt t l]
(IF (NIL? l)
(delay l)
(delay
@(IF (t (HEAD l))
(delay (CONS (HEAD l) @(filt t (TAIL l))))
(delay @(filt t (TAIL l))))))))
(def FILTER (f* [t l] @((Y FILTER-HELPER) t l)))
;;We have to use delay and @ here because clojure is not lazy
(def MAP-HELPER
(f* [m f l]
(IF (NIL? l)
(delay l)
(delay (CONS (f (HEAD l)) @(m f (TAIL l)))))))
(def MAP (f* [f l] @((Y MAP-HELPER) f l)))
;;CALCULATING FACTORIALS
(def FACT-HELPER (f* [fact x] (IF (ZERO? x) (delay ONE) (delay (MULT x @(fact (PRED x)))))))
(def FACTORIAL (f* [x] @((Y FACT-HELPER) x)))
;;SIMPLE PRIME NUMBER CHECKER FOR CHURCH NUMERALS
(def PRIME-HELPER
(f* [p? n s c]
(IF (GREATER? s n) (delay TRUE)
(IF (GREATER? (MULT s c) n) (delay @(p? n (SUCC s) TWO))
(IF (EQUALS? (MULT s c) n) (delay FALSE)
(delay @(p? n s (SUCC n))))))))
(def PRIME? (f* [x] @((Y PRIME-HELPER) x TWO TWO)))
;;THIS IS A HELPER FUNCTION THAT ALLOWS US TO PRINT A LIST OF CHURCH NUMERALS
(defn print-list [l]
@(IF (NIL? l) (delay (println))
(delay
(do (print (str " " ((HEAD l) #(+ 1 %) 0)))
(print-list (TAIL l))))))
user> (PRED TWO #(+ 1 %) 0)
1
user> ((MULT TWO THREE) #(+ 1 %) 0)
6
user> (IF (EQUALS? (PRED THREE) TWO) "true" "false")
"true"
user> (IF (EQUALS? (PRED THREE) THREE) "true" "false")
"false"
user> (IF (LESS? (PRED THREE) THREE) "true" "false")
"true"
user> (IF (LESS? (PRED THREE) TWO) "true" "false")
"false"
user> ((FACTORIAL THREE) #(+ 1 %) 0)
6
user> (IF (PRIME? THREE) "true" "false")
"true"
user> (IF (PRIME? (SUCC THREE)) "true" "false")
"false"
user> (IF (PRIME? (SUCC (MULT TWO THREE))) "true" "false") ;7
"true"
user> (print-list (FILTER PRIME? (CONS TWO (CONS THREE (CONS (SUCC THREE) NIL)))))
2 3
nil
user> (print-list (MAP (f* [x] (SUCC x)) (CONS TWO (CONS THREE (CONS (SUCC THREE) NIL)))))
3 4 5
nil
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment