Fork me on GitHub
article    dev example    prod example     core test

Tail metacomposition

by Guillaume Lathoud [0], March 2013

Implementing mutual tail recursion optimization without trampoline [1] - for good performance - led me to write quite insane code [2].

Here is a lighter approach, that extends JavaScript with two keywords metafun and metaret, implementing one tiny bit of Backus' metacomposition [3].

[Budapest 2014 slides, video, both]

Update 2016-02-02: If you like this, you might also like the transfun.js tool for fast map/filter/reduce/...

Update 2018-06-28: There is now an even lighter implementation, similar to Tail Metacomposition, but in 100% standard JavaScript - without any new keyword: fext.js

Getting started

node.js support

Thanks to Iain Ballard, there is a node.js npm package (GitHub source).

Metafunction declarations


Thanks to metacomposition, you get anonymous self-recursion for free: no need for a Y combinator or arguments.callee:

        metaret self, k - 1, acc * k; // anonymous self-recursion


Metafunctions are implemented by generating normal JavaScript functions, where metaret call(s) have been unrolled using a while loop, and switch statements for mutual recursion.

Each case contains the code for one metaret call, where variable names have been renamed to prevent collisions. I call that "hygienic inlining". (I need to add an example targetted on this.)

Generated code

 (Indentation can be improved.)


Generated code

 (Indentation can be improved.)