Warum arbeiten Trampoline?

104

Ich habe ein funktionierendes JavaScript erstellt. Ich hatte gedacht, dass die Tail-Call-Optimierung implementiert wurde, aber wie sich herausstellte, habe ich mich geirrt. So musste ich mir Trampolinspringen beibringen . Nachdem ich hier und anderswo ein bisschen gelesen hatte, konnte ich die Grundlagen erläutern und mein erstes Trampolin bauen:

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

function loopy(x){
    if (x<10000000){ 
        return function(){
            return loopy(x+1)
        }
    }else{
        return x;
    }
};

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

Mein größtes Problem ist, dass ich nicht weiß, warum das funktioniert. Ich habe die Idee, die Funktion in einer while-Schleife erneut auszuführen, anstatt eine rekursive Schleife zu verwenden. Ausgenommen, technisch gesehen hat meine Basisfunktion bereits eine rekursive Schleife. Ich führe die loopyBasisfunktion nicht aus, aber ich führe die Funktion darin aus. Was hindert Sie foo = foo()daran, einen Stapelüberlauf zu verursachen? Und ist foo = foo()technisch nicht mutierend oder fehlt mir etwas? Vielleicht ist es nur ein notwendiges Übel. Oder eine Syntax, die mir fehlt.

Gibt es überhaupt eine Möglichkeit, das zu verstehen? Oder ist es nur ein Hack, der irgendwie funktioniert? Ich konnte alles andere durchstehen, aber dieser hat mich verwirrt.

Ucenna
quelle
5
Ja, aber das ist immer noch Rekursion. loopyläuft nicht über, weil es sich nicht selbst nennt .
Tkausl
4
"Ich hatte gedacht, dass TCO implementiert wurde, aber wie sich herausstellte, habe ich mich geirrt." In den meisten Szenarien war dies zumindest in V8 der Fall. Sie können es beispielsweise in jeder neueren Version von Node verwenden, indem Sie Node mitteilen , dass es in V8 aktiviert werden soll : stackoverflow.com/a/30369729/157247 Chrome hat es (hinter einem "experimentellen" Flag) seit Chrome 51.
TJ Crowder,
125
Die kinetische Energie des Benutzers wird in elastische potentielle Energie umgewandelt, wenn das Trampolin nachgibt, und dann zurück in kinetische Energie, wenn es zurückprallt.
immibis
66
@immibis, Im Namen aller, die hierher gekommen sind, ohne zu überprüfen, um welche Stack Exchange-Site es sich handelt, vielen Dank.
user1717828
4
@jpaugh meintest du "hüpfen"? ;-)
Hulk

Antworten:

89

Der Grund, warum Ihr Gehirn gegen die Funktion rebelliert loopy(), ist der inkonsistente Typ :

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

Viele Sprachen lassen Sie nicht einmal solche Dinge tun oder verlangen zumindest viel mehr Tipparbeit, um zu erklären, wie dies Sinn machen soll. Weil es das wirklich nicht tut. Funktionen und Ganzzahlen sind völlig unterschiedliche Arten von Objekten.

Lassen Sie uns diese while-Schleife sorgfältig durchgehen:

while(foo && typeof foo === 'function'){
    foo = foo();
}

Anfangs fooist gleich loopy(0). Was ist loopy(0)? Nun, es ist weniger als 10000000, also bekommen wir function(){return loopy(1)}. Das ist ein wahrer Wert, und es ist eine Funktion, so dass die Schleife weitergeht.

Nun kommen wir zu foo = foo(). foo()ist das gleiche wie loopy(1). Da 1 immer noch kleiner als 10000000 ist, gibt function(){return loopy(2)}dies zurück , dem wir dann zuweisen foo.

fooist immer noch eine funktion, also machen wir weiter ... bis irgendwann foo gleich ist function(){return loopy(10000000)}. Das ist eine Funktion, also machen wir noch foo = foo()einmal, aber dieses Mal, wenn wir anrufen loopy(10000000), ist x nicht kleiner als 10000000, also bekommen wir einfach x zurück. Da 10000000 ebenfalls keine Funktion ist, wird auch die while-Schleife beendet.

Kevin
quelle
1
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Yannis
Es ist wirklich nur eine Summenart. Manchmal auch als Variante bekannt. Dynamische Sprachen unterstützen sie ziemlich einfach, da jeder Wert mit Tags versehen ist, während bei statisch typisierten Sprachen angegeben werden muss, dass die Funktion eine Variante zurückgibt. Trampoline sind beispielsweise in C ++ oder Haskell problemlos möglich.
GManNickG
2
@GManNickG: Ja, das habe ich mit "viel mehr Tippen" gemeint. In C müssten Sie eine Union deklarieren, eine Struktur deklarieren, die die Union markiert, die Struktur an beiden Enden packen und entpacken, die Union an beiden Enden packen und entpacken und (wahrscheinlich) herausfinden, wem der Speicher gehört, in dem sich die Struktur befindet . C ++ ist sehr wahrscheinlich weniger Code als das, aber konzeptionell nicht weniger kompliziert als C und es ist immer noch ausführlicher als das Javascript von OP.
Kevin
Klar, das bestreite ich nicht, ich denke nur, dass die Betonung, die Sie darauf legen, dass es seltsam ist oder keinen Sinn ergibt, ein bisschen stark ist. :)
GManNickG
173

Kevin erklärt kurz und bündig, wie dieses Codefragment funktioniert (und warum es ziemlich unverständlich ist), aber ich wollte einige Informationen darüber hinzufügen, wie Trampoline im Allgemeinen funktionieren.

