JavaScript tail-call optimization decorator using exceptions
JavaScript does not have tail call optimization,
at least until proper tail calls arrive in ES6,
because of the existence of <function>.caller and <function>.callee.
So, if you’re doing something crazy like
implementing the lambda calculus from first principles,
you’re gonna have a bad time.
Let’s consider a really simple recursive Node.js module, recurse.js:
1
2
3
4
5
6
7
var r = recurse(process.argv[2] || 5000, 0);
console.log('found', r);
function recurse(n, j) {
if(n>0) return recurse(n-1, j+1);
else return j;
}
We can then test recurse.js to see how many stack frames it takes to crash Node:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var fork = require('child_process').spawn;
var cProcess = 0;
bounds(0, 1000);
function exec(param){
cProcess++;
return fork(process.argv[0], [process.argv[2], param]);
}
function bounds(min, max) {
exec(max).on('exit', function(exitCode) {
if(exitCode == 0) {
bounds(max, max*2);
} else {
console.log("Bounds:", min, max);
bisect(min, max);
}
});
}
function bisect(min, max) {
if(min == max)
{
console.log(min);
console.log(cProcess, 'processes created');
return;
}
var sample = Math.floor((min+max)/2);
exec(sample).on('exit', function(exitCode) {
if(exitCode == 0) {
bisect(sample, max);
}
else {
bisect(min, sample);
}
});
}
On my Linode, node bisect.js recurse.js prints:
Bounds: 16000 32000
16376
39 'processes created'
16,376 should be enough stack frames for anyone.
Unless you’re writing in a purely functional style, in which case recursion is the only way you can write a loop.
The way one usually gets out of this situation is by writing in trampoline style. (You can rewrite your compiler or interpreter to automatically use trampoline style, but V8 and Node.js are too big for me to consider it tonight.)
Instead of rewriting my functions, I just want to be able to call a decorator and have them trampoline without manual rewriting. JavaScript exceptions unwind the stack, and can be of any type. So let’s just throw a continuation to the trampoline.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function throwup(fxn) {
return function() {
throw [fxn, Array.prototype.slice.call(arguments)];
}
}
function makecallable(fxn) {
return function() {
var params = Array.prototype.slice.call(arguments);
while(params) {
try {
var r= fxn.apply(null, params);
return r;
}catch(e){
params = e[1];
fxn = e[0];
}
}
}
}
module.exports = {makecallable: makecallable, throwup: throwup};
throwup is the tail-call optimizing decorator around the original function; its return value
should overwrite the original variable name.
makecallable creates the trampoline in the form of a try\{...\}catch\{...\} statement.
Here’s an example:
1
2
3
4
5
6
7
8
9
10
11
var throwup = require('throw').throwup, makecallable = require('throw').makecallable;
var recurse = throwup(_recurse);
var callable_recurse = makecallable(_recurse);
var result = callable_recurse(parseInt(process.argv[2], 10) || 5000, 0);
console.log('found', result);
function _recurse(n, j) {
if(n>0) return recurse(n-1, j+1);
else return j;
}
And another one, which uses corecursion:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var throwup = require('throw').throwup, makecallable = require('throw').makecallable;
var even = throwup(_even),
odd = throwup(_odd);
var r = makecallable(_even)(parseInt(process.argv[2], 10) || 5000, 0);
console.log('found2', r);
function _even(n,j) {
if(n>0) return odd(n-1, j+1);
else return ['even', j];
}
function _odd(n, j) {
if(n>0) return even(n-1, j+1);
else return ['odd', j];
}
I ran node bisect.js tco.js to measure when exception-based tail-call-optimization fails.
(I let it run to 32M before getting bored. (It took 2 minutes.))
The stack trace of the exception is allocated on the heap, so it cannot overflow the stack.
Trampolined functions must be called in tail position. Throwing an exception will blow away the surrounding context.
How is performance?
Comically bad.
Here are the results of wrapping the calls to
recurse and throwup(_recurse) in for(var i=0;i<100000;i++):
Execution time vs iteration size, looped 100,000 times
recursethrowup
Henry Baker describes an unpublished suggestion from Appel
to have the compiler (in our case, throwup()) check the stack size and only return to
the trampoline if the stack is about to overflow. This method
“avoids making a large number of small [but slow] trampoline bounces
by occasionally jumping off the Empire State Building.”
Implementation is left to the reader. Don’t forget your parachute!