Kiedy nie ma TCO, kiedy martwić się o wysadzenie stosu?

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?

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

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

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ę recurformę, 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 recurspecjalnych 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

return foo(bar, baz); // foo is just a simple method

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.

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:

1. Kompilator może zoptymalizować prostą rekurencję ogona do pętli.
2. Jeśli program działa w sposób ciągły, to używanie „trampolinowania” jest banalne. Tutaj funkcja nie zwraca wyniku końcowego, ale kontynuację, która jest następnie wykonywana na zewnątrz. Ta technika pozwala twórcy kompilatora modelować dowolnie złożony przepływ sterowania.

Może to wymagać większego przykładu. Rozważ język z zamknięciami (np. JavaScript lub podobny). Możemy zapisać silnię jako

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Teraz możemy poprosić, aby zamiast tego oddzwonił:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

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ć.

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, GOTOale 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ć GOTOtrampolin 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.

„JVM nie obsługuje optymalizacji wywołania ogona, więc przewiduję wiele eksplodujących stosów”

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 informatyce wywołanie ogona jest wywołaniem podprogramu, które odbywa się w ramach innej procedury jako jej ostateczne działanie; może wygenerować wartość zwracaną, która jest następnie natychmiast zwracana przez procedurę wywołującą

W poniższym kodzie wezwanie do bar()jest wywołaniem końcowym foo():

private void foo() {
    // do something
    bar()
}

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.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Aby wdrożyć optymalizację wezwania ogona, potrzebujesz dwóch rzeczy:

• Platforma obsługująca rozgałęzianie oprócz połączeń podprogramowych.
• Analizator statyczny, który może ustalić, czy możliwa jest optymalizacja wezwania ogona.

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:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Ta funkcja zmienia się w następujący kod bajtowy:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Uwaga goto 0na końcu. Dla porównania równoważna funkcja Java (która musi Iteratornaś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.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

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 switchzachowania 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ć jako foldLeft(). 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ć JSRprzez JUMP.