Fork me on GitHub

Fast explicit tail calls in JavaScript

by G. Lathoud, June 2018.

If you don't know what this is about, please have a look at an excellent background article on tail calls in JavaScript. Also my own early work on this might be helpful.

In LISP and other languages, tail calls are automatically optimized. In Clojure, there is an explicit keyword recur. Generally, programmers may well not know which "return" statements are optimized by the engine, and which not. This would lead to practical issues when debugging and optimizing [2009].

What about JavaScript?

As of 2018, progress is "slow" and the Chrome team has already removed the automatic self-recursion tail call optimization from its JavaScript engine.

Another possibility is to explicitly mark the tail calls that will be optimized. JavaScript extensions were proposed that add new keywords to the language [2013] [2016].

It turns out that we can do this explicit approach using today's JavaScript, without extending the language. fext.js demonstrates this.

Mutual recursion is supported. API doc and source on GitHub. Node.js package.

Quick example

<script type="text/javascript" src="fext.js"></script>
<script type="text/javascript">
var gcd = mfun(
       (a, b) => a > b  ?  mret( mself, a-b, b )
           :     a < b  ?  mret( mself, b-a, a )
           :     a
);
console.log( gcd( 2*3*5*17, 3*5*19 ) );  // 15 (3*5)
</script>

Mutual recursion example

<script type="text/javascript" src="fext.js"></script>
<script type="text/javascript">
var isOdd = mfun( function isOdd( n ) {
    return n > 0  ?  mret( isEven, n-1 )
        :  n < 0  ?  mret( mself, -n )
        :  false
    ;
})
,  isEven = mfun( isOdd, function isEven( n ) {
    return n > 0  ?  mret( isOdd, n-1 )
        :  n < 0  ?  mret( mself, -n )
        :  true
    ;
})
console.log( isOdd( 8951531 ) ); // true ; no call stack issue
</script>

Namespace alternative

In some situations the globals mfun, meth, mfunD, etc. may feel annoying. Solution: use the fext.* namespace. Below, an example in the Node.js context:

var fx = require( '../fext' ).fext;
            
var isOdd = fx.mfun( function isOdd( n ) {
    return n > 0  ?  fx.mret( isEven, n-1 )
        :  n < 0  ?  fx.mret( fx.mself, -n )
        :  false
    ;
})
,  isEven = fx.mfun( isOdd, function isEven( n ) {
    return n > 0  ?  fx.mret( isOdd, n-1 )
        :  n < 0  ?  fx.mret( fx.mself, -n )
        :  true
    ;
})
console.log( isOdd( 8951531 ) ); // true ; no call stack issue

API Documentation and debugging tools

On GitHub (formatted), or directly here (unformatted).

Debugging: instead of mfun & meth, simply use mfunD & methD to deactivate the optimizations. You can then set breakpoints as usual.

Speed test

These results present the average relative speed (higher is better):

  • 100.0 is the max of each row,
  • standard deviation in brackets e.g. (2.9),
  • absolute speed in square brackets, e.g. [5.78e+8] (iterations per second).

The isOdd_mfun and isOdd_mret results show that the proposed approach runs:

  • similar to, or faster than isOdd_metaret, another approach that extends the JavaScript language with new keywords (2013),
  • much faster than tailtramp, the fastest trampoline implementation I could find (feel free to ping me with a faster one).

So the proposed approach (1) runs very fast and (2) does not need to extend JavaScript with new keywords.

| Browser     | isOdd_mfun |  isOdd_meth | isOdd_metaret | isOdd_tailtramp |
| :---        |       ---: |        ---: |          ---: |            ---: |
| Firefox 60  | 95.5 (2.6) | 100.0 (1.4) |    81.2 (0.2) |      0.1 (<0.1) |
|             |  [9.34e+8] |   [9.78e+8] |     [7.93e+8] |       [1.25e+6] |
| ----        |       ---- |        ---- |          ---- |            ---- |
| Chromium 66 | 98.5 (0.3) | 100.0 (4.9) |    52.0 (0.1) |      0.7 (<0.1) |
|             |  [8.87e+8] |   [9.00e+8] |     [4.68e+8] |       [6.12e+6] |
| ----        |       ---- |        ---- |          ---- |            ---- |
| Chrome 67   | 99.8 (0.8) | 100.0 (0.3) |    62.2 (0.2) |      0.8 (<0.1) |
|             |  [7.49e+8] |   [7.51e+8] |     [4.67e+8] |       [6.18e+6] |

Running (please be patient...)

Unit tests

Running...

Longer example

Search the first & last indices of a given value in a sorted array that has duplicates:

Annex A: Setup details of the speed test

The isOdd/isEven mutual recursion use case measures well the overhead due to each approach, since both isOdd & isEven do little inside their function bodies.

We measure 10 times the duration of isOdd( niter ) where niter is adjusted to have a duration > 1.0 second.

isOdd_mfun & isOdd_meth are the proposed approach, using only standard JavaScript, e.g.:

var isOdd = mfun( function isOdd( n ) {
    return n > 0  ?  mret( isEven, n-1 )
        :  n < 0  ?  mret( mself, -n )
        :  false
    ;
})
,  isEven = mfun( isOdd, function isEven( n ) {
    return n > 0  ?  mret( isOdd, n-1 )
        :  n < 0  ?  mret( mself, -n )
        :  true
    ;
})

isOdd_metaret is another approach that extends the JavaScript language with new keywords, including metafun and metaret (2013):

metafun isEven( self, n )
{
    if (n > 0)
        metaret isOdd, n - 1; // mutual recursion

    if (n < 0)
        metaret self, -n;

    return true;
}

metafun isOdd( self, n )
{
    if (n > 0)
        metaret isEven, n - 1;

    if (n < 0)
        metaret self, -n;

    return false; 
}

and isOdd_tailtramp is the fastest trampoline implementation that I could find:

var isOdd = tailtramp( function( n ) {
    return n > 0  ?  isEven( n-1 )
        :  n < 0  ?  isOdd( -n )
        :  false
    ;
})
, isEven = tailtramp( function( n ) {
    return n > 0  ?  isOdd( n-1 )
        :  n < 0  ?  isEven( -n )
        :  true
    ;
})

function tailtramp(g)
{
    var tailtramp_n = 0;
    return tailtramp_impl;
    
    function tailtramp_impl()
    {
        var arr = [g, this, arguments]
        , ret;

        // Jump off a small Empire State Building
        if (tailtramp_n>5)
            return new TailCall(arr);
        
        while (true)
        {
            tailtramp_n++;
            ret = arr[0].apply(arr[1], arr[2]);
            tailtramp_n--;
            
            if (!(ret instanceof TailCall))
            {
                tailtramp_n = 0;
                return ret;
            }
            
            // Hit 33rd Street and bounce again
            arr = ret.arr;
        }
    }
}

function TailCall(arr)
{
    this.arr  = arr;
}

Annex B: More code

On GitHub and here below.