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:
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.
Y = λf·(λx·f (x x)) (λx·f (x x))
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
factrecursively. But what happens if you try to make
factinto 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
Fact. Unfortunately, Erlang doesn't let you do this. If you tried, Erlang would say that
Factis unbound. This is true - until we've finished defining the fun, we can't assign it to
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.
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
Helperis a fun/2. Since
Helper2is supposed to be another name for
Helper2must 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
Helper2along when we call
Now that leaves us to deal with the function
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!