lambda_calculus.clj

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