Dlaczego Java w ogóle nie ma optymalizacji pod kątem rekurencji?

92

Z tego, co przeczytałem: Powodem jest to, że nie jest łatwo ustalić, która metoda zostanie faktycznie wywołana, ponieważ mamy dziedziczenie.

Dlaczego jednak Java nie ma przynajmniej optymalizacji rekurencji dla metod statycznych i nie wymusza właściwego sposobu wywoływania metod statycznych za pomocą kompilatora?

Dlaczego Java nie ma żadnego wsparcia dla rekursji ogona?

Nie jestem pewien, czy w ogóle są tu jakieś trudności.

Jeśli chodzi o sugerowany duplikat , jak wyjaśniono w Jörg W Mittag ¹ :

Drugie pytanie dotyczy TCO, w tym TRE. TRE jest znacznie prostszy niż TCO.

Także inne pytanie dotyczy tego, jakie ograniczenia JVM nakłada na implementacje językowe, które chcą się skompilować do JVM, pytanie to dotyczy Java, która jest jedynym językiem, który nie jest ograniczony przez JVM, ponieważ specyfikację JVM można zmienić przez ci sami ludzie, którzy projektują Javę.

I na koniec, nie ma nawet ograniczeń w JVM dotyczących TRE, ponieważ JVM ma wewnętrzną metodę GOTO, która jest wszystkim, co jest potrzebne do TRE

¹_{Dodano formatowanie do wywołanych punktów.}

java compiler recursion

— Poinformowano
źródło

26

Cytując Erica Lipperta : „Funkcje nie są tanie; są niezwykle drogie i muszą nie tylko uzasadniać własne koszty, ale muszą uzasadniać koszt alternatywny niewykonania setki innych funkcji, które moglibyśmy zrobić przy tym budżecie”. Java została częściowo zaprojektowana, aby spodobać się programistom C / C ++, a optymalizacja rekurencji ogona nie jest gwarantowana w tych językach.

— Doval

5

Popraw mnie, jeśli się mylę, ale czy Eric Lippert jest projektantem języka C #, który ma optymalizację rekurencji ogona?

— InformedA

1

Jest w zespole kompilatorów C #, tak.

— Doval

10

Z tego, co rozumiem, JIT może to zrobić , jeśli mogą być spełnione pewne warunki . Więc w praktyce nie możesz na tym polegać. Ale to, czy C # ma, czy nie, jest nieistotne z punktu widzenia Erica.

— Doval

4

@InstructA Jeśli zagłębisz się nieco głębiej, zobaczysz, że nigdy nie zrobiono tego w 32-bitowym kompilatorze JIT. 64-bitowy JIT jest nowszy i mądrzejszy pod wieloma względami. Jeszcze nowszy eksperymentalny kompilator (zarówno dla wersji 32-bitowej, jak i 64-bitowej) jest jeszcze mądrzejszy i będzie obsługiwał optymalizację rekurencji ogona w IL, która tego wyraźnie nie wymaga. Jest jeszcze jedna kwestia, którą należy wziąć pod uwagę - kompilatory JIT nie mają dużo czasu. Są mocno zoptymalizowane pod kątem szybkości - aplikacja, której kompilacja w C ++ może zająć wiele godzin, nadal będzie musiała przejść z IL do natywnej za najwyżej kilkaset ms (przynajmniej częściowo).

— Luaan

132

Jak wyjaśnił Brian Goetz (architekt języka Java w Oracle) w tym filmie :

w klasach jdk [...] istnieje wiele metod wrażliwych na bezpieczeństwo, które polegają na zliczaniu ramek stosu między kodem biblioteki jdk a kodem wywołującym, aby dowiedzieć się, kto je wywołuje.

Wszystko, co zmieniło liczbę ramek na stosie, zepsułoby to i spowodowałoby błąd. Przyznaje, że był to głupi powód, dlatego programiści JDK zastąpili ten mechanizm.

Następnie wspomina, że nie jest to priorytet, ale rekursja ogona

w końcu się skończy.

Uwaga: dotyczy to HotSpot i OpenJDK, inne maszyny wirtualne mogą się różnić.

— ggovan
źródło

7

Dziwię się, że istnieje taka dość cięta i wysuszona odpowiedź! Ale tak naprawdę wygląda na Odpowiedź - jest to możliwe teraz, z przestarzałych przyczyn technicznych jeszcze tego nie zrobiono, więc teraz czekamy, aż ktoś zdecyduje, że jest wystarczająco ważny do wdrożenia.

— BrianH

