glathoud / fext

Fast explicit tail calls. In today's JavaScript!

fext.js

Fast explicit tail calls in JavaScript [live page] [Node.js package]

Classically, 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 tail call optimization from its JavaScript engine.

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

It turns out that we can do this with today's JavaScript, without extending the language.

fext.js demonstrates this.

API

Two entry points:

• mfun(...) returns an optimized function,
• meth(...) returns an optimized method.

Debugging

Just append a "D" character:

• turn mfun() into mfunD().
• turn meth() into methD().

...to turn off the optimizations. You can then use logging and breakpoints.

Getting started

Wrap the whole function with mfun(...) and use return mret(<expr>) to mark the tail calls to be optimized.

Self-recursion example:

<script src="fext.js"></script>
<script>
  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

var groupkey = {}  // whatever object (won't be modified)

,   isOdd = mfun( groupkey
                 , "isOdd"
                 , n => n < 0    ?  mret( mself, -n )
                 :      n === 0  ?  false
                 :      mret( isEven, n-1 )
               )
,  isEven = mfun( groupkey
                 , "isEven"
                 , n => n < 0    ?  mret( mself, -n )
                 :      n === 0  ?  true
                 :      mret( isOdd, n-1 )
               )
;
console.log( isOdd( 84327681 ) );   // true (no call stack issue)
console.log( isEven( 84327681 ) );  // false (no call stack issue)

groupkey is only used as a key to determine "groups" of function that know each other.

You can conveniently omit groupkey:

// The default `groupkey` is the returned function
// `var isOdd` in this case
var isOdd = mfun( n => n < 0    ?  mret( mself, -n )
                  :    n === 0  ?  false
                  :    mret( isEven, n-1 )
                )
,  isEven = mfun( isOdd  // <<< `isOdd` is used here as `groupkey`
                  , "isEven"
                  , n => n < 0    ?  mret( mself, -n )
                  :      n === 0  ?  true
                  :      mret( isOdd, n-1 )
                )
;
console.log( isOdd( 84327681 ) );   // true (no call stack issue)
console.log( isEven( 84327681 ) );  // false (no call stack issue)

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

Shortcut

Note that fext === fext.mfun as a shortcut for the simplest cases, especially in the Node.js context:

var fx = require( '../fext' ).fext;

var self_recursive_fun = fx( ... );

...and in the IE11 context, when relying on the fext namespace, this gives easy access to arrow functions:

var sum_two = fext('(x,y) => x+y');

Methods

Self-recursion example:

var o = {
   gcd : meth( "gcd"
               , (that, a, b) => a > b  ?  mret( that.mself, a-b, b )
               :                 a < b  ?  mret( that.mself, b-a, a )
               :                 a
             )
};
console.log( o.gcd( 2*3*5*17, 3*5*19 ) );  // 15 (3*5)

No need for groupkey here. Moreover, instead of:

mfun( (a,b,c) => ... )

use:

meth( "methodname", (that,a,b,c) => ... )

• "methodname" MUST be the name of the method,
• The first parameter MUST be that,
• Inside the method, you MUST use that (and not this). Reason: .bind() slower in Firefox 60.
• Use that. in the mret calls, as in:

return mret( that.mself, ...)

or

return mret( that.otherMethod, ... )

The mret( that.<methodName> ) call syntax

• makes clear we are calling a method, not just a simple function,
• AND permits easy debugging through methD.

Methods: Mutual recursion example

var o = {
    isOdd : meth( "isOdd"
                  , (that, n) => n < 0  ?  mret( that.mself, -n )
                  :            n === 0  ?  false
                  :            mret( that.isEven, n-1 )
                )
    , isEven : meth( "isEven"
                     , (that, n) => n < 0  ?  mret( that.mself, -n )
                     :            n === 0  ?  true
                     :            mret( that.isOdd, n-1 )
                   )
};
console.log( o.isOdd( 84327681 ) );  // true (no call stack issue)
console.log( o.isEven( 84327681 ) ); // false (no call stack issue)

Prototype methods

Pretty much the same as above.

function A() {}
A.prototype.isOdd = meth( "isOdd"
                          , (that, n) => n < 0  ?  mret( that.mself, -n )
                          :            n === 0  ?  false
                          :            mret( that.isEven, n-1 )
                        );
