Another Y - Combinator Derrivation

In this post I'm going to readily derive the Y - combinator. The Y - combinator allows an anonymous function to call itself, means it allows anonymous function to recursion. At first glance this impossible, since anonymous functions doesn't have names (so how to call them from inside a function?). But it works and building blocks are very simple. As a language I used scheme - because of simplicity, and this derivation is based on fantastic talk by Jim Weirich (RIP, you were the best!).

Suppose I have the recursive factorial function, it's easy to write, if we can give the function a name: 

(define fact 
   (lambda (n) (if (zero? n) 1 
      (* n (fact (dec n))))))

Dec returns argument minus one. I can't have now anonymous factorial function - without a name - this is impossible for the function to call itself.

(lambda (n) (if (zero? n) 1 
   (* n (??? (dec n))))))

 But what if we try to define a function which creates factorial  and then call it with some partial value, which we're going to improve?

(define make-fact 
  (lambda (partial)
    (lambda (n) (if (zero? n) 1 

      (* n (partial (dec n))))))

This is pretty cool, but it's we have no idea what argument use to call make-fact! 

(make fact ???)

Let's try something different, rename it, and call over some partial value (not over the whole domain of factorial) and will try to improve it step by step. First I'm creating function error, to be sure that this function never be called:

(define error (lambda (n) 

(display "This can't be called")))

And function now:

(define improver 
  (lambda (partial)
    (lambda (n) (if (zero? n) 1 

      (* n (partial (dec n)))))))

 

 Now let's create some higher order functions the (higher order function is a function which returns a function):

(define first (improver error))
(define second (improver first))
(define third (improver second))

The first computes factorial of 0, but not one, the second computes factorial of 1 (and 0), but not 2, and the third... This is not the best way as is seen;-)

