How the Y Works

Welcome to my explanation to myself of how the applicative-order Y-combinator works.

1 Materials

There are a lot of materials out there. Most of them were confusing and didn’t "speak to me". The following provided the different bits that I needed:

• The Little Schemer, 4th Edition

• Deriving the Y-Combinator

The Y-combinator provides the machinery to provide recursion to anonymous methods. This document is a record of what I worked through to try to understand the problem that it solves, and how.

2 The Modern World: Recursive References with Factorial

• Q. Define the factorial function for the domain [0,∞], in words.

• A. The factorial of n for the domain [0, ∞] is

  • If n=0 then 1.

  • If n=1 then 1.

  • Else n * factorial(n-1).

• Q. Hand code the calculation for the factorial of 5.

• A.

  > (check-eq? (* 5 (* 4 (* 3 (* 2 1)))) 120)

• Q. How would you implement the definition above?

• A.

  > (define auto-fac-with-auto-recursion     (lambda (n)       (cond ((= n 0) 1)             ((= n 1) 1)             (else (* n (auto-fac-with-auto-recursion (- n 1)))))))

  > (check-eq? (auto-fac-with-auto-recursion 0) 1)

  > (check-eq? (auto-fac-with-auto-recursion 1) 1)

  > (check-eq? (auto-fac-with-auto-recursion 2) 2)

  > (check-eq? (auto-fac-with-auto-recursion 3) 6)

  > (check-eq? (auto-fac-with-auto-recursion 4) 24)

  > (check-eq? (auto-fac-with-auto-recursion 5) 120)

  > (check-eq? (* 5 (* 4 (* 3 (* 2 1)))) 120)

• Q. Descartes was right, God is an evil-genius, or in this case, an evil programming language designer, and he has taken away the ability to recursively reference names. We need to cope with this, but we are not yet sure now. The first thing we have to fix is to remove the recursive reference to factorial.

  We’ll just replace it with a call to the error function. Implement this version of factorial with a domain of [0,1].

• A.

  > (define man-fac-w/o-recursion-0-1     (lambda (n)       (cond ((= n 0) 1)             ((= n 1) 1)             (else (* n (error (- n 1)))))))

  > (check-eq? (man-fac-w/o-recursion-0-1 0) 1)

  > (check-eq? (man-fac-w/o-recursion-0-1 1) 1)

3 The Primordial World: No Recursive References

• Q. What about a domain of [0,2]?

  We know from above that where factorial will "go next" is to the factorial function, so provide a new instance of a factorial function and pass it to the first implementation you had already defined.

• A.

  > (define man-fac-w/o-recursion-0-2     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        (lambda (n)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (error (- n 1)))))))))

  > (check-eq? (man-fac-w/o-recursion-0-2 0) 1)

  > (check-eq? (man-fac-w/o-recursion-0-2 1) 1)

  > (check-eq? (man-fac-w/o-recursion-0-2 2) 2)

• Q. What about a domain of [0,3]? And again...

• A.

  > (define man-fac-w/o-recursion-0-3     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (fact (- n 1)))))))         (lambda (n)            (cond ((= n 0) 1)                  ((= n 1) 1)                  (else (* n (error (- n 1))))))))))

  > (check-eq? (man-fac-w/o-recursion-0-3 0) 1)

  > (check-eq? (man-fac-w/o-recursion-0-3 1) 1)

  > (check-eq? (man-fac-w/o-recursion-0-3 2) 2)

  > (check-eq? (man-fac-w/o-recursion-0-3 3) 6)

• Q. What about a domain of [0,4]? And again...

• A.

  > (define man-fac-w/o-recursion-0-4     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (fact (- n 1)))))))         ((lambda (fact)            (lambda (n)              (cond ((= n 0) 1)                    ((= n 1) 1)                    (else (* n (fact (- n 1)))))))          (lambda (n)            (cond ((= n 0) 1)                  ((= n 1) 1)                  (else (* n (error (- n 1)))))))))))

  > (check-eq? (man-fac-w/o-recursion-0-4 0) 1)

  > (check-eq? (man-fac-w/o-recursion-0-4 1) 1)

  > (check-eq? (man-fac-w/o-recursion-0-4 2) 2)

  > (check-eq? (man-fac-w/o-recursion-0-4 3) 6)

  > (check-eq? (man-fac-w/o-recursion-0-4 4) 24)

• Q. What about a domain of [0,5]? And again...

