Wie Endrekursion in einer benutzerdefinierten VM implementieren

Question

Wie kann ich Endaufruf in einer benutzerdefinierten virtuellen Maschine implementieren?

Ich weiß, dass ich die ursprüngliche Funktion der lokalen Stack abspringt, dann ist es Argumente, dann auf die neuen Argumente schieben. Aber, wenn ich aus der Funktion der lokalen Stack Pop, wie soll ich auf die neuen Argumente schieben? Sie haben gerade aus dem Stapel genommen wurde.

Answer 1

Ich gehe davon aus, dass wir eine traditionelle „Stack-basierte“ virtuelle Maschine hier sind zu diskutieren.

Sie Pop-off der aktuellen Funktion des lokalen Stack Erhaltung der noch relevanten Teile in nicht-Stack „Register“ (wo die „relevanten Teile“ sind, klar, das Argument für die bevorstehende rekursive Endrekursion ), dann (einmal alle lokalen Stack und Argumente der Funktion bereinigt werden) können Sie die Argumente für den rekursiven Aufruf drücken. Beispiel: Angenommen, die Funktion, die Sie Optimierung ist so etwas wie:

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

, die ohne Optimierung könnte Byte-Code symbolisch wie produzieren:

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

die CALL_FUN2 Mittel „nennen eine Funktion mit zwei Argumenten“. Mit der Optimierung könnte es irgendwann wie werden:

   POP_KEEP     2
   POP_DISCARD  2
   PUSH_KEPT    2
   JUMP         AUX

Natürlich mache mich auf meine symbolischen Bytecode wie ich mitgehen, aber ich hoffe, dass es die Absicht ist klar: POP_DISCARD n der normale Pop ist, dass nur verwirft die oben n Einträge aus dem Stapel, aber POP_KEEP n eine Variante ist, die sie hält „irgendwo“ (zB in einem Hilfsstapel nicht direkt zugänglich für die Anwendung, sondern nur auf die eigenen Maschinen VM - Speicher mit einem solchen Charakter wird manchmal als „ein Register“ genannt, wenn VM Implementierung diskutiert) und eine passende PUSH_KEPT n, die die „Register leert "wieder in den normalen Stack des VM.

Answer 2

Ich glaube, du bist gerade mitten in dieser dem falschen Weg. Anstatt die alten Variablen von dem Stapel knallte und dann die neuen drängen, einfach die, die neu zuweisen schon da (vorsichtig). Dies ist in etwa die gleiche Optimierung, das würde passieren, wenn Sie den Code neu geschrieben entsprechen iterativer Algorithmus sein.

Für diesen Code:

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

wäre

 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"

Es gibt keine Notwendigkeit oder Push etwas auf dem Stapel Pop, lediglich neu zuweisen.
Natürlich kann diese weiter optimiert werden, indem die Ausgangsbedingung zweiten setzen, so dass wir einen Sprung überspringen, in weniger Operationen zur Folge hat.

 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

wieder Sehen, diese „Versammlung“ spiegelt besser, diese C ++, die eindeutig die Rekursion Anrufe vermieden hat

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