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?