• A.

  > (define man-fac-w/o-recursion-0-5     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (fact (- n 1)))))))         ((lambda (fact)            (lambda (n)              (cond ((= n 0) 1)                    ((= n 1) 1)                    (else (* n (fact (- n 1)))))))          ((lambda (fact)             (lambda (n)               (cond ((= n 0) 1)                     ((= n 1) 1)                     (else (* n (fact (- n 1)))))))           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (error (- n 1))))))))))))

  > (check-eq? (man-fac-w/o-recursion-0-5 0) 1)

  > (check-eq? (man-fac-w/o-recursion-0-5 1) 1)

  > (check-eq? (man-fac-w/o-recursion-0-5 2) 2)

  > (check-eq? (man-fac-w/o-recursion-0-5 3) 6)

  > (check-eq? (man-fac-w/o-recursion-0-5 4) 24)

  > (check-eq? (man-fac-w/o-recursion-0-5 5) 120)

• Q. What about a domain of [0,∞]?

• A. Just kidding. Think about how it would look, though.

• Q. There is a lot of code duplication. Write a function to do the repetitive labor. First, what is the repetitive labor?

• A. The repetitive labor is in (1) creating a new factorial function instance whose (2) factorial recur-function is parameterized.

  > (define mk-fact     (lambda (fact)       (lambda (n)         (cond ((= n 0) 1)               ((= n 1) 1)               (else (* n (fact (- n 1))))))))

  > (check-eq? ((mk-fact error) 0) 1)

  > (check-eq? ((mk-fact error) 1) 1)

  > (check-eq? ((mk-fact (mk-fact error)) 2) 2)

4 Don’t Ask, Do Tell

• Q. Factor out the fifth anonymous method creation in your manual recursion factorial implementation.

• A.

  > (define man-fac-with-mk-recursion-0-5-a     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (fact (- n 1)))))))         ((lambda (fact)            (lambda (n)              (cond ((= n 0) 1)                    ((= n 1) 1)                    (else (* n (fact (- n 1)))))))          ((lambda (fact)             (lambda (n)               (cond ((= n 0) 1)                     ((= n 1) 1)                     (else (* n (fact (- n 1)))))))           (mk-fact error)))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-a 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-a 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-a 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-a 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-a 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-a 5) 120)

• Q. Factor out the fourth anonymous method creation in your manual recursion factorial implementation.

• A.

  > (define man-fac-with-mk-recursion-0-5-b     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (fact (- n 1)))))))         ((lambda (fact)            (lambda (n)              (cond ((= n 0) 1)                    ((= n 1) 1)                    (else (* n (fact (- n 1)))))))          ((lambda (fact)             (mk-fact fact))           (mk-fact error)))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-b 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-b 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-b 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-b 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-b 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-b 5) 120)

• Q. Factor out the third anonymous method creation in your manual recursion factorial implementation.

• A.

  > (define man-fac-with-mk-recursion-0-5-c     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (fact (- n 1)))))))         ((lambda (fact)            (mk-fact fact))          ((lambda (fact)             (mk-fact fact))           (mk-fact error)))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-c 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-c 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-c 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-c 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-c 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-c 5) 120)

• Q. Factor out the second anonymous method creation in your manual recursion factorial implementation.

• A.

  > (define man-fac-with-mk-recursion-0-5-d     (lambda (n)       ((lambda (fact)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (fact (- n 1))))))        ((lambda (fact)           (mk-fact fact))         ((lambda (fact)            (mk-fact fact))          ((lambda (fact)             (mk-fact fact))           (mk-fact error)))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-d 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-d 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-d 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-d 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-d 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-d 5) 120)

• Q. Factor out the first anonymous method creation in your manual recursion factorial implementation.

