The Y Combinator in C#

Introduction

Most of the programmers are quite familiar with the common definition of a recursive function. Let's take factorial for example, using C#:

static int Factorial(int n)
{
    return n == 0 ? 1 : n * Factorial(n - 1);
}

Using lambda expression:

int n => n == 0 ? 1 : n * (???)(n - 1);

A lambda expression basically is a description of how the function works. The left of => is the function parameter, for the prior one, the parameter is an integer called n. The right side of => is the way to produce the result of the function. for the prior one, the result is also an integer (suppose the largest result we need is no bigger than the biggest value the integer in C# can present). The only question need to be solved is the (???) part. It should be the function itself, but the function does not have a name so we can call it.

So, it seems if we need recursion, we have to give the function a name, like this:

Func<int, int> FactorialFunc = n => n == 0 ? 1 : n * FactorialFunc(n - 1);

Func<int, int> means the type of FactorialFunc is a delegate (aka, a type of function) that takes a parameter of type int, and returns a result of type int. Actually, this code will give us a compilation error, says that you cannot use FactorialFunc before you have assigned it to some value. (There is a hack to solve this problem, we'll see in the following part.) Now, the question is, how do we describe a recursive function without naming it? The answer will lead us to the Y Combinator.

Background

Mike Vanier wrote an excellent article about the Y Combinator, which this one is inspired a lot. Mike uses Scheme language in his article to demonstrate, we will use C# here. C# is a static and strong type language, so the extra work is to explicitly define what type a variable is.

Derive the Y Combinator Step by Step

C# Hacking

Now we are going to derive the Y Combinator step by step. But before we start, remember you can't use a variable before you have assigned it to some value? So the hack is:

// some c# hack for lambda recursion
Func<int, int> fac1 = null; // fac1 should be first declared and assigned
fac1 = n => n == 0 ? 1 : n * fac1(n - 1);
int i1 = fac1(5); // 120

It works! What have we done? Well, we first declared a function fac1 and assigned it to a value of whatever, then we "redefined" it using recursion. Since fac1 has already "assigned", we can use it in the "re-definition" and there is no compilation error.

One Straight-Forward Approach

Take a look at the problem we need to solve again:

n => n == 0 ? 1 : n * (???)(n - 1);

Since we don't have the name of the function, why not pass the function itself as a parameter?

(self, n) => n == 0 ? 1 : n * self(n - 1);

When you need to calculate the factorial of n, you not only supply n as a parameter, but also supply the function itself as another parameter. But this will not work, since the function takes two parameters, and the self(n - 1) is only supplied by one. It should be like this:

(self, n) => n == 0 ? 1 : n * self(self, n - 1);

We know self is a function (delegate) that takes two parameters, one is a function type, the other is an int type, and returns int type. We can define it in C#:

// late-bound for delegate, that we don't have to specify its type
Func<Delegate, int, int> fac2Partial = (self, n) => n == 0 ? 1 : n * (int)self.DynamicInvoke(new[] { (object)self, n - 1 });
Func<int, int> fac2 = n => fac2Partial(fac2Partial, n);
int i2 = fac2(5); // 120

It works! But note that the function which need "self" as a parameter is not really the factorial function that takes an integer and returns an integer, the real factorial function is the function when you put fac2Partial to fac2Partial as parameter. Like this:

Func<int, int> fac2 = n => fac2Partial(fac2Partial, n);

Another thing we need to notice is that we have not specified the first parameter's type of fac2Partial. The first parameter's type of fac2Partial is also the type of fac2Partial itself. The only thing we know is that it is a function, aka Delegate. And when we call the function, we don't know the function's signature, So we have to use DynamicInvoke method and try to pass two parameters to the function.

If You Need to Know Its Type, You Need to Know Its Type First

C# is a static-type language, so what is the type of fac2Partial? Well, it is a function with two parameters, one of the parameters is int type, and the return is int type, so basically its type is Func<first-parameter-type, int, int>, and the first parameter's type is just the function type itself, so it's Func<Func<first-parameter-type, int, int>, int, int>, it's an infinite loop, if you need to know its type, you need to know its type first.

But things are not going to end. With some tricks:

// a delegate that takes two parameters, one of the parameter's type is itself
delegate TR SelfApplicable<T1, T2, TR>(SelfApplicable<T1, T2, TR> self, T2 p);

We defined a function type with two parameters, self and p, the type of self is SelfApplicable<T1, T2, TR>, that is the type of the function itself. The other parameter's type is T2, and the return type is TR.

With this definition, we can define the type of the self-feeded function:

SelfApplicable<Func<int, int>, int, int> fac3Partial = (self, n) => n == 0 ? 1 : n * self(self, n - 1);
Func<int, int> fac3 = n => fac3Partial(fac3Partial, n);
int i3 = fac3(5); // 120

And it works!

Take It the Lambda Way

fac3Partial is a function that takes two parameters. Using lambda calculus, we can convert it to a nested function, the outer one takes the first parameter, and the inner one takes the second parameter:

fac4Partial = self => n => n == 0 ? 1 : n * self(self)(n - 1);

fac4Partial takes one parameter self, and what it returns is a function n => n == 0 ? 1 : n * self(self)(n - 1). This makes fac4Partial a high-order function, that is, it produces functions. By eliminating the parameter n, the return value of fac4Partial is no longer an integer, but a function of n. This is referred to partial evaluation. The return type of fac4Partial is Func<int, int>, so does the parameter's type of fac4Partial. We can define it:

// a delegate that takes itself's type as parameter
delegate T SelfApplicable<T>(SelfApplicable<T> self);

SelfApplicable<Func<int, int>> fac4Partial = self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<int, int> fac4 = n => fac4Partial(fac4Partial)(n);
int i4 = fac4(5); // 120

It works! Note that in n => n == 0 ? 1 : n * self(self)(n - 1), we use self, which is defined out of the function's scope. This is referred to a closure.

We can also write fac4 as:

Func<int, int> fac4 = fac4Partial(fac4Partial);

It works too, but they have a little but important difference. fac4 = fac4Partial(fac4Partial) means fac4 is the product of fac4Partial when you supply fac4Partial as the parameter, this expression defines what the function is. fac4 = n => fac4Partial(fac4Partial)(n) describes how the function works. Keep this important difference in mind, it will solve big problems later.

The Fix Point

Take a look back at the first attempt we try to construct the recursive factorial function:

n => n == 0 ? 1 : n * (???)(n - 1);

Since we don't know what (???) should be, make it a parameter:

(Func<int, int> f, int n) => n == 0 ? 1 : n * f(n - 1);

Make it the lambda way, and define it with name AlmostRecursiveFactorial

AlmostRecursiveFactorial = f => n => n == 0 ? 1 : n * f(n - 1);

What is the type of AlmostRecursiveFactorial? It's parameter is f, which is a function takes int as parameter and returns int, and it returns n => n == 0 ? 1 : n * f(n - 1), which is also a function takes int as parameter and returns int. We can define:

// a function type that parameter is a function type, return value is the same function type
delegate Func<TIn, TOut> AlmostRecursiveFuncType<TIn, TOut>(Func<TIn, TOut> p);

static AlmostRecursiveFuncType<int, int> AlmostRecursiveFactorial = f => n => n == 0 ? 1 : n * f(n - 1);

Here comes the magic. Suppose that we have a real recursive factorial function named RealRecursiveFactorial that will calculate the factorial of n, and use it as the parameter of AlmostRecursiveFactorial, what will it produce?

AlmostRecursiveFactorial(RealRecursiveFactorial) = n => n == 0 ? 1 : n * RealRecursiveFactorial(n - 1);

n => n == 0 ? 1 : n * RealRecursiveFactorial(n - 1) looks like a real recursive factorial function! Actually, we can prove that the production of AlmostRecursiveFactorial(RealRecursiveFactorial) is identical to RealRecursiveFactorial. This means RealRecursiveFactorial is the fix point of AlmostRecursiveFactorial.

Again, the fix point of the "almost-recursive function" is the "real-recursive function".

Place the Recursion to Somewhere Else

OK, now we have an "almost-recursive" function, if we find its fix point, we find the "real-recursive" function. And Here the magic Y Combinator comes. It can give the fix point of an "almost-recursive function":

fix-point-of-AlmostRecursiveFactorial = Y(AlmostRecursiveFactorial);
// aka
RealRecursiveFactorial = Y(AlmostRecursiveFactorial);

And we have: RealRecursiveFactorial is identical to AlmostRecursiveFactorial(RealRecursiveFactorial), we can derive:

Y(AlmostRecursiveFactorial) = AlmostRecursiveFactorial(Y(AlmostRecursiveFactorial));
// aka
Y = f => f(Y(f));

Here we get a definition of Y. Let's practice this in C#, but first we need to define its type:

delegate Func<TIn, TOut> YType<TIn, TOut>(AlmostRecursiveFuncType<TIn, TOut> f);

Y takes a parameter of "almost-recursive function" type and returns the "real-recursive" function. Then we can define the Y Combinator using C# function and lambda expressions:

static Func<int, int> YIntRecursiveFunc(AlmostRecursiveFuncType<int, int> f)
{
    return f(x => YIntRecursiveFunc(f)(x));  // still use explicit recursion
}

static YType<int, int> YIntRecursiveDelegate1 = f => n => f(YIntRecursiveDelegate1(f))(n);
static YType<int, int> YIntRecursiveDelegate2 = f => f(YIntRecursiveDelegate2(f));

Still, notice that the difference of what and how between YIntRecursiveDelegate1 and YIntRecursiveDelegate2. Sadly, we have to use explicit recursions in the definition of Y. It looks like we just replace the recursions from the recursive functions to the body of Y. But, at least this is one step forward. Let's see if this will work.

var fac5 = YIntRecursiveFunc(AlmostRecursiveFactorial);
int i5 = fac5(5); // 120

var fac6 = YIntRecursiveDelegate1(AlmostRecursiveFactorial);
int i6 = fac6(5); // 120

// evaluation of fac7 will lead to infinite loop
var fac7 = YIntRecursiveDelegate2(AlmostRecursiveFactorial); // Stack overflow!
int i7 = fac7(5); // never goes here

fac5 works fine, but that's not a surprise, it still uses recursive functions. fac6(5) seems to work fine too. But the real interesting thing is, when evaluating fac7, stack overflows. It looks like that it has gone into some infinite loop. Actually, you can try evaluating fac7 using YIntRecursiveDelegate2, the evaluation will be infinite. But why YIntRecursiveDelegate1 works? Take a look at the definition of Y:

Y = f => f(Y(f));

When you supply f with the "almost-recursive" function, you will get the "real-recursive" function. That is, Y(f) is a function. But when you try to get it, you go into infinite loop. However, if you just accept that you will never get the function, all you can do is describing how it works, the problem is solved. The function itself will never be evaluated, but when you use it, like Y(f)(5), because you have described how it works, you will get the result of the function. The principal is avoiding evaluating functions, but describing it. How to describe a function? The answer is lambda expression:

Y = f => f(n => Y(f)(n));

Here we describe Y(f) by using lambda expression n => Y(f)(n). So fac6 won't be evaluated when you define it as var fac6 = YIntRecursiveDelegate1(AlmostRecursiveFactorial). But you have clearly described how fac6 should work, so when you apply the parameter 5 to fac6, it will give you the answer.

Still notice that in YIntRecursiveFunc we use "describing". If we write the function like this return f(YIntRecursiveFunc(f));, it won't work, I think you have got the idea. And here's a question for you: will the following code work? And why?

Func<int, int> facX = n => YIntRecursiveDelegate2(AlmostRecursiveFactorial)(n);
int iX = facX(5); // ???

Infinite Loops

As for now, we have solved the problem, partially, by replacing the recursion into Y Combinator. The final goal is to eliminate recursions totally. But before that, let's go through some infinite loops, hope that we can still come back.

Let's start from fac4, but define the self(self) thing as a variable f:

SelfApplicable<Func<int, int>> fac8Partial = self => { var f = self(self); return new Func<int, int>(n => n == 0 ? 1 : n * f(n - 1)); };
var fac8 = fac8Partial(fac8Partial); // infinite loop
int i8 = fac8(5); // never goes here

Looks like the n => n == 0 ? 1 : n * f(n - 1) is the "almost-recursive" function, so f could be the fix point! However, this won't works, because evaluating f leads to infinite loop.

We can use our pre-defined "almost-recursive" function here:

SelfApplicable<Func<int, int>> fac9Partial = self => AlmostRecursiveFactorial(self(self));
var fac9 = fac9Partial(fac9Partial); // infinite loop
int i9 = fac9(5); // never goes here

Again, infinite loop.

Define the AlmostRecursiveFactorial in the "partial" function:

SelfApplicable<Func<int, int>> fac10Partial = self => new AlmostRecursiveFuncType<int, int>(f => n => n == 0 ? 1 : n * f(n - 1))(self(self));
var fac10 = fac10Partial(fac10Partial); // infinite loop
int i10 = fac10(5); // never goes here

Same.

Take a look back at fac8. What about put the evaluation of f into the n != 0 branch?

SelfApplicable<Func<int, int>> fac11Partial = self => new Func<int, int>(n => { if (n == 0) return 1; else { var f = self(self); return n * f(n - 1); } });
var fac11 = fac11Partial(fac11Partial);
int i11 = fac11(5); // 120

It works! Because the evaluation of f will only happens when n is bigger than 0. When n decreases to 0, the infinite loop breaks.

Still start from fac8, we place the "partial" function into lambda expression:

Func<int, int> fac12 = n => { SelfApplicable<Func<int, int>> fac12Partial = self => AlmostRecursiveFactorial(self(self)); return fac12Partial(fac12Partial)(n); };
int i12 = fac12(5); // infinite loop

Although infinite loop, we are closer and closer to Y Combinator. this time we do not define the "partial" function:

Func<int, int> fac13 = n => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => x(x))(self => AlmostRecursiveFactorial(self(self)))(n);
int i13 = fac13(5); // infinite loop

If we don't use n explicitly, like this:

Func<int, int> fac14 = new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => x(x))(self => AlmostRecursiveFactorial(self(self))); // infinite loop
int i14 = fac14(5); // never goes here