Ohne Tail-Call-Optimierung (TCO) fügt jeder Funktionsaufruf dem aktuellen Ausführungsstapel einen Stack-Frame hinzu . Angenommen, wir haben eine Funktion zum Ausdrucken eines Countdowns von Zahlen:

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

Wenn wir anrufen countdown(3), analysieren wir , wie der Aufrufstapel ohne TCO aussehen würde.

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

Mit TCO befindet sich jeder rekursive Aufruf an countdownin der Endposition (es bleibt nichts anderes zu tun, als das Ergebnis des Aufrufs zurückzugeben), sodass kein Stapelrahmen zugewiesen wird. Ohne TCO explodiert der Stapel sogar geringfügig n.

Mit Trampolin wird diese Einschränkung umgangen, indem ein Wrapper um die countdownFunktion eingefügt wird . Führt dann countdownkeine rekursiven Aufrufe durch und gibt stattdessen sofort eine aufzurufende Funktion zurück. Hier ist eine Beispielimplementierung:

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

Sehen wir uns den Aufrufstapel an, um einen besseren Überblick über die Funktionsweise zu erhalten:

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

Bei jedem Schritt die countdownHopFunktion verlässt direkte Kontrolle darüber , was als nächstes passiert, sondern eine Funktion der Rückkehr zu nennen das beschreibt , was es würde gerne nächstes passieren. Die Trampolin - Funktion nimmt dann diese und es nennt, dann ruft , was Funktion , die zurückgibt, und so weiter , bis es kein „nächster Schritt“ ist. Dies wird als Trampolin bezeichnet, da der Kontrollfluss zwischen jedem rekursiven Aufruf und der Trampolinimplementierung "springt", anstatt dass die Funktion direkt wiederholt wird. Durch den Verzicht Kontrolle darüber , wer macht den rekursiven Aufruf kann die Trampolin - Funktion Damit der Stapel nicht zu groß wird. Randnotiz: Bei dieser Implementierung werden der trampolineEinfachheit halber keine Werte zurückgegeben.

Es kann schwierig sein zu wissen, ob dies eine gute Idee ist. Die Leistung kann durch jeden Schritt, der einen neuen Abschluss zuweist, beeinträchtigt werden. Clevere Optimierungen können dies möglich machen, aber Sie werden es nie erfahren. Trampolinieren ist vor allem nützlich, um harte Rekursionsgrenzen zu umgehen, beispielsweise wenn eine Sprachimplementierung eine maximale Call-Stack-Größe festlegt.

Jack
quelle
18

Vielleicht wird es einfacher zu verstehen, wenn das Trampolin mit einem bestimmten Rückgabetyp implementiert ist (anstatt eine Funktion zu missbrauchen):

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

Vergleichen Sie dies mit Ihrer Version von trampoline, in der der Rekursionsfall ist, wenn die Funktion eine andere Funktion zurückgibt, und der Basisfall ist, wenn sie etwas anderes zurückgibt.

Was hindert Sie foo = foo()daran, einen Stapelüberlauf zu verursachen?

Es nennt sich nicht mehr. Stattdessen wird ein Ergebnis (in meiner Implementierung buchstäblich a Result) zurückgegeben, das angibt, ob die Rekursion fortgesetzt oder abgebrochen werden soll.

Und ist foo = foo()technisch nicht mutierend oder fehlt mir etwas? Vielleicht ist es nur ein notwendiges Übel.

Ja, das ist genau das notwendige Übel der Schleife. Man könnte auch trampolineohne Mutation schreiben , aber es würde eine erneute Rekursion erfordern:

function trampoline(fn, x) {
    const res = fn(x);
    if (res instanceof Recurse)
        return trampoline(fn, res.arg);
    else if (res instanceof Return)
        return res.value;
}

Trotzdem zeigt es die Idee, was die Trampolinfunktion noch besser macht.

Der Punkt des Trampolierens ist das Abstrahieren des schwanzrekursiven Aufrufs von der Funktion, die die Rekursion in einen Rückgabewert verwenden möchte, und das Ausführen der tatsächlichen Rekursion an nur einer Stelle - der trampolineFunktion, die dann an einer einzelnen Stelle für die Verwendung von a optimiert werden kann Schleife.

Bergi
quelle
foo = foo()Dies ist eine Mutation im Sinne einer Änderung des lokalen Status, aber ich würde diese Neuzuweisung im Allgemeinen in Betracht ziehen, da Sie das zugrunde liegende Funktionsobjekt nicht ändern, sondern es durch die zurückgegebene Funktion (oder den zurückgegebenen Wert) ersetzen.
JAB
@JAB Ja, ich wollte nicht implizieren, dass der Wert, fooder die Variable enthält, geändert wird. Eine whileSchleife benötigt einen veränderlichen Zustand, wenn sie beendet werden soll, in diesem Fall die Variable foooder x.
Bergi
Ich habe so etwas vor einiger Zeit in dieser Antwort auf eine Stapelüberlauf-Frage über Schwanzrufoptimierung, Trampoline usw. gemacht
Joshua Taylor
2
Ihre Version ohne Mutation hat einen rekursiven Aufruf von fnin einen rekursiven Aufruf von konvertiert. trampolineIch bin nicht sicher, ob dies eine Verbesserung darstellt.
Michael Anderson
1
@MichaelAnderson Es soll nur die Abstraktion demonstrieren. Natürlich ist ein rekursives Trampolin nicht sinnvoll.
Bergi