Ich habe einen Tail-rekursiven Pathfinding-Algorithmus, den ich in Javascript implementiert habe und würde gerne wissen, ob irgendwelche (alle?) Browser möglicherweise Stapelüberlauf-Ausnahmen bekommen würden.Sind Javascript Engine-Tail Calls optimiert?
Die ECMAScript 4 spec würde ursprünglich Unterstützung für TCO hinzufügen, aber es wurde fallen gelassen.
http://lambda-the-ultimate.org/node/3047
Soweit ich weiß, keine weithin verfügbaren Implementierungen von JS derzeit tun automatische TCO. Dies kann allerdings zu Ihnen, von Nutzen sein:
http://www.paulbarry.com/articles/2009/08/30/tail-call-optimization
Wesentlichen mit dem Akkumulator Muster den gleichen Effekt zu erreichen.
Oder benutzen Sie einfach ein Trampolin. .. – sclv
Nur ein FYI, Rhino hat automatische TCO zusammen mit Fortsetzungen im "interpretierten" Modus (opt = -1) http://wiki.apache.org/cocoon/RhinoWithContinuations –
(Entschuldigung für Trolling) ECMAScript 6 hat TCO enthalten, in der Spezifikation als Tail Calls bezeichnet. – frosty
ziemlich jeder Browser Sie auf „zu viel Rekursion“ wird barf begegnen. Hier ist eine entry in the V8 bug tracker, die wahrscheinlich interessant zu lesen sein wird.
Wenn es einfach selbst Rekursion, ist es wahrscheinlich die Mühe wert explizite Iteration zu verwenden, anstatt Tail-Call-Eliminierung erhofft.
Der Fehler wurde endlich akzeptiert. Es steht unter dem Epos: "Feature Request Harmony". Hoffentlich bedeutet das, dass sie planen, ES6-Unterstützung in V8 hinzuzufügen. – Txangel
Sie können im Internet Explorer für die TCO-Unterstützung stimmen: https://wpdev.uservoice.com/forums/257854-internet-explorer-platform/suggestions/6850816-es6-tail-call-optimization –
Keine Freude für den Moment, aber zum Glück sind richtige Endaufruf für Harmony (ECMAScript Version 6) geplant ist http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls
@MarkWilbur Die Frage war speziell über _browser_, nicht alle vorhandenen Implementierungen von ECMAScript. –
@UselessCode Nein, diese Frage bezieht sich auf "Javascript-Engines", also ... nicht nur auf Browser –
@BT Es gibt tatsächlich viele Nicht-Browser-JS-Umgebungen, und der Titel verwendet die allgemeineren "Javascript-Engines", aber den Hauptteil des Frage spezifiziert "... würde gerne wissen, ob irgendwelche (alle?) ** Browser ** Stapelüberlauf-Ausnahmen erhalten könnten." –
Endaufruf Optimierung jetzt in LispyScript zur Verfügung, die auf Javascript kompiliert. Sie können mehr darüber lesen here.
Was ist mit wechselseitiger Rekursion? – cat
Momentan erkennen keine JS-Implementierungen die Tail-Rekursion. Änderungen sind in ECMAScript 6, hergestellt und wie andere gesagt haben, gibt es ein offenes Ticket auf V8
Hier können Sie sehen V8 erzeugt Assembler für eine Endrekursion Funktion
https://gist.github.com/mcfedr/832e3553964a014621d5
Vergleichen Sie das mit, wie Klirren hat die gleiche Funktion in C kompilierten
https://gist.github.com/mcfedr/63ad08370d856bad3694
V8 den rekursiven Aufruf behält, während die C-Compiler die Endrekursion und verändert es i erkannt hat nto eine Schleife
"Derzeit erkennen keine JS-Implementierungen die Tail-Rekursion." das ist falsch wie bei Knoten 6.2.0, aber du musst eine Flagge bestehen –
Endaufruf Optimierung wird in ECMAScript 6 Strict-Modus in Zukunft unterstützt werden. Überprüfen Sie http://www.2ality.com/2015/06/tail-call-optimization.html für Details.
prüfen http://kangax.github.io/compat-table/es6/ für aktuelle Motorunterstützung.
Im Moment (2018.05.01) die Unterstützung Schwanz folgenden Motoren Call-Optimierung:
Unterstützung, wenn „experimental JavaScript-Funktionen "-Flag ist eingeschaltet:
Ist es Liste tatsächlich ein rekursive Algorithmus oder ein iterativer Algorithmus mit Rekursion implementiert? Mein Verständnis ist, dass TCO nur mit letzterem helfen kann. – nmichaels
Ich möchte nur hinzufügen, dass TCO nicht "nur" eine Optimierung ist. Es sollte Teil der Sprachspezifikation sein, nicht der Compiler/Interpreter, da Code, der gegen einen Interpreter/Compiler mit TCO geschrieben wurde, wahrscheinlich nicht mit einem Interpreter/Compiler ohne TCO arbeiten würde. – Hoffmann
Sie können die aktuelle Unterstützung sehen und beobachten, wie sie in der ES6-Kompatibilitäts-Tabelle von Kangax in Engines entwickelt wird: http://kangax.github.io/compat-table/es6/#proper_tail_calls_(tail_call_optimization) –