Czy są zoptymalizowane jakiekolwiek wywołania ogonowe silników JavaScript (TCO)?

91

Mam rekurencyjny algorytm znajdowania ścieżki ogona, który zaimplementowałem w JavaScript i chciałbym wiedzieć, czy którakolwiek (wszystkie?) Przeglądarki prawdopodobnie otrzymają wyjątki przepełnienia stosu.

javascript functional-programming tail-recursion clofresh
źródło
2
Czy jest to faktycznie algorytm rekurencyjny, czy też iteracyjny algorytm zaimplementowany z rekurencją? Rozumiem, że TCO może pomóc tylko w tym drugim przypadku.
nmichaels,
1
Chcę tylko dodać, że TCO nie onlyjest optymalizacją. Obsługa tego powinna być częścią specyfikacji języka, a nie kompilatorem / interpretatorem, ponieważ kod napisany dla jednego interpretera / kompilatora z TCO prawdopodobnie nie działałby na interpretatorze / kompilatorze bez TCO.
Hoffmann
1
Możesz zobaczyć bieżące wsparcie i obserwować, jak zmienia się w różnych silnikach w tabeli kompatybilności Kangax ES6 tutaj: kangax.github.io/compat-table/es6/…
Roy Tinker

Odpowiedzi:

47

Specyfikacja ECMAScript 4 pierwotnie miała dodać obsługę TCO, ale została odrzucona:

Nigdy więcej wywołań ogonowych w JavaScript?

O ile mi wiadomo, żadne powszechnie dostępne implementacje JavaScript nie zapewniają obecnie automatycznego TCO. Może się to jednak przydać:

Tail Call Optimization

Zasadniczo użycie wzorca akumulatorowego daje ten sam efekt.

Tim Sylvester
źródło
1
Tylko do Twojej wiadomości, Rhino ma automatyczny całkowity koszt posiadania wraz z kontynuacjami w trybie „interpretowanym” (opt = -1) wiki.apache.org/cocoon/RhinoWithContinuations
Mark Porter
5
(przepraszam za trollowanie) ECMAScript 6 uwzględnił TCO, określany w specyfikacji jako Proper Tail Calls.
mroźny
@sclv: Jakie jest odniesienie do trampoliny?
bukzor
39
Wzorzec akumulatora nie daje tego samego efektu co całkowity koszt posiadania. Po prostu przekształca algorytmy rekurencyjne w formę rekurencyjną ogonową. Jest to warunek wstępny, aby TCO był możliwy, ale nie zastępuje go. Nadal będziesz wysadzać stos w języku, który nie optymalizuje wywołań ogonowych.
Marcelo Cantos
„żadne szeroko dostępne implementacje JS obecnie nie wykonują automatycznego TCO” jest to niepoprawne od węzła 6.2.0, jeśli przekażesz odpowiednią flagę
Janus Troelsen
26

W tej chwili nie ma radości, ale na szczęście Harmony (wersja 6 ECMAScript) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls ma na szczęście właściwe wywołania ogonowe

Panie Marszałku
źródło
1
@MarkWilbur Pytanie dotyczyło w szczególności przeglądarek , a nie wszystkich istniejących implementacji ECMAScript.
Bezużyteczny kod
1
@UselessCode Nie, to pytanie dotyczy „silników Javascript”, więc ... nie tylko przeglądarek
BT
1
@BT Rzeczywiście istnieje wiele środowisk JS innych niż przeglądarki, a tytuł używa bardziej ogólnych "silników Javascript", ale treść pytania określa "... chciałbym wiedzieć, czy którakolwiek (wszystkie?) Przeglądarki prawdopodobnie otrzymałyby stos wyjątki dotyczące przepełnienia ”.
Bezużyteczny kod,
Muszę sprzeciwić się „ale tytuł mówi…”. Myślę, że ponieważ wspomina oba, pytanie dotyczy obu. Ale masz rację, jeśli mówisz, że nie oznacza to, że odpowiedź jest nieaktualna.
BT,
4
@MarkWilbur O ile wiem, węzeł używa tej samej wersji v8 co chrome - która obecnie nie obsługuje TCO. Miałem sedno sprawy z JS i zoptymalizowanym asemblerem, który produkuje obecny V8 - gist.github.com/mcfedr / 832e3553964a014621d5
mcfedr
12

Prawie każda przeglądarka, którą napotkasz, będzie borykać się z „zbyt dużą rekurencją”. Oto wpis w narzędziu do śledzenia błędów V8 , który prawdopodobnie będzie interesującą lekturą.

Jeśli jest to prosta rekursja własna, prawdopodobnie warto spróbować użyć jawnej iteracji, zamiast mieć nadzieję na eliminację wywołań ogonowych.

Hank Gay
źródło
Błąd został ostatecznie zaakceptowany. Jest pod eposem: „Feature Request Harmony”. Miejmy nadzieję, że oznacza to, że planują dodać go do obsługi ES6 w V8.
Txangel
Możesz głosować na wsparcie TCO w przeglądarce Internet Explorer tutaj: wpdev.uservoice.com/forums/257854-internet-explorer-platform/…
Roy Tinker
12

Optymalizacja połączeń końcowych będzie obsługiwana w trybie ścisłym ECMAScript 6 w przyszłości. Sprawdzić http://www.2ality.com/2015/06/tail-call-optimization.html szczegóły.

Sprawdź http://kangax.github.io/compat-table/es6/, aby uzyskać aktualne wsparcie dla silnika.

W tej chwili (18-07-2019) następujące silniki obsługują optymalizację połączeń ogonowych:

  • Safari> = 10
  • iOS> = 10
  • Kinoma XS6
  • Duktape 2.3

obsługa, jeśli „eksperymentalne funkcje JavaScript” są włączone:

  • Węzeł 6.5
  • Chrome 54 / Opera 41 Aktualna wersja tabeli kompatybilności już jej nie wymienia
Simon Zyx
źródło
3

Optymalizacja wywołań ogona jest teraz dostępna w LispyScript, który kompiluje się do JavaScript. Więcej na ten temat przeczytasz tutaj .

Santosh
źródło
A co z wzajemną rekurencją?
kot
2

Obecnie żadna implementacja JavaScript nie rozpoznaje rekurencji ogonowej. Zmiany są wprowadzane w ECMAScript 6 , i jak powiedzieli inni, jest otwarty bilet na V8 .

Tutaj możesz zobaczyć wygenerowany asembler V8 dla funkcji rekurencyjnej ogona:

Przykład tego, jak V8 kompiluje rekursję

Porównaj to z tym, jak Clang skompilował tę samą funkcję w C

Przykład rekurencji ogona kompilatora C.

V8 zachowuje wywołanie rekurencyjne, podczas gdy kompilator C rozpoznał rekurencję ogonową i zmienił ją w pętlę.

mcfedr
źródło
„Obecnie żadna implementacja JS nie rozpoznaje rekurencji ogonowej”. to jest niepoprawne w węźle 6.2.0, ale musisz przekazać flagę
Janus Troelsen