• A.

  > (define man-fac-with-mk-recursion-0-5-e     ((lambda (fact)        (mk-fact fact))      ((lambda (fact)         (mk-fact fact))       ((lambda (fact)          (mk-fact fact))        ((lambda (fact)           (mk-fact fact))         (mk-fact error))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-e 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-e 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-e 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-e 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-e 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-e 5) 120)

• Q. Much better.

  There isn’t duplication, but there is an opportunity for simplification.

  Clean up the code to simplify it. First, what is the simplification?

• A. Notice mk-fact is really being passed directly into itself. You can just substitute the fact binding in the enclosing lambda with the function passed into it.

  Simplify man-fac-with-mk-recursion-0-5-e by removing this redundancy, step by step, until it can’t be simplified anymore, doing so from the outermost anonymous method to the innermost.

  > (define man-fac-with-mk-recursion-0-5-f     ((lambda (fact)        (mk-fact fact))      ((lambda (fact)         (mk-fact fact))       ((lambda (fact)          (mk-fact fact))        (mk-fact         (mk-fact error))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-f 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-f 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-f 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-f 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-f 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-f 5) 120)

  > (define man-fac-with-mk-recursion-0-5-g     ((lambda (fact)        (mk-fact fact))      ((lambda (fact)         (mk-fact fact))       (mk-fact        (mk-fact         (mk-fact error))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-g 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-g 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-g 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-g 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-g 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-g 5) 120)

  > (define man-fac-with-mk-recursion-0-5-h     ((lambda (fact)        (mk-fact fact))      (mk-fact       (mk-fact        (mk-fact         (mk-fact error))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-h 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-h 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-h 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-h 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-h 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-h 5) 120)

  > (define man-fac-with-mk-recursion-0-5-i     (mk-fact      (mk-fact       (mk-fact        (mk-fact         (mk-fact error))))))

  > (check-eq? (man-fac-with-mk-recursion-0-5-i 0) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-i 1) 1)

  > (check-eq? (man-fac-with-mk-recursion-0-5-i 2) 2)

  > (check-eq? (man-fac-with-mk-recursion-0-5-i 3) 6)

  > (check-eq? (man-fac-with-mk-recursion-0-5-i 4) 24)

  > (check-eq? (man-fac-with-mk-recursion-0-5-i 5) 120)

5 Looking Back

• Q. Why do we have to create a new factorial function every time we want to recur?

• A. Because there are no recursive definitions in this world so we need a new instance of a factorial function every time we want to make our recursive call given our recursive definition of the factorial function.

• Q. What do we always want to do when we recur according to the recursive definition of factorial?

• A. Make a recursive call into factorial with a decremented argument.

• Q. Do we always recur into factorial in our code?

• A. No.

• Q. Why not?

• A. Because we can’t write code to create new anonymous factorial function instances up to ∞, eventually we just have to error out.

• Q. What do we object to doing?

• A. Things that a computer can do for us.

• Q. Can a computer do our bidding for eternity?

• A. "((lambda (x) (x x)) (lambda (x) (x x)))"

• Q. Wouldn’t it be nice if every time we needed a new factorial function instance the computer could just create a new one for us instead of having to write it ourselves?

• A. Yes.

6 Looking Forward

• Q. Most of the time what is mk-fact recurring to?

• A. A new factorial function instance created by mk-fact.

• Q. What if the function created by mk-fact could do the work of creating a function to which it could recur?

• A. Laziness, impatience, and hubris.

• Q. Will it take much work?

• A. No, but explaining it to myself will take some work.

  We already implemented mk-length. It creates functions that perform one step of factorial, and you have to pass it a function to which it should recur. Up above, we are manually creating a new instance of a function to which they should recur. We are doing it by hand. It would be easier if the newly created factorial function instance knew how to do this work rather than us doing it manually each time.

  We already have something like this in mk-length. It would be easy if our language provided recursive definitions because if it did then we could generate a new function function instance that "knew how" to generate another new factorial function instance to which it may recur. This is one of those "the glass is half-full" time where you need to look at the good things that the language designer did leave you with.

  In our world, we have anonymous methods (lambda expressions) as we’ve seen above. Lambda let’s you create new functions, but it also lets you bind objects to names. Here, lambda gives us a solution. The answer is to pass mk-length a reference to itself so it can generate new factorial function instances. When you rely on the evaluation mechanics of the underlying language, you can sort of tell yourself a story of the objects, when and how they are created, and what is happening with evaluation of those objects.

  The simplest way to start is to leverage the body of mk-length, and leave it hanging out there as an anonymous method. From there we can pass it into a helper function that provides it with a reference to itself. "Itself" is something to be pondered. That anonymous function "mk-length" produces new factorial function instances who have a handle on their creator, for lack of a better term. This is where the manual recursion comes from, and it works in a way that is identical to what we hand-coded up above.

7 Finding Y

• Q. Implement factorial with this new approach.

• A.

  > (define man-fac-with-mk-Y-recursion     ((lambda (mk-fact)        (mk-fact mk-fact))      (lambda (mk-fact)        (lambda (n)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n ((mk-fact mk-fact) (- n 1)))))))))

  > (check-eq? (man-fac-with-mk-Y-recursion 0) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion 1) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion 2) 2)

  > (check-eq? (man-fac-with-mk-Y-recursion 3) 6)

  > (check-eq? (man-fac-with-mk-Y-recursion 4) 24)

  > (check-eq? (man-fac-with-mk-Y-recursion 5) 120)

• Q. The factorial function body is kind of ugly in that it has to know to create where to go next.

  Make it simpler for it to recur.

• A.

  > (define man-fac-with-mk-Y-recursion-b     ((lambda (mk-fact)        (mk-fact mk-fact))      (lambda (mk-fact)        ((lambda (factorial)           (lambda (n)             (cond ((= n 0) 1)                   ((= n 1) 1)                   (else (* n (factorial (- n 1)))))))         (lambda (x)           ((mk-fact mk-fact) x))))))

  > (check-eq? (man-fac-with-mk-Y-recursion-b 0) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion-b 1) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion-b 2) 2)

  > (check-eq? (man-fac-with-mk-Y-recursion-b 3) 6)

  > (check-eq? (man-fac-with-mk-Y-recursion-b 4) 24)

  > (check-eq? (man-fac-with-mk-Y-recursion-b 5) 120)

