Czy JVM zapobiega optymalizacji wywołań końcowych?

99

Widziałem ten cytat dotyczący pytania: Jaki jest dobry język funkcjonalny, na którym można zbudować usługę internetową?

W szczególności Scala nie obsługuje eliminacji wywołań ogonowych, z wyjątkiem funkcji samorekursywnych, co ogranicza rodzaje kompozycji, które możesz wykonać (jest to fundamentalne ograniczenie JVM).

Czy to prawda? Jeśli tak, co jest takiego w JVM, że stwarza to podstawowe ograniczenie?

java jvm scala tail-recursion Jason Dagit
źródło

Odpowiedzi:

74

Ten post: Rekursja czy iteracja? może pomóc.

Krótko mówiąc, optymalizacja wywołań ogonowych jest trudna do wykonania w JVM ze względu na model bezpieczeństwa i konieczność posiadania zawsze dostępnego śladu stosu. Te wymagania mogłyby być teoretycznie obsługiwane, ale prawdopodobnie wymagałoby to nowego kodu bajtowego (patrz nieformalna propozycja Johna Rose'a ).

Więcej dyskusji znajduje się w błędzie Sun # 4726340 , gdzie kończy się ocena (z 2002 roku):

Mimo wszystko uważam, że można to zrobić, ale nie jest to małe zadanie.

Obecnie trwają prace nad projektem Da Vinci Machine . Stan podprojektu wywołania ogonowego to „proto 80%”; jest mało prawdopodobne, aby przedostał się do Javy 7, ale myślę, że ma bardzo duże szanse na Javę 8.

Michael Myers
źródło
Nie do końca podążyłem za wyjaśnieniem. Myślałem, że kompilator zaimplementował optymalizację wywołań ogonowych. Zakładając, że masz funkcję, która mogłaby być zoptymalizowana przez kompilator do wywołań ogonowych, możesz również mieć równoważną funkcję nierekurencyjną, która implementuje tę samą funkcjonalność za pomocą pętli, prawda? Jeśli tak, kompilator nie mógł tego zrobić. Nie jestem w stanie śledzić zależności od JVM. Jak wypada to w porównaniu z kompilatorem Scheme, który wygenerował natywny kod i386?
Gautham Ganapathy
4
@Gautham: Moje oświadczenie dotyczące debugowania dotyczyło użycia trampolin jako obejścia braku eliminacji wywołań ogonowych w JVM. Eliminacja wywołań ogonowych może i została zaimplementowana w JVM (Arnold Schaighofer zrobił to w OpenJDK, a także LLVM), więc nie ma wątpliwości, czy można to zrobić, czy nie. Microsoft CLR oczywiście wspiera eliminację wywołań ogonowych przez 10 lat, a wydanie F # pokazało, że jest to przełom. Myślę, że odpowiedź jest taka, że ​​JVM już dawno znajduje się w stagnacji.
JD
3
Jest to powszechne nieporozumienie i często powtarzana wymówka, ale jest błędna. Od wielu lat dobrze wiadomo, że bezpieczeństwo poprzez inspekcję stosu (i dostarczenie użytecznych śladów stosu) nie jest niezgodne z właściwymi wywołaniami końcowymi. Na przykład, zobacz ten papier z 2004 citeseerx.ist.psu.edu/viewdoc/... Downvoting, jak odpowiedź jest błędna.
Justin Sheehy
5
@JustinSheehy: Co jest nieprawidłowe? Pytanie brzmiało: „Czy maszyna JVM zapobiega optymalizacji połączeń końcowych?” Odpowiedź brzmi: „Nie, ale to trudne”.
Michael Myers
5
Czy wiesz, czy w java8 jest to uwzględnione?
nachokk
27

Podstawowym ograniczeniem jest po prostu to, że JVM nie zapewnia wywołań ogona w swoim kodzie bajtowym, a zatem nie ma bezpośredniego sposobu, aby język zbudowany na JVM sam zapewniał wywołania ogona. Istnieją obejścia, które mogą przynieść podobny efekt (np. Trampolinowanie), ale wiążą się one z poważnym kosztem fatalnej wydajności i zaciemniania wygenerowanego kodu pośredniego, co czyni debugger bezużytecznym.

Dlatego JVM nie może obsługiwać żadnych funkcjonalnych języków programowania o jakości produkcyjnej, dopóki Sun nie zaimplementuje wywołań końcowych w samej JVM. Dyskutują o tym od lat, ale wątpię, czy kiedykolwiek zaimplementują wywołania ogonowe: będzie to bardzo trudne, ponieważ przedwcześnie zoptymalizowali swoją maszynę wirtualną przed wdrożeniem tak podstawowej funkcjonalności, a wysiłki firmy Sun koncentrują się na językach dynamicznych, a nie na językach funkcjonalnych.

Stąd istnieje bardzo mocny argument, że Scala nie jest prawdziwym funkcjonalnym językiem programowania: języki te uważały wywołania ogonowe za zasadniczą cechę od czasu wprowadzenia Scheme ponad 30 lat temu.

JD
źródło
5
Hence there is a very strong argument that Scala is not a real functional programming language - argument jest właściwie dość słaby. Jasne tail calls [as] an essential featurei fajnie, jeśli sprzęt (lub maszyna virtal) obsługuje go bezpośrednio. Ale to szczegóły implementacji.
Ingo
8
@Ingo: Tylko jeśli nie uważasz, że przepełnienia stosu w programie w czasie wykonywania, które użytkownik widzi, stanowią istotny problem. Według jego modułu do śledzenia błędów, nawet sam kompilator Scala był nękany przepełnieniem stosu. Więc nawet najbardziej doświadczeni programiści Scali wciąż się mylą ...
JD
7
Dobrze jest być zwolennikiem, powiedzmy F #. Ale zauważyłem cię od dawna (nawet lata wcześniej w usenecie) za to, że jesteś wrogo nastawiony do wszystkiego, co nie jest F #, a jednak Twoje opracowania pokazują, że nie wiesz, o czym mówisz. Tak jak tutaj: wydaje się, że twój argument jest taki, że język, w którym mogę napisać program, który przerywa pracę z przepełnieniem stosu, nie jest językiem funkcjonalnym? Ale czy nie można przedstawić tego samego argumentu w przypadku języków, w których mogę sprowokować przepełnienie stosu? W związku z tym sam święty F # nie liczyłby się jako funkcjonalny.
Ingo
7
@Ingo: Kilka idiomów w programowaniu funkcjonalnym, takich jak wzajemna rekurencja i styl przekazywania kontynuacji, może wymagać eliminacji wywołań końcowych do działania. Bez tego twoje programy będą się przepełniać. Jeśli język nie może niezawodnie obsługiwać idiomatycznego kodu funkcjonalnego, czy jest funkcjonalny? Odpowiedzią jest wezwanie do osądu, jak mówisz, ale ważne rozróżnienie w praktyce. Martin Trojer właśnie opublikował interesujący wpis na blogu na ten temat: martinsprogrammingblog.blogspot.com/2011/11/...
JD
2
Jednak tylko dlatego, że JVM (niestety, bez wątpienia) nie może wykonywać wywołań ogonowych, nie oznacza to, że eliminacja wywołań ogonowych jest niemożliwa. To tak, jakby ktoś stwierdził, że obliczenia zmiennoprzecinkowe są możliwe tylko na komputerach z jednostkami FPU.
Ingo
22

Scala 2.7.x obsługuje optymalizację wywołań końcowych dla samorekursji (funkcji wywołującej samą siebie) końcowych metod i funkcji lokalnych.

Scala 2.8 może również zawierać obsługę biblioteki dla trampoliny, co jest techniką optymalizacji wzajemnie rekurencyjnych funkcji.

Wiele informacji na temat stanu rekurencji Scala można znaleźć na blogu Richa Dougherty'ego .

Daniel C. Sobral
źródło
Czy możesz zaktualizować pytanie o aktualny status scali?
om-nom-nom
@ om-nom-nom AFAIK, nic się nie zmieniło, ani po stronie Scali, ani po stronie JVM.
Daniel C. Sobral,
0

Wszystkie źródła wskazują, że JVM nie jest w stanie zoptymalizować w przypadku rekurencji ogonowej, ale po przeczytaniu dostrajania wydajności Java (2003, O areilly) stwierdziłem, że autor twierdzi, że może osiągnąć większą wydajność rekurencji poprzez implementację rekurencji ogonowej.

Możesz znaleźć jego twierdzenie na stronie 212 (wyszukaj „rekurencję ogonową”, powinien to być drugi wynik). Co daje?

fthinker
źródło
IBM wspierał pewną formę TCO w ich implementacji JVM (w ramach optymalizacji, więc nie ma gwarancji). Być może autorzy Java Performance tuning sądzili, że ta funkcja zostanie ostatecznie zaimplementowana we wszystkich maszynach JVM. ibm.com/developerworks/java/library/j-diag8.html
llemieng