Come implementare le chiamate di coda in un costume VM

Question

Come faccio a implementare le chiamate di coda in una macchina virtuale personalizzata?

Lo so che ho bisogno di pop off di stack locale della funzione originale, allora è argomenti, quindi spingere sui nuovi argomenti. Ma, se ho pop fuori dello stack locale della funzione, come faccio a spingere sui nuovi argomenti? Sono stati appena estratto dallo stack.

Answer 1

Do per scontato che stiamo discutendo di una tradizionale macchina virtuale "stack-based" qui.

È pop off di stack locale della funzione corrente preservare le parti ancora rilevanti nei non-stack "registri" (dove le "parti interessate" sono, chiaramente, l'argomento per la prossima chiamata coda ricorsiva ), poi (una volta che tutti gli argomenti stack e locali della funzione vengono eliminati) si spingono gli argomenti per la chiamata ricorsiva. Per esempio, si supponga che la funzione che state ottimizzando è qualcosa di simile:

def aux(n, tot):
  if n <= 1: return tot
  return aux(n-1, tot * n)

che senza ottimizzazione potrebbe produrre bytecode simbolicamente come:

AUX:   LOAD_VAR   N
       LOAD_CONST 1
       COMPARE
       JUMPIF_GT  LAB
       LOAD_VAR   TOT
       RETURN_VAL
LAB:   LOAD_VAR   N
       LOAD_CONST 1
       SUBTRACT
       LOAD_VAR   TOT
       LOAD_VAR   N
       MULTIPLY
       CALL_FUN2  AUX
       RETURN_VAL

i mezzi CALL_FUN2 "chiamare una funzione con due argomenti". Con l'ottimizzazione, potrebbe diventare a volte come:

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

Naturalmente sto facendo le mie bytecode simbolici come vado avanti, ma spero che l'intento è chiaro: POP_DISCARD n è la comparsa normale che appena scarta le voci top n dalla pila, ma POP_KEEP n è una variante che li tiene "qualche parte" (ad esempio in un ausiliario della pila non direttamente accessibili per l'applicazione, ma solo proprio macchinario della VM - stoccaggio con tale carattere un è talvolta chiamato "registro" quando si parla di attuazione VM) e un PUSH_KEPT n di corrispondenza che svuota i "registri "indietro nella pila normale del VM.

Answer 2

credo che tu stia guardando questo nel modo sbagliato. Invece di schioccare le vecchie variabili dallo stack e quindi spingere le nuove, è sufficiente riassegnare quelli già presenti (attenzione). Questo è più o meno lo stesso di ottimizzazione che accadrebbe se si riscritto il codice per essere l'algoritmo iterativo equivalente.

Per questo codice:

 int fact(int x, int total=1) {
     if (x == 1)
         return total;
     return fact(x-1, total*x);
 }

sarebbe

 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total
 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
   jmp fact               #"recurse"

Non c'è bisogno di pop o nulla spinta in pila, semplicemente Riassegna.
Chiaramente, questo può essere ulteriormente ottimizzata, mettendo la condizione di uscita secondo, che ci permette di saltare un salto, con conseguente minor numero operazioni.

 fact_cont:               # update variables for "recursion
   mul total,x,total      # total=total*x
   sub x,1,x              # x=x-1
 fact:
   jmpne x, 1, fact_cont  # if x!=1 jump to multiply
   retrn total            # return total

In cerca di nuovo, questa "assemblea" riflette meglio questo C ++, che chiaramente ha evitato le chiamate di ricorsione

int fact(int x, int total=1)
    for( ; x>1; --x)
        total*=x;
    return total;
}