Y Combinator

\[\begin{equation}Y = \lambda f . ((\lambda x. f (x x)) (\lambda x. f (x x)))\label{y}\end{equation}\] where \(f\) is a function that takes one argument

We will look of an example of a factorial function in scheme (see ELisp) that implements recursion using the Y combinator from Mike Vanier. Then, we will discuss it below as a general template for using the Y combinator to recurse

(define almost-factorial
  (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

(define Y 
  (lambda (f)
    (lambda (x) (f (x x)))
    (lambda (x) (f (x x)))))

(define factorial (Y almost-factorial))

(factorial 5) 

First, I will give the functions names that reflect how I intuitively understand them.

(define almost-factorial
  (lambda (create-recursive-call)
      (lambda (n)
        (if (= n 0)
            1
            (* n (create-recursive-call (- n 1)))))))

(define make-recursive 
  (lambda (f)
    (lambda (x) (f (x x)))
    (lambda (x) (f (x x)))))

(define factorial (make-recursive almost-factorial))

(factorial 5) 

The high-level plan:

• Take an almost-recursive function \(f\) and make it recursive: everywhere recursion needs to happen, we substitute create-recursive-call which calls \(f\) again. \(f\) takes the body of create-recursive-call as an argument.

Slightly more detailed plan:

• almost-factorial, or more generally, a function \(f\) that takes one argument…
• and this argument will be the body of create-recursive-call
• \(f\) is almost recursive, but everywhere a call to \(f\) might be made in the body of \(f\), we instead say create-recursive-call
• Note that \(f\) is itself a combinator
• Given create-recursive-call as an argument, almost-factorial returns a function that takes an integer as \(n\) input. This is an example of currying. This integer argument will act as our counter. Not all recursive functions require a counter, but in this example, it allows us to terminate the recursion when \(n=0\).

\(Y f\) will be a recursive version of \(f\). Let's see how it works. We'll evaluate (make-recursive almost-factorial) n and talk about how \((Y f) n\) would be evaluated in general.

First, what happens when \((Y f)\) is evaluated? We drop in the body of \(Y\) in place: \[Y f = (\lambda f (\lambda x . f (x x)) (\lambda x . f (x x))) f\]

Substituting \(f\) into the body: \[(\lambda x . f (x x)) (\lambda x . f (x x))\]

The next step of evaluation is applying the first lambda to the second lambda. \[f ((\lambda x . f (x x)) (\lambda x . f (x x)))\]

Now \(f\) can be called with its one argument. In our specific example, we this looks like:

(almost-factorial ((lambda (x) (f (x x)))(lambda (x) (f (x x)))))

In the body of almost-factorial the symbol create-recursive-call will be bound to ((lambda (x) (f (x x)))(lambda (x) (f (x x)))). In general, in the body of \(f\), \(((\lambda x . f (x x)) (\lambda x . f (x x)))\) will be bound to some variable, call it \(r\). Now, recall that because of currying, almost-factorial should be able to take a second argument now, namely n. Similarly, \(f\) can now take \(n\) as an argument:

\[f ((\lambda x . f (x x)) (\lambda x . f (x x))) n\]

Side question: Why didn't we keep evaluating the body of create-recursive-call? How did we avoid that infinite series of substitution steps? It's because that body was bound to the name create-recursive-call in the body of almost-factorial. Since we're doing lazy evaluation, this expression will not need to be evaluated until later on in the body when it is called. By then, n will be decremented and we will be making progress in our recursion. Similarly, we can think of the evaluation of \(r\) in the body of \(f\) being postponed.

Now, let's get to evaluating the body of almost-factorial, or \(f\). Inside, we decrement \(n\). Now, we come to the portion of the program where we need to make a recursive call. We call on our passed in create-recursive-call or \(r\). Recall that \(r\) looks like this: \((\lambda x. f (x x)) (\lambda x . f (x x))\) and recall that we call it in this context:

(* n (create-recursive-call (- n 1)))

Evaluation for our specific example proceeds as follows:

(* n ((lambda (x) (f (x x)))(lambda (x) (f (x x)))) (- n 1))

which evaluates to:

(*n (f ((lambda (x) (f (x x)))(lambda (x) (f (x x)))) (- n 1)))

Similarly, when we evaluate \(r\): \[f ((\lambda x. f (x x)) (\lambda x . f (x x)))\]

We're back where we started! I read the above as (* n (almost-factorial (create-recursive-call) (- n 1))). Recall that f was bound to the body of almost-factorial. Again recall that we don't evaluate the lambda expressions further, because they have been bound to a variable in the subsequent call to almost-factorial, or \(f\).

Now \(f\) is ready to receive another numerical argument. We pass it \(n-1\). Eventually, the counter will reach 0, and the base case will be reached. Because we are lazy-evaluating, we will not need to evaluate any further create-recursive-call expressions in the base case.

Side questoion: Why can we call \(f\) here, inside the body of \(f\)? Isn't that explicit recursion? Because \(f\) is a combinator, we just plop in the body of \(f\) for the symbol \(f\). Remember that \(Y f\) created a combinator that knows about \(f\).

Y returns the fixed point of a function. That is, \(f (Y f) = Y f\). We can verify this with our definition of \(Y\) \(\eqref{y}\) \[\begin{align*} Y f &= (\lambda x. f (x x)) (\lambda x. f (x x)) \\ &= f ((\lambda x. f (x x)) (\lambda x. f (x x)))\\ &= f (Y f) \end{align*}\]

When lazy evaluation is possible, the Y combinator in scheme looks like:

(define Y 
  (lambda (f)
    ((lambda (x) (f (x x)))
     (lambda (x) (f (x x))))))

This is called normal-order form

When only strict evaluation is allowed, the combinator looks like:

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (y) (x x) y)))
     (lambda (x) (f (lambda (y) (x x) y))))))

This is called applicative-order form.

What is the difference between these two? When the normal-order version is called: (Y f), the strict evaluator will try to evaluate

((lambda (x) (f (x x)))
 (lambda (x) (f (x x))))

which will result in (lambda (x) (f (x x))) being substituted for x in the first lambda expression:

(f (lambda (x) (f (x x)))
   (lambda (x) (f (x x))))

This will prompt another immediate evaluation of the lambda expression and so on. For a strict evaluator, these substitutions will continue forever, without the body of f ever being run.

In contrast, when the applicative-order version is called, the strict evaluator will try to evaluate

((lambda (x) (f (lambda (y) (x x) (y))))
 (lambda (x) (f (lambda (y) (x x) (y)))))

This will result in:

(f (lambda (y)
    ((lambda (x) (f (lambda (y) (x x) (y))))
     (lambda (x) (f (lambda (y) (x x) (y)))))))

Now, due to the lambda expression wrapper, the contents of the lambda expression will not be evaluated immediately. Rather, they will be evaluated when needed in the body of f.

• Intuitive explanation of how the Y combinator might have been derived
• In depth explanation in Scheme by Mike Vanier
• Article that covers the same concepts in haskell