Während der letzten Diskussionen bei der Arbeit bezog sich jemand auf eine Trampolinfunktion.
Ich habe die Beschreibung bei Wikipedia gelesen . Es reicht aus, einen allgemeinen Überblick über die Funktionalität zu geben, aber ich möchte etwas Konkreteres.
Haben Sie einen einfachen Codeausschnitt, der ein Trampolin illustriert?
Antworten:
Es gibt auch den LISP-Sinn für "Trampolin", wie auf Wikipedia beschrieben:
Nehmen wir an, wir verwenden Javascript und möchten die naive Fibonacci-Funktion im Continuation-Passing-Stil schreiben. Der Grund, warum wir dies tun würden, ist nicht relevant - zum Beispiel, um Scheme auf JS zu portieren oder um mit CPS zu spielen, das wir sowieso verwenden müssen, um serverseitige Funktionen aufzurufen.
Der erste Versuch ist also
Wenn Sie dies jedoch
n = 25
in Firefox ausführen, wird der Fehler "Zu viel Rekursion!" Angezeigt. Dies ist genau das Problem (fehlende Tail-Call-Optimierung in Javascript), das Trampolin löst. Anstatt eine Funktion (rekursiv) aufzurufen, geben wirreturn
eine Anweisung (thunk) an, um diese Funktion aufzurufen und in einer Schleife zu interpretieren.quelle
Lassen Sie mich einige Beispiele für die mit Trampolinen implementierte Fakultätsfunktion in verschiedenen Sprachen hinzufügen:
Scala:
Java:
C (Pech ohne Implementierung großer Zahlen):
quelle
if (n < 2) Done(product)
, SO erlaubte mir nicht, 1 Symbol zu bearbeiten ...Ich gebe Ihnen ein Beispiel, das ich in einem Anti-Cheat-Patch für ein Online-Spiel verwendet habe.
Ich musste in der Lage sein, alle Dateien, die vom Spiel geladen wurden, auf Änderungen zu scannen. Der robusteste Weg, dies zu tun, war die Verwendung eines Trampolins für CreateFileA. Wenn das Spiel gestartet wurde, fand ich die Adresse für CreateFileA mithilfe von GetProcAddress, änderte dann die ersten Bytes der Funktion und fügte Assembler-Code ein, der zu meiner eigenen "Trampolin" -Funktion springen würde, wo ich einige Dinge tun würde, und dann würde ich nach meinem jmp-Code zum nächsten Speicherort in CreateFile zurückspringen. Es ist etwas schwieriger, dies zuverlässig zu tun, aber das Grundkonzept besteht darin, nur eine Funktion zu verknüpfen, sie zu zwingen, zu einer anderen Funktion umzuleiten, und dann zur ursprünglichen Funktion zurückzukehren.
Bearbeiten: Microsoft hat ein Framework für diese Art von Dingen, die Sie betrachten können. genannt Detours
quelle
Ich experimentiere derzeit mit Möglichkeiten zur Implementierung der Tail-Call-Optimierung für einen Scheme-Interpreter. Daher versuche ich im Moment herauszufinden, ob das Trampolin für mich machbar wäre.
Soweit ich weiß, handelt es sich im Grunde genommen nur um eine Reihe von Funktionsaufrufen, die von einer Trampolinfunktion ausgeführt werden. Jede Funktion wird als Thunk bezeichnet und gibt den nächsten Schritt in der Berechnung zurück, bis das Programm beendet wird (leere Fortsetzung).
Hier ist der erste Code, den ich geschrieben habe, um mein Verständnis des Trampolins zu verbessern:
Ergebnisse in:
quelle
Hier ist ein Beispiel für verschachtelte Funktionen:
compar
kann keine externe Funktion sein, da sie verwendetnbytes
, die nur während dessort_bytes
Aufrufs vorhanden ist. Bei einigen Architekturen wird zur Laufzeit eine kleine Stub-Funktion - das Trampolin - generiert, die den Stapelspeicherort des aktuellen Aufrufs von enthältsort_bytes
. Beim Aufruf springt es zumcompar
Code und übergibt diese Adresse.Dieses Durcheinander ist bei Architekturen wie PowerPC nicht erforderlich, bei denen der ABI angibt, dass ein Funktionszeiger tatsächlich ein "fetter Zeiger" ist, eine Struktur, die sowohl einen Zeiger auf den ausführbaren Code als auch einen weiteren Zeiger auf Daten enthält. Unter x86 ist ein Funktionszeiger jedoch nur ein Zeiger.
quelle
Für C wäre ein Trampolin ein Funktionszeiger:
Bearbeiten: Esoterischere Trampoline würden implizit vom Compiler generiert. Eine solche Verwendung wäre ein Sprungtisch. (Obwohl es deutlich kompliziertere gibt, versuchen Sie weiter unten, komplizierten Code zu generieren.)
quelle
Jetzt, da C # über lokale Funktionen verfügt , kann die Bowling Game-Codierungskata elegant mit einem Trampolin gelöst werden:
Die Methode
Game.RollMany
wird mit einer Anzahl von Rollen aufgerufen: normalerweise 20 Rollen, wenn keine Ersatzteile oder Schläge vorhanden sind.Die erste Zeile ruft sofort die Trampolinfunktion auf :
return Trampoline(1, 0, rs.ToList());
. Diese lokale Funktion durchläuft rekursiv das Rollenarray. Die lokale Funktion (das Trampolin) ermöglicht es der Durchquerung, mit zwei zusätzlichen Werten zu beginnen: Start mitframe
1 undrsf
(bisheriges Ergebnis) 0.Innerhalb der lokalen Funktion gibt es einen ternären Operator, der fünf Fälle behandelt:
Die Fortsetzung des Durchlaufs erfolgt durch erneutes Aufrufen des Trampolins, jetzt jedoch mit aktualisierten Werten.
Weitere Informationen finden Sie unter: " Schwanzrekursionsakkumulator ". Beachten Sie, dass der Compiler die Schwanzrekursion nicht optimiert. So elegant diese Lösung auch sein mag, es wird wahrscheinlich nicht das Fasten sein.
quelle
quelle