• Q. That reads better. It is sort of confusing because now there are two anonymous methods that are very similar, and for good reason: they are both responsible for creating a new factorial function instance that tells the anonymous method where to go next. The only difference is that the first one is used only once to create the first instance and get it running by giving it a reference to itself, the second one has the job of re-using that first one doing the same job but inside the anonymous method body, creating a place to which it may recur.

  The code can be simplified one step further by factoring out the anonymous factorial method.

  Refactor it.

• A.

  > (define man-fac-with-mk-Y-recursion-c     ((lambda (le)        ((lambda (mk-fact)           (mk-fact mk-fact))         (lambda (mk-fact)           (le (lambda (x) ((mk-fact mk-fact) x))))))      (lambda (factorial)        (lambda (n)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (factorial (- n 1)))))))))

  > (check-eq? (man-fac-with-mk-Y-recursion-c 0) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion-c 1) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion-c 2) 2)

  > (check-eq? (man-fac-with-mk-Y-recursion-c 3) 6)

  > (check-eq? (man-fac-with-mk-Y-recursion-c 4) 24)

  > (check-eq? (man-fac-with-mk-Y-recursion-c 5) 120)

• Q. The refactoring above can be generalized even further.

  Do it.

• A.

  > (define man-fac-with-mk-Y-recursion-d     ((lambda (le)        ((lambda (f)           (f f))         (lambda (f)           (le (lambda (x) ((f f) x))))))      (lambda (factorial)        (lambda (n)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (factorial (- n 1)))))))))

  > (check-eq? (man-fac-with-mk-Y-recursion-d 0) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion-d 1) 1)

  > (check-eq? (man-fac-with-mk-Y-recursion-d 2) 2)

  > (check-eq? (man-fac-with-mk-Y-recursion-d 3) 6)

  > (check-eq? (man-fac-with-mk-Y-recursion-d 4) 24)

  > (check-eq? (man-fac-with-mk-Y-recursion-d 5) 120)

• Q. Excellent. Now that helper function can be extracted to the applicative-order Y-combinator.

  Do it.

• A.

  > (define Y     (lambda (le)       ((lambda (f)          (f f))        (lambda (f)          (le (lambda (x) ((f f) x)))))))

• Q. Define factorial using an anonymous method and the Y-combinator.

• A.

  > (define Y-combinator-recursion-factorial     (Y      (lambda (factorial)        (lambda (n)          (cond ((= n 0) 1)                ((= n 1) 1)                (else (* n (factorial (- n 1)))))))))

  > (check-eq? (Y-combinator-recursion-factorial 0) 1)

  > (check-eq? (Y-combinator-recursion-factorial 1) 1)

  > (check-eq? (Y-combinator-recursion-factorial 2) 2)

  > (check-eq? (Y-combinator-recursion-factorial 3) 6)

  > (check-eq? (Y-combinator-recursion-factorial 4) 24)

  > (check-eq? (Y-combinator-recursion-factorial 5) 120)

• Q. Now you should understand the how of the Y.

  It really doesn’t matter whether or not anyone agrees with you that lambda is the ultimate, right?

• A. Right.