Road to the Y Combinator, Part I

01.04.2023 — Code, Functional — 4 min read

Be Anonymous

Ever since I first learned Lisp, assisted by lectures from Gerald Sussman and Harold Ableson, I have been interested in the Lambda Calculus. For the uninitiated, the Lambda Calculus is a model of computation and a macro expansion language.

Everything that is considered effectively computable can be computed in the Lambda Calculus. A synonym you may have heard is Turing-complete. While Turing's model for computation, the Turing Machine is the more famous of the two, I think Church's Lambda Calculus is interesting for the following reasons:

it was published first
it is a more natural form for computer programs
it demonstrates the power of the function

The last two points are about applicability. As a programmer who aims to leverage the state of the art in software craftsmanship, the ability to apply what I learn is of utmost importance. In this spirit, we'll take a tour of functional refactorings, and apply them to derive the Y Combinator from first principles.

Instead of plunging head-over-heels into the Lambda Calculus syntax, we can introduce a limted set of JS constructs to program in a lambda style. In the Lambda Calculus, nothing is ever changed. We can substitute a value for any occurrence of its name in the process of evaluation. This won't work in typical JS style:

((foo) => {
    let bar = foo;
    foo = 2;
    bar = bar + foo;
    foo = 3;
    bar = bar * foo;
    return bar;
})(1);

Running this in the Node repl results in:

The above code evaluates to the value 9. If we substituted 1 for every occurrence of foo which is used for a value in the function body, we would get this:

((foo) => {
    let bar = 1;
    foo = 2;
    bar = bar + 1;
    foo = 3;
    bar = bar * 1;
    return bar;
})(1);

The result being:

By introducing assignment, we have added a dependency on time. During the evaluation of the function body, the value of foo depends on how "far" down we are; each assignment to foo changes its value.

For this exploration, assignment is out. The only way we are allowed to bind a value bound to a name is through the application of anonymous functions. In JS, anonymous functions can take a few forms:

The function expression:

(
    function() {
        return 1;
    }
)

This is wrapped in parentheses, which are necessary to inform the parser that a function expression is intended, otherwise the code would result in a SyntaxError. The function returns a value, so that the result can be "seen" by the caller.

The arrow function expression:

() => {
    return 1;
};

Other than being a few characters shorter, this looks the same. There are other differences, but nothing that will affect this exercise.

The arrow function expression with a single expression return value:

() => 1

We'll use this form because it is terse, and we have no need for statements.

Setting the Stage

The goal is to write a recursive program in pure, anonymous functions. We can get away with using Javascript if we avoid mutation. Usually this would be considered a fine use of functional style:

const factorial = (n) => {
    return n === 0 ? 1 :
        n * factorial(n - 1);
}

However, the function uses a value that was bound in the parent scope. We have to yeet this code, since in the Lambda Calculus we can only reference names which are arguments to anonymous functions.

Our goal then, is to transform this recursive function above into a form that has two distinct parts:

A function that knows how to do the plumbing for recursion in this context
A function that, given a partial solution of Factorial, will improve it by one step

Factorial Definition

Let f be a function that computes the Factorial of N, a positive integer. Then f(N) is defined to be:

1 if N is 0
N * Factorial of N - 1 otherwise

Examples

f(1) is 1 * f(0), which is 1 * 1, or 1
f(2) is 2 * f(1), which is 2 * 1 * f(0), yielding 2 * 1 * 1, or 2
f(3) is 3 * 2 * 1 * 1, which works out to 6

Note that f(3) is 3 * 2 * 1 * 1, which is 3 * (2 * 1 * 1), or 3 * f(2).
In general, f(n) is n * f(n - 1), which is where we get our recursive definition for Factorial.

What's Next

In the next part, we'll learn some functional refactorings that will help us on our way to derive the Y Combinator.