Eliminazione programmatica della ricaduta senza coda

Question

Sto realizzando un interprete Lisp giocattolo in JavaScript. JS ha alcuna eliminazione ricorsione in coda (TRE), così ho implementato TRE utilizzando ciclo while a JS (pseudocodice):

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 

, quindi sono felice, e le funzioni di coda ricorsive come la seguente non a corto di pila :

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

(+ 10000 1) ;=> 10001 

Tuttavia, funzioni che non sono ricorsiva in coda, a corto di JS pila (perché il codice JS ricorre troppo su 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 

Come faccio a trattare con i non-tai funzioni ricorsive? Quali sono le opzioni? Quali sono le buone risorse? Ho letto un po 'di trampolino, stack esternalizzazione e stile di passaggio continuo, ma tutto quello che ho potuto trovare è come scrivere codice in quegli stili, non come usare quelle tecniche per scrivere interpreti.

Answer 1

È possibile sempre trasformare le chiamate in salti se si è in grado di mantenere le informazioni sulla cornice di chiamata da qualche altra parte. Questo è il significato di "stack externalizing".

Per l'interprete, i dati del frame di chiamata devono contenere la continuazione della chiamata non-tail (che può contenere ulteriori riferimenti, ad esempio a qualsiasi variabile a cui è necessario accedere). Avrai bisogno di un frame di chiamata per chiamata non a coda attiva.

Tutto ciò, ovviamente, è lo spazio dello stack di commercio per lo spazio heap. Alla fine, non si risparmia davvero memoria in questo modo. :-)