Why Y? Deriving the Y Combinator in JavaScript

…and two practical applications…

The Y Combinator is an important result in theoretical computer science.¹

In this essay, after a brief review of the work we’ve already done on the Mockingbird, we’ll derive the Why Bird, known most famously as the Y Combinator. The why bird provides all the benefits of the mockingbird, but allows us to write more idiomatic JavaScript. We’ll see that one of the benefits of writing recursive functions in “why bird form” is that we can compose and decorate them easily.

We’ll then derive the “Decoupled Trampoline,” a/k/a “Long-Tailed Widowbird.” The decoupled trampoline builds on the why bird and Y Combinator to allow us to write tail-recursive functions that execute in constant stack space, while hewing closely to idiomatic JavaScript.

While this use case is admittedly rare in production code, it does arise from time to time and it is pleasing to contemplate a direct connection between one of programming’s most cerebrally theoretical constructs, and a tool for overcoming the limitations of today’s JavaScript implementations.

Preamble: Revisiting the mockingbird

To review what we saw in To Grok a Mockingbird, a typical recursive function calls itself by name, like this:²

function exponent (x, n) {
  if (n === 0) {
    return 1;
  } else if (n % 2 === 1) {
    return x * exponent(x * x, Math.floor(n / 2));
  } else {
    return exponent(x * x, n / 2);
  }
}

exponent(2, 7)
  //=> 128

Because it calls itself by name, it is tightly coupled to itself. This means that if we want to decorate it–such as by memoizing its return values, or if we want to change its implementation strategy–like employing trampolining–we have to rewrite the function.

We saw that we can decouple a recursive function from itself. Instead of calling itself by name, we arrange to pass the recursive function to itself as a parameter. We begin by rewriting our function to take itself as a parameter, and also to pass itself as a parameter.

We call that writing a recursive function in mockingbird form. It looks like this:

(myself, x, n) => {
  if (n === 0) {
    return 1;
  } else if (n % 2 === 1) {
    return x * myself(myself, x * x, Math.floor(n / 2));
  } else {
    return myself(myself, x * x, n / 2);
  }
};

Given a function written in mockingbird form, we use a JavaScript implementation of the mockingbird to turn it into a recursive function:³

const mockingbird =
  fn =>
    (...args) =>
      fn(fn, ...args);

const exponent =
  mockingbird(
    (myself, x, n) => {
      if (n === 0) {
        return 1;
      } else if (n % 2 === 1) {
        return x * myself(myself, x * x, Math.floor(n / 2));
      } else {
        return myself(myself, x * x, n / 2);
      }
    }
  );

exponent(3, 3)
  //=> 27

Because the recursive function has been decoupled from itself, we can do things like memoize it:

const memoized = (fn, keymaker = JSON.stringify) => {
  const lookupTable = Object.create(null);

  return function (...args) {
    const key = keymaker.call(this, args);

    return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
  }
};

const ignoreFirst = ([_, ...values]) => JSON.stringify(values);

const exponent =
  mockingbird(
    memoized(
      (myself, x, n) => {
        if (n === 0) {
          return 1;
        } else if (n % 2 === 1) {
          return x * myself(myself, x * x, Math.floor(n / 2));
        } else {
          return myself(myself, x * x, n / 2);
        }
      },
      ignoreFirst
    )
  );

Memoizing our recursive function does not require any changes to its code. We can easily reuse it elsewhere if we wish.

why the mockingbird needs improvement

The mockingbird is a useful tool, but it has a drawback: In addition to rewriting our functions to take themselves as a parameter, we also have to rewrite them to pass themselves along. So in addition to this:

(myself, x, n) => ...

We must also write this:

myself(myself, x * x, n / 2)

The former is the point of decoupling. The latter is nonsense!

The idea behind the way we use the mockingbird (as opposed to a literal interpretation of the M combinator) is to write idiomatic JavaScript. But there’s nothing “idiomatic” about a function invoking itself with myself(myself, ...).

What we want is a function like the mockingbird, but it must support functions calling themselves idiomatically, e.g. myself(x * x, n / 2).

Let’s visualize exactly what we want. With the mockingbird, we write:

const exponent =
  mockingbird(
    (myself, x, n) => {
      if (n === 0) {
        return 1;
      } else if (n % 2 === 1) {
        return x * myself(myself, x * x, Math.floor(n / 2));
      } else {
        return myself(myself, x * x, n / 2);
      }
    }
  );

We want a better recursive combinator, one that lets us write:

