## Friday, January 29, 2010

### Deriving the Y Combinator in Erlang - Part 2: Abstraction

This is the second post in a series on the Y combinator. Part 1

In the last post on the Y combinator, we established that some functional languages (such as Erlang) make it hard to have recursive, anonymous functions. Namely, there is no name that is bound to the "current" anonymous function. Furthermore, we established that we could work around this problem by passing the anonymous function to itself. When we concluded, we had derived this much:

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

Fact = fun(X) -> Helper(Helper, X) end
```

This post will focus on extracting the Y combinator from the above code. We will follow a sequence of transformations, each with a specific intent. In the end, we will hopefully have some beautiful code.

#### Reducing the Number of Arguments

This factorial algorithm started with a function that took a single parameter. This function called itself with successively smaller values, until it reached a base case. However, we muddied the waters by passing the function around as well. We would like to return to having a one-parameter function. We can accomplish this by creating another level of closure:

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

Fact = fun(X) -> (Helper(Helper))(X) end
```
Now it is clear that our recursive function is really only calling itself with one parameter.

#### Simplifying the Recursive Function Call

The place where we make the recursive call is rather ugly. We have to build the function upon which we will recurse before we can actually call it. It would be better if the recursive function was explicitly named. We can do that, too:

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

Fact = fun(X) -> (Helper(Helper))(X) end
```

We call the new identifier `PAHelper2` to suggest that it's a partially-applied version of `Helper2`.

We can simplify the body further by moving `PAHelper2` to a higher scope.

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

Fact = fun(X) -> (Helper(Helper))(X) end
```

As an aside, you might find this step overly complicated. You may ask, why did we not simply define `PAHelper2 = Helper2(Helper2)`? Why the extra indirection? We don't actually want to evaluate `Helper2` just yet. In fact, if we were to do so, we'd end up in an infinite loop. If the first step of `Helper` is to immediately call `Helper2` (an alias for `Helper`), we'll be recursing on ourself with no way to ever terminate.

#### Extracting the Anonymous Function

Right now, the body of our algorithm is embedded deeply within some necessary plumbing. We would like to extract our algorithm from the center of this. This is quite easy:

```Helper = fun(Helper2) ->
PAHelper2 = fun(Z) -> (Helper2(Helper2))(Z) end,
FactRec = fun(Self) ->
fun(N) ->
case N of
1 -> 1;
_ -> N * Self(N - 1)
end
end
end,
FactRec(PAHelper2)
end,

Fact = fun(X) -> (Helper(Helper))(X) end
```

Now we can pull it outside the body of `Helper`.

```FactRec = fun(Self) ->
fun(N) ->
case N of
1 -> 1;
_ -> N * Self(N - 1)
end
end
end,

Helper = fun(Helper2) ->
PAHelper2 = fun(Z) -> (Helper2(Helper2))(Z) end,
FactRec(PAHelper2)
end,

Fact = fun(X) -> (Helper(Helper))(X) end
```

#### Simplifying Fact

We're getting close, but the definition of `Fact` still leaves something to be desired. However, in order to make it simpler, we have to first make it messier. Start by moving `Helper` inside the definition for `Fact`:

```FactRec = fun(Self) ->
fun(N) ->
case N of
1 -> 1;
_ -> N * Self(N - 1)
end
end
end,

Fact = fun(X) ->
Helper = fun(Helper2) ->
PAHelper2 = fun(Z) -> (Helper2(Helper2))(Z) end,
FactRec(PAHelper2)
end,

(Helper(Helper))(X)
end
```

Our goal is to build a general-purpose function `Y` that takes a function ```F ``` and produces a self-recursive version of that function. Right now, the innermost part of `Helper` makes an explicit reference to `FactRec`. We want to eliminate that explicit reference:

```FactRec = fun(Self) ->
fun(N) ->
case N of
1 -> 1;
_ -> N * Self(N - 1)
end
end
end,

Fact = fun(X) ->
Y = fun(Proc) ->
Helper = fun(Helper2) ->
PAHelper2 = fun(Z) -> (Helper2(Helper2))(Z) end,
Proc(PAHelper2)
end,
Helper(Helper)
end,
(Y(FactRec))(X)
end
```

Now that we've done this, `Y` no longer has any bound variables, so we can pull it out of `Fact` completely:

```FactRec = fun(Self) ->
fun(N) ->
case N of
1 -> 1;
_ -> N * Self(N - 1)
end
end
end,

Y = fun(Proc) ->
Helper = fun(Helper2) ->
PAHelper2 = fun(Z) -> (Helper2(Helper2))(Z) end,
Proc(PAHelper2)
end,
Helper(Helper)
end,

Fact = fun(X) ->
(Y(FactRec))(X)
end
```

Of course, if we want, we can simplify some of these definitions. `Y` can become a normal Erlang module function (rather than a function value). `Fact` itself can be curried - we can eliminate the noise of the explicit parameter. Also, `FactRec` doesn't need to be named anymore - it can become the anonymous function that we originally intended:

```y(F) ->
G = fun(G2) ->
F(fun(Z) -> (G2(G2))(Z) end)
end,
G(G).

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

Unfortunately, the `y` function only supports functions that take a single parameter. Some languages have a "splat" operator that can be used to represent "all the parameters;" unfortunately, Erlang does not. Instead, it can be useful to define a family of y functions that deal with functions taking more than one parameter:

```y2(F) ->
G = fun(G2) ->
F(fun(Y, Z) -> (G2(G2))(Y, Z) end)
end,
G(G).
```

#### Conclusion

We have shown the difficulty in defining recursive, anonymous functions in Erlang. We showed a simple solution to this problem, and then generalized the plumbing to make it easier to use. While this is not necessary in all functional languages, I hope that this is useful to anybody working in a strict language, such as Erlang.

I am planning more posts on this topic. One post will explain the strange step I took in Simplifying the Recursive Function Call. Others will explain just what a fixed point is, what the fixed point combinators are, and how the Y combinator satisfies the definition of a fixed point combinator.

Anonymous said...

This is why Landin invented letrec.

For single functions the problem of self reference
is much easier solved with a meta variable.

Fac = fun(0) -> 1;
(N) -> Self * fac(N-1)
end.

The obscurity of the Y combinator necessitates the invention of letrec.

The third part of the article should be
Replacing the Y combinator with labels

Dan said...

I've toyed with functional languages before, but never extensively. I was unaware of letrec. Thanks!

Correct me if I'm wrong, but I don't think Erlang supports letrec. It would certainly be convenient.

The Y combinator is certainly not perfect. It supports self-recursive functions well, but I'm not sure how it would scale to mutually-recursive functions.

There is an interesting consequence to the Y combinator that I will try to cover in another post. In short: it might make some forms of unit testing easier.

Anonymous said...

"it might make some forms of unit testing easier."
Really? How?