anler.me

I first knew about the Y-combinator while reading Paul Graham’s paper The Roots of Lisp, there he said that Lisp’s primitive labels was not technically necessary since you can implement recursive functions by means of the Y-combinator, and that’s what we are going to try to derive here.

Let's make an anonymous function recurse!

Implementation

As an example we are going to use the so loved factorial function 😜, which is defined as:

\begin{equation} n! = \begin{cases} 1 & \quad \text{if } n = 0 \\ n*(n-1)! & \quad \text{if } n > 0 \end{cases} \end{equation}

Here is how I would write that function in JavaScript:

tsfunction factorial(n: number): number {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

Removing recursion

If JavaScript didn't allow us to call a function from its own definition, we would be in trouble since our code would not be able to recurse naturally:

tsfunction factorial(n: number): number {
  if (n === 0) {
    return 1;
  }
  // Pretending we can't call factorial from within itself
  throw new Error("Can't recurse :(")
}

factorial(0) // => 0
factorial(1) // => Can't recurse :(

Factorial closure

We know the recursive call should happen at the point we raise the exception, so let's change our definition in order to create a lexical closure capturing the factorial binding we need.

tstype Factorial = (n: number) => number;

function factorialFactory(factorialBinding: Factorial): Factorial {
  return function actualFactorial(n) {
    if (n === 0) {
      return 1;
    }
    // Now we are able to recurse since we have
    // access to the factorial function
    return n * factorialBinding(n - 1);
  }
}

This is an interesting idea, we are creating sort of lazily computed chain of factorial functions. See:

tsconst factorial = factorialFactory(
  function actualFactorial(n: number): number {
    if (n === 0) {
      return 1;
    }
    throw new Error("Can't recurse :(")
  }
)

console.log(factorial(0)) // => 0
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => Can't recurse :(

But notice that if we keep stacking factory calls, each time we are able to calculate a bigger factorial.

$n = 2$

tsconst factorial = factorialFactory(
  factorialFactory(
    function actualFactorial(n: number): number {
      if (n === 0) {
        return 1;
      }
        throw new Error("Can't recurse :(")
    }
  )
)

console.log(factorial(0)) // => 0
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => Can't recurse :(

$n = 3$

tsconst factorial = factorialFactory(
  factorialFactory(
    factorialFactory(
      function actualFactorial(n: number): number {
        if (n === 0) {
          return 1;
        }
        throw new Error("Can't recurse :(")
      }
    )
  )
)

console.log(factorial(0)) // => 0
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => 6
console.log(factorial(4)) // => Can't recurse :(

Recursing with closures

And this my friends is the key idea, I lied when I mentioned we are creating recursion "out of thin air", we instead are taking it from another place: the closures.

Right now, the recursion is quite manual since we are stacking the factory calls ourselves, but we can automate that by letting our factory recurse too by receiving a factory binding itself.

tstype FactorialFactory = (factorialFactoryBinding: FactorialFactory) => Factorial;

function factorialFactory(factorialFactoryBinding: FactorialFactory): Factorial {
  return factorialFactoryBinding(factorialFactoryBinding); // the recursive magic 🪄
}

Note the types, the factory now recurse by calling the factory binding with itself in order to be able to return the actual value it needs to return: the factorial function.

tsconst factorial = factorialFactory(
  function actualFactorialFactory(factorialFactoryBinding: FactorialFactory): Factorial {
    return function actualFactorial(n: number): number {
      if (n === 0) {
        return 1;
      }
      const factorialBinding = factorialFactoryBinding(factorialFactoryBinding);

      return n * factorialBinding(n - 1);
    }
  }
)

Look at it go!

tsconsole.log(factorial(0)) // => 1
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => 6
console.log(factorial(4)) // => 24
console.log(factorial(5)) // => 120

The applicative Y-Combinator

Pay attention, because this is the hard part. Right now we have achieved recursion, but our implementation is really tied to the factorial business. Our goal now is to generalise this closure-recursion technique to any function.

Let's change our types first to make them more agnostic:

ts// Any function from an input to an output
type Fn<I, O> = (input: I) => O

// Any factory function
type Factory<T> = (factoryBinding: Factory<T>) => T;

// The recursive implementation of our factory
function factory<I, O>(factoryBinding: Factory<Fn<I, O>>): Fn<I, O> {
  return factoryBinding(factoryBinding);
}

Now, our goal is to be able to use a "super factory" function, let's name it $Y$ , that given any function Fn<I, O>, is able to give us back a recursive version of the same function.

This is the API we are looking for:

tstype Factorial = Fn<number, number>;

const factorial = Y(function(factorialBinding: Factorial) {
  return function actualFactorial(n: number): number {
    if (n === 0) {
      return 1;
    }
    return n * factorialBinding(n - 1);
  }
})

Knowing this, implementing it is just a matter of making the types match:

tsfunction Y<I, O>(fnFactory: (binding: Fn<I, O>) => Fn<I, O>): Fn<I, O> {
  return factory(
    function actualFactory(factoryBinding: Factory<Fn<I, O>>): Fn<I, O> {
      const binding = factory(factoryBinding);
      return fnFactory(binding);
    }
  )
}

Well, there's a problem with that implementation, its recursion is eager, so we need to make it lazy again if want it to be useful:

tsfunction Y<I, O>(fnFactory: (binding: Fn<I, O>) => Fn<I, O>): Fn<I, O> {
  return factory(
    function actualFactory(factoryBinding: Factory<Fn<I, O>>): Fn<I, O> {
      return function(input: I): O {
        const binding = factory(factoryBinding);
        const fn = fnFactory(binding);

        return fn(input);
      };
    }
  )
}

console.log(factorial(0)) // => 1
console.log(factorial(1)) // => 1
console.log(factorial(2)) // => 2
console.log(factorial(3)) // => 6
console.log(factorial(4)) // => 24
console.log(factorial(5)) // => 120

And that, is the applicative Y-Combinator which we can use to make any function recurse, not just factorial.

jsconst factorial = Y(factorial => n => {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
})

const fibonacci = Y(fibonacci => n => {
  if (n <= 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
})

The Z-Combinator

You may wonder our insistence in using the applicative adjetive. The reason is that Lambda Calculus syntax for the Y-Combinator is:

$Y = \lambda f.(\lambda x.f (x x)) (\lambda x.f (x x))$

Very diferent from our definition which looks like this in compact form:

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

The reason is the Y-Combinator just won't work in languages with applicative or strict order of evaluation (see Evaluation Orders)

This applicative property of the Y-Combinator is also known by the Z-Combinator.

Conclusion

The Y-Combinator is one those things in lambda calculus and computer science that epitomises how math can be both beautiful and surprising. It allows us to make functions that can call themselves in a neat, clever way. Moreover, any programming language with lexical-closures/function-closures can be used to implement the Y-Combinator. This fact shows us how closely linked math and modern computer languages can be.

References

As with many constructs in mathematical logic and computer science, the origins of much can be found in combinatory logic Fixed-point combinator
Splending talk by Jim Weirich (RIP): Y Not- Adventures in Functional Programming
The Little Schemer
Some background on Lambda Calculus

Y-Combinator