FIX: Factorial with church numerals

7 files changed, 66 insertions, 33 deletions

diff --git a/languages/c/clojure/lambda-core/src/booleans.clj b/languages/c/clojure/lambda-core/src/booleans.clj
index e48f9a7..fa94183 100644
--- a/languages/c/clojure/lambda-core/src/booleans.clj
+++ b/languages/c/clojure/lambda-core/src/booleans.clj
@@ -1,8 +1,5 @@
-(ns booleans)
-
-(defmacro λ
-  [args & body]
-  `(fn [~args] ~@body))
+(ns booleans
+  (:require [lambda :refer [λ]]))
 
 (def T
   (λ a (λ b a)))
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
index e18da0f..53e08fa 100644
--- a/languages/c/clojure/lambda-core/src/numerals.clj
+++ b/languages/c/clojure/lambda-core/src/numerals.clj
@@ -1,8 +1,5 @@
-(ns numerals)
-
-(defmacro λ
-  [args & body]
-  `(fn [~args] ~@body))
+(ns numerals
+  (:require [lambda :refer [λ]]))
 
 (def zero
   (λ f (λ x x)))
diff --git a/languages/c/clojure/lambda-core/src/y_combinator.clj b/languages/c/clojure/lambda-core/src/y_combinator.clj
deleted file mode 100644
index c474fbf..0000000
--- a/languages/c/clojure/lambda-core/src/y_combinator.clj
+++ /dev/null
@@ -1,9 +0,0 @@
-(ns y-combinator)
-
-(def Y (fn [f]
-         ((fn [x]
-            (x x))
-          (fn [x]
-            (f (fn [y]
-                 ((x x) y)))))))
-
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..586946d
--- /dev/null
+++ b/languages/c/clojure/lambda-core/test/combinators_test.clj
@@ -0,0 +1,39 @@
+(ns combinators-test
+  (:require [lambda :refer [λ]]
+            [combinators :refer :all]
+            [booleans :refer :all]
+            [numerals :refer :all]
+            [clojure.test :refer :all]))
+
+(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 (= (toInt (Y-factorial (fromInt 9) one)) 362880))))
+
+(deftest Z-Combinator
+  (testing "Z-factorial"
+    (is (= (toInt (Z-factorial (fromInt 9) one)) 362880))))
+
diff --git a/languages/c/clojure/lambda-core/test/y_combinator_test.clj b/languages/c/clojure/lambda-core/test/y_combinator_test.clj
deleted file mode 100644
index c5396a0..0000000
--- a/languages/c/clojure/lambda-core/test/y_combinator_test.clj
+++ /dev/null
@@ -1,14 +0,0 @@
-(ns y-combinator-test
-  (:require [y-combinator :refer :all]
-            [clojure.test :refer :all]))
-
-
-(def factorial-gen (fn [func]
-                     (fn [n]
-                       (if (zero? n)
-                         1
-                         (* n (func (dec n)))))))
-
-(deftest λ-Y-Combinator
-  (testing "factorial"
-    (is (= ((Y factorial-gen) 19) 121645100408832000))))