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

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