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?