Czy i czy kompilatory mogą konwertować logikę rekurencyjną na równoważną logikę nierekurencyjną?

15

Uczyłem się F # i zaczyna to wpływać na to, jak myślę, kiedy programuję w C #. W tym celu używam rekurencji, gdy czuję, że wynik poprawia czytelność i nie mogę sobie wyobrazić, że kończy się przepełnieniem stosu.

To prowadzi mnie do pytania, czy kompilatory mogą automatycznie konwertować funkcje rekurencyjne na równoważne formy nierekurencyjne?

Aaron Anodide
źródło
Optymalizacja wywołania ogona jest dobrym, jeśli podstawowym przykładem, ale działa to tylko wtedy, gdy masz return recursecall(args);do rekurencji, bardziej złożone rzeczy są możliwe, tworząc wyraźny stos i likwidując go, ale wątpię, że tak będzie
maniak ratchet
@ratchet freak: Recursion nie oznacza „obliczeń korzystających ze stosu”.
Giorgio
1
@Giorgio Wiem, ale stos jest najprostszym sposobem na przekształcenie rekurencji w pętlę
maniak ratchet

Odpowiedzi:

21

Tak, niektóre języki i kompilatory przekonwertują logikę rekurencyjną na logikę nierekurencyjną. Jest to znane jako optymalizacja połączeń ogonowych - pamiętaj, że nie wszystkie połączenia rekurencyjne są zoptymalizowane. W tej sytuacji kompilator rozpoznaje funkcję formularza:

int foo(n) {
  ...
  return bar(n);
}

Tutaj język jest w stanie rozpoznać, że zwracany wynik jest wynikiem innej funkcji i zmienić wywołanie funkcji z nową ramką stosu na skok.

Zrozum, że klasyczna metoda czynnikowa:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

nie jest optymalizowany na podstawie ogona ze względu na kontrolę konieczną po powrocie.

Aby zoptymalizować to połączenie z ogonem,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Kompilowanie tego kodu za pomocą gcc -O2 -S fact.c(-O2 jest konieczne, aby umożliwić optymalizację w kompilatorze, ale przy większej optymalizacji -O3 trudno jest odczytać człowiekowi ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

Widać w segmencie .L4, jnea nie w call(który wywołuje podprogram z nową ramką stosu).

Należy pamiętać, że zostało to wykonane w C. Optymalizacja wywołania ogona w Javie jest trudna i zależy od implementacji JVM - rekurencja tail + java i rekursja tail + optymalizacja to dobre zestawy znaczników do przeglądania. Można znaleźć inne języki JVM są w stanie optymalizować rekursji ogonowej lepiej (Clojure try (co wymaga ponownie wystąpi zadzwonić ogon Optimize) lub Scala).

Społeczność
źródło
1
Nie jestem pewien, czy o to pyta OP. To, że środowisko wykonawcze w określony sposób zajmuje lub nie zajmuje miejsca na stosie, nie oznacza, że ​​funkcja nie jest rekurencyjna.
1
@MattFenwick Co masz na myśli? „To prowadzi mnie do pytania, czy kompilatory mogą automatycznie konwertować funkcje rekurencyjne na równoważne formy nierekurencyjne” - odpowiedź brzmi „tak pod pewnymi warunkami”. Warunki są pokazane, a niektóre gotcha są w niektórych innych popularnych językach z optymalizacjami ogonów, o których wspomniałem.
9

Stąpaj ostrożnie.

Odpowiedź brzmi: tak, ale nie zawsze i nie wszystkie. Jest to technika, która nosi kilka różnych nazw, ale można znaleźć tu dość definitywne informacje tutaj i na Wikipedii .

Wolę nazwę „Tail Call Optimization”, ale są też inni, a niektórzy mylą to określenie.

To powiedziawszy, jest kilka ważnych rzeczy do zrealizowania:

  • Aby zoptymalizować ogon, ogon wymaga parametrów, które są znane w momencie nawiązywania połączenia. Oznacza to, że jeśli jeden z parametrów jest wywołaniem samej funkcji, nie można jej przekształcić w pętlę, ponieważ wymagałoby to dowolnego zagnieżdżenia tej pętli, której nie można rozwinąć w czasie kompilacji.

  • C # nie niezawodnie optymalizuje wezwania ogona. IL ma instrukcję, aby to zrobić, którą wyemituje kompilator F #, ale kompilator C # wyemituje go niekonsekwentnie, aw zależności od sytuacji JIT, JIT może, ale nie musi, wcale. Wszystko wskazuje na to, że nie powinieneś polegać na optymalizacji połączeń ogonowych w języku C #, ryzyko przepełnienia jest znaczne i realne

Jimmy Hoffa
źródło
1
Czy jesteś pewien, że o to pyta OP? Jak napisałem pod drugą odpowiedzią, tylko dlatego, że środowisko wykonawcze w określony sposób zajmuje lub nie zajmuje miejsca na stosie, nie oznacza, że ​​funkcja nie jest rekurencyjna.
1
@MattFenwick jest to naprawdę świetna kwestia, w rzeczywistości zależy to od tego, że kompilator F # wysyłający instrukcje wywołania ogona całkowicie zachowuje logikę rekurencyjną, po prostu instruuje JIT, aby wykonał go w sposób zastępujący przestrzeń stosu, a nie przestrzeń stosu rośnie, jednak inne kompilatory mogą dosłownie kompilować się w pętli. (Technicznie JIT kompiluje się w pętlę, a może nawet bez pętli, jeśli pętla jest całkowicie z góry)
Jimmy Hoffa