Refactoring Towards the Y Combinator: Part 1

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

Sometimes I wish that I had studied computer science rather than software engineering at university. The software engineering degree was much more practical, and as a result there is a bunch of interesting computer science theory out there that I am yet to be exposed to. In an effort to make some tiny progress on this front, this Christmas break I decided to spend a few days exposing myself to a lovely little thing called the Y combinator.

What is the Y combinator exactly? Basically, its a mechanism that can be used to call functions recursively, even if your programming language does not support recursion, as long as it does have support for first class functions (e.g. you can pass one function to another as an argument). It is extremely unlikely that you will find a use for it in your day to day work as a programmer, but I found learning about the Y combinator to be a worthwhile exercise nonetheless simply because it made my head hurt in a good way.

I found three particularly useful resources for learning about the Y combinator. These were:

• Recursive Lambda Expressions by Mads Torgersen
• The Y Combinator by Mike Vanier
• The Why of Y [PDF] by Richard Gabriel

Just reading through them, they all managed to lose me at some point. The Y combinator is really a functional programming concept, so programmers such as myself that were crippled at a young age by being first exposed to an imperative language like Basic will really struggle with it. It was clear that the only way I was really going to understand it was roll up my sleeves and write some code.

Mads’ post uses C#, and it had enough code to give me a clear goal. I would start with the most basic implementation of a recursive method I could, and try to slowly refactor it towards the final Mads code. This turned out to work very well, but I probably would not have succeeded without the help of the other resources, especially The Why of Y. Both Mike and Richard use Scheme (a dialect of Lisp), but fortunately I have watched enough SICP lectures to be able to follow it at a basic level. In the Why of Y, Richard provides an example derivation of Y, and I was able to successfully translate each of his steps to the appropriate C#. I promise you, there will be no Lisp code in any of the posts in this series.

So what does the Y combinator look like? Well here is the definition I ended up with:

SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
   self => algorithm => t => algorithm(self(self)(algorithm))(t);

HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y);

Here is my definition for the factorial function:

HigherOrderFunction<Func<int, int>> factorial =
               f => x => x < 2 ? 1 : x * f(x - 1);

And here is the usage:

public int CalculateFactorialOf10()
{
   return YCombinator<int>.ApplyY(factorial)(10);
}

What’s the phrase you’re looking for? How about: “My eyes! The goggles do nothing!”

Even now when I look at it, I struggle to make sense of it. This is the compressed version, but in my opinion even a far more verbose version is still difficult to comprehend. I understand this code by understanding the steps I followed to arrive at it, and hopefully by the end of this series of posts, so will you.