A.prototype.isEven = meth( "isEven"
                           , (that, n) => n < 0  ?  mret( that.mself, -n )
                           :            n === 0  ?  true
                           :            mret( that.isOdd, n-1 )
                         );
var o = new A;
console.log( o.isOdd( 84327681 ) );  // true (no call stack issue)
console.log( o.isEven( 84327681 ) ); // false (no call stack issue)

Speed test

The higher, the better. 100.0 is the highest in each row, (2.6) is a standard deviation, and [9.34e8] is the absolute speed in iterations per second.

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]

• isOdd_mfun and isOdd_meth: Proposed "explicit" approach. Uses standard JavaScript.
• isOdd_metaret Another "explicit" approach (2013). Extends JavaScript with new keywords.
• isOdd_tailtramp: The fastest trampoline implementation that I could find.

For more details, explanations, and run this test in your browser, either open the live instance or open the ./index.html file here.

Browser support

Modern browsers, and IE11, as of June 2018.

Unit tests

Either in the browser (live instance) or in the command-line (e.g. Nashorn).

An example: sortedSearch

Code: lib/sorted_search.js

Tests: lib/sorted_search_unittest.js

The code in that example shows an issue when having to pass too many parameters around: the code contains 5 times the same list of parameters, as in the code excerpt:

var improveFirst = mfun( improveFirst )
,   improveLast  = mfun( improveFirst, improveLast )
;   

function sortedSearch(sortedArray, x, /*?fun?*/less, /*?fun?*/equal)
{
   // ...
   return improveFirst(
       sortedArray, x, less, equal, isFirstFound, isLastFound
       , first_found, last_found, i, j, imax, jmin
   );     
}

function improveFirst(
    sortedArray, x, less, equal, isFirstFound, isLastFound
    , first_found, last_found, i, j, imax, jmin
)
{
    // ...

    return mret(
        improveLast
        , sortedArray, x, less, equal, isFirstFound, isLastFound
        , first_found, last_found, i, j, imax, jmin
    );
}

function improveLast(
    sortedArray, x, less, equal, isFirstFound, isLastFound
    , first_found, last_found, i, j, imax, jmin
)
{
    // ...

    return mret(
        improveFirst
        , sortedArray, x, less, equal, isFirstFound, isLastFound
        , first_found, last_found, i, j, imax, jmin
    );
}

The straightforward answer to this issue would be to put all parameters in an object, but this leads to a performance degradation (see "Performance cost of passing parameters through an object" further below).

An alternative is to declare the parameters only once, use closure and eval so that the generated code has access to the parameters through the closure.

For a complete example see:

Code: lib/sorted_search_closure.js

Tests: lib/sorted_search_closure_unittest.js

Excerpt:

    // First "declare" all functions so that co-dependencies can be
    // solved.
    //
    // Use `mfunD` to debug
    var improveFirst = mfun( improveFirst )
    ,   improveLast  = mfun( improveFirst, improveLast )
    ;
    
    // Now we can implement them, using evil access to the local
    // lexical scope so that we do not need to write parameters
    // repeatedly 5 times (see above `function sortedSearch(...)`).
    improveFirst = eval( improveFirst.getEvalImpl() );
    improveLast  = eval( improveLast.getEvalImpl() );
    
    var first_found
    ,    last_found
    ,             i
    ,             j
    ,          imax
    ,          jmin
    ;
    var sortedArray, x, less, equal;
    
    function sortedSearchClosure
    (in_sortedArray, in_x, /*?fun?*/in_less, /*?fun?*/in_equal)
    /*
      In a sorted array, search for first & last occurences of `x`.
      
      If `x` found, return `[ first_index, last_index ]` (integers).
      
      If `x` not found, return `null`.
    */
    {
        // ...
        
        return improveFirst();
    }

    function improveFirst()
    {
        // ...

        return mret( improveLast );
    }

    function improveLast()
    {
        // ...
        return mret( improveFirst );
    }

Performance cost of passing parameters through an object

To measure the extra overhead of wrapping parameters inside an object, we use the isOdd/isEven case, since each function does very little in itself. First the results, then the detailed implementations.

Browser	isOdd_mfun	isOdd_mfun_obj	isOdd_mfun_obj_inplace
Firefox 60	89.0 (5.4)	24.8 (1.6)	19.3 (0.3)
	[8.02e+8]	[2.24e+8]	[1.74e+8]
