<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:
We can then test recurse.js to see how many stack frames it takes to crash Node:
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.)
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
Here’s an example:
And another one, which uses corecursion:
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?
Here are the results of wrapping the calls to
Execution time vs iteration size, looped 100,000 times
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!