Merge pull request #3 from nitincodery/clojure

Add Lambda Calculus in Clojure

11 files changed, 315 insertions, 0 deletions

diff --git a/languages/c/clojure/README.md b/languages/c/clojure/README.md
new file mode 100644
index 0000000..cbeeb34
--- /dev/null
+++ b/languages/c/clojure/README.md
@@ -0,0 +1,11 @@
+[Download Clojure](https://clojure.org/guides/install_clojure)
+
+Run all tests like this: `clj -M:test`
+
+Sourced from: https://github.com/srodrigo/lambda-calculus-in-clojure
+
+Blog post by source author (Sergio Rodrigo):
+1. [Booleans in Clojure](https://srodrigo.me/lambda-calculus-in-clojure-part-1/)
+2. [Numerals in Clojure](https://srodrigo.me/lambda-calculus-in-clojure-part-2/)
+
+Blog post about [Y-Combinator in Clojure](https://blog.klipse.tech/lambda/2016/08/07/pure-y-combinator-clojure.html) by different author (Yehonathan Sharvit).
diff --git a/languages/c/clojure/lambda-core/deps.edn b/languages/c/clojure/lambda-core/deps.edn
new file mode 100644
index 0000000..7c90c0d
--- /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..fa94183
--- /dev/null
+++ b/languages/c/clojure/lambda-core/src/booleans.clj
@@ -0,0 +1,26 @@
+(ns booleans
+  (:require [lambda :refer [λ]]))
+
+(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/combinators.clj b/languages/c/clojure/lambda-core/src/combinators.clj
new file mode 100644
index 0000000..6746e29
--- /dev/null
+++ b/languages/c/clojure/lambda-core/src/combinators.clj
@@ -0,0 +1,18 @@
+(ns combinators)
+
+(def Y (fn [f]
+         ((fn [x]
+            (x x))
+          (fn [x]
+            (f (fn [y]
+                 ((x x) y)))))))
+
+(def Z
+  (fn [f]
+    ((fn [x]
+       (f (fn [y]
+            ((x x) y))))
+     (fn [x]
+       (f (fn [y]
+            ((x x) y)))))))
+
diff --git a/languages/c/clojure/lambda-core/src/lambda.clj b/languages/c/clojure/lambda-core/src/lambda.clj
new file mode 100644
index 0000000..6580bff
--- /dev/null
+++ b/languages/c/clojure/lambda-core/src/lambda.clj
@@ -0,0 +1,5 @@
+(ns lambda)
+
+(defmacro λ
+  [args & body]
+  `(fn [~args] ~@body))
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..53e08fa
--- /dev/null
+++ b/languages/c/clojure/lambda-core/src/numerals.clj
@@ -0,0 +1,44 @@
+(ns numerals
+  (:require [lambda :refer [λ]]))
+
+(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..6c4dc63
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/booleans_test.clj
@@ -0,0 +1,68 @@
+(ns booleans-test
+  (:require [booleans :refer :all]
+            [clojure.test :refer :all]
+            [print-macro :refer [is-print]]))
+
+(deftest λ-booleans
+  (testing "true"
+    (is-print (= (toBoolean T) true)))
+
+  (testing "false"
+    (is-print (= (toBoolean F) false)))
+
+  (testing "If"
+    (is-print (= (toBoolean (((If T) T) F)) true))
+    (is-print (= (toBoolean (((If F) T) F)) false)))
+
+  (testing "And"
+    (is-print (= (toBoolean ((And T) T)) true))
+    (is-print (= (toBoolean ((And T) F)) false))
+    (is-print (= (toBoolean ((And F) T)) false))
+    (is-print (= (toBoolean ((And F) F)) false))
+    (is-print (= (toBoolean ((And T) ((And T) T))) true))
+    (is-print (= (toBoolean ((And T) ((And F) T))) false)))
+
+  (testing "Or"
+    (is-print (= (toBoolean ((Or T) T)) true))
+    (is-print (= (toBoolean ((Or T) F)) true))
+    (is-print (= (toBoolean ((Or F) T)) true))
+    (is-print (= (toBoolean ((Or F) F)) false))
+    (is-print (= (toBoolean ((Or F) ((Or F) F))) false))
+    (is-print (= (toBoolean ((Or F) ((Or T) F))) true)))
+
+  (testing "Not"
+    (is-print (= (toBoolean (Not T)) false))
+    (is-print (= (toBoolean (Not F)) true))
+    (is-print (= (toBoolean (Not (Not T))) true))
+    (is-print (= (toBoolean (Not (Not F))) false)))
+
+  (testing "Xor"
+    (is-print (= (toBoolean ((Xor T) T)) false))
+    (is-print (= (toBoolean ((Xor T) F)) true))
+    (is-print (= (toBoolean ((Xor F) T)) true))
+    (is-print (= (toBoolean ((Xor F) F)) false)))
+
+  (testing "Expressions"
+    ;T AND T AND F OR T
+    (is-print (= (toBoolean ((And T) ((And T) ((Or F) T))))
+           true))
+
+    ;T AND F AND F OR T AND T
+    (is-print (= (toBoolean ((And T) ((And F) ((Or F) ((And T) T)))))
+           false))
+
+    ;T OR (F AND F OR T AND T)
+    (is-print (= (toBoolean ((Or T) ((And F) ((Or F) ((And T) T)))))
+           true))
+
+    ;F OR (F AND F OR F AND T)
+    (is-print (= (toBoolean ((Or F) ((And F) ((Or F) ((And F) T)))))
+           false))
+
+    ;F OR F AND F OR T AND T
+    (is-print (= (toBoolean ((And ((Or F) F)) ((And T) ((Or F) T))))
+           false))
+
+    ;T OR F AND F OR T AND T
+    (is-print (= (toBoolean ((And ((Or T) F)) ((And T) ((Or F) T))))
+           true))))
diff --git a/languages/c/clojure/lambda-core/test/combinators_test.clj b/languages/c/clojure/lambda-core/test/combinators_test.clj
new file mode 100644
index 0000000..ba32fd2
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/combinators_test.clj
@@ -0,0 +1,40 @@
+(ns combinators-test
+  (:require [lambda :refer [λ]]
+            [combinators :refer :all]
+            [booleans :refer :all]
+            [numerals :refer :all]
+            [clojure.test :refer :all]
+            [print-macro :refer [is-print]]))
+
+(def factorial-gen
+  ;; Church encoding of functions, such as 'λ', does not 
+  ;; naturally support 'recur'. This is because the 'λ' macro expands into an 
+  ;; anonymous function (created using 'fn'), and functions defined with 'fn' 
+  ;; cannot use 'recur' unless the 'recur' is in the tail position.
+  ;;
+  ;; The 'fn' function in Clojure is needed because it allows us to define a 
+  ;; recursive function where 'recur' can be used correctly in the tail position. 
+  ;; When the function is structured with 'fn', 'recur' will correctly jump back 
+  ;; to the function without adding a new stack frame, thus ensuring the recursion 
+  ;; is efficient and won't result in stack overflow.
+  (fn [f]
+    (fn [n acc]
+      ;; Church's 'If' introduces an additional function call, which prevents 'recur'
+      ;; from being the final operation, thus breaking TCO and causing a stack overflow.
+      ;; Hence, using native 'if' instead of Church's 'If' because
+      ;; 'recur' must be the last operation for tail call optimization (TCO).
+      (if (toBoolean ((n (λ x F)) T))
+        acc
+        (recur (pred n) ((mult acc) n))))))
+
+(def Y-factorial (Y factorial-gen))
+(def Z-factorial (Z factorial-gen))
+
+(deftest Y-Combinator
+  (testing "Y-factorial"
+    (is-print (= (toInt (Y-factorial (fromInt 9) one)) 362880))))
+
+(deftest Z-Combinator
+  (testing "Z-factorial"
+    (is-print (= (toInt (Z-factorial (fromInt 9) one)) 362880))))
+
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..e7e5526
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/numerals_test.clj
@@ -0,0 +1,76 @@
+(ns numerals-test
+  (:require [numerals :refer :all]
+            [clojure.test :refer :all]
+            [print-macro :refer [is-print]]))
+ 
+(deftest λ-numbers
+  (testing "zero"
+    (is-print (= (toInt zero) 0)))
+
+  (testing "one"
+    (is-print (= (toInt (succ zero)) 1))
+    (is-print (= (toInt one) 1)))
+
+  (testing "two"
+    (is-print (= (toInt (succ (succ zero))) 2))
+    (is-print (= (toInt two) 2)))
+
+  (testing "three"
+    (is-print (= (toInt (succ (succ (succ zero)))) 3)))
+
+  (testing "predecessor"
+    (is-print (= (toInt (pred one)) 0))
+    (is-print (= (toInt (pred two)) 1))
+    (is-print (= (toInt (pred (succ (succ (succ zero))))) 2))
+    (is-print (= (toInt (pred (fromInt 10))) 9))))
+
+(deftest λ-numerical-operations
+  (testing "addition"
+    (is-print (=
+         (toInt ((plus (fromInt 7)) (fromInt 5)))
+         12))
+    (is-print (=
+         (toInt ((plus (fromInt 7)) ((plus (fromInt 6)) (fromInt 2))))
+         15)))
+
+  (testing "subtraction"
+    (is-print (=
+         (toInt ((minus (fromInt 7)) (fromInt 5)))
+         2))
+    (is-print (=
+         (toInt ((minus (fromInt 7)) ((minus (fromInt 6)) (fromInt 2))))
+         3)))
+
+  (testing "multiplication"
+    (is-print (=
+          (toInt ((mult (fromInt 2)) (fromInt 3)))
+          6))
+    (is-print (=
+          (toInt ((mult (fromInt 2)) ((mult (fromInt 5)) (fromInt 3))))
+          30)))
+
+  (testing "exponentiation"
+    (is-print (=
+          (toInt ((exp (fromInt 2)) (fromInt 3)))
+          8))
+    (is-print (=
+          (toInt ((exp (fromInt 2)) ((exp (fromInt 2)) (fromInt 3))))
+          256))))
+
+(deftest λ-numeral-expressions
+  (testing "numeral expressions"
+    ; 3 * (2 + 5) - 2^3
+    (is-print (=
+         (toInt ((minus ((mult (fromInt 3))
+                         ((plus (fromInt 2)) (fromInt 5))))
+                 ((exp (fromInt 2)) (fromInt 3))))
+         13))))
+
+(deftest λ-toStr
+  (testing "toStr"
+    (is-print (= (toStr zero) "λf.λn.(n)"))
+    (is-print (= (toStr one) "λf.λn.(f(n))"))
+    (is-print (= (toStr two) "λf.λn.(f(f(n)))"))
+    (is-print (= (toStr (succ (succ (succ zero)))) "λf.λn.(f(f(f(n))))"))
+    (is-print (= (toStr (fromInt 5)) "λf.λn.(f(f(f(f(f(n))))))"))))
+
diff --git a/languages/c/clojure/lambda-core/test/print_macro.clj b/languages/c/clojure/lambda-core/test/print_macro.clj
new file mode 100644
index 0000000..5fc4de6
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/print_macro.clj
@@ -0,0 +1,13 @@
+(ns print-macro
+  (:require  [clojure.test :as t]))
+
+(defmacro is-print
+  ([form]
+   `(let [form-args# (rest '~form)
+          first-arg# (first form-args#)
+          second-arg# (second form-args#)]
+      (println (format "%s = %s => %s" 
+                       t/*testing-contexts* 
+                       (pr-str first-arg#) 
+                       (pr-str second-arg#)))
+      (t/is ~form))))
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..404df1d
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/test_runner.clj
@@ -0,0 +1,8 @@
+(ns test-runner
+  (:require [clojure.test :as t]
+            [numerals-test]
+            [booleans-test]
+            [combinators-test]))
+
+(defn -main [& args]
+  (t/run-tests 'numerals-test 'booleans-test 'combinators-test))