## Monday, January 18, 2010

### 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!