Élimination programmée de la récursivité sans queue

Question

Je fais un interpréteur Lisp jouet en JavaScript. JS n'a pas l'élimination de la récursion arrière (ERT), donc je mis en œuvre ERT en utilisant en boucle JS (pseudo-code):

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 

Je suis heureux, et les fonctions récursives queue comme celle qui suit ne manquent pas de pile :

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

(+ 10000 1) ;=> 10001 

Cependant, les fonctions qui ne sont pas récursive, à court de pile JS (parce que le code JS trop sur revient 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 

Comment puis-je traiter de la non-tai fonctions l-récursives? Quelles sont les options? Quelles sont les bonnes ressources? J'ai lu un peu sur le trampoline, l'extériorisation de pile et le style continuation-passing, mais tout ce que j'ai pu trouver c'est comment écrire du code dans ces styles, pas comment utiliser ces techniques pour écrire un interpréteur.

Answer 1

Vous pouvez toujours transformer les appels en sauts si vous êtes en mesure de conserver des informations de trame d'appel ailleurs. C'est ce que l'on appelle "externalisation de pile". Pour votre interprète, vos données de télégramme doivent contenir la continuation de l'appel sans queue (qui peut elle-même contenir d'autres références, telles que les variables auxquelles il doit avoir accès). Vous aurez besoin d'une trame d'appel par appel non-stop actif.

Tout ceci, bien sûr, est l'espace de pile de commerce pour l'espace de tas. En fin de compte, vous ne sauvegardez pas vraiment de mémoire de cette façon. :-)