Implementing Recursion with the Y Combinator in any Language
The most beautiful piece of code in computer science implemented in six programming languages.

New to Lambda Calculus? I’d recommend reading Lambda Calculus in JavaScript before continuing!

The Y Combinator is a fixed-point higher order function which is used to implement recursion in any programming language which does not support it natively. It has been introduced by the mathematician and logician Haskell Curry in 1940’s and is considered to be one of the most beautiful ideas in programming and logic. We’ll see how to implement that amazing piece of code in 6 programming languages:

  • JavaScript
  • Haskell
  • Java
  • Racket
  • Python
  • C

#Original Y Combinator in Lambda Calculus

Y = λf.(λx.(f(xx))λx.(f(xx)))

We’ve just expressed one of the most powerful concepts in computer science in less than 30 characters. As you may have guessed, we just wrote down the Y Abstraction. What’s its actual application? Let’s use the classical factorial example.

The factorial of a number n is the product of all the positive integers between 0 and n. We can easily use recursion in order to find the factorial of any positive integer (in pseudocode):

factorial(x)
    if x == 1 then 1
    else x * factorial(x - 1)

So let’s pretend we have to compute the factorial of 3; adopting the solution above, we’ll be executing our function the following way:

factorial(4) = 4 * factorial(3)
               4 * 3 * factorial(2)
               4 * 3 * 2 * factorial(1)
               4 * 3 * 2 * 1

So as you can see, we’re calling the factorial function inside the factorial function itself. This is a simple example about how recursion works, and not every language supports that style of programming!

Here comes the Y Combinator. Let’s start by implementing it in JavaScript.

#Y Combinator in JavaScript

const Y = f => (x => x(x))(x => f(y => x(x)(y)));

It’s actually pretty easy! As you can see, that is pretty close to the code we wrote above using the Lamba Calculus notation! Now, we need to implement our function which will calculate the factorial of a given integer:

const factorial = f => (x => (x === 1 ? 1 : x  * f(x - 1)));

Great! As you can see, we’re not taking an integer as first argument, but we’re taking a function that returns an anonymous function which takes an integer as its only argument. That way, we parametrized the f call, which will be used inside our Y implementation.

Now let’s call the factorial function using the *Y Combinator *we just wrote above and here we are:

const Y = f => (x => x(x))(x => f(y => x(x)(y)));
const factorial = f => (x => (x === 1 ? 1 : x  * f(x - 1)));
const YFactorial = Y(factorial)(10);

We can now call any kind of recursive function inside our Y Combinator avoiding runtime memory exceptions!

#Y Combinator in Haskell

y = \f -> (\x -> f (x x)) (\x -> f (x x))

As you can see, writing the Y Combinator Abstraction in Haskell is pretty easy when you’re coming from the Lambda Calculus notation! By the way, this code won’t compile because of (x x) which requires an infinite type. For that reason, we have to choose if we want to adopt an Unsafe Coercion and make it work, or change the approach:

Using Unsafe Coercion (unsafe):

import Unsafe.Coerce

y :: (t1 -> t2) -> t2
y = \f -> (\x -> f (unsafeCoerce x x)) (\x -> f (unsafeCoerce x x))

Adopting a non-recursive solution (safe):

newType Mu a = Mu (My a -> a)
y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)

(Taken from: https://stackoverflow.com/questions/4273413/y-combinator-in-haskell/5885270#5885270)

Just to keep it simple, we’re gonna use the unsafe version, which is easier to show and explain. Let’s implement the factorial function in Haskell!

factorial :: (Eq p, Num p) => (p -> p) -> p -> p
factorial f x = if x <= 1 then 1 else x * f(x - 1)

We can now call the factorial function using the previously defined Y Combinator:

import Unsafe.Coerce

y :: (t1 -> t2) -> t2
y = \f -> (\x -> f (unsafeCoerce x x)) (\x -> f (unsafeCoerce x x))

factorial :: (Eq p, Num p) => (p -> p) -> p -> p
factorial f x = if x <= 1 then 1 else x * f(x - 1)

main :: IO()
main = print $ y factorial 10 -- 3628800

It’s actually pretty cool! But I find it to be more “conceptual” to implement that kind of solution in Haskell, which already has an amazing support for recursion.

#Y Combinator in Java

import java.util.function.Function;

public class Main {

    interface Y extends Function, F> { }

    public static  Function Y(Function, Function> f) {
        Y> r = w -> f.apply(x -> w.apply(w).apply(x));
        return r.apply(r);
    }

    public static void main(String... arguments) {
        Function factorial = Y(f -> x -> (x == 1) ? 1 : (x * f.apply(x - 1)));

        System.out.println(factorial.apply(10));
    }
}

I have to admit it: I am not a Java expert and that is actually the most complex piece of code I ever wrote… but it works! And it shows you an alternative to the classical Imperative/Object Oriented approach in Java. I am not saying that you should use this kind of approach everytime you have to solve a problem using recursion in Java: instead, I strongly believe that the example above shows you how Lambda Calculus can actually be as complete as the Turing Machine, which is the foundation of imperative and Object Oriented languages such as Java!

#Y Combinator in Racket

(define Y (λ(f)((λ(x)(f (x x)))(λ(x)(f (x x))))))

(define Fact
  (Y (λ(fact) (λ(x) (if (equal? x 1) 1 (* x (fact (- x 1))))))))

Racket implementation is basically the same as the Lambda Calculus one! They’re actually pretty similar and that language shows how close it is to the Lambda Calculus notation, which is the foundation of any LISP programming language!

#Y Combinator in Python

Y = lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))

factorial = lambda f: lambda x: (1 if x == 1 else x * f(x - 1))

Y(factorial)(10)

Y Combinator in Python is actually easy to implement, but a little “messy” because of its lambda syntax. By the way, the way it works is extremely clear and developer working with Python will certainly understand how the Y Combinator works under the hood!

#Y Combinator in C

#include 
#include 

typedef struct func_t *func;
typedef struct func_t {
    func (*fn) (func, func);
    func _;
    int num;
} func_t;

func new(func(*f)(func, func), func, _) {
    func x = malloc(sizeof(func_t));
    x->fn = f;
    x->_ = _;
    x->num = 0;
    return x;
}

func call(func f, func n) {
    return n->fn(f, n);
}

func Y(func(*f)(func, func)) {
    func g = new(f, 0);
    g->_ = g;
    return g;
}

func num(int n) {
    func x = new(0, 0);
    x->num = n;
    return x;
}

func fac(func self, func x) {
    int xx = x->num;
    return xx == 1
            ? num(1)
            : num(xx * call(self->_, num(xx - 1))->num);
}

void printNum(func n) { printf(" %d", n->num); }

int main {
    int i;
    func f = Y(fac)
    printNum(call(f, num(10)));
    return 0;
}

That has probably been the worst idea in my life, but its pretty satisfying to see how such a low level language, can still implement such an abstract concept derived from Lambda Calculus!

Pure C solution is not even close to the Lambda Calculus definition, but does the exact same job with outstanding performances!

#Conclusion

As we’ve seen in both Java and C examples, Lambda Calculus concepts can still be expressed in languages which were born with a totally different approach their core. Lambda Calculus is an amazing topic and is totally worth to spend some time studying it. It’s actually mind-changing!