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.
Update 2019-03-12: fext is now available in the D language as well.
<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><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>
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
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.
These results present the average relative speed (higher is better):
100.0 is the max of each row,(2.9),[5.78e+8] (iterations per second).The isOdd_mfun and isOdd_mret
results show that the proposed approach runs:
isOdd_metaret,
another approach that extends the JavaScript language with
new keywords
(2013),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...)
Running...Search the first & last indices of a given value in a sorted array that has duplicates:
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;
}On GitHub and here below.