Deriving the Y Combinator in Erlang - Part 1: Intuition

This is the first of a series on the Y combinator. Part 2

---

When I heard about the fixed point combinators before, I didn't know what to make of them, so I filed the topic away in my brain. However, when I was working on implementing continuations in Erlang, I ended up building a small structure that reminded me of the Y combinator. With a little massaging, I extracted the actual Y combinator, and proceeded with what I was working on.

The actual definition of the Y combinator is insanely dense:

Y = λf·(λx·f (x x)) (λx·f (x x))

This is precisely why I didn't understand it at first - that definition means nothing to me. We need a more intuitive way to think about it.

Suppose you decide to write the factorial function in Erlang. A simple (by which I mean unoptimized) implementation might look like this:

fact(N) -> 
    case N of
        1 -> 1;
        _ -> N * fact(N - 1)
    end.

There's nothing particularly complicated here - we're just calling fact recursively. But what happens if you try to make fact into a fun (an anonymous function in Erlang). Watch:

Fact = fun(N) -> 
    case N of
        1 -> 1;
        _ -> N * ??? (N - 1) %%How do we call ourselves? Fact isn't yet bound!
    end
end.

In some languages, we could replace the ??? with Fact. Unfortunately, Erlang doesn't let you do this. If you tried, Erlang would say that Fact is unbound. This is true - until we've finished defining the fun, we can't assign it to Fact. Other languages provide you with a magic variable that represents the current function (Javascript has arguments.callee). Again, as far as I know, Erlang doesn't provide such a variable. Does that mean that we have no hope?

Let's look at this problem one step at a time. We need something to stand in for the ???. We need a name that represents the current, anonymous function. Where can we get that from? In functional Erlang, there are only three ways that names are bound - by closure, by parameter, or by local definition. We can't close over it, because the anonymous function isn't yet defined. We can't create a local definition, because the local scope is too narrow a scope for that. That leaves only one possibility - we need to pass the anonymous function to itself.

Helper = fun(Helper2, N) ->
    case N of
        1 -> 1;
        _ -> N * Helper2(Helper2, N - 1)
    end
end.

Fact = fun(N) -> Helper(Helper, N) end.

OK, so we created a helper function - more on that in a minute. Helper (formerly Fact) now takes an extra parameter, which just creates another name for the current, anonymous function. Since we intend for that to be the same as Helper, we call it Helper2. We know that Helper is a fun/2. Since Helper2 is supposed to be another name for Helper, then Helper2 must be a fun/2 as well. This means that, when we call Helper2, we need to also tell it about itself - that is, we need to pass Helper2 along when we call Helper2 to recurse.

Now that leaves us to deal with the function Fact. Clearly, Fact needs to call Helper. We noted that Helper is a fun/2, so again, we need to call it with two parameters. The intent of the extra parameter to Helper was to be able to pass Helper to itself, so we do just that.

Believe it or not, we have just derived the concept behind the Y combinator. We have invented a scheme that allows an anonymous function to know itself, even in a language that doesn't directly support this. This is (I believe) the purpose behind the Y combinator. However, we're not yet done. There is still some cruft that we would like to eliminate. In particular, we hand-built the plumbing to route Helper2 around. We would like to use higher order functions to eliminate this. This is what the Y combinator does - it manages the plumbing of anonymous functions that refer to themselves.

In the next part, we will continue the derivation of the Y combinator in Erlang. Our goal is to eventually be able to write something like this:

Fact = y(fun(Self) ->
    fun(N) ->
        case N of
            1 -> 1;
            _ -> N * Self(N - 1)
        end
    end
end).

It's not perfect, but in a language that doesn't directly support anonymous function recursion, it's not too bad!