Road to the Y Combinator, Part IV

04.04.2023 — Code — 6 min read

In Part III, we made Factorial using our functional style. In this part, we'll tease apart the two things hiding in our implementation:

a thing that can do recursion
a thing that can do Factorial in terms of recursion

Recall our implementation, here renamed fact:

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

This code is still silly. The first problem is that improver doesn't take an improver, but rather something that can generate a recursive function when it consumes itself.

The second is that there is a bunch of plumbing in the middle of our recursive definition:

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

Let's make this look like something we want to write, then pull it out.

Recover the Improver

Renaming improver to gen results in the following:

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

Wrap this function in a Tennent Function (so gen is in scope):

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

This gives us:

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

Now add a binding (remember, we're trying to extract those ugly plumbing bits). Call it code, and pass it our trusty error function:

const fact = (
    gen => gen(gen)
)(
    gen => (
        (code) =>
            n =>
                n === 0n ? 1n :
                    n * gen(
                       gen 
                    )(n - 1n)
    )(error)
);

That works. Let's pass in gen for code instead:

const fact = (
    gen => gen(gen)
)(
    gen => (
        (code) =>
            n =>
                n === 0n ? 1n :
                    n * gen(
                       gen 
                    )(n - 1n)
    )(gen)
);

It works:

> fact(5n);
120n

Now let's try gen(gen):

const fact = (
    gen => gen(gen)
)(
    gen => (
        (code) =>
            n =>
                n === 0n ? 1n :
                    n * gen(
                       gen 
                    )(n - 1n)
    )(
        gen(
            gen
        )
    )
);

If we enter the above code into the Node repl, we discover that we can't even create the fact function with this definition:

Uncaught RangeError: Maximum call stack size exceeded
...

Can you tell what the problem is? Previously, gen(gen) would not be called for the base case, but only when there was more work to do. Now the recursion is not stopping until we overflow the stack.

Just like any true slacker will tell you, when the going gets tough, the tough get lazy. Let's apply a function wrap to achieve laziness:

const fact = (
    gen => gen(gen)
)(
    gen => (
        (code) =>
            n =>
                n === 0n ? 1n :
                    n * gen(
                       gen 
                    )(n - 1n)
    )(
        v =>
            gen(
                gen
            )(v)
     )
);

Type this at the repl, and you'll discover we're back in action!

fact(5n)
120n

Note that for the moment, our lazy version of gen(gen) isn't being used yet. We need to apply our wrapping function to the other gen(gen) too:

const fact = (
    gen => gen(gen)
)(
    gen => (
        (code) =>
            n =>
                n === 0n ? 1n :
                    n * (
                        v =>
                            gen(
                                gen 
                            )(v)
                    )(n - 1n)
    )(
        v =>
            gen(
                gen
            )(v)
    )
);

Now this is podracing! Those recursive plumbing bits look just like our argument to code! Let's substitute:

const fact = (
    gen => gen(gen)
)(
    gen => (
        (code) =>
            n =>
                n === 0n ? 1n :
                    n * code(n - 1n)
    )(
        v =>
            gen(
                gen
            )(v)
    )
);

Since we want to end up with our improver function, lets rename code to partial:

const fact = (
    gen => gen(gen)
)(
    gen => (
        (partial) =>
            n =>
                n === 0n ? 1n :
                    n * partial(n - 1n)
    )(
        v =>
            gen(
                gen
            )(v)
    )
);

And voila, now we have the improver in our desired form!

Pull out Improver

Let's pull this sucker out. Wrap the whole expression in a Tennent Function:

const fact = (
    () =>
        (
            gen => gen(gen)
        )(
            gen => (
                (partial) =>
                    n =>
                        n === 0n ? 1n :
                            n * partial(
                                n - 1n
                            )
            )(
                v =>
                    gen(
                        gen
                    )(v)
            )
        )
)();

We'll follow that up with a new binding, code and error as before:

const fact = (
    (code) =>
        (
            gen => gen(gen)
        )(
            gen => (
                (partial) =>
                    n =>
                        n === 0n ? 1n :
                            n * partial(
                                n - 1n
                            )
            )(
                v =>
                    gen(
                        gen
                    )(v)
            )
        )
)(error);

Replace error with the improver definition:

const fact = (
    (code) =>
        (
            gen => gen(gen)
        )(
            gen => (
                (partial) =>
                    n =>
                        n === 0n ? 1n :
                            n * partial(
                                n - 1n
                            )
            )(
                v =>
                    gen(
                        gen
                    )(v)
            )
        )
)(
    (partial) =>
        n =>
            n === 0n ? 1n :
                n * partial(
                    n - 1n
                )
);

Now code has the same value as the expression we just copied, so let's substitute:

const fact = (
    (code) =>
        (
            gen => gen(gen)
        )(
            gen =>
                code(
                    v =>
                        gen(
                            gen
                        )(v)
                )
        )
)(
    (partial) =>
        n =>
            n === 0n ? 1n :
                n * partial(
                    n - 1n
                )
);

Rename:

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

Extract our improver like so:

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

const fact = (
    (improver) =>
        (
            gen => gen(gen)
        )(
            gen =>
                improver(
                    v =>
                        gen(
                            gen
                        )(v)
                )
        )
)(factImprover);

Similarly, we can pull out the expression called with factImprover. We'll call it y:

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

const y = (improver) => (
    gen => gen(gen)
)(
    gen =>
        improver(
            v =>
                gen(
                    gen
                )(v)
        )
);
const fact = y(factImprover);

...and that's it. We found the Y Combinator!

Summary

We have almost solved the puzzle. We found our prize, but it looks weird, like a baby Pokemon.

In Part V, we'll see this creature in its final form, and look at what this exercise has taught us about functional programming.