Road to the Y Combinator, Part III

03.04.2023 — Code — 5 min read

In Part II, we covered some essential functional refactorings. In this chapter, we'll apply those refactorings to implement Factorial in lambdas (pure, anonymous functions).

Make it Work

Recall our starting point, a recursive Factorial function that isn't yet free of names from the outside scope:

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

This is good, as it clearly communicates:

when n === 0, the return value is n
when n > 0, the return value is n * factorial(n - 1)

But we have set out to program in the style of the Lambda Calculus. We can't use any names, except function arguments. Let's yeet that factorial reference!

Maybe we can make a function that takes a factImprover, and use it to construct Factorial:

const makeFact = factImprover => n =>
    n === 0 ? n :
        n * factImprover(n - 1)

Unfortunately this won't work. The function returned by makeFact is a Factorial function for the case
n === 0, no matter what is passed for factImprover. But for the Factorial of 5, it would yield 5 * factImprover(4).

In other words, makeFact isn't getting us anywhere, since it requires a full Factorial function to make it work! Let's see if we can handle more cases with some manual plumbing. Make an improver:

const improver = partial => n =>
    n === 0 ? n : n * partial(n - 1);

This takes a partial definition of Factorial and improves it by a single step.

Let's pass a function error to let us know when we have hit the end of the road:

const error = _ => {
    throw new Error('error WAS CALLED!!!');
};

const f0 = improver(error);

Now f0 is a partial solution which handles arguments up to 0. Confirm that it works:

> f0(0)
1

Running the recursive case results in an Error:

> f0(1)
Uncaught Error: error WAS CALLED!!!
...

We can handle even larger values of N:

const f1 = improver(f0);
const f2 = improver(f1);
const f3 = improver(f2);
console.log(f3(3));

resulting in:

as expected.

We can inline the value of f3 and remove the line that defines it:

const f1 = improver(f0);
const f2 = improver(f1);
console.log(improver(f2)(3));

Likewise we can inline f2, then f1, and f0, to achieve something like this:

console.log(improver(improver(improver(improver(error))))(3));

which still works:

This works, but is kind of clunky. We should be able to calculate the Factorial of 10, but we'd have to inline 11 calls to improver to make that work.

Instead, let's assign the improver call chain to a new function fx, which is a partial solution. Our code could look like this:

const error = _ => {
    throw new Error('error WAS CALLED!!!');
};

const improver = partial => n =>
    n === 0 ? n : n * partial(n - 1);

const fx = improver(
    improver(
        improver(
            improver(error)
        )
    )
);

console.log(
    fx(3)
);

We need something that is going to do the wrapping for us. Change the design to a function which:

takes an improver
applies improver to itself

...and pass the previous definition of improver to it:

const fx = (
    improver => improver(improver(error))
)(
    partial =>
        n =>
            n === 0 ? 1 :
                n * partial(n - 1)
);

We can pass 0 or 1, but it still panics on 2:

> fx(2)
Uncaught Error: error WAS CALLED!
...

However, we can call improver on itself and skip error:

const fx = (
    improver => improver(improver)
)(
    partial =>
        n =>
            n === 0 ? 1 :
                n * partial(n - 1)
);

The Node repl shows we can calculate f(0):

> fx(0)
1

But if we try fx(1), we get NaNNers! 🦝 🍌

> fx(1)
NaN

Let's fix our NaNNers with a proper error message. BigInt will do. It behaves like a normal integer Number in Javascript, except:

all arithmetic must be performed with BigInt operands only
BigInt's can be as big as we want them to

To change our number literals to BigInt, we must postfix n to the number, like this:

1n

When Node echoes a BigInt value in the repl, it will have an n at the end. Our code will now look like this:

const error = _ => {
    throw new Error('error WAS CALLED!!!');
};

const fx = (
    improver => improver(improver)
)(
    partial =>
        n =>
            n === 0n ? 1n :
                n * partial(n - 1n)
);
console.log(
    fx(1n)
);

If we run this, Node will now give us a TypeError:

TypeError: Cannot mix BigInt and other types, use explicit conversions
...

The key here is the TypeError telling us that our program attempted to do something with BigInt and another type.

Let's do a rename on partial to make it obvious it is the value of improver:

const fx = (
    improver => improver(improver)
)(
    improver =>
        n =>
            n === 0n ? 1n :
                n * improver(n - 1n)
);

This function that takes an improver calls it, passing it as an argument to itself. improver then is not a function that operates on BigInts, but a higher order function that operates on functions, that themselves operate BigInts. To get back a function that operates on BigInts, we have to call improver on itself:

const fx = (
    improver => improver(improver)
)(
    improver =>
        n =>
            n === 0n ? 1n :
                n * improver(
                    improver
                )(n - 1n)
);

Test it in the repl:

> fx(1n)
1n
> fx(5n)
120n
> fx(100n)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000n

Yeehaaw! Now we can compute a recursive function without assignment. To prove it, we can inline and paste this into a fresh Node repl:

> ((
    improver => improver(improver)
)(
    improver =>
        n =>
            n === 0n ? 1n :
                n * improver(
                    improver
                )(n - 1n)
))(5n);
120n

It's amazing to see that we can do this without assignment!

Summary

In this episode we successfully implemented Factorial in pure, anonymous functions, with no names from the outside world.

In Part IV, we'll refactor to a design with the "recursive plumbing" in one function, and the Factorial knowledge in another.