----	----	----	----
Chromium 66	100.0 (2.3)	47.9 (0.7)	87.6 (0.8)
	[8.35e+8]	[4.00e+8]	[7.31e+8]

Browser	isOdd_meth	isOdd_meth_obj	isOdd_meth_obj_inplace
Firefox 60	94.0 (2.1)	26.3 (0.5)	18.7 (0.5)
	[8.47e+8]	[2.37e+8]	[1.69e+8]
----	----	----	----
Chromium 66	99.2 (1.7)	45.6 (0.2)	87.9 (0.9)
	[8.28e+8]	[3.80e+8]	[7.34e+8]

To obtain the best performance, it is preferable to pass parameters separately: isOdd_mfun and isOdd_meth. If there are too many parameters, one can use closure, see sortedSearchClosure just above.

*_obj implementations:

For the full details, see the *_obj functions in test/fext_speedtest.js

Excerpt:

function isOdd_mfun_obj( niter )
{
    // The default `namespacekey` is the returned
    // function `var isOdd` in this case.
    var isOdd = mfun( function isOdd( o ) {
        let n = o.n;
        if (n > 0)
        {
            o = { n : n-1 };
            return mret( isEven, o );
        }
        else if (n < 0)
        {
            o = { n : -n };
            return mret( mself, o );
        }
        else
        {
            return false;                
        }
    })

    ,  isEven = mfun( isOdd, function isEven( o ) {
        let n = o.n;
        if (n > 0)
        {
            o = { n : n-1 };
            return mret( isOdd, o );
        }
        else if (n < 0)
        {
            o = { n : -n };
            return mret( mself, o );
        }
        else
        {
            return true;
        }
    })
    ;
    // Sanity check
    isOdd_isEven_check( isOdd, isEven, function (n) { return {n:n}; } );
    
    var result = isOdd( { n : niter } ); // <<< speedtest

    // Sanity check
    result === (niter % 2 !== 0)  ||  null.bug;
}

function isOdd_mfun_obj_inplace( niter )
{
    // The default `namespacekey` is the returned
    // function `var isOdd` in this case.
    var isOdd = mfun( function isOdd( o ) {
        let n = o.n;
        if (n > 0)
        {
            o.n--;
            return mret( isEven, o );
        }
        else if (n < 0)
        {
            o.n = -n;
            return mret( mself, o );
        }
        else
        {
            return false;                
        }
    })

    ,  isEven = mfun( isOdd, function isEven( o ) {
        let n = o.n;
        if (n > 0)
        {
            o.n--;
            return mret( isOdd, o );
        }
        else if (n < 0)
        {
            o.n = -n;
            return mret( mself, o );
        }
        else
        {
            return true;
        }
    })
    ;
    // Sanity check
    isOdd_isEven_check( isOdd, isEven, function (n) { return {n:n}; } );
    
    var result = isOdd( { n : niter } ); // <<< speedtest

    // Sanity check
    result === (niter % 2 !== 0)  ||  null.bug;
}

