A module for tail call optimization by Continuation Passing Style (CPS) transformation with trampoline technique for Node.js
A module for tail call optimization by Continuation Passing Style (CPS) transformation with trampoline technique for Node.js
JavaScript is a nice programming language, but compared to Scheme, it doesn't handle tail calls properly. Node.js is often used with callback functions, which tend to be tail calls (but not necessarily recursions) consuming call stacks.
This module allows to transform native JavaScript code into CPS code in a best effort manner. It utilizes so-called trampoline technique to avoid a stack overflow error. Transforming all functions into CPS is not very easy (and sometimes not very efficient), hence it has a fallback mechanism, that is, only supported function style is transformed into CPS and other functions are called in an original style. Because of the fallback mechanism, mixing CPS code and non-CPS code is possible.
Here is the table showing modules that support tail call optimization.
$ git clone https://github.com/dai-shi/continuation.js.git
$ cd continuation.js
$ ./bin/continuation-compile sample/fact.js > cps_fact.js
$ npm install continuation.js
and add the following:
require('continuation.js').enable_on_require();
which transforms all following .js files by require
.
Simple factorial function:
$ cat sample/fact.js
function fact(x) {
function fact_tail(x, r) {
if (x === 0) {
return r;
} else {
return fact_tail(x - 1, x * r);
}
}
return fact_tail(x, 1);
}
exports.fact = fact;
$ node -e "console.log(require('./sample/fact.js').fact(100000))"
.../continuation.js/sample/fact.js:2
function fact_tail(x, r) {
^
RangeError: Maximum call stack size exceeded
$ node -e "require('./lib/continuation.js').enable_on_require();console.log(require('./sample/fact.js').fact(100000))"
Infinity
Mutual recursion example:
$ cat sample/mutual.js
function isEven(x) {
if (x === 0) {
return true;
} else {
return isOdd(x - 1);
}
}
function isOdd(x) {
if (x === 0) {
return false;
} else {
return isEven(x - 1);
}
}
exports.isEven = isEven;
exports.isOdd = isOdd;
$ node -e "console.log(require('./sample/mutual.js').isOdd(1234567))"
.../sample/mutual.js:1
tion isEven(x) {
^
RangeError: Maximum call stack size exceeded
$ node -e "require('./lib/continuation.js').enable_on_require();console.log(require('./sample/mutual.js').isOdd(1234567))"
true
The following is the results of Octane benchmark suites (except for one).
Since trampoline is costly, performance drops in most suites especially basic ones. Whereas in relatively complex suites, there are some cases when performance is comparable.