Программируемая исключение неконцевой рекурсии

Question

Я делаю переводчик Lisp в JavaScript. JS не имеет устранение хвост рекурсии (TRE), поэтому я реализовал TRE, используя в то время как цикл в JS (псевдокод):

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 

Так что я рад, и хвост рекурсивные функции, такие как следующий один не кончатся стека :

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

(+ 10000 1) ;=> 10001 

Однако функции, которые не являются хвостовой рекурсией, бегите из стека JS (потому что JS код рецидивирует слишком много на 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 

Как я имею дело с не-таи l-рекурсивные функции? Каковы варианты? Какие хорошие ресурсы? Я немного прочитал о батуте, стиле экстернализации стека и продолжении прохождения, но все, что я мог найти, - это написать код в этих стилях, а не как использовать эти методы для написания интерпретатора.

Answer 1

Вы можете всегда превращать вызовы в прыжки, если вы можете хранить информацию о кадре вызова в другом месте. Это то, к чему относится «экстернализация стека».

Для вашего переводчика ваши данные кадра вызова должны удерживать продолжение не-хвостового вызова (которое может содержать дополнительные ссылки, например любые переменные, к которым ему нужен доступ). Вам понадобится один кадр вызова для активного не-хвостового вызова.

Все это, конечно же, является пространством торгового стека для кучного пространства. В конце концов, вы действительно не сохраняете память таким образом. :-)