The evaluation of fac14 leads to infinite loop, because we are not "describing" it.

Take AlmostRecursiveFactorial out and make it a parameter, we get the Y Combinator:

YType<int, int> NormalOrderY1 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => x(x))(self => f(self(self)));
var fac15 = NormalOrderY1(AlmostRecursiveFactorial);  // infinite loop
int i15 = fac15(5); // never goes here

By applying the lambda expression self => f(self(self)) to x => x(x), then we get:

YType<int, int> NormalOrderY2 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => f(x(x)))(x => f(x(x)));
var fac16 = NormalOrderY2(AlmostRecursiveFactorial); // infinite loop

These Y Combinators has no explicit recursions. They are referred to the normal-order Y Combinators. However, they won't work in C#, all we have got are infinite loops.

I'm Not Going to Tell you, I Will Only Describe for You

Take a while to recall the way we have done to solve infinite loops: describing. Delay the evaluation to when it is really needed, until then, everything has to be described but not defined. Take a look at fac8. Because we defined a variable f, then the evaluation of f leads us to infinite loop. What if we just describe f?

SelfApplicable<Func<int, int>> fac17Partial = self => { Func<int, int> f = y => self(self)(y); return new Func<int, int>(n => n == 0 ? 1 : n * f(n - 1)); };
var fac17 = fac17Partial(fac17Partial);
int i17 = fac17(5); // 120

It works! Just by changing the definition to description. So, let's also try changing the x(x) thing in NormalOrderY2:

YType<int, int> ApplicativeOrderY1 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => f(y => x(x)(y)))(x => f(y => x(x)(y)));
var fac18 = ApplicativeOrderY1(AlmostRecursiveFactorial);
int i18 = fac18(5); // 120

Actually it could also be like this:

YType<int, int> ApplicativeOrderY2 = f => new Func<SelfApplicable<Func<int, int>>, Func<int, int>>(x => f(x(x)))(x => f(y => x(x)(y)));
var fac19 = ApplicativeOrderY2(AlmostRecursiveFactorial);
int i19 = fac19(5); // 120

Both of these works! Finally we have eliminated all explicit recursions and get our usable Y Combinators. These are referred to the applicative-order Y Combinators. Problem solved!

Summary

Functional programming makes us to think how things works, not what they are. When we describe how the functions should work, they don't really do the work. Nothing is produced. We can apply more and more functions to make a nested description, and when we apply the input parameter to the function, the nested functions just expand automatically and produce the answer.

With this article would help you think in a functional way!

History

Revision 0.1, May 27th, 2014