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!

## No comments:

Post a Comment