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 ~= fac

In a strict language, we evaluate all the arguments to a function call before applying the function, whether or not those arguments are needed. As opposed to a lazy language.

Hmm, python is a lazy language too by this definition, but the implicit definition of a y combinator won't be valid python. Would python with tail optimization solve this for us?

ycomb = lambda f: f(ycomb(f))

Well, it is valid python but it gets stuck in a recursive loop and throws the max recursion depth error.

This works in python though, and it is the creature referred to as Y. The python lambda expression lets you postpone the evaluation to later, when the argument is available.

ycom = lambda f: f(lambda x: ycom(f)(x))

# for all x, we'll see, ycom(sortfac)(x) == fac(x)

Going from the Y to the Y combinator

Why don't we want explicit reference though?

fac = lambda n: 1 if n<1 else n*fac(n-1)
bac = fac
fac = lambda x: x

# bac doesn't work anymore

Making part-factorial:

partfac = lambda f,n: 1 if n<1 else n*f(f, n-1)
# fac = partfac(partfac, )

partfac = lambda f: lambda n: 1 if n<1 else n*f(f)(n-1)
# sort of currying? Now, fac = partfac(partfac)

This is a non-explicit recursive implementation! But we want a HOF that does the transformation for any function, not just the factorial function.

Discovering sort-of-factorial inside part-factorial:

sortfac = lambda f: lambda n: 1 if n<1 else n*f(n-1)

partfac = lambda f: sortfac(f(f))
fac = partfac(partfac)
# this didn't work out, we are evaluating everything at the first call

Can we still write a single expression for factorial, instead of one involving an assignment defining partfac first?

fac = (lambda x: x(x))(lambda f: sortfac(f(f)))
# still doesn't work in python since early evaluation

Now try to rewrite partfac using sortfac, but now it should work:

partfac = lambda f: sortfac(lambda x: f(f)(x))
# this works! So, we can write fac using sortfac now.

fac = (lambda x: x(x))(lambda f: sortfac(lambda n: f(f)(n)))

We got the y combinator! Now, we gotta extract the HOF definition so it works with any sort-of-recursive-function as an argument.

ycombinator = lambda f: (lambda x: x(x))(lambda y: f(lambda x: y(y)(x)))
# this works!

sortfac = lambda f: lambda n: 1 if n<1 else n*f(n-1)
fac = lambda n: 1 if n<1 else n*fac(n-1)
# ycombinator(sortfac) == fac

sortfib = lambda f: lambda n: n if n<2 else f(n-1) + f(n-2)
fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)
# ycombinator(sortfib) == fib