Clojure nie wykonuje optymalizacji ogona na własną rękę: jeśli masz funkcję rekurencji ogona i chcesz ją zoptymalizować, musisz użyć specjalnej formy recur. Podobnie, jeśli masz dwie wzajemnie rekurencyjne funkcje, możesz je zoptymalizować tylko za pomocą trampoline.
Kompilator Scala jest w stanie wykonać TCO dla funkcji rekurencyjnej, ale nie dla dwóch wzajemnie rekurencyjnych funkcji.
Ilekroć czytałem o tych ograniczeniach, zawsze przypisywano im pewne ograniczenia właściwe dla modelu JVM. Prawie nic nie wiem o kompilatorach, ale to mnie trochę zastanawia. Pozwól mi wziąć przykład z Programming Scala. Tutaj funkcja
def approximate(guess: Double): Double =
if (isGoodEnough(guess)) guess
else approximate(improve(guess))jest przetłumaczone na
0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2Tak więc na poziomie kodu bajtowego wystarczy goto. W tym przypadku kompilator wykonuje ciężką pracę.
Jakie narzędzie bazowej maszyny wirtualnej pozwoliłoby kompilatorowi łatwiej obsługiwać TCO?
Na marginesie, nie spodziewałbym się, że rzeczywiste maszyny będą znacznie mądrzejsze niż JVM. Mimo to wiele języków kompilujących się do kodu natywnego, takich jak Haskell, nie wydaje się mieć problemów z optymalizacją wywołań ogonowych (no cóż, Haskell może czasami mieć z powodu lenistwa, ale to już inna kwestia).
tailcallinstrukcja dla JVM została już zaproponowana już w 2007 roku: Blog na sun.com za pośrednictwem maszyny powrotnej . Po przejęciu Oracle link 404. Myślę, że nie znalazło się na liście priorytetów JVM 7.tailcallInstrukcja oznaczałoby jedynie połączenia ogonowych rozmowy ogonowej. To, czy JVM faktycznie zoptymalizowało wspomniane ogonowanie, to zupełnie inne pytanie. CLI CIL ma.tailprefiks instrukcji, ale 64-bitowy CLR Microsoft przez długi czas go nie optymalizował. OTOH, IBM J9 JVM nie wykrywa połączenia ogon i optymalizuje je, bez konieczności specjalnej instrukcji, aby poinformować go, które połączenia są rekurencja ogonowa. Adnotacje dotyczące wezwań do ogonów i optymalizacja wezwań do ogonów są naprawdę ortogonalne. (Oprócz tego, że statyczne dedukowanie, które połączenie jest ogonem, może być nierozstrzygalne. Dunno.)call something; oreturn. Podstawowym zadaniem JVM Spec aktualizacji nie byłoby wprowadzić wyraźne polecenie tail-rozmowę, lecz nakazuje , że taka instrukcja jest zoptymalizowany. Taka instrukcja tylko ułatwia zadania pisarzy kompilatora: autor JVM nie musi upewnić się, że rozpoznaje tę sekwencję instrukcji, zanim ulegnie zniekształceniu nie do rozpoznania, a kompilator X-> bytecode może mieć pewność, że ich kod bajtowy jest nieprawidłowy lub faktycznie zoptymalizowane, nigdy nie przepełniające przepełnienia stosu.call something; return;byłaby równoważna wywołaniu ogonowemu tylko wtedy, gdy wywoływana rzecz nigdy nie prosi o ślad stosu; jeśli dana metoda jest wirtualna lub wywołuje metodę wirtualną, JVM nie będzie wiedział, czy mógłby zapytać o stos.Clojure może przeprowadzić automatyczną optymalizację rekurencji ogona w pętle: z pewnością jest to możliwe na JVM, jak udowadnia Scala.
W rzeczywistości była to decyzja projektowa, aby tego nie robić - musisz jawnie użyć
recurspecjalnego formularza, jeśli chcesz tę funkcję. Zobacz wątek pocztowy Re: Dlaczego nie ma optymalizacji połączeń ogonowych w grupie Google Clojure.W obecnej JVM jedyne, co jest niemożliwe, to optymalizacja wywołania ogonowego między różnymi funkcjami (wzajemna rekurencja). Nie jest to szczególnie skomplikowane do wdrożenia (inne języki, takie jak Scheme, miały tę funkcję od samego początku), ale wymagałoby to zmiany specyfikacji JVM. Na przykład musisz zmienić zasady dotyczące zachowania pełnego stosu wywołań funkcji.
Przyszła iteracja JVM prawdopodobnie uzyska tę możliwość, chociaż prawdopodobnie jako opcję, aby zachować zachowanie kompatybilności wstecznej dla starego kodu. Powiedz, Podgląd funkcji w Geeknizer wymienia to dla Java 9:
Oczywiście przyszłe plany działania zawsze mogą ulec zmianie.
Jak się okazuje, i tak nie jest to nic wielkiego. W ciągu ponad 2 lat kodowania Clojure mam nigdy nie się z sytuacją, w której brak TCO był problemem. Głównymi tego przyczynami są:
recurpętlą lub pętlą. Przypadek wzajemnej rekurencji ogona jest rzadki w normalnym kodzieźródło
Nie chodzi o bycie mądrzejszym, ale o bycie innym. Do niedawna JVM był zaprojektowany i zoptymalizowany wyłącznie dla jednego języka (oczywiście Java), który ma bardzo ścisłą pamięć i modele wywoływania.
Nie tylko nie było żadnych
gotowskaźników ani wskaźników, nie było nawet sposobu, aby wywołać funkcję „gołą” (która nie była metodą zdefiniowaną w klasie).Koncepcyjnie, podczas atakowania JVM, autor kompilatora musi zapytać „jak mogę wyrazić tę koncepcję w kategoriach Java?”. I oczywiście nie ma możliwości wyrażenia całkowitego kosztu posiadania w Javie.
Pamiętaj, że nie są one postrzegane jako awarie JVM, ponieważ nie są potrzebne w Javie. Gdy tylko Java będzie potrzebować takich funkcji, jest dodawana do JVM.
Dopiero niedawno władze Java zaczęły poważnie traktować JVM jako platformę dla języków innych niż Java, więc już uzyskało wsparcie dla funkcji, które nie mają odpowiednika w Javie. Najbardziej znanym jest pisanie dynamiczne, które jest już w JVM, ale nie w Javie.
źródło
Czy zauważyłeś, że adres metody zaczyna się od 0? Że wszystkie metody zbiorów zaczynają się od 0? JVM nie pozwala wyskoczyć poza metodę.
Nie mam pojęcia, co by się stało z odgałęzieniem z przesunięciem poza metodą, które zostało załadowane przez java - być może zostanie przechwycony przez weryfikator kodu bajtowego, może wygeneruje wyjątek, a może faktycznie wyskoczy poza metodę.
Problem polega oczywiście na tym, że tak naprawdę nie można zagwarantować, gdzie będą inne metody tej samej klasy, a tym bardziej metody innych klas. Wątpię, aby JVM udzielał jakichkolwiek gwarancji co do miejsca załadowania metod, ale chętnie bym go poprawił.
źródło