This is an unpublished work. It contains errors and/or omissions. Please do not share it with others.
This essay has been incorporated into Why Y? Deriving the Y Combinator in JavaScript
The Y Combinator is an important result in theoretical computer science. A famous technology investment firm and startup incubator takes its name from the Y Combinator, likely because the Y Combinator acts as a kind of “bootstrap” to allow a function to build upon itself.
In this essay, after a brief review of the work we’ve already done on the Mockingbird, Why Bird, M Combinator, and Y Combinator, we’ll derive the “Decoupled Trampoline,” a/k/a “LongTailed Widowbird.” The decoupled trampoline builds on the why bird and Y Combinator to allow us to write tailrecursive functions that execute in constant stack space, while hewing closely to idomatic 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.
revisiting the why bird
This review of the why bird recapitulates the material from To Grok a Mockingbird and Deriving the Y Combinator and Why Bird from the Mockingbird. Readers familiar with these two essays can skim it quickly.
In To Grok a Mockingbird, we explored the mockingbird, a recursive combinator that decouples recursive functions from themselves. We explored how writing recursive functions “in mockingbird form” decreases couplingand helps us increase reuse and composition.^{1}
We then moved on to Deriving the Y Combinator and Why Bird from the Mockingbird, where we derived the Why Bird. Although it has tremendous application to combinatory logic as a fixed point combinator, our interest in the why bird was how it helps us obtain all of the benefits of the mockingbird, but we saw that functions written”in why bird form” were much closer to idiomatic JavaScript.
This is the compact expression of the why bird:
const why =
fn =>
(x => x(x))(
maker =>
(...args) =>
fn(maker(maker), ...args)
);
With the why bird, instead of writing a recursive function like this:
const isEven =
n =>
(n === 0)  !isEven(n  1);
In why bird form, we write it like this:
const _isEven =
(myself, n) =>
(n === 0)  !myself(n  1);
We use the why bird in conjunction with a function written “in why bird form” like this:
why(_isEven)(42)
//=> true
This arrangement decouples the recursive function from itself, allowing us to use an anonymous function if we wish, like this:
why(
(myself, n) =>
(n === 0)  !myself(n  1)
)(42)
//=> true
It also allows us to decorate the recursive function easily, whether anonymous or not.
The why bird is an idiomatic JavaScript version of combinatorial logic’s Y Combinator. The Y Combinator works with functions in curried form, i.e. functions that take only one argument.
The full expression of the Y Combinator looks like this:
const Y =
fn =>
(m => a => fn(m(m))(a))(
m => a => fn(m(m))(a)
);
Its compact form, like the compact why bird, makes use of the M Combinator, reduced to x => x(x)
:
const Y =
fn =>
(x => x(x))(m => a => fn(m(m))(a));
Either expression of the Y Combinator is used with functions in curried form:
Y(
myself =>
n =>
(n === 0)  !myself(n  1)
)(1962)
We will work with the why bird in this essay, however everything we do can also be done with the Y Combinator, albeit by writing functions in a form that is not usual for JavaScript.
tail recursion
This function for determining whether a number is even is extremely slow, and it has another problem:
const isEven =
n =>
(n === 0)  !isEven(n  1);
isEven(1000042)
//=> Maximum call stack exceeded
Revising it to work with the why bird does not fix the issue:
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 tailrecursive form. If the JavaScript engine supports tailcall 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 tailcall 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” tailcall optimization ourselves by implementing a trampoline:^{2}
A trampoline is a loop that iteratively invokes thunkreturning functions (continuationpassing 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 tailrecursive function calls in stackoriented 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 tailrecursive 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 tailrecursive functions in constant stack space.
We will call this function the “Longtailed Widowbird.” Let’s derive it.
deriving the longtailed 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! But this Is code that only its author could love.
from longtailed widowbird to decoupled trampoline
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 specialpurpose 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 longtailed widowbird. Well, actually, we are ignoring “the elephant in the room,” the name of the function. “Longtailed 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 tailrecursive 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.
summarizing the use case for 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:
 Refactor the function into tailrecursive form;
 Refactor the tailrecursive version to explicitly invoke a trampoline;
 Wrap the result in a trampoline function.
With the decoupled trampoline, we can:
 Refactor the function into tailrecursive form;
 Refactor the function into “why bird form,” then;
 Wrap the result in the decoupled trampoline.
Why is this superior? We’re going to refactor into tailrecursive form either way, and we’re going to wrap the function either way, however:
 Refactoring into “why bird form” is less intrusive than rewriting the code to explicitly return thunks, and;
 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!
The essays in this series on recursive combinators are: To Grok a Mockingbord, Deriving the Y Combinator and Why Bird from the Mockingbird, and A practical (albeit infrequently needed) use for the Y Combinator. Enjoy them all!
Notes

The mockingbird is more formally known as the M Combinator. Our naming convention is that when discussing formal combinators from combinatory logic, or direct implementations in JavaScript, we will use the formal name. But when using variations designed to work more idiomatically in JavaScript–such as versions that work with functions taking more than one argument), we will use Raymond Smullyan’s ornithological nicknames.
For a formalist, the M Combinator’s direct translation isconst M = fn => fn(fn)
. This is only useful iffn
is implemented in “curried” form, e.g.const isEven = myself => n => n === 0  !myself(n  1)
. If we wish to use a function written in idiomatic JavaScript form, such asconst isEven = (myself, n) => n === 0  !myself(n  1)
, we use the mockingbird, which is given later asconst mockingbird = fn => (...args) => fn(fn, ...args)
. This is far more practical for programming purposes. ↩ 
A more complete exploration of ways to convert recursive functions to nonrecusrives functions can be found in Recursion? We don’t need no stinking recursion!, and its followup, A Trick of the Tail. ↩