Rekursion und StackOverflowError

Question

Wie würden Sie dieses einfache Rekursionsbeispiel so anpassen, dass die Optimierung der Tail-Calls erfolgt (und keine StackOverflowError)?

count 0 = 0 
count n = succ (count (pred n)) 
count 100000 

Answer 1

Dies ist die Art von Stack-Überläufen, die ich die "Länge/foldr" Art nennen. Es tritt auf, wenn die rekursive Funktion angewendet wird, um das strikte Argument der Funktionsanwendung zu berechnen, die das Ergebnis darstellt. Vergleichen:

-- naive computation of list length 
-- this is not like it's defined in Frege, of course 
length [] = 0 
length (_:xs) = 1 + length xs 

Dies geschieht auch mit foldr f wenn f in seinem zweiten Argument streng.

Es gibt andere mögliche Gründe für die Stapelüberlauf (SO):

1. Endrekursion. Dies wird in Frege am effizientesten gehandhabt, da eine tail rekursive Funktion in eine while-Schleife kompiliert wird. Wird im Gegensatz zu anderen JVM-Sprachen niemals eine SO verursachen.
2. explizite indirekte Tail-Rekursion: (z. B. a Tail ruft b, die Tail ruft c, ..., die Tail ruft a). Dies sollte auch niemals zu einem SO in Frege führen.
3. Aufbau von Thunks, die so tief verschachtelt sind, dass SO bei der Auswertung auftritt. Dies geschieht in foldl in Haskell. In Frege ist der Standard fold in vielen Fällen streng im Akkumulator und damit immun. Bei langen Listen läuft jedoch immer noch folgendes über: fold (<>) mempty (map (Just . Sum) [1..10000])
4. Die Länge/Falzart der Rekursion, wie in unserem Beispiel.
5. Rekursion in non Endaufruf:

Hier ist ein Beispiel für den letzteren Fall ist:

even 0 = true 
    even n = case even (pred n) of 
      true -> false 
      false -> true 

Die zweite Gleichung ist semantisch äquivalent zu even n = not (even (pred n)) und somit ist eine noch böswillige Variante von 4.

Ihre Frage zu beantworten, in Ihrem Beispiel ein einen Akkumulator verwenden könnte einen Schwanz-rekursive Version zu erstellen:

count n = go 0 n 
    where 
     go acc 0 = acc 
     go acc n = go (succ acc) (pred n) 

Es ist vielleicht erwähnenswert, dass Ihr Beispiel nicht auch in Haskell:

GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help 
Loading package ghc-prim ... linking ... done. 
Loading package integer-gmp ... linking ... done. 
Loading package base ... linking ... done. 
Prelude> let count 0 = 0; count n = succ (count (pred n)) 
Prelude> count 10000 
10000 
Prelude> count 100000 
100000 
Prelude> count 1000000 
1000000 
Prelude> count 10000000 
10000000 
Prelude> count 100000000 
*** Exception: stack overflow 

Der Grund, dass es nur mit viel höheren Zahlen überläuft, ist, dass die Haskell RTS den RAM in einer Weise verwaltet, die besser geeignet ist für Funktionale Programmierung, während die JVM beim Start einen kleinen Standard-Stack zuweist, der bestenfalls eine Aufruftiefe von einigen 1000 bietet.

Sie können viel größere Zahlen mit Ihrem Programm auch in Frege berechnen, wenn Sie die JVM zwingen, größere Stacks zuzuordnen:

java -Xss512m .... 

Erfahrung zeigt, dass ein Stapel von Größe 512m Anruf Tiefe von approximatly 10 Millionen ermöglicht Einzelargumentfunktionen.

Dies ist jedoch keine allgemeine Lösung, da die JVM dann alle Threads mit dieser Stapelgröße erstellt.So wird wertvoller RAM verschwendet. Und selbst wenn Sie viel RAM haben, werden Sie wahrscheinlich keinen Stapel größer als 2g erstellen können.

In der nächsten Hauptversion von Frege werden bestimmte pathologische Fälle der Stack-Überlaufarten 3 und 4 (siehe oben) hoffentlich besser gemanagt. Bis heute funktionieren solche Konstrukte jedoch nur für kleine Problemgrößen, die zufällig in den JVM-Stack passen.