1

Dlaczego nie wdrożyć obejścia? Jak etykieta goto pod przykryciem, która przeskakuje na początek wywołania metody z nowymi wartościami argumentów? Byłaby to optymalizacja czasu kompilacji i nie musiałaby przesuwać ramek stosu ani powodować naruszenia bezpieczeństwa.

— James Watkins

2

Będzie nam znacznie lepiej, jeśli ty lub ktoś inny tutaj będzie mógł kopać głębiej i podać dokładnie, jakie są te „metody wrażliwe na bezpieczeństwo”. Dziękuję Ci!

— Poinformowano

3

@InstructedA - patrz securingjava.com/chapter-three/chapter-three-6.html, który zawiera szczegółowy opis działania systemu Java Security Manager około wydania Java 2.

— Jules

3

Jednym obejściem jest użycie innego języka JVM. Na przykład Scala robi to w kompilatorze, a nie w czasie wykonywania.

— James Moore,

24

Java nie ma optymalizacji wywołania ogona z tego samego powodu, dla którego większość imperatywnych języków tego nie ma. Pętle imperatywne są preferowanym stylem języka, a programista może zastąpić rekurencję ogonami pętlami imperatywnymi. Złożoność nie jest tego warta w przypadku funkcji, której użycie jest odradzane ze względu na styl.

To, w czym programiści chcą czasami pisać w stylu FP w skądinąd imperatywnych językach, stało się modne dopiero w ciągu ostatnich 10 lat, po tym jak komputery zaczęły skalować się w rdzeniach zamiast GHz. Nawet teraz nie jest tak popularny. Gdybym zasugerował zastąpienie pętli rozkazów rekurencją ogona w pracy, połowa recenzentów kodu śmiałaby się, a druga połowa wyglądałaby na zdezorientowanych. Nawet w programowaniu funkcjonalnym na ogół unika się rekurencji ogona, chyba że inne konstrukcje, takie jak funkcje wyższego rzędu, nie pasują idealnie.

— Karl Bielefeldt
źródło

36

Ta odpowiedź wydaje się nieprawidłowa. To, że rekurencja ogona nie jest ściśle potrzebna, nie oznacza, że nie byłaby użyteczna. Rozwiązania rekurencyjne są często łatwiejsze do zrozumienia niż iteracja, ale brak wywołań ogonowych oznacza, że algorytmy rekurencyjne stają się niepoprawne w przypadku dużych problemów, które mogłyby zniszczyć stos. Chodzi o poprawność, a nie wydajność (prędkość handlowa dla uproszczenia jest często tego warta). Jak zauważa poprawna odpowiedź, brak wywołań ogonowych wynika z dziwnego modelu bezpieczeństwa opartego na śladach stosu, a nie z bezwzględnej bigoterii.

— amon

4

@amon James Gosling powiedział kiedyś, że nie doda funkcji do Javy, chyba że o to poprosi wiele osób , i dopiero wtedy to rozważy . Więc nie zdziwiłbym się, gdyby część odpowiedzi naprawdę był „zawsze można użyć forpętli” (podobnie do pierwszej klasy funkcji vs obiektów). Nie posunąłbym się tak daleko, że nazwałbym to „imperatywną bigoterią”, ale nie sądzę, że byłby bardzo potrzebny w 1995 roku, kiedy najważniejszą kwestią była prawdopodobnie szybkość Javy i brak generycznych.

— Doval

7

@amon, model bezpieczeństwa uderza mnie jako uzasadniony powód, aby nie dodawać TCO do wcześniej istniejącego języka, ale kiepski powód, aby nie projektować go w tym języku. Nie wyrzucasz dużej widocznej dla programisty funkcji w celu włączenia drobnej funkcji za kulisami. „Dlaczego Java 8 nie ma TCO” to zupełnie inne pytanie niż „Dlaczego Java 1.0 nie ma TCO?” Odpowiedziałem na to drugie.

— Karl Bielefeldt

3

@rwong, możesz przekształcić dowolną funkcję rekurencyjną w iteracyjną. (Jeśli mogę, napisałem tutaj przykład )

— alain

3

@ZanLynx zależy od rodzaju problemu. Na przykład wzór użytkownika może korzystać z TCO (w zależności od specyfiki struktury i odwiedzającego), nie mając przy tym nic wspólnego z FP. Przechodzenie przez maszyny stanowe jest podobne, chociaż transformacja za pomocą trampolin wydaje się nieco bardziej naturalna (w zależności od problemu). Ponadto, chociaż technicznie można implementować drzewa za pomocą pętli, uważam, że konsensus jest taki, że rekurencja jest znacznie bardziej naturalna (podobnie w przypadku DFS, chociaż w tym przypadku można uniknąć rekurencji z powodu ograniczeń stosu nawet przy TCO).

