How is this lamda function beeing executed in an example for the Y combinator

Question

I have spent a few hours now trying to understand how the Y Combinator is working and how it allows us to construct recursive functions with higher order functions.

I have been going through this derivation http://mvanier.livejournal.com/2897.html which is using the factorial function for explanation which I find quite helpful but at some point I am always getting lost.

I still understand this part

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

  (define factorial (part-factorial part-factorial))
  (factorial 5) ==> 120

We have a function part-factorial which takes as a formal parameter self and applies it as argument (self self) to the first lambda function. So inside the first lambda f will evaluate to (self self) which in case of the factorial function will evaluate to (part-factorial, part-factorial). So in the second lambda then if we take 5 as our n the call to the function f will evaluate to part-factorial part-factorial 4 which will start the recursion.

After a few syntax changes we now define the functions as

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

  (define factorial
    ((lambda (x) (x x))
     (lambda (self) 
       (almost-factorial (self self)))))

  (factorial 5) ==> 120

And at this point I am confused. I understand the almost-factorial function as it is pretty much unchanged compared to part-factorial however the new factorial function is unclear to me, from a syntax perspective. I don't understand anymore which lamda will be executed with which parameters and in which order.

Could anybody explain to me the execution of this function?

Answer 1

I am just going to write h for almost-factorial because long names can sometimes obscure math.

We consider:

((lambda (x) (x x))
 (lambda (self) 
   (h (self self))))

Write foo for ((lambda (x) (x x)) and write bar for (lambda (self) (h (self self)))). Then our expression is just

(foo bar)

Using the definition of foo we see that this is equal to

(bar bar)

Then we use the definition of bar on the first occurrence of bar to see that this is equal to

((lambda (self) (h (self self)))) bar)

which in turn is just

(h (bar bar))

We discovered that (bar bar) is equal to (h (bar bar)). Let us write g for (bar bar), so g is equal to (h g). Taking into account the definition of h (which is jsut almost-factorial from your question) we see that (h g), and therefore g, is equal to

(lambda (n)
  (if (= n 0)
      1
      (* n (g (- n 1)))))

In other words, g is the usual factorial function. I hope I got all the silly lisp parentheses where they are supposed to be.