Sind Programme in funktionalen Sprachen eher Stapel überläuft haben?

Question

Ich beginne ocaml zu lernen, und bin wirklich die Macht der Rekursion in der Sprache zu schätzen. Aber eine Sache, die ich mache mir Sorgen über ist Stack überläuft.

Wenn ocaml den Stack für Funktionsaufrufe verwendet, wird es nicht schließlich den Stack überlaufen? Zum Beispiel, wenn ich die folgende Funktion:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

es muss schließlich einen Stapel-Überlauf verursachen. Wenn ich die äquivalent Sache in c zu tun war ++ (unter Verwendung von Rekursion), weiß ich, dass es würde überlaufen.

Also meine Frage ist, ist es in Garantien gebaut zu verhindern funktionale Sprachen aus dem Stapel überfüllt? Wenn nicht, sind sie nicht weniger nützlich wie diese, da der obige Summationsalgorithmus, mit einem in einem prozeduralen Stil geschrieben, für Schleife eines beliebige Anzahl umgehen konnte (dis-Bezug Integer-Überlauf)?

Answer 1

Alle (anständige Implementierungen ;-) funktionalen Sprachen optimieren Endrekursion, aber das ist nicht das, was Sie hier tun, da der rekursive Aufruf nicht die letzte Operation ist (es muss durch die Zugabe folgte).

Also, man lernt schnell eine Hilfsfunktion zu verwenden, den Schwanz rekursiv (und nimmt die aktuelle Summe als Argument akkumuliert werden), so kann der Optimierer seine Arbeit tun, also nach Abzug der möglichen O'Caml Syntax, in denen ich m rostig:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Hier ist nun mal die Summe als ein Argument für den rekursiven Aufruf, das heißt vor der Rekursion selbst, und so kann Schwanz Optimierung tritt in (weil die Rekursion die letzte Sache ist, dass passieren muss!).

Answer 2

Funktionale Sprachen haben in der Regel einen viel größeren Stapel. Zum Beispiel habe ich eine Funktion speziell geschrieben Stapel Grenzen in OCaml zu testen, und es bekam 10.000 Anrufe über, bevor es barfed. Allerdings ist Ihr Punkt gültig. Stack-Überläufe sind immer noch etwas, das Sie in funktionalen Sprachen aufpassen müssen.

Eine der Strategien, die funktionalen Sprachen verwenden, um ihre Abhängigkeit von Rekursion zu mildern, ist die Verwendung von Tail-Call-Optimierung . Wenn der Anruf an die nächsten Rekursion der aktuellen Funktion die letzte Anweisung in der Funktion ist, kann der aktuelle Anruf aus dem Stapel abgelegt werden und den neuen Anruf an seiner Stelle instanziert. Die Montageanleitung, die generiert werden, werden im Grunde die gleichen wie die für while-Schleifen in imperativen Stil.

Ihre Funktion ist nicht Tail-Call optimierbar, da die Rekursion nicht der letzte Schritt ist. Es muss zurückkehren und dann kann es x zu dem Ergebnis hinzufügen. Normalerweise ist dies leicht zu umgehen, erstellen Sie nur eine Hilfsfunktion, die einen Akkumulator gelangt zusammen mit den anderen Parametern

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;

Answer 3

Einige funktionale Sprachen wie Scheme festlegen, dass Schwanz rel="nofollow Rekursion muss äquivalent Iteration sein optimiert werden; daher eine tail-rekursive Funktion in Schema wird nie in einem Stapelüberlauf führen, egal wie oft es recurses (vorausgesetzt, natürlich, dass es nicht auch nicht Rekursion oder in gegenseitiger Rekursion in anderen Orten neben dem Ende engagieren).

Die meisten anderen funktionalen Sprachen erfordern keine Endrekursion effizient umgesetzt werden; einige wählen, dies zu tun, andere nicht, aber es ist relativ einfach zu implementieren, so würde ich erwarten, dass die meisten Implementierungen tun.

Answer 4

Es ist sicherlich leicht für Anfänger tief Rekursion zu schreiben, die den Stapel blasen. Ziel Caml ist ungewöhnlich, dass die Bibliothek List Funktionen sind nicht stapel sicher für lange Listen . Anwendungen wie Unison tatsächlich die Caml Standard List Bibliothek mit einem Stapel-Safe ersetzt Ausführung. Die meisten anderen Implementierungen machen einen besseren Job mit dem Stapel. (Disclaimer:. Meine Informationen beschreibt Objective Caml 3,08; die aktuelle Version, 3.11, kann besser sein)

Standard ML von New Jersey ist in ungewöhnlich, dass es nicht einen Stapel nicht verwendet, so dass Ihre tief Rekursion weiter, bis Sie aus dem Haufen laufen. Es ist frei in Andrew Appel ausgezeichneten Buch Kompilieren mit Fortsetzungen .

Ich glaube nicht, dass es ein ernstes Problem hier; es ist mehr ein „point of awareness“, dass, wenn Sie eine Menge von rekursiven Code gehen zu schreiben, die Sie wahrscheinlicher sind in einer funktionalen Sprache zu tun, Sie wissen nicht Endrekursion sein und der Stack-Größe als im Vergleich zu der Größe der Daten Sie verarbeiten wird.

Answer 5

Das ist heikel - im Prinzip ja, aber die Compiler und Runtimes für funktionale Sprachen machen die erhöhten Grade an Rekursion in funktionalen Sprachen. Die einfachste ist, dass die meisten funktionale Sprache Runtimes einen viel größeren Stapel verlangt als normale iterative Programme verwenden würden. Aber zusätzlich zu, dass eine funktionale Sprache Compiler ist viel mehr in der Lage rekursiven Code in eine nicht-rekursive zu verwandeln aufgrund der wesentlich strengeren Einschränkungen der Sprache.