Lambda.clj

(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))))))

Lambda.repl.clj

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