15,999,410 members
Articles / Programming Languages / C#

# The Y Combinator in C#

Rate me:
28 May 2014CPOL10 min read 15.9K   18   1
This article described how to derive the Y Combinator using C# language.

## Introduction

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

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

Using lambda expression:

C#
`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:

C#
`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:

C#
```// 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:

C#
`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?

C#
`(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:

C#
`(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#:

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:

C#
`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:

C#
```// 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:

C#
```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:

C#
`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:

C#
```// 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:

C#
`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:

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

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

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

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

C#
`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:

C#
```// 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?

C#
`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":

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

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

C#
```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:

C#
`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:

C#
```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.

C#
```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`:

C#
`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:

C#
`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?

C#
```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`:

C#
```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:

C#
```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:

C#
```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?

C#
```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:

C#
```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:

C#
```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:

C#
```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:

C#
```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:

C#
```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`?

C#
```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`:

C#
```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:

C#
```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.

## History

Revision 0.1, May 27th, 2014

Written By
Software Developer
China
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.