To go further we need to recall some notions: Refactoring Principles (code refactoring is process of restructuring the code without changing it's external behavior). 

1. Tennant Refactoring Principle: If we surround an expression by the lambda it doesn't change anything, example: 

(* x 3) -> ((lambda ()(* x 3)))

 2. Introduce binding: If wrap a function call, by another function with arguments which are not bound anywhere  in the body of our current call and call that function with some arbitrary argument; it doesn't change anything, example:

(f (g n))-> 
((lambda (xuv) (f (g n))) 12343456789)

3. Function Wrapping - if we wrap function by another and call the inner with the wrapper function argument, it doesn't change anything:

(lambda (n) (+ n x)) ->
(lambda (s)((lambda (n) (+ n x)) s))

4. Inlining - anywhere when function is called by name , instead of a name of the function, put an actual function body - it doesn't change anything: 

(define compose (lambda (f g)
   (lambda (n) (f (g n))))) 

(compose dec inc) -> 

((lambda (f g)
   (lambda (n) (f (g n)))) dec inc)

Now let's make some inlining on our first, second and third, name this whole thing and make some more copies the calls:

(define fy (improver (improver
 (improver  (improver (improver  
 (improver (improver (improver 
(improver (improver (improver  error))))))))))))

 Now by calling fy from zero, one , two,..., we are able to compute factorial up to ten, recursively and anonymously, but obviously that's, again, not what we want. 

Nothing new now, we rewrite fy, in the way that it applying improver to partial directly (we have one definition now):

(define fy
  ((lambda (improver) (improver
    (improver  error)))
     (lambda (partial) 
      (lambda (n) (if (zero? n) 1
         (* n   (partial (dec n)
            )))))))

It was noting new, it can compute factorial from zero: (fy 0)  -> 1. But now let's try this: instead of call improver from error, call, in the line 2, improver from improver! There may be no partial now, so  we can rename it to improver and, remember that, when partial calls number in the line 5 now function must call function with decremented number(because improver expects function, not a number), so we have now: 

(define fy
  ((lambda (improver) (improver improver))
     (lambda (improver) 
      (lambda (n) (if (zero? n) 1 
        (* n ((improver improver) (dec n)
)))))))

Now, after removing definition of the function and changing names:

(((lambda (x) (x x))(lambda (x) 
   (lambda (n) (if (zero? n) 1 
       (* n ((lambda (v) ((x x) v))
          (dec n))))))) 7)

This computes factorial! So it proves, that Lambda Calculus is powerful enough to make recursion and perform computation, but recursion and factorial is mixed; we want to split it, to have a Y, which can be applied to any recursive function. Make a move than! Suppose, that we wrap around the second (x x) (line 4), and use Tennant in the third Lambda:

(((lambda (x) (x x))
   (lambda (x) 
    ((lambda () (lambda (n) (if (zero? n) 1 
       (* n ((lambda (v) ((x x) v)) (dec n)))))
           )))) 7)

Now we introduce binding. To the "empty" Lambda, we bind: name of the variable will be "code" and is called with the value "error":

(((lambda (x) (x x))
  (lambda (x) 
    ((lambda (code) 
       (lambda (n) (if (zero? n) 1 
         (* n ((lambda (v) ((x x) v))
            (dec n)))))) error))) 7)

 Because it doesn't matter what value we put instead the value error (it's never used in the inner function, we can legitimate put:

(lambda (v) ((x x) v))

So it's now:

(((lambda (x) (x x))
  (lambda (x) 
    ((lambda (code) 
      (lambda (n) (if (zero? n) 1
        (* n ((lambda (v) ((x x) v)) 

         (dec n)))))) 

          (lambda (v) ((x x) v))))) 7)

 Another move, since the code in the scope of the third Lambda is bind to:

(lambda (v) ((x x) v))

then we are allowed to make some kind of the "reverse inline" and change this expression to "code" in the line 6:

(((lambda (x) (x x))
     (lambda (x) 
      ((lambda (code) 
         (lambda (n) (if (zero? n) 1 

           (* n (code (dec n))))))
            (lambda (v) ((x x) v))))) 7) 

Renaming "code" to "partial" gives us our original partial factorial definition (still lumped together tough):

(((lambda (x) (x x))
     (lambda (x) 
      ((lambda (partial) 
         (lambda (n) (if (zero? n) 1 (* n (partial (dec n))))))

            (lambda (v) ((x x) v)) ))) 7)

1. Tennant Refactoring on the whole function. 2 Introduce Binding "code" and "error" again:

(((lambda (code)
   ((lambda (x) (x x))
     (lambda (x) 
      ((lambda (partial) 
         (lambda (n) (if (zero? n) 1 

           (* n (partial (dec n))))))
           (lambda (v) ((x x) v)) )))) error) 7)

Now, take function:

(lambda (partial) 
   (lambda (n) (if (zero? n) 1 

     (* n (partial (dec n))))))

And replace it for error:

(((lambda (code)
  ((lambda (x) (x x))
     (lambda (x) 
        ((lambda (partial) 
            (lambda (n) (if (zero? n) 1 

              (* n (partial (dec n))))))
               (lambda (v) ((x x) v)) )))) 

               (lambda (partial) 
                 (lambda (n) (if (zero? n) 1 

                  (* n (partial (dec n))))))) 7)

And again, since:
 

(lambda (partial) 
   (lambda (n) (if (zero? n) 1 

      (* n (partial (dec n))))))

Is now bounded to code ,(in the scope of this function a variable code is bounded to it) we can substitute "code" for this function:

 (((lambda (code)
    ((lambda (x) (x x))
     (lambda (x) (code (lambda (v) ((x x) v)) )))) 
        (lambda (partial) 
           (lambda (n) (if (zero? n) 1 

            (* n (partial (dec n)))))))  7)

Changing code to improver now:

 (((lambda (improver)
   ((lambda (x) (x x))
    (lambda (x) (improver (lambda (v) ((x x) v)) )))) 

      (lambda (partial) (lambda (n) (if (zero? n) 1 

        (* n (partial (dec n))))))) 7)

Recall, that those functions keep computing factorial all way around! We have three lines of code dealing with recursion mechanism and two with factorial, let's tear it out:

(define factorial-improver
   (lambda (partial) 
       (lambda (n) (if (zero? n) 1 

         (* n (partial (dec n))))))

(define y 
   (lambda (improver)
        ((lambda (x) (x x))
       (lambda (x) (improver (lambda (v) ((x x) v)) )))))

Y is a Fixed Point Combinator or Applicative Order Y Combinator, computes a
fixed point of the improver function, which is factorial function! We know it because:

((y factorial-improver) 7)

It's just another way to write our factorial computing functions. So, Y takes a recursive anonymous function and returns the full - fledged recursive version of it! Which is a fixed point of anonymous function - we see that, because: Let's name:

((y factorial-improver) 7)

As a factorial :

(define fact (y factorial-improver)) 

And we see, that:

(factorial-improver fact)

Is still the factorial function (means it's fixed point!).

Now we are going to "tweak" our Y a little bit, to make it looks more like a textbook one;). First, change "improver" to "f":

(define y 
  (lambda (f)
    ((lambda (x) (x x))
      (lambda (x) (f (lambda (v) ((x x) v)) )))))

And then, because (x, x) returns fully fledged factorial and "f" is our "improver", then calling "f" upon it ((x, x)) doesn't change anything (improved factorial is still factorial). And  next, I'm doing function wrap around incriminated (x, x):

(define y 
   (lambda (f)
        ((lambda (x) (f (lambda (v) ((x x) v))))
         (lambda (x) (f (lambda (v) ((x x) v)))))))

Notice, both the last lines looks the same! Finally we have more wiki looks like one;) Y - Combinator, sometimes called Z - Combinator.  Existence of this function is shocking for me, this must be very important fact, that something so simple, like the  Lambda Calculus, is powerful enough to make computation, recursion, to build algorithms!  This is a screenshot of the last few lines of my notes to this post - with computed factorial from 1550 (few first digits):

Thank you for patience!