Skip to content

Instantly share code, notes, and snippets.

@alexandergunnarson
Last active February 14, 2017 16:13
Show Gist options
  • Save alexandergunnarson/588bf86980d40d31bea8986fd964c4f4 to your computer and use it in GitHub Desktop.
Save alexandergunnarson/588bf86980d40d31bea8986fd964c4f4 to your computer and use it in GitHub Desktop.
(ns quantum.lambda-calculus)
(defmacro λ [arg ret] `(fn [~arg] ~ret))
(def ^{:doc "Whatever function `f` you pass in, called on itself (composed) `n` times."}
NUM (λ n (λ f (λ x ((apply comp (repeat n f)) x)))))
(def I (λ x x)) ; `identity`
(def K (λ x (λ y x))) ; `firsta`
(def ZERO (NUM 0))
(def TRUE (λ x (λ y x))) ; `firsta`
(def FALSE (λ x I))
(def AND (λ p (λ q ((p q) p))))
(def OR (λ p (λ q ((p p) q))))
(def NOT (λ p ((p FALSE) TRUE)))
(def IF (λ p (λ a (λ b ((p a) b)))))
(def ISZERO (λ n ((n (λ x FALSE)) TRUE)))
(def S (λ x (λ y (λ z ((x z) (y z))))))
(def B (λ x (λ y (λ z (x (y z))))))
(def C (λ x (λ y (λ z ((x z) y)))))
(def W (λ x (λ y ((x y) y))))
(def U (λ x (λ y (y ((x x) y)))))
(def ω (λ x (x x))) ; self-call
#_(def Ω (ω ω)) ; stack overflow
(def Y (λ g ((λ x (g (x x))) (λ x (g (x x)))))) ; Y-combinator, a fixed-point of its argument
#_"
(((IF TRUE) 1) FALSE) -> 1
((AND TRUE) 1) -> 1
((AND FALSE) 1) -> FALSE
(ISZERO FALSE) -> TRUE
(ISZERO ZERO) -> TRUE
(ISZERO I) -> FALSE
(ISZERO TRUE) -> ISZERO
(ISZERO (NUM 2)) -> FALSE
((λ x (+ x 1)) 2) <-> (let [x 2] (+ x 1))
"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment