Programmatic non-tail recursion elimination

Question

I'm making a toy Lisp interpreter in JavaScript. JS has no tail recursion elimination (TRE), so I implemented TRE using 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 am happy, and tail-recursive functions like the following one do not run out of stack:

(define +
  (lambda (n m)
    (cond ((zero? n) m)
          (else (+ (sub1 n) (add1 m))))))

(+ 10000 1) ;=> 10001

However, functions that are not tail-recursive, run out of JS stack (because JS code recurs too much on eval_operands):

(define +
  (lambda (n m)
    (cond ((zero? n) m)
          (else (add1 (+ (sub1 n) m)))))  ; not proper tail-recursive

(+ 10000 1) ;=> JS: Maximum call stack size exceeded

How do I deal with non-tail-recursive functions? What are the options? What are good resources? I have read a bit about trampolining, stack externalising and continuation-passing style, but all I could find is how to write code in those styles, not how to use those techniques for writing interpreter.

Answer 1

You can always turn calls into jumps if you are able to hold call frame information somewhere else. That is what "stack externalising" refers to.

For your interpreter, your call frame data needs to hold the non-tail call's continuation (which may itself hold further references, such as to any variables it needs access to). You will need one call frame per active non-tail call.

All this does, of course, is trade stack space for heap space. In the end, you don't really save any memory this way. :-)