const exponent =
  _____(
    (myself, x, n) => {
      if (n === 0) {
        return 1;
      } else if (n % 2 === 1) {
        return x * myself(x * x, Math.floor(n / 2));
      } else {
        return myself(x * x, n / 2);
      }
    }
  );

Let’s build that!

Part I: Deriving the Y Combinator from the Mockingbird

Before we begin, there are some rules we have to follow if we are to take the mockingbird and derive another combinator from it. Every combinator has the following properties:

1. It is a function.
2. It can only use its parameters or previously defined combinators that have these same properties. This means it cannot refer to non-combinators, like constants, ordinary functions, or object from the global namespace.
3. It cannot be a named function declaration or named function expression.
4. It cannot create a named function expression.
5. It cannot declare any bindings other than via parameters.
6. It can invoke a function in its implementation.

In combinatory logic, all combinators take exactly one parameter, as do all of the functions that combinators create. Combinatory logic also eschews all gathering and spreading of parameters. When creating an idiomatic JavaScript combinator (like mockingbird), we eschew these limitations. Idiomatic JavaScript combinators can:

• Gather parameters, and;
• Spread parameters.

from mockingbird to why bird in seven easy pieces

Step Zero: We begin with the mockingbird:

const mockingbird =
  fn =>
    (...args) =>
      fn(fn, ...args);

Step One, we name our combinator. Honouring Raymond Smullyan’s choice, we shall call it the why bird:

const why =
  fn =>
    (...args) =>
      fn(fn, ...args);

Step Two, we identify the key change we have to make:

const why =
  fn =>
    (...args) =>
      fn(?, ...args);

We’ve replaced that one fn with a placeholder. Why? Well, our fn is a function that looks like this: (myself, arg0, arg1, ..., argn) => .... But whatever we pass in for myself will look like this: (arg0, arg1, ..., argn) => .... So it can’t be fn.

But what will it be?

Well, the approach we are going to take is to think about the mockingbird. What does it do? It takes a function like (myself, arg0, arg1, ..., argn) => ..., and returns a function that looks like (arg0, arg1, ..., argn) => ....

The mockingbird isn’t what we want, but let’s airily assume that there is such a function. We’ll call it maker, because it makes the function we want.

Step Three, we replace ? with maker(??). We know it will make the function we want, but we don’t yet know what we must pass to it:

const why =
  fn =>
    (...args) =>
      fn(maker(??), ...args);

This leaves us two things to figure out:

1. Where do we get maker, and;
2. What parameter(s) do we pass to it.

For 1, we could define maker as an anonymous function expression. Another option arises. In the days before ES6, if we wanted to define variables within a scope smaller than a function, we created an immediately invoked function expression.

Step Four, we could, after some experimentation, consider this format that binds a function expression to maker with an immediately invoked function expression;

const why =
  fn =>
    (
      maker =>
        (...args) =>
          fn(maker(??), ...args)
    )(???);

This still leaves us two things to work out: ?? is what we pass to maker, and ??? is maker’s expression. Here’s the “Eureka!” moment:

maker is a function that takes one or more parameters and returns a function that looks like (...args) => fn(maker(??), ...args). That’s the function we want to pass to fn as myself. The mockingbird isn’t such a function, but we can see one right in front of us:

maker => (...args) => fn(maker(??), ...args) is a function that takes one parameter(maker) and returns a function that looks like (...args) => fn(maker(??), ...args)!

Step Five, let’s fill that in for ???:

const why =
  fn =>
    (
      maker =>
        (...args) =>
          fn(maker(??), ...args)
    )(
      maker =>
        (...args) =>
          fn(maker(??), ...args)
    );

Now what about ??? Well, we have just decided two things:

1. maker takes one or more parameters and returns a function that looks like (...args) => fn(maker(??), ...args), and;
2. maker => (...args) => fn(maker(??), ...args) is a function that takes one parameter(maker) and returns a function that looks like (...args) => fn(maker(??), ...args).

Conclusion: maker takes one parameter, maker, and returns a function that looks like (...args) => fn(maker(??), ...args). Therefore, the expression we want is maker(maker), and ?? is nothing more than maker!

Step Six:

const why =
  fn =>
    (
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    )(
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    );

Let’s test it:

const exponent =
  why(
    (myself, x, n) => {
      if (n === 0) {
        return 1;
      } else if (n % 2 === 1) {
        return x * myself(x * x, Math.floor(n / 2));
      } else {
        return myself(x * x, n / 2);
      }
    }
  );

exponent(2, 9)
  //=> 512

Voila! A working why bird!!

