In the untyped lambda calculus, you cannot assign names to functions, you define anonymous functions. That’s it.

This is a puzzle: in such an environment, how can you define recursive functions? Y is a fundamental (and nice) theoretical exercise.

These are my notes based on chapter 9 of The Little Schemer. Buy it, it’s a great book.

I develop the applicative-order Y combinator from the function factorial. The code is in Clojure, which has a limited TCO. Thus, the factorial function defined here has just a didactic purpose.

I suggest to run this stuff in a Clojure REPL. The Lighttable Instant REPL is perfect here. In this post you can find some notes on how to setup everything.

To obtain Y, I apply multiple times the transformation defined in the first section. In the second section I define an anonymous function computing recursively the factorial. In the last one, I perform some cleanup, and I finally extract the factorial function and the applicative-order Y combinator.

How to create bindings

Consider

1
(fn [n] (+ n 1))

In a world without def, how can I bind this anonymous function to the name increment?

The only names I see are the function arguments. Thus, I create a new function whose argument is increment, that I invoke using the snippet as argument.

1
2
3
((fn [increment]   ; the "environment"
  (println "The name increment exists. (increment 1) is" (increment 1)))
(fn [n] (+ n 1))) ; the argument

When executed, it prints The name increment exists. (increment 1) is 2

This is the basic building block of the post.

Factorial

In this section we are going to build an anonymous function which computes the factorial using recursion.

To simplify the code, I use a placeholder pointing to the location where I should recur. I will this helper function

1
(defn if-only-i-could-recur [x] (throw (Exception. "you cannot call me")))

I cheat a bit since I cannot name things, but when invoked it raises an Exception. It just means you cannot be here.

The factorial function looks like this

1
2
3
4
5
(fn [n]
  (cond
   (zero? n) 1
   :else (* n
            (if-only-i-could-recur (dec n)))))

It takes an integer as parameter:

  1. if it’s 0, then the factorial is 1
  2. otherwise we should recur on n-1. Unfortunately, we cannot. We don’t have a name to refer to itself. Good place for our placeholder, isn’t it?

For the moment, this function is able to compute the factorial of 0 only. What we do want to do is to pass to it the recursive step to execute.

But how can we assign a name to the next recursive step? By wrapping everything in a new function.

1
2
3
4
5
6
7
((fn [recursive-step]
  (fn [n]
    (cond
     (zero? n) 1
     :else (* n
              (recursive-step (dec n))))))
 if-only-i-could-recur)

This is really the same as above: it can just compute the factorial of 0.

As a refactoring, I want to give a name to that template of the factorial function. Again, I create an anonymous function to name it build-factorial.

1
2
3
4
5
6
7
8
((fn [build-factorial]
   (build-factorial if-only-i-could-recur))
 (fn [recursive-step]
  (fn [n]
    (cond
     (zero? n) 1
     :else (* n
              (recursive-step (dec n)))))))

Why that name? Because it does not know yet how to recur, but it returns a function that really looks like a factorial.

How can I make it perform more steps? Instead of if-only-i-could-recur, the recursive step should be the function generated by build-factorial, i.e. that factorial-like function.

To start, we can use simply build-factorial.

1
2
3
4
5
6
7
8
9
((fn [build-factorial]
   (build-factorial build-factorial))
 (fn [recursive-step]
  (fn [n]
    (cond
     (zero? n) 1
     :else (* n
              (recursive-step
               (dec n)))))))

but unfortunately this function is broken. Try to run it!

The problem is that at line 8 we call recursive-step, which now is bound to build-factorial. But build-factorial is not the factorial function, it is a function able to build it when it receives a function (the recurring step) as argument. Which function can we use as argument? The key of the puzzle is that the only function with a name here is recursive-step itself. So we use it.

1
2
3
4
5
6
7
8
9
((fn [build-factorial]
   (build-factorial build-factorial))
 (fn [recursive-step]
  (fn [n]
    (cond
     (zero? n) 1
     :else (* n
              ((recursive-step recursive-step)
               (dec n)))))))

This is a working factorial definition. Try it!

Extract Y

The goal is now to refactor the last expression to extract the factorial function. The remaining part is Y.

First of all, we extract the form (recursive-step recursive-step) at line 8.

We do it in two steps. First of all, I wrap it in the call to a function that receives an argument, and apply (recursive-step recursive-step) to it. In Clojure this is

1
(fn [x] ((recursive-step recursive-step) x))

which means, in our factorial function

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
((fn [build-factorial]
  (build-factorial build-factorial))
(fn [recursive-step]
 (fn [n]
   (cond
    (zero? n) 1
    :else (* n
             ((fn [x] ((recursive-step recursive-step) x))
             (dec n)))
   ))
 ))

Then, I extract that, assigning a name to it. Which name? Since that’s the place for the recursive call, it seems natural to call it factorial.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
((fn [build-factorial]
  (build-factorial build-factorial))
(fn [recursive-step]
  ((fn [factorial]
    (fn [n]
      (cond
       (zero? n) 1
       :else (* n
             (factorial
             (dec n))))))
   (fn [x] ((recursive-step recursive-step) x)))))

Now what’s beneath ((fn [factorial]... really looks like the recursive definition of factorial. I name it f and I extract it to get

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
((fn [f]
     ((fn [build-factorial]
        (build-factorial build-factorial))
      (fn [recursive-step]
        (f
         (fn [x] ((recursive-step recursive-step) x))))))
   (fn [factorial]
     (fn [n]
       (cond
        (zero? n) 1
        :else (* n
                 (factorial
                  (dec n)))))))

Here the anonymous function (fn [factorial] ...) is a factory building factorial functions, i.e. functions whose body is the form (fn [n] ...), which compute the factorial of n by using the name factorial to recur.

It works because the factory is passed as argument to another function, called the applicative-order Y combinator.

1
2
3
4
5
6
(defn Y
    [f]
    ((fn [g] (g g))
     (fn [h]
       (f
        (fn [x] ((h h) x))))))

Y uses the factory to build a new function, passing as argument to it (i.e. the recursive step) another instance of the function built with the factory itself.

In an environment where you cannot name things, Y allows you to build functions referring to themselves.

This code

1
2
3
4
5
6
7
8
(Y
  (fn [factorial]
    (fn [n]
      (cond
       (zero? n) 1
       :else (* n
                (factorial
                 (dec n)))))))

returns the factorial function.

1
2
3
4
5
6
7
8
9
((Y
  (fn [factorial]
    (fn [n]
      (cond
       (zero? n) 1
       :else (* n
                (factorial
                 (dec n)))))))
 5)

is 120.