fext.js: Fast Explicit Tail Calls

by G. Lathoud, June 2018.

...using today's JavaScript!

Usually, tail calls are automatically optimized (LISP...).

In JavaScript, programmers may well not know which "return" statements are optimized by the engine, and which not. This would lead to practical issues when debugging/optimizing (2009).

As of 2018, progress is "slow" and the Chrome team has already removed the automatic self-recursion 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 (20132016).

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.

Quick example

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

API Documentation incl. debugging tools

README.md on GitHub (formatted), or directly here (unformatted).

Included: two simple debugging tools mfunD & methD that deactivate the optimizations.

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: More code

On GitHub and here below:

    Annex B: 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( self, -n )
            :  false
        ;
    })
    ,  isEven = mfun( isOdd, function isEven( n ) {
        return n > 0  ?  mret( isOdd, n-1 )
            :  n < 0  ?  mret( self, -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;
    }