-
-
Save ckirkendall/4581826 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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)))))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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