from why bird to y combinator

Our why bird is written in–and for–idiomatic JavaScript, especially with respect to employing functions that take more than one parameter. A direct implementation of a formal combinator only takes one parameter and only works with functions that take one parameter.

We can translate our why bird to its formal combinator, the y combinator. To aid us, let’s first imagine a recursive function:

const isEven =
  n =>
    (n === 0) || !isEven(n - 1);

In why bird form, it becomes:

const _isEven =
  (myself, n) =>
    (n === 0) || !myself(n - 1);

Alas, it now takes two parameters. We fix this by currying it:

const __isEven =
  myself =>
    n =>
      (n === 0) || !myself(n - 1);

Instead of taking two parameters (myself and n), it is now a function taking one parameter, myself, and returning a function that takes another parameter, n.

To accommodate functions in this form, we take our why bird and perform some similar modifications. We’ll start as above by renaming it:

const Y =
  fn =>
    (
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    )(
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    );

Next, we observe that (...args) => fn(maker(maker), ...args) is not allowed, we do not gather and spread parameters. First, we change ...args into just arg, since only one parameter is allowed:

const Y =
  fn =>
    (
      maker =>
        arg => fn(maker(maker), arg)
    )(
      maker =>
        arg => fn(maker(maker), arg)
    );

fn(maker(maker), arg) is also not allowed, we do not pass two parameters to any function. Instead, we pass one parameter, get a function back, and pass the second parameter to that function. Like this:

const Y =
  fn =>
    (
      maker =>
        arg => fn(maker(maker))(arg)
    )(
      maker =>
        arg => fn(maker(maker))(arg)
    );

Let’s try it:

Y(
  myself =>
    n =>
      (n === 0) || !myself(n - 1)
)(1962)

It works too, and now we have derived one of the most important results in theoretical computer science. The Y Combinator matters deeply, because in the kind of formal computation models that are simple enough to prove results (like the Lambda Calculus and Combinatory Logic), we do not have any iterative constructs, and must use recursion for nearly everything non-trivial.⁴

The Y Combinator makes recursion possible without requiring variable declarations. As we showed above, we can even make an anonymous function recursive, which is necessary in systems where functions do not have names.⁵

if a forest contains a mockingbird, it also contains a why bird

Looking this expression of the Y combinator, we can see why it was named after the letter “Y,” the code literally looks like a forking branch:

const Y =
  fn =>
    (m => a => fn(m(m))(a))(
      m => a => fn(m(m))(a)
    );

Since we’re talking direct implementations of formal combinators, let’s have a look at the M combinator:

const M =
  fn => fn(fn);

We can combine M and Y to create a more compact expression of the Y combinator:

const Y =
  fn =>
    M(m => a => fn(m(m))(a));

The compact expression of the Y combinator is usually expressed with the M combinator “reduced” to (x => x(x)):

const Y =
  fn =>
    (x => x(x))(m => a => fn(m(m))(a));

We can use the reduced M combinator make a compact why bird, too:

const why =
  fn =>
    (x => x(x))(
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    );

And with that, we have derived compact implementations of both the Y combinator and its idiomatic JavaScript equivalent, the why bird, from our mockingbird implementation.

Part II: Two practical applications for the Y Combinator

This function for determining whether a number is even is extremely slow:

const _isEven =
  (myself, n) =>
    (n === 0) || !myself(n - 1);

const isEven = why(_isEven);

isEven(1000)
  //=> Go for coffee,
  //   then return to find out that the answer is `true`

isEven(1001)
  //=> Go for another coffee,
  //   then return to find out that the answer is `false`

As discussed in To Grok a Mockingbird, one of the things we can do to improve performance is to memoize our function:

const memoized = (fn, keymaker = JSON.stringify) => {
  const lookupTable = Object.create(null);

  return function (...args) {
    const key = keymaker.call(this, args);

    return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
  }
};

const ignoreFirst = ([_, ...values]) => JSON.stringify(values);

const isEvenFast = why(memoized(_isEven));

isEvenFast(1000)
  //=> Go for coffee,
  //   then return to find out that the answer is `true`

isEvenFast(1001)
  //=> false, immediately

Because the why bird decouples our _isEven function from itself, we can compose it with our memoized decorator or not as we see fit. Nothing in _isEven is coupled to whether we are memoizing the function or not.

Thus, the first benefit of functions written in “why bird form” is that they can be easily composed with decorators.⁶

trampolining tail-recursive functions

There’s another–albeit rarer–benefit to rewriting functions in why bird form. Consider this extreme use case:

