Wie verstehe ich Trampolin in JavaScript?


0 Answers

Das Trampolin ist nur eine Technik, um die Rekursion zu optimieren und Stack-Overflow-Ausnahmen in Sprachen zu verhindern, die keine tail call optimization wie Javascript ES5-Implementierung und C # unterstützen. ES6 wird jedoch wahrscheinlich Unterstützung für die Tail-Call-Optimierung haben.

Das Problem bei der regulären Rekursion besteht darin, dass jeder rekursive Aufruf dem Aufruf-Stack einen Stapelrahmen hinzufügt, den Sie als eine Pyramide von Aufrufen visualisieren können. Hier ist eine Visualisierung des rekursiven Aufrufs einer faktoriellen Funktion:

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0)))) 
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Hier ist eine Visualisierung des Stapels, wobei jeder vertikale Strich ein Stapelrahmen ist:

         ---|---
      ---|     |---
   ---|            |--- 
---                    ---

Das Problem besteht darin, dass der Stapel eine begrenzte Größe hat und das Stapeln dieser Stapelrahmen den Stapel überlaufen lassen kann. Abhängig von der Stapelgröße würde eine Berechnung eines größeren Faktors den Stapel überlaufen lassen. Daher kann eine reguläre Rekursion in C #, Javascript etc. als gefährlich angesehen werden .

Ein optimales Ausführungsmodell wäre etwas wie ein Trampolin anstelle einer Pyramide, wobei jeder rekursive Aufruf an Ort und Stelle ausgeführt wird und nicht auf dem Aufrufstapel gestapelt wird. Diese Ausführung in Sprachen, die die Optimierung von Endanrufen unterstützen, könnte folgendermaßen aussehen:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Sie können den Stapel wie ein hüpfendes Trampolin visualisieren:

   ---|---   ---|---   ---|---
---      ---       ---       

Dies ist deutlich besser, da der Stapel immer nur einen Rahmen hat und man aus der Visualisierung auch sehen kann, warum es ein Trampolin genannt wird. Dies verhindert, dass der Stapel überläuft.

Da wir in Javascript nicht den Luxus der tail call optimization , müssen wir einen Weg finden, um aus der regulären Rekursion eine optimierte Version zu machen, die in Trampolin-Mode ausgeführt wird.

Ein naheliegender Weg besteht darin , die Rekursion loszuwerden und den Code als iterativ neu zu schreiben.

Wenn das nicht möglich ist, brauchen wir etwas komplexeren Code, wo wir statt der rekursiven Schritte higher order functions , um eine Wrapper-Funktion zurückzugeben, anstatt den rekursiven Schritt direkt auszuführen, und eine andere Funktion die Ausführung steuern lässt.

In Ihrem Beispiel wickelt die Wiederholungsfunktion den regulären rekursiven Aufruf mit einer Funktion ab und gibt diese Funktion zurück, anstatt den rekursiven Aufruf auszuführen:

function repeat(operation, num) {
    return function() {
       if (num <= 0) return
       operation()
       return repeat(operation, --num)
    }
}

Die zurückgegebene Funktion ist der nächste Schritt der rekursiven Ausführung und das Trampolin ist ein Mechanismus, um diese Schritte in der while-Schleife kontrolliert und iterativ auszuführen:

function trampoline(fn) {
    while(fn && typeof fn === 'function') {
        fn = fn()
    }
}

Der einzige Zweck der Trampolin-Funktion besteht also darin, die Ausführung iterativ zu steuern und sicherzustellen, dass der Stapel zu jedem gegebenen Zeitpunkt nur einen einzigen Stapelrahmen auf dem Stapel hat.

Die Verwendung eines Trampolins ist offensichtlich weniger leistungsfähig als eine einfache Rekursion, da Sie den normalen rekursiven Fluss "blockieren", aber es ist viel sicherer.

http://en.wikipedia.org/wiki/Tail_call

http://en.wikipedia.org/wiki/Trampoline_%28computing%29

Question

Hier ist der Code:

function repeat(operation, num) {
  return function() {
    if (num <= 0) return
    operation()
    return repeat(operation, --num)
  }
}

function trampoline(fn) {
  while(fn && typeof fn === 'function') {
    fn = fn()
  }
}

module.exports = function(operation, num) {
  trampoline(function() {
    return repeat(operation, num)
  })
}

Ich habe gelesen, dass das Trampolin benutzt wird, um mit Überlaufproblemen fertig zu werden, also würde die Funktion nicht nur den Anruf selbst und den Stack hochhalten.

Aber wie funktioniert dieses Snippet? Vor allem die trampoline Funktion? Was hat es genau while und wie hat es sein Ziel erreicht?

Danke für jede Hilfe :)






Related