What is a Y Combinator?
I've always been curious why the Hackernews company is named "Ycombinator". Finally found a neat article to work though - The Y Combinator (Slight Return). Scattered notes below.
We try to write a recursive definition for the factorial function so that it has no dependence on any free variables (bound variables inside a lambda expression are those passed to it as an argument, the others are free).
This is an explicitly recursive implementation, since the body of the function refers to a symbol fac that we assign to the function outside. We want to avoid this.
fac = lambda n: 1 if n<1 else n*fac(n-1)Combinators are lambda-expressions/functions with no free variables.
Umm, why does a programming environment need to explicitly support recursion? If functions can call other functions, which is kinda essential, recursion is legible too.
sortfac is a higher order function, such that sortfac(fac) = fac.
sortfac = lambda f: lambda n: 1 if n<1 else n*f(n-1)Woah, is fac like a fixed point of the sortfac routine?
That's exactly right. In fact, starting off with feeding in the identity routine to the sortfac function, we can successively extract better and better approximations to the correct factorial function.
iden = lambda x: x
fac0 = sortfac(iden) # matches fac for x<1
fac1 = sortfac(fac0) # matches fac for x<2
fac2 = sortfac(fac1) # matches fac for x<3
# and so on.
# fac-infi ~= facIn a strict language, we evaluate all the arguments to a function call before applying the function