Za każdym razem, gdy pojawia się dyskusja na temat nowego języka programowania ukierunkowanego na JVM, nieuchronnie ludzie mówią takie rzeczy jak:
„JVM nie obsługuje optymalizacji wywołania ogona, więc przewiduję wiele eksplodujących stosów”
Istnieją tysiące odmian tego tematu.
Teraz wiem, że niektóre języki, na przykład Clojure, mają specjalną konstrukcję cykliczną , której można użyć.
Nie rozumiem tylko: na ile poważny jest brak optymalizacji wezwania ogona? Kiedy mam się tym martwić?
Moje główne źródło nieporozumień wynika prawdopodobnie z faktu, że Java jest jednym z najbardziej udanych języków w historii i całkiem sporo języków JVM wydaje się całkiem dobrze. Jak to możliwe, jeśli brak TCO naprawdę budzi jakiekolwiek obawy?
recursion
stack
stackoverflow
tail-call
Cedric Martin
źródło
źródło
GOTO
, JVM nie. A x86 nie jest używane jako platforma międzyoperacyjna. JVM nie ma,GOTO
a jednym z głównych powodów wyboru platformy Java jest interop. Jeśli chcesz wdrożyć TCO na JVM, musisz coś zrobić na stosie. Zarządzaj nim sam (tj. W ogóle nie używaj stosu wywołań JVM), używaj trampolin, używaj wyjątków jakoGOTO
, czegoś takiego. We wszystkich tych przypadkach stajesz się niezgodny ze stosem wywołań JVM. Nie można być kompatybilnym z Javą, mieć całkowity koszt posiadania i wysoką wydajność. Musisz poświęcić jedną z tych trzech.Odpowiedzi:
Zastanówmy się, powiedzmy, że pozbyliśmy się wszystkich pętli w Javie (autorzy kompilatora są na strike czy coś takiego). Teraz chcemy napisać silnię, abyśmy mogli naprawić coś takiego
Teraz czujemy się całkiem sprytni, udało nam się napisać naszą silnię nawet bez pętli! Ale kiedy testujemy, zauważamy, że przy każdej rozsądnej wielkości liczbowej pojawiają się błędy przepełnienia stosu, ponieważ nie ma TCO.
W prawdziwej Javie to nie jest problem. Jeśli kiedykolwiek będziemy mieli algorytm rekurencyjny, możemy przekształcić go w pętlę i wszystko będzie w porządku. A co z językami bez pętli? Więc jesteś po prostu węszony. Dlatego clojure ma tę
recur
formę, bez niej nawet nie jest ukończona (nie ma możliwości robienia nieskończonych pętli).Klasa języków funkcjonalnych, które są skierowane do JVM, Frege, Kawa (schemat), Clojure zawsze próbują poradzić sobie z brakiem wywołań ogonowych, ponieważ w tych językach TC jest idiomatycznym sposobem wykonywania pętli! Gdyby zostało przetłumaczone na Schemat, powyższy czynnik byłby dobrym silnikiem. Byłoby strasznie niewygodne, gdyby zapętlenie 5000 razy spowodowało awarię programu. Można to obejść, korzystając ze
recur
specjalnych formularzy, adnotacji wskazujących na optymalizację samodzielnych połączeń, trampoliny itp. Ale wszystkie wymuszają albo pogorszenie wydajności, albo niepotrzebną pracę programisty.Teraz Java też nie jest dostępna, ponieważ TCO to coś więcej niż rekurencja, co z funkcjami wzajemnie rekurencyjnymi? Nie można ich bezpośrednio przetłumaczyć na pętle, ale JVM ich nie optymalizuje. To sprawia, że spektakularnie nieprzyjemne jest pisanie algorytmów przy użyciu wzajemnej rekurencji przy użyciu Javy, ponieważ jeśli chcesz przyzwoitej wydajności / zasięgu, musisz wykonać czarną magię, aby dopasować ją do pętli.
Podsumowując, w wielu przypadkach nie jest to wielka sprawa. Większość wywołań ogonowych albo rozgrywa tylko jedną ramkę stosu, z takimi rzeczami
lub są rekurencyjne. Jednak w przypadku klasy TC, która do tego nie pasuje, każdy język JVM odczuwa ból.
Istnieje jednak dobry powód, dla którego nie mamy jeszcze TCO. JVM daje nam ślady stosu. Dzięki TCO systematycznie eliminujemy ramki stosów, o których wiemy, że są „skazane na zagładę”, ale JVM może chcieć ich później dla śledzenia stosu! Załóżmy, że wdrażamy taki FSM, w którym każdy stan wywołuje następny. Skasowalibyśmy wszystkie zapisy poprzednich stanów, aby śledzenie pokazało nam, jaki stan, ale nic o tym, jak się tam dostaliśmy.
Ponadto, co bardziej naglące, większość weryfikacji kodu bajtowego opiera się na stosie, eliminacja rzeczy, która pozwala nam zweryfikować kod bajtowy, nie jest przyjemną perspektywą. Pomiędzy tym a faktem, że Java ma pętle, TCO wygląda na więcej problemów niż jest to warte dla inżynierów JVM.
źródło
Optymalizacja wywołań ogonów jest ważna głównie ze względu na rekurencję ogonów. Istnieje jednak argument, dlaczego tak naprawdę dobrze, że JVM nie optymalizuje wywołań ogona: Ponieważ TCO ponownie wykorzystuje część stosu, ślad stosu z wyjątku będzie niekompletny, co utrudni debugowanie.
Istnieją sposoby obejścia ograniczeń JVM:
Może to wymagać większego przykładu. Rozważ język z zamknięciami (np. JavaScript lub podobny). Możemy zapisać silnię jako
Teraz możemy poprosić, aby zamiast tego oddzwonił:
Działa to teraz na stałym obszarze stosu, co jest trochę głupie, ponieważ i tak jest rekurencyjne. Jednak ta technika jest w stanie spłaszczyć wszystkie wezwania ogona do stałej przestrzeni stosu. A jeśli program jest w CPS, oznacza to, że całkowity stos wywołań jest stały (w CPS każde wywołanie jest wywołaniem ogonowym).
Główną wadą tej techniki jest to, że jest ona dużo trudniejsza do debugowania, nieco trudniejsza do wdrożenia i mniej wydajna - zobacz wszystkie zamknięcia i kierunki, których używam.
Z tych powodów byłoby znacznie lepiej, gdyby VM zaimplementowało języki ogowe wywołania ogona, takie jak Java, które mają dobre powody, aby nie obsługiwać połączeń ogonowych, nie musiałyby go używać.
źródło
return foo(....);
w metodziefoo
(2), oczywiście w pełni się zgadzają. Mimo to akceptujemy niepełne śledzenie z pętli, przypisań (!), Sekwencji instrukcji. Na przykład, jeśli znajdziesz nieoczekiwaną wartość w zmiennej, na pewno chcesz wiedzieć, jak się tam dostała. Ale w tym przypadku nie narzekasz na brakujące ślady. Ponieważ w jakiś sposób wyryte jest w naszych mózgach, że a) dzieje się to tylko podczas połączeń b) dzieje się to podczas wszystkich połączeń. Oba nie mają sensu, IMHO.Znaczna część połączeń w programie to wywołania ogonowe. Każdy podprogram ma ostatnie wywołanie, więc każdy podprogram ma co najmniej jedno wywołanie ogonowe. Wywołania ogona mają charakterystykę wydajności,
GOTO
ale bezpieczeństwo wywołania podprogramu.Posiadanie prawidłowych połączeń z ogonem umożliwia pisanie programów, których inaczej nie można napisać. Weźmy na przykład maszynę stanu. Automat stanów może być bardzo bezpośrednio zaimplementowany poprzez to, że każdy stan jest podprogramem, a każde przejście stanu jest wywołaniem podprogramu. W takim przypadku przechodzisz ze stanu do stanu, wykonując połączenie za połączeniem, a tak naprawdę nigdy nie wracasz! Bez prawidłowego wezwania ogona natychmiast zdmuchnąłbyś stos.
Bez PTC musisz używać
GOTO
trampolin lub wyjątków jako kontroli przepływu lub coś w tym rodzaju. Jest o wiele bardziej brzydsza, a nie bezpośrednia reprezentacja maszyny stanu 1: 1.(Zwróć uwagę, jak sprytnie uniknąłem nudnego przykładu „pętli”. Jest to przykład, w którym PTC są przydatne nawet w języku z pętlami).
Celowo użyłem tutaj terminu „Właściwe ogony” zamiast TCO. TCO to optymalizacja kompilatora. PTC to funkcja języka, która wymaga każdego kompilatora do wykonywania TCO.
źródło
The vast majority of calls in a program are tail calls.
Nie, jeśli „zdecydowana większość” wywoływanych metod wykonuje więcej niż jedno własne wywołanie.Every subroutine has a last call, so every subroutine has at least one tail call.
Jest to trywialnie wykazać jako fałszywareturn a + b
. (Chyba, że jesteś w jakimś szalonym języku, w którym podstawowe operacje arytmetyczne są oczywiście definiowane jako wywołania funkcji).Każdy, kto powie to: (1) nie rozumie optymalizacji wywołania ogona, lub (2) nie rozumie JVM, lub (3) jedno i drugie.
Zacznę od definicji wezwań ogonowych z Wikipedii (jeśli nie lubisz Wikipedii, oto alternatywa ):
W poniższym kodzie wezwanie do
bar()
jest wywołaniem końcowymfoo()
:Optymalizacja wywołania ogona ma miejsce, gdy implementacja języka, widząc wywołanie ogona, nie używa normalnego wywołania metody (która tworzy ramkę stosu), ale zamiast tego tworzy gałąź. Jest to optymalizacja, ponieważ ramka stosu wymaga pamięci i wymaga cykli procesora w celu wypchnięcia informacji (takich jak adres zwrotny) do ramki oraz ponieważ zakłada się, że para wywołania / powrotu wymaga więcej cykli procesora niż bezwarunkowy skok.
TCO jest często stosowane do rekurencji, ale to nie jest jedyne jej zastosowanie. Nie dotyczy to również wszystkich rekurencji. Prostego kodu rekurencyjnego do obliczania silni nie można na przykład zoptymalizować wywołania ogonowego, ponieważ ostatnią rzeczą, która dzieje się w funkcji, jest operacja mnożenia.
Aby wdrożyć optymalizację wezwania ogona, potrzebujesz dwóch rzeczy:
Otóż to. Jak zauważyłem gdzie indziej, JVM (jak każda inna architektura Turinga) ma goto. Zdarza się, że ma bezwarunkowe goto , ale funkcjonalność można łatwo zaimplementować za pomocą gałęzi warunkowej.
Fragment analizy statycznej jest trudny. W ramach jednej funkcji nie ma problemu. Na przykład, tutaj jest funkcja Scala rekurencyjna, która sumuje wartości w
List
:Ta funkcja zmienia się w następujący kod bajtowy:
Uwaga
goto 0
na końcu. Dla porównania równoważna funkcja Java (która musiIterator
naśladować zachowanie polegające na rozbiciu listy Scala na głowę i ogon) zamienia się w następujący kod bajtowy. Zauważ, że dwie ostatnie operacje są teraz invoke , po czym następuje wyraźny zwrot wartości wytworzonej przez to rekurencyjne wywołanie.Optymalizacja pojedynczego wywołania ogona jest banalna: kompilator widzi, że nie ma kodu, który wykorzystuje wynik wywołania, więc może zastąpić wywołanie przez
goto
.Życie staje się trudne, jeśli masz wiele metod. Instrukcje rozgałęziające JVM, w przeciwieństwie do instrukcji procesora ogólnego przeznaczenia, takiego jak 80x86, są ograniczone do jednej metody. Nadal jest to stosunkowo proste, jeśli masz metody prywatne: kompilator może dowolnie wstawiać te metody, więc może zoptymalizować wywołania ogona (jeśli zastanawiasz się, jak to może działać, rozważ wspólną metodę, która używa
switch
zachowania kontrolującego). Możesz nawet rozszerzyć tę technikę na wiele metod publicznych w tej samej klasie: kompilator wstawia ciała metod, udostępnia publiczne metody pomostowe, a wywołania wewnętrzne zamieniają się w skoki.Ale model ten psuje się, gdy weźmie się pod uwagę metody publiczne w różnych klasach, szczególnie w świetle interfejsów i programów ładujących klasy. Kompilator na poziomie źródła po prostu nie ma wystarczającej wiedzy, aby wdrożyć optymalizacje wywołania ogona. Jednak w odróżnieniu od implementacji typu „bare-metal” * JVM (posiada odpowiednie informacje, aby to zrobić, w formie kompilatora Hotspot (przynajmniej robi to kompilator ex-Sun). Nie wiem, czy faktycznie wykonuje optymalizacje wywołania ogona i nie podejrzewam, ale może .
Co prowadzi mnie do drugiej części twojego pytania, które sformułuję jako „czy powinno nas to obchodzić?”
Oczywiście, jeśli twój język używa rekurencji jako jedynej prymitywnej iteracji, zależy ci. Ale języki, które potrzebują tej funkcji, mogą ją zaimplementować; jedynym problemem jest to, czy kompilator dla wspomnianego języka może wytworzyć klasę, która może wywoływać i być wywoływana przez dowolną klasę Java.
Poza tym przypadkiem zapraszam głosujących, mówiąc, że to nie ma znaczenia. Większość kodu rekurencyjnego, który widziałem (i pracowałem z wieloma projektami graficznymi), nie można zoptymalizować . Podobnie jak prosta silnia, wykorzystuje rekurencję do budowania stanu, a operacja tail jest kombinacją.
W przypadku kodu, który można zoptymalizować za pomocą wywołania ogona, często łatwo jest przetłumaczyć ten kod na postać iterowalną. Na przykład
sum()
funkcję, którą pokazałem wcześniej, można uogólnić jakofoldLeft()
. Jeśli spojrzysz na źródło , zobaczysz, że jest ono faktycznie zaimplementowane jako operacja iteracyjna. Jörg W Mittag miał przykład maszyny stanów zaimplementowanej za pomocą wywołań funkcji; istnieje wiele wydajnych (i możliwych do utrzymania) implementacji maszyn stanów, które nie polegają na tłumaczeniu wywołań funkcji na skoki.Skończę z czymś zupełnie innym. Jeśli przejdziesz do Google od przypisów w SICP, możesz tu skończyć . Ja osobiście uważam, że znacznie ciekawsze miejsce niż o mój kompilator zastąpić
JSR
przezJUMP
.źródło
return foo(123);
mogłaby być lepiej wykonana przez wstawianiefoo
niż generowanie kodu do manipulowania stosem i wykonywania skoku, ale nie rozumiem, dlaczego wywołanie tail różni się od zwykłego wywołania w w związku z tym