How to implement a recursive function in lambda calculus using a subset of Clojure language?

Question

I'm studying lambda calculus with the book "An Introduction to Functional Programming Through Lambda Calculus" by Greg Michaelson.

I implement examples in Clojure using only a subset of the language. I only allow :

• symbols
• one-arg lambda functions
• function application
• var definition for convenience.

So far I have those functions working :

(def identity (fn [x] x))
(def self-application (fn [s] (s s)))

(def select-first (fn [first] (fn [second] first)))
(def select-second (fn [first] (fn [second] second)))
(def make-pair (fn [first] (fn [second] (fn [func] ((func first) second)))))    ;; def make-pair =  λfirst.λsecond.λfunc.((func first) second)

(def cond make-pair)
(def True select-first)
(def False select-second)

(def zero identity)
(def succ (fn [n-1] (fn [s] ((s False) n-1))))
(def one (succ zero))
(def zero? (fn [n] (n select-first)))
(def pred (fn [n] (((zero? n) zero) (n select-second))))

But now I am stuck on recursive functions. More precisely on the implementation of add. The first attempt mentioned in the book is this one :

(def add-1
  (fn [a]
    (fn [b]
      (((cond a) ((add-1 (succ a)) (pred b))) (zero? b)))))

((add zero) zero)

Lambda calculus rules of reduction force to replace the inner call to add-1 with the actual definition that contains the definition itself... endlessly.

In Clojure, wich is an application order language, add-1 is also elvaluated eagerly before any execution of any kind, and we got a StackOverflowError.

After some fumblings, the book propose a contraption that is used to avoid the infinite replacements of the previous example.

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) (((f f) (succ a)) (pred b)))))))
(def add (add2 add2))

The definition of add expands to

(def add (fn [a] 
           (fn [b]
             (((zero? b) a) (((add2 add2) (succ a)) (pred b)))))) 

Which is totally fine until we try it! This is what Clojure will do (referential transparency) :

((add zero) zero)
;; ~=>
(((zero? zero) zero) (((add2 add2) (succ zero)) (pred zero)))
;; ~=>
((select-first zero) (((add2 add2) (succ zero)) (pred zero)))
;; ~=>
((fn [second] zero) ((add (succ zero)) (pred zero)))

On the last line (fn [second] zero) is a lambda that expects one argument when applied. Here the argument is ((add (succ zero)) (pred zero)). Clojure is an "applicative order" language so the argument is evaluated before function application, even if in that case the argument won't be used at all. Here we recur in add that will recur in add... until the stack blows up. In a language like Haskell I think that would be fine because it's lazy (normal order), but I'm using Clojure.

After that, the book go in length presenting the tasty Y-combinator that avoid the boilerplate but I came to the same gruesome conclusion.

EDIT

As @amalloy suggests, I defined the Z combinator :

(def YC (fn [f] ((fn [x] (f (fn [z] ((x x) z)))) (fn [x] (f (fn [z] ((x x) z)))))))

I defined add2 like this :

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) ((f (succ a)) (pred b)))))))

And I used it like this :

(((YC add2) zero) zero)

But I still get a StackOverflow.

I tried to expand the function "by hand" but after 5 rounds of beta reduction, it looks like it expands infinitely in a forest of parens.

So what is the trick to make Clojure "normal order" and not "applicative order" without macros. Is it even possible ? Is it even the solution to my question ?

This question is very close to this one : How to implement iteration of lambda calculus using scheme lisp? . Except that mine is about Clojure and not necessarily about Y-Combinator.

Answer 1

For strict languages, you need the Z combinator instead of the Y combinator. It's the same basic idea but replacing (x x) with (fn [v] (x x) v) so that the self-reference is wrapped in a lambda, meaning it is only evaluated if needed.

You also need to fix your definition of booleans in order to make them work in a strict language: you can't just pass it the two values you care about and select between them. Instead, you pass it thunks for computing the two values you care about, and call the appropriate function with a dummy argument. That is, just as you fix the Y combinator by eta-expanding the recursive call, you fix booleans by eta-expanding the two branches of the if and eta-reduce the boolean itself (I'm not 100% sure that eta-reducing is the right term here).

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                ((((zero? b) (fn [_] a)) (fn [_] ((f (succ a)) (pred b)))) b)))))

Note that both branches of the if are now wrapped with (fn [_] ...), and the if itself is wrapped with (... b), where b is a value I chose arbitrarily to pass in; you could pass zero instead, or anything at all.