— Maciej Piechotka,

5

Java nie ma optymalizacji wysokich wywołań, ponieważ JVM nie ma kodu bajtowego dla wywołań tail (do jakiegoś statycznie nieznanego wskaźnika funkcji, np. Metody w niektórych vtable).

Wygląda na to, że z przyczyn społecznych (i być może technicznych) dodanie nowej operacji kodu bajtowego w JVM (co spowodowałoby, że byłaby niezgodna z wcześniejszymi wersjami tej JVM) jest niezwykle trudne dla właściciela specyfikacji JVM.

^{Techniczne powody, dla których nie dodano nowego kodu bajtowego do specyfikacji JVM, obejmują fakt, że rzeczywiste implementacje JVM są strasznie złożonymi elementami oprogramowania (np. Z powodu wielu optymalizacji JIT).}

Wywołania Tail do jakiejś nieznanej funkcji wymagają zastąpienia bieżącej ramki stosu nową, a ta operacja powinna znajdować się w JVM (nie chodzi tylko o zmianę kompilatora generującego kody bajtowe).

— Basile Starynkevitch
źródło

17

Pytanie nie dotyczy wezwań ogonów, dotyczy rekurencji ogonów. Pytanie nie dotyczy języka kodu bajtowego JVM, lecz języka programowania Java, który jest zupełnie innym językiem. Scala kompiluje się do kodu bajtowego JVM (między innymi) i ma eliminację rekurencji ogona. Wdrożenia programu w JVM mają pełne Prawidłowe wezwania ogona. Java 7 (JVM Spec, wydanie trzecie) dodał nowy kod bajtowy. JVM J9 firmy IBM wykonuje TCO nawet bez potrzeby specjalnego kodu bajtowego.

— Jörg W Mittag

1

@ JörgWMittag: To prawda, ale zastanawiam się, czy to prawda, że język programowania Java nie ma odpowiednich wywołań ogonowych. Bardziej dokładne może być stwierdzenie, że język programowania Java nie musi mieć odpowiednich wywołań ogonowych, ponieważ nic w specyfikacji tego nie wymaga. (To znaczy: nie jestem pewien, czy cokolwiek w specyfikacji faktycznie zabrania implementacji eliminowania wywołań ogona. Po prostu nie jest wspomniane.)

— ruakh

4

O ile język nie ma specjalnej składni do wykonywania wywołania ogonowego (rekurencyjnego lub w inny sposób), a kompilator będzie skrzeczał, gdy żąda się wywołania ogona, ale nie można go wygenerować, „opcjonalna” optymalizacja wywołania ogona lub rekurencji ogona da sytuacje, w których kawałek kodu może wymagać mniej niż 100 bajtów stosu na jednym komputerze, ale więcej niż 100 000 000 bajtów stosu na innym komputerze. Taką różnicę należy traktować raczej jakościowo niż ilościowo.

Oczekuje się, że maszyny mogą mieć różne rozmiary stosów, dlatego zawsze jest możliwe, aby kod działał na jednej maszynie, ale wysadzał stos na innej. Zasadniczo jednak kod, który będzie działał na jednej maszynie, nawet gdy stos jest sztucznie zawężony, prawdopodobnie będzie działał na wszystkich komputerach z „normalnymi” rozmiarami stosów. Jeśli jednak metoda, która powtarza 1 000 000 głębokości, jest zoptymalizowana na jednym komputerze, ale nie na innej, wykonanie na pierwszej maszynie prawdopodobnie zadziała, nawet jeśli jej stos jest niezwykle mały, i zawiedzie na drugiej, nawet jeśli jej stos jest niezwykle duży .

— supercat
źródło

2

Sądzę, że rekurencja wywołania ogona nie jest używana w Javie głównie dlatego, że zmieniłoby to ślady stosu i dlatego znacznie utrudniłoby debugowanie programu. Myślę, że jednym z głównych celów Javy jest umożliwienie programistom łatwego debugowania kodu, a śledzenie stosu jest niezbędne, aby to zrobić, szczególnie w wysoce obiektowym środowisku programistycznym. Ponieważ zamiast tego można zastosować iterację, komitet językowy musiał zorientować się, że nie warto dodawać rekurencji ogona.

— irytująca kałamarnica
źródło