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

• A very simple example: development and production.
• Code and documentation on GitHub.
• Slides from mloc.js 2014.
• Core test.

• [0] http://glat.info
• [1] http://glat.info/jscheck/tomrec.xhtml
• [2] http://glat.info/jscheck/tool.tailopt.js
• [3] http://www.stanford.edu/class/cs242/readings/backus.pdf

node.js support

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

Metafunction declarations

Bonus

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

Implementation

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

Show it! (Indentation can be improved.)

Longer example: Search a sorted array

Source:

Generated code

Show it! (Indentation can be improved.)

Tests