why(
  (myself, n) =>
    (n === 0) || !myself(n - 1)
)(1000042)
  //=> Maximum call stack exceeded

Our function consumes stack space equal to the magnitude of the argument n. Naturally, this is a contrived example, but recursive functions that consume the entire stack to occur from time to time, and it is not always appropriate to rewrite them in iterative form.

One solution to this problem is to rewrite the function in tail-recursive form. If the JavaScript engine supports tail-call optimization, the function will execute in constant stack space:

// Safari Browser, c. 2018

why(
  (myself, n) => {
    if (n === 0)
      return true;
    else if (n === 1)
      return false;
    else return myself(n - 2);
  }
)(1000042)
  //=> true

However, not all engines support tail-call optimization, despite it being part of the JavaScript specification. If we wish to execute such a function in constant stack space, one of our options is to “greenspun” tail-call optimization ourselves by implementing a trampoline:⁷

A trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined, or in trampolined style; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail-recursive function calls in stack-oriented programming languages.–Wikipedia

As we saw in To Grok a Mockingbird, this necessitates having our recursive function become tightly coupled to its execution strategy. In other words, above and beyond being rewritten in tail-recursive form, it must explicitly return thunks rather than call myself:

class Thunk {
  constructor (delayed) {
    this.delayed = delayed;
  }

  evaluate () {
    return this.delayed();
  }
}