Destructuring (#18)

Test run on the 2019-09-12:

Without (implementation with intermediary variables, as done until now):

| Chromium 76 | 98.9 (0.6) | 100.0 (0.4) |    57.3 (0.2) |      0.5 (<0.1) |
|             |  [7.79e+8] |   [7.87e+8] |     [4.51e+8] |       [4.28e+6] |

With destructuring (#18), no need for intermediary variables anymore:

| Chromium 76 | 100.0 (0.3) |  95.3 (9.3) |    77.2 (0.2) |      0.7 (<0.1) |
|             |   [5.84e+8] |   [5.56e+8] |     [4.51e+8] |       [4.34e+6] |

As of 2019-09 using destructuring thus brings a marked slow-down (about 33% slower) so we'll leave that deactivated for now.

fext's Issues

code cleanup: remove `__fext_undefined__`

AFAIK all browsers support a non-modifiable undefined so we don't need that extra variable __fext_undefined__, let's remove it.

Thanks to Frederico Kereki for the feedback.

investigate feasability in D

Reason: performance would be great + mutual recursion syntax then allowed

see also https://github.com/glathoud/fext/tree/master/misc/d_performance_feasability

consider Evil Mode

The sortedSearch example shows the suffering of having a great tool like new Function(...) but no access to the local context.

Until JS has tools similar to D's template mixins and string mixins, we might consider an optional activation of the One Evil Thing.

For more background, see the discussion on comp.lang.javascript.

Result

Added a .getImplEval method to support eval, as in:

    // First "declare" all functions so that co-dependencies can be
    // solved.
    //
    // Use `mfunD` to debug
    var improveFirst = mfun( improveFirst )
    ,   improveLast  = mfun( improveFirst, improveLast )
    ;
    
    // Now we can implement them, using evil access to the local
    // lexical scope so that we do not need to write parameters
    // repeatedly 5 times (see above `function sortedSearch(...)`).
    improveFirst = eval( improveFirst.getEvalImpl() );
    improveLast  = eval( improveLast.getEvalImpl() );

For a complete use case see sorted_search_local about here

support transfun's "inlineable" interface

So that we can integrate fext's generated code directly in transfun: glathoud/transfun#7

speed measurement GUI

try to improve IE11 support

IE11 supported

internals: investigate destructuring

[this deals with the generated code, in particular the tail call elimination]

Frederico Kereki suggested to use destructuring when "updating" the variables, so that intermediary variables are not needed.

Paying attention to performance and IE11 compatibility (=no destructuring), the plan would look like this:

• add a hidden option "destructuring", deactivated by default,
• measure the performance with and without destructuring, at least in FF and Chrome
• if positive results, make the option activated by default except in IE

try not to modify non-mret returns

investigate d performance feasability

https://github.com/glathoud/fext/blob/master/misc/d_performance_feasability/d_perf_feas.d

gives some first results on the isOdd/isEven example, things working fine so far. I guess in the D spirit of fast compiling it would be better to:

• stick with subfunctions (no self-made inlining/unrolling),
• have at most 1 or 2 expansion levels,
• and let the user actively set pragma( inline, true ) and call dmd -inline or equivalent.

To better evaluate the expansion, I guess the is0mod3/is1mod3/is2mod3 example is better. Won't write it by hand => Need to polish a bit the JS code generation, to make it easier to convert it to D.

argument macros

For performance reasons it is often best to stick to direct parameter transmission, but that can lead to many parameters, as in the sortedSearch example, see #11

Reason (performance): when parameter names are simply "copied", the corresponding (superfluous) assignments can be completely eliminated by fext.js

Reason (implementation): we are using new Function which has no access to the target scope, so closure cannot be used.

Task: implement "argument macros" shortcuts as fext.__args in:

function sortedSearch(sortedArray, x, /*?fun?*/less, /*?fun?*/equal)
{
     // ....
      return improveFirst(  // UNCHANGED
            sortedArray, x, less, equal, isFirstFound, isLastFound
            , first_found, last_found, i, j, imax, jmin
        );
}

// ...

   // --- Private details

    function improveFirst(  // UNCHANGED
        sortedArray, x, less, equal, isFirstFound, isLastFound
        , first_found, last_found, i, j, imax, jmin
    )
    {
 // ...
  return mret(  // CHANGED
            improveLast
            , fext.__args
        );
    }

Other argument macros could be:

return mret( someFun, a, b, c, fext.__lastArgs );

// equivalent to:
return mret( someFun, a, b, c, fext.__args(3) );

and:

return mret( someFun, fext.__firstArgs, x, y, z );

// equivalent to:
return mret( someFun, fext.__args(0, -3), x, y, z ) 

The optional call syntax fext.__args(a [, b] ) would be similar to that of Array.prototype.slice

offer easy debugging

deactivate one or all code generations

shortcut fext === fext.mfun

Permits generally to write shorter code, and in particular in IE11 to make arrow functions easy to use, as in fext("x => x+1")

fix nashorn support

The recent improvements have broken some of the nashorn support.

Task: fix this!

After that fext.js is ready for integration into production.

node rpm package

investigate inlining

Within ES6 inlining could be feasable AND safe provided we forbid var within the bodies.

beautify the generated code

...and write up a bit about it

add "real life" example like sortedsearch

improve nashorn support

At the moment nashorn spits a strange error:

[error] fext: caught error while compiling the implementation: java.lang.NullPointerException
[error] #22 failed on graph_recursion_test: java.lang.NullPointerException