Tailless exception

Question

I am making a Lisp translator in JavaScript. JS has no tail recursion exception (TRE), so I applied TRE using the while loop in JS (pseudocode):

function eval (exp, env) while true if exp is self evaluating return exp else if ... ... else if exp is a function call procedure = eval(car(exp), env) arguments = eval_operands(cdr(exp), env) exp = procedure.body env = extend_env(procedure.env, env) continue # tail call 

So I'm happy, and tail-recursion functions like the following are not exhausted:

 (define + (lambda (nm) (cond ((zero? n) m) (else (+ (sub1 n) (add1 m)))))) (+ 10000 1) ;=> 10001 

However, functions that are not tail recursive end from the JS stack (because the JS code repeats too much on eval_operands ):

 (define + (lambda (nm) (cond ((zero? n) m) (else (add1 (+ (sub1 n) m))))) ; not proper tail-recursive (+ 10000 1) ;=> JS: Maximum call stack size exceeded 

How do I work with non-recursive functions? What are the options? What are some good resources? I read a little about the trampoline, the style of externalizing the stack and continuing through, but all I could find was to write code in these styles, not how to use these methods to write an interpreter.

Answer 1

You can always turn calls into jumps if you can store frame information elsewhere. This is what “stack equalization” refers to.

For your translator, your call frame data should hold the continuation of the non-tail call (which may itself contain additional references, for example, any variables that it needs access to). You will need one call frame for an active non-tail call.

All this, of course, is the trading stack space for heap space. After all, you really don't save memory that way. :-)