const trampoline =
  fn =>
    (...initialArgs) => {
      let value = fn(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };

const isEven =
  trampoline(
    function myself (n, parity = 0) {
      if (n === 0) {
        return parity === 0;
      } else {
        return new Thunk(() => myself(n - 1, 1 - parity));
      }
    }
  );

isEven(1000001)
  //=> false

In To Grok a Mockingbird, we solved this problem for functions written “in mockingbird form” with the Jackson’s Widowbird function. We created a function with the same contract as the mockingbird, but its implementation used a trampoline to execute recursive functions in constant stack space.

Functions written “in why bird form” are more idiomatically JavaScript than functions written in mockingbird form. If we can create a similar function that has the same contract as the why bird, but uses a trampoline to evaluate the recursive function, we could execute tail-recursive functions in constant stack space.

We will call this function the “Long-tailed Widowbird.” Let’s derive it.

deriving the long-tailed widowbird from the why bird

Our goal is to create a trampolining function. So let’s start with the basic outline of a trampoline, and call it longtailed:

class Thunk {
  constructor (delayed) {
    this.delayed = delayed;
  }

  evaluate () {
    return this.delayed();
  }
}

const longtailed =
  fn =>
    (...initialArgs) => {
      let value = fn(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };

We won’t even bother trying this, we know that fn(...initialArgs) is not going to work without injecting a function for myself. But we do know a function that we can call with ...initialArgs:

class Thunk {
  constructor (delayed) {
    this.delayed = delayed;
  }

  evaluate () {
    return this.delayed();
  }
}

const longtailed =
  fn =>
    (...initialArgs) => {
      let value = why(fn)(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };

This works, but never actually creates any thunks. To do that, let’s reduce why(fn):

class Thunk {
  constructor (delayed) {
    this.delayed = delayed;
  }

  evaluate () {
    return this.delayed();
  }
}

const longtailed =
  fn =>
    (...initialArgs) => {
      let value =
        (x => x(x))(
          maker =>
            (...args) =>
              fn(maker(maker), ...args)
        )(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };

Now we see where the value for myself comes from, it’s maker(maker). Let’s replace that with a function that, given some arguments, returns a new thunk that—when evaluated—returns maker(maker) invoked with those arguments:

class Thunk {
  constructor (delayed) {
    this.delayed = delayed;
  }

  evaluate () {
    return this.delayed();
  }
}

const longtailed =
  fn =>
    (...initialArgs) => {
      let value =
        (x => x(x))(
          maker =>
            (...args) =>
              fn((...argsmm) => new Thunk(() => maker(maker)(...argsmm)), ...args)
        )(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };

longtailed(
  (myself, n) => {
    if (n === 0)
      return true;
    else if (n === 1)
      return false;
    else return myself(n - 2);
  }
)(1000042)
  //=> true

It works! And it executes in constant stack space, as we wanted.⁸

from long-tailed widowbird to decoupled trampoline

The long-tailed widowbird works, but it is code that only its author could love.

Let’s begin our cleanup by moving Thunk inside our function. This has certain technical advantages if we ever create a recursive program that itself returns thunks. Since it is now a special-purpose class that only ever invokes a single function, we’ll give it a more specific implementation:

const longtailed =
  fn => {
    class Thunk {
      constructor (fn, ...args) {
        this.fn = fn;
        this.args = args;
      }

      evaluate () {
        return this.fn(...this.args);
      }
    }

    return (...initialArgs) => {
      let value =
        (x => x(x))(
          maker =>
            (...args) =>
              fn((...argsmm) => new Thunk(maker(maker), ...argsmm), ...args)
        )(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };
  };

Next, let’s extract the creation of a function that delays the invocation of maker(maker):

const longtailed =
  fn => {
    class Thunk {
      constructor (fn, ...args) {
        this.fn = fn;
        this.args = args;
      }

      evaluate () {
        return this.fn(...this.args);
      }
    }

    const thunkify =
      fn =>
        (...args) =>
          new Thunk(fn, ...args);

    return (...initialArgs) => {
      let value =
        (x => x(x))(
          maker =>
            (...args) =>
              fn(thunkify(maker(maker)), ...args)
        )(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };
  };

And now we have a considerably less ugly long-tailed widowbird. Well, actually, we are ignoring “the elephant in the room,” the name of the function. “Long-tailed Widowbird” is a touching tribute to the genius of Raymond Smullyan, and there is an amusing correlation between its long tail and the business of optimizing tail-recursive functions.

Nevertheless, if we are to work with others, we might want to consider the possibility that they would prefer a less poetic approach:

const decoupledTrampoline =
  fn => {
    class Thunk {
      constructor (fn, ...args) {
        this.fn = fn;
        this.args = args;
      }

      evaluate () {
        return this.fn(...this.args);
      }
    }

    const thunkify =
      fn =>
        (...args) =>
          new Thunk(fn, ...args);

    return (...initialArgs) => {
      let value =
        (x => x(x))(
          maker =>
            (...args) =>
              fn(thunkify(maker(maker)), ...args)
        )(...initialArgs);

      while (value instanceof Thunk) {
        value = value.evaluate();
      }

      return value;
    };
  };

And there we have our decoupled trampoline in its final form.

summary

The mockingbird that we explored in To Grok a Mockingbird is easy to understand, and decouples recursive functions from themselves. This provides us with more ways to compose recursive functions with other functions like decorators. However, it requires us to pass myself along when making recursive calls.

This is decidedly not idiomatic, so in Part I we derived the why bird, an idiomatic JavaScript recursive combinator that enables recursive functions to call themselves without any additional parameters. We then derived a JavaScript implementation of the Y combinator from the why bird, and finished by using a reduced version of the M combinator to produce “compact” implementations of both the why bird and the Y combinator.

In Part II, we revisited the need for optimizing tail-recursive recursive functions such that they operate in constant stack space. We derived the long-tailed widowbird from the why bird, then polished its implementation, naming the finished function the Decoupled Trampoline.

To recapitulate the use case for the decoupled trampoline, in the rare but nevertheless valid case where we wish to refactor a singly recursive function into a trampolined function to ensure that it does not consume the stack, we previously had to:

1. Refactor the function into tail-recursive form;
2. Refactor the tail-recursive version to explicitly invoke a trampoline;
3. Wrap the result in a trampoline function.

With the decoupled trampoline, we can:

1. Refactor the function into tail-recursive form;
2. Refactor the function into “why bird form,” then;
3. Wrap the result in the decoupled trampoline.

Why is this superior? We’re going to refactor into tail-recursive form either way, and we’re going to wrap the function either way, however:

1. Refactoring into “why bird form” is less intrusive than rewriting the code to explicitly return thunks, and;
2. The refactored code is decoupled from trampolining, so it is easier to reverse the procedure if need be, or even just used with the why bird;

If we compare and contrast:

const isEven =
  trampoline(
    function myself (n) {
      if (n === 0)
        return true;
      else if (n === 1)
        return false;
      else return new Thunk(() => myself(n - 2));
    }
  );

With:

const isEven =
  decoupledTrampoline(
    (myself, n) => {
      if (n === 0)
        return true;
      else if (n === 1)
        return false;
      else return myself(n - 2);
    }
  );

The latter has clearer separation of concerns and is thus easier to grok at first sight. And thus, we have articulated a practical (albeit infrequently needed) use for the Y Combinator.

That’s all!

(discuss on hacker news or reddit)

The essays in this series on recursive combinators are: To Grok a Mockingbird and Why Y? Deriving the Y Combinator in JavaScript. Enjoy them both!

Notes