ADD: Lambda Calculus in Clojure

Source: https://github.com/srodrigo/lambda-calculus-in-clojure

6 files changed, 231 insertions, 0 deletions

diff --git a/languages/c/clojure/lambda-core/deps.edn b/languages/c/clojure/lambda-core/deps.edn
new file mode 100644
index 0000000..6cb68b3
--- /dev/null
+++ b/languages/c/clojure/lambda-core/deps.edn
@@ -0,0 +1,6 @@
+{:paths ["src"]
+ :deps {org.clojure/clojure {:mvn/version "1.10.0"}}
+ :aliases
+ {:test
+  {:extra-paths ["test"]
+   :main-opts ["-m" "test-runner"]}}}
diff --git a/languages/c/clojure/lambda-core/src/booleans.clj b/languages/c/clojure/lambda-core/src/booleans.clj
new file mode 100644
index 0000000..e48f9a7
--- /dev/null
+++ b/languages/c/clojure/lambda-core/src/booleans.clj
@@ -0,0 +1,29 @@
+(ns booleans)
+
+(defmacro λ
+  [args & body]
+  `(fn [~args] ~@body))
+
+(def T
+  (λ a (λ b a)))
+
+(def F
+  (λ a (λ b b)))
+
+(def And
+  (λ p (λ q ((p q) p))))
+
+(def Or
+  (λ p (λ q ((p p) q))))
+
+(def Not
+  (λ p ((p F) T)))
+
+(def Xor
+  (λ a (λ b ((a (Not b)) b))))
+
+(def If
+  (λ p (λ a (λ b ((p a) b)))))
+
+(def toBoolean
+  (λ f ((f true) false)))
diff --git a/languages/c/clojure/lambda-core/src/numerals.clj b/languages/c/clojure/lambda-core/src/numerals.clj
new file mode 100644
index 0000000..e18da0f
--- /dev/null
+++ b/languages/c/clojure/lambda-core/src/numerals.clj
@@ -0,0 +1,47 @@
+(ns numerals)
+
+(defmacro λ
+  [args & body]
+  `(fn [~args] ~@body))
+
+(def zero
+  (λ f (λ x x)))
+
+(def one
+  (λ f (λ x (f x))))
+
+(def two
+  (λ f (λ x (f (f x)))))
+
+(def succ
+  (λ n (λ f (λ x (f ((n f) x))))))
+
+(def pred
+  (λ n (λ f (λ x (((n (λ g (λ h (h (g f))))) (λ u x)) (λ u u))))))
+
+(def plus
+  (λ m (λ n ((n succ) m))))
+
+(def minus
+  (λ m (λ n ((n pred) m))))
+
+(def mult
+  (λ m (λ n (λ f (m (n f))))))
+
+(def exp
+  (λ m (λ n (n m))))
+
+(def fromInt
+  (λ n
+    (if (= n 0)
+      zero
+      (succ (fromInt (- n 1))))))
+
+(def toInt
+  (λ f ((f (λ n (+ n 1))) 0)))
+
+(def λToStr
+  (λ f ((f (λ n (format "f(%s)" n))) "n")))
+
+(def toStr
+  (λ f (format "λf.λn.(%s)" (λToStr f))))
diff --git a/languages/c/clojure/lambda-core/test/booleans_test.clj b/languages/c/clojure/lambda-core/test/booleans_test.clj
new file mode 100644
index 0000000..8a75125
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/booleans_test.clj
@@ -0,0 +1,67 @@
+(ns booleans-test
+  (:require [booleans :refer :all]
+            [clojure.test :refer :all]))
+
+(deftest λ-booleans
+  (testing "true"
+    (is (= (toBoolean T) true)))
+
+  (testing "false"
+    (is (= (toBoolean F) false)))
+
+  (testing "If"
+    (is (= (toBoolean (((If T) T) F)) true))
+    (is (= (toBoolean (((If F) T) F)) false)))
+
+  (testing "And"
+    (is (= (toBoolean ((And T) T)) true))
+    (is (= (toBoolean ((And T) F)) false))
+    (is (= (toBoolean ((And F) T)) false))
+    (is (= (toBoolean ((And F) F)) false))
+    (is (= (toBoolean ((And T) ((And T) T))) true))
+    (is (= (toBoolean ((And T) ((And F) T))) false)))
+
+  (testing "Or"
+    (is (= (toBoolean ((Or T) T)) true))
+    (is (= (toBoolean ((Or T) F)) true))
+    (is (= (toBoolean ((Or F) T)) true))
+    (is (= (toBoolean ((Or F) F)) false))
+    (is (= (toBoolean ((Or F) ((Or F) F))) false))
+    (is (= (toBoolean ((Or F) ((Or T) F))) true)))
+
+  (testing "Not"
+    (is (= (toBoolean (Not T)) false))
+    (is (= (toBoolean (Not F)) true))
+    (is (= (toBoolean (Not (Not T))) true))
+    (is (= (toBoolean (Not (Not F))) false)))
+
+  (testing "Xor"
+    (is (= (toBoolean ((Xor T) T)) false))
+    (is (= (toBoolean ((Xor T) F)) true))
+    (is (= (toBoolean ((Xor F) T)) true))
+    (is (= (toBoolean ((Xor F) F)) false)))
+
+  (testing "Expressions"
+    ;T AND T AND F OR T
+    (is (= (toBoolean ((And T) ((And T) ((Or F) T))))
+           true))
+
+    ;T AND F AND F OR T AND T
+    (is (= (toBoolean ((And T) ((And F) ((Or F) ((And T) T)))))
+           false))
+
+    ;T OR (F AND F OR T AND T)
+    (is (= (toBoolean ((Or T) ((And F) ((Or F) ((And T) T)))))
+           true))
+
+    ;F OR (F AND F OR F AND T)
+    (is (= (toBoolean ((Or F) ((And F) ((Or F) ((And F) T)))))
+           false))
+
+    ;F OR F AND F OR T AND T
+    (is (= (toBoolean ((And ((Or F) F)) ((And T) ((Or F) T))))
+           false))
+
+    ;T OR F AND F OR T AND T
+    (is (= (toBoolean ((And ((Or T) F)) ((And T) ((Or F) T))))
+           true))))
diff --git a/languages/c/clojure/lambda-core/test/numerals_test.clj b/languages/c/clojure/lambda-core/test/numerals_test.clj
new file mode 100644
index 0000000..44458dc
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/numerals_test.clj
@@ -0,0 +1,75 @@
+(ns numerals-test
+  (:require [numerals :refer :all]
+            [clojure.test :refer :all]))
+
+(deftest λ-numbers
+  (testing "zero"
+    (is (= (toInt zero) 0)))
+
+  (testing "one"
+    (is (= (toInt (succ zero)) 1))
+    (is (= (toInt one)) 1))
+
+  (testing "two"
+    (is (= (toInt (succ (succ zero))) 2))
+    (is (= (toInt two)) 2))
+
+  (testing "three"
+    (is (= (toInt (succ (succ (succ zero)))) 3)))
+
+  (testing "predecessor"
+    (is (= (toInt (pred one)) 0))
+    (is (= (toInt (pred two)) 1))
+    (is (= (toInt (pred (succ (succ (succ zero))))) 2))
+    (is (= (toInt (pred (fromInt 10))) 9))))
+
+(deftest λ-numerical-operations
+  (testing "addition"
+    (is (=
+         (toInt ((plus (fromInt 7)) (fromInt 5)))
+         12))
+    (is (=
+         (toInt ((plus (fromInt 7)) ((plus (fromInt 6)) (fromInt 2))))
+         15)))
+
+  (testing "subtraction"
+    (is (=
+         (toInt ((minus (fromInt 7)) (fromInt 5)))
+         2))
+    (is (=
+         (toInt ((minus (fromInt 7)) ((minus (fromInt 6)) (fromInt 2))))
+         3)))
+
+  (testing "multiplication"
+    (is (=
+          (toInt ((mult (fromInt 2)) (fromInt 3)))
+          6))
+    (is (=
+          (toInt ((mult (fromInt 2)) ((mult (fromInt 5)) (fromInt 3))))
+          30)))
+
+  (testing "exponentiation"
+    (is (=
+          (toInt ((exp (fromInt 2)) (fromInt 3)))
+          8))
+    (is (=
+          (toInt ((exp (fromInt 2)) ((exp (fromInt 2)) (fromInt 3))))
+          256))))
+
+(deftest λ-numeral-expressions
+  (testing "numeral expressions"
+    ; 3 * (2 + 5) - 2^3
+    (is (=
+         (toInt ((minus ((mult (fromInt 3))
+                         ((plus (fromInt 2)) (fromInt 5))))
+                 ((exp (fromInt 2)) (fromInt 3))))
+         13))))
+
+(deftest λ-toStr
+  (testing "toStr"
+    (is (= (toStr zero) "λf.λn.(n)"))
+    (is (= (toStr one) "λf.λn.(f(n))"))
+    (is (= (toStr two) "λf.λn.(f(f(n)))"))
+    (is (= (toStr (succ (succ (succ zero)))) "λf.λn.(f(f(f(n))))"))
+    (is (= (toStr (fromInt 5)) "λf.λn.(f(f(f(f(f(n))))))"))))
+
diff --git a/languages/c/clojure/lambda-core/test/test_runner.clj b/languages/c/clojure/lambda-core/test/test_runner.clj
new file mode 100644
index 0000000..038b818
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/test_runner.clj
@@ -0,0 +1,7 @@
+(ns test-runner
+  (:require [clojure.test :as t]
+            [numerals-test]
+            [booleans-test]))
+
+(defn -main [& args]
+  (t/run-tests 'numerals-test 'booleans-test))