To Grok a Mockingbird

Using recursive combinators to enhance functional composition, with special guests the Mockingbird, Widowbird, and Why Bird

In this essay we’re going to look at recursive combinators. A recursive combinator is a function that takes another function that is not recursive, and returns a function that is recursive. Recursive combinators make it possible to create recursive functions that are not tightly coupled to themselves.

Recursive combinators have important theoretical implications, but for the working programmer they decouple recursive functions from the mechanism that implements recursion. This makes it easier to compose recursive functions with decorators and to implement recursion strategies like trampolining.

We’ll begin our exploration with a look at the mockingbird, also called the M Combinator.¹ We’ll then move on to examine the widowbird, a combinator that executes tail-recursive functions in constant space. We’ll finish with a brief look at the famous Why Bird, or Y Combinator.

recursion and binding

As the number of people discussing recursion in an online forum increases, the probability that someone will quote the definition for recursion as Recursion: see ‘recursion’, approaches one.

This is a function that computes exponentiation. If we want to compute something like 2^8 (two to the power of eight), we can compute it like this: 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2, which requires O(n) operations. Our function exploits basic arithmetic and recursion to obtain the same result in O(log2n) operations:²

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

Question: How does our exponent function actually perform recursion? The immediate answer is, “It calls itself when the work to be performed is not the base case” (the base case for exponentiation is an exponent of 0 or 1).

How does it call itself? Well, when we have a function declaration (like above), or a named function expression, the function is bound to its own name within the body of the function automatically.

So within the body of the exponent function, the function itself is bound to the name exponent, and that’s what it calls. This is obvious to most programmers, and it’s how we nearly always implement recursion.

But it’s not always exactly what we want. If we want even more performance, we might consider memoizing the function.

Here’s a memoization decorator, snarfed from Time, Space, and Life As We Know 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));
  }
};

We can make a memoized version of our exponent function:

const mExponent = memoized(exponent);

mExponent(2, 8)
  //=> 256, performs three multiplications
mExponent(2, 8)
  //=> 256, returns the memoized result without further multiplications

There is a hitch with this solution: Although we are invoking mExponent, internally exponent is invoking itself directly, without memoization. So if we write:

const mExponent = memoized(exponent);

mExponent(2, 8)
  //=> 256, performs three multiplications
mExponent(2, 9)
  //=> 512, performs four multiplications

When we invoke exponent(2, 8), we also end up invoking exponent(4, 4), exponent(16, 2), and exponent(256, 1). We want those memoized. That way, when we invoke exponent(2, 9), and it invoked exponent(4, 4), the result is memoized and it need do no further computation.

Our problem here is that exponent is “hard-wired” to call exponent, not mExponent. So it never invoked the memoized version of the function.

We can work around that like this:

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

mExponent(2, 8)
  //=> 256, performs three multiplications
mExponent(2, 9)
  //=> 512, performs only one multiplication

In many cases this is fine. But conceptually, writing it this way means that our exponent function needs to know whether it is memoized or not. This runs counter to our “Allongé” style of writing things that can be composed without them needing to know anything about each other.

For example, if we wanted a non-memoized exponentiation function, we’d have to duplicate all of the code, with a minor variation:

const 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);
  }
};

That is not composing things, at all. What we want is to have one exponentiation function, and find a way to use it with or without decoration (such as with or without memoization). And we can do this.

composeable recursive functions

The sticking point is that to have full memoization, our exponentiation function needs to have a hard-coded reference to the memoized version of itself, which means it can’t be used without memoization. This is a specific case of a more general problem where things that have hard-coded references to each other become tightly coupled, and are thus difficult to compose in different ways. Only in this case, we’ve made the thing tightly coupled to itself!

So let’s attack the hard-coded reference problem, decoupling our recursive function from itself. Since it doesn’t have to be a named function, we can make it a “fat arrow” expression. If we want a function to have a reference to another function in JavaScript, we can pass it in as a parameter. So the ‘signature’ for our new function expression will look like this:

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

In this case, our function assumes that myself is going to be bound to the function itself. Now what about the body of the function? We can change exponent to myself:

(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);
  }
};

One little hitch: Our function signature is (myself, x, n), but when we invoke myself, we’re only passing in x and n. So we can pass myself in as well:

(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);
  }
};

Now this seems very contrived, and it doesn’t even work yet. How can we make it work?

the mockingbird

Behold, the JavaScript mockingbird:

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

The mockingbird is a function that takes another function, and returns a function. That function takes a bunch or arguments, and invoked the original function with itself and the arguments.³

So now we can write:

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);
  }
})(2, 8)
  //=> 256

That is all very well and good, but we’ve added some extra bookkeeping. Do we have any wins? Let’s try composing it with the memoization function. Although we didn’t use it above, our memoize function does allow us to customize the function used to create a key. Here’s a key making function that deliberately ignores the first argument:

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

And now we can create a memoized version of our anonymous function. First, here it is step-by-step:

const _exponent = (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);
  }
};

mockingbird(memoized(_exponent, ignoreFirst))(2, 8)
  //=> 256

But now for the big question: Does it memoize everything? Let’s test it:

const mExponent = mockingbird(memoized(_exponent, ignoreFirst));

mExponent(2, 8)
  //=> 256, performs three multiplications
mExponent(2, 9)
  //=> 512, performs only one multiplication

Yes it does properly memoize everything. And best of all, our function need have absolutely NO reference to the name of our memoized function. It doesn’t know whether it’s memoized or not.⁴

Because we’ve separated the function from the mockingbird that implements recursion, we can compose our exponentiation function with memoization or not as we see fit. When the exponentiation function was responsible for directly calling itself, if we wanted one version memoized and one not, we’d have to write two nearly identical versions of the same code.

But with the mockingbird separating how a function calls itself from the function, we can now write:

const _exponent = (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);
  }
};

const mExponent = mockingbird(memoized(_exponent, ignoreFirst));
const exponent = mockingbird(_exponent);

We have our composeability and reuse!

tail recursion

Here’s a function that determines whether a whole number is even (true) or odd (false).

It is highly pessimum, and its use of recursion is completely gratuitous. But we’ll experiment with it, as it provides a good demonstration of the perils of deeply recursive functions:

const isEven =
  n => {
    if (n === 0) {
      return true;
    } else {
      return !isEven(n - 1);
    }
  };

isEven(47)
  //=> false

For any number n, this function makes n recursive calls. So, what happens if we write:

isEven(1000000)

We know the answer is true, but will it actually return at all? No. For technical reasons, JavaScript engines place a hard limit on the maximum depth of the call stack. Meaning, if too many function calls are nested–including recursive calls–we get Maximum call stack size exceeded.

One fix for this is to rewrite the function in tail-recursive form, and then allow the engine to automatically execute the function without consuming excess stack space. Here it is again, with its recursive call “in tail position:”⁵

const isEven =
  (n, parity = 0) => {
    if (n === 0) {
      return parity === 0;
    } else {
      return isEven(n - 1, 1 - parity);
    }
  };

isEven(42)
  //=> true

This code works just fine on the Safari browser, which in addition to being far more thrifty with battery life on OS X and iOS devices, implements Tail Call Optimization, as specified in the JavaScript standard. Alas, most other implementations refuse to implement TCO.

There’s a workaround for engines that don’t support TCO: As discussed in Trampolines in JavaScript, we can get around the call stack problem ourselves with a technique called trampolining:

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

Like our mockingbird, the trampoline pattern separates the code into a function that defines the work to be done, and a trampoline function that calls the recursive function. The trampoline function checks the function’s return value. If it’s a thunk, the trampoline evaluates the thunk, usually invoking the function again. Since the recursive function always returns before evaluating the next call, the stack does not grow.

Here’s the simplest trampoline good enough to criticize. Unlike approaches that rely on returning functions for thunks instead of a class, this works for functions that are supposed to return functions.

We include a version of isEven designed to work with it:

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

This works, but suffers from the recursive sins that our mockingbird fixed. The isEven function is coupled to itself, and it is coupled to the implementation of trampolining. Why should it know what a Thunk is?

a new kind of passerine science

A mockingbird cannot directly solve our problem, but we can learn from the mockingbird to write a new kind of trampolining function based on the mockingbird. We start by rewriting our isEven function in both tail-recursive and decoupled form.

Note that this works just fine with our mockingbird:

const _isEven =
  (myself, n, parity = 0) => {
    if (n === 0) {
      return parity === 0;
    } else {
      return myself(myself, n - 1, 1 - parity);
    }
  };

mockingbird(_isEven)(1001)
  //=> false

Now we’ve decoupled the form of the function from the mechanism of recursion. So, let’s swap the mechanism of recursion for a trampoline without altering the recursive function to suit the new implementation.

We’ll call our new “combinator” a Jackson’s Widowbird:⁶

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

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

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

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

      return value;
    };
  };

widowbird(_isEven)(1001)
  //=> false

Since we’re passing the function to be called recursively into our recursive function, we can place the thunk mechanism in our widowbird, instead of in the recursive function. Thus, the recursive function is completely decoupled from the mechanism for recursing without consuming the stack.

And what about our naive exponentiation that broke the stack earlier?

widowbird(_isEven)(1000000)
  //=> true

It works just fine, even on engines that don’t support tail call optimization. The widowbird has shown us another benefit of separating the recursive computation to be done from the mechanism for performing the recursion.⁷

the why bird

The mockingbird has the advantage of being the very simplest recursive combinator. But it can be enhanced. One of the annoying things about it is that when we write our functions to use with a mockingbird, not only do we need a myself parameter, but we need to remember to pass it on as well.

This isn’t a bad tradeoff, but logicians searched for a combinator that could implement recursion with a parameter, like the mockingbird, but avoid having to pass that parameter on. This had important theoretical consequences, but for us, the value of such a combinator is that the functions we write are more natural.

The combinator that decouples recursion using a parameter, but doesn’t require passing that parameter along, is called the Y Combinator.

A compact JavaScript implementation looks like this:

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

Without getting into exactly how it works, we can see that the disadvantage of the Y combinator is that it assumes that all functions are curried to take only one argument.⁸

Here’s an idiomatic JavaScript version, called the Why Bird. It handles functions with more than one argument:

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

Armed with our why bird, we can write recursive functions that look a little more idiomatic. This implementation of map is gratuitously recursive, but demonstrates that using the why bird, we need not pass myself along when map calls itself recursively:

const _map =
  (myself, fn, input) => {
    if (input.length === 0) {
      return [];
    } else {
      const [first, ...rest] = input;

      return [fn(first)].concat(myself(fn, rest));
    }
  };

why(_map)(x => x * x, [1, 2, 3])
  //=> [1, 4, 9]

No more myself(myself, ...)!

The why bird makes the code we write much simpler. And like the mockingbird, it allows us to separate the mechanism for recursion from the function we wish to make recursive.

(We look at how to derive the Why bird and Y combinator from the Mockingbird and M combinator in the literally named Why Y? Deriving the Y Combinator in JavaScript)

summary

In summary, the mockingbird is a recursive combinator: It takes a function that is not directly recursive, and makes it recursive by passing the subject function to itself as a parameter. This has the effect of removing a hard-coded dependency between the subject function and itself, which allows us to decorate it with functionality like memoization.

We’ve also seen that having performed this separation, we can swap the mockingbird out for other functions implementing recursion, such as the widowbird. We’ve seen that the widowbird is superior to other approaches, because it does not require the function being trampolined to “know” that it is being trampolined.

And finally, we saw the why bird, or Y Combinator. We saw that it makes our functions a little more idiomatic, and once again delivers the value of separating function from recursion mechanism.

Recursive combinators like mockingbirds, widowbirds, and why birds are a few more tools in our “composeable functions” toolbox, increasing reuse by decoupling recursive functions from themselves.

(discuss on reddit here, or here, or on hacker news)

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