Warum sind Funktionen in Ocaml / F # nicht standardmäßig rekursiv?

103

Warum sind Funktionen in F # und Ocaml (und möglicherweise in anderen Sprachen) nicht standardmäßig rekursiv?

Mit anderen Worten, warum haben die Sprachdesigner entschieden, dass es eine gute Idee ist, Sie explizit dazu zu bringen, receine Erklärung einzugeben wie:

let rec foo ... = ...

und nicht standardmäßig die Funktion rekursiv geben? Warum ein explizites recKonstrukt?

nsantorello
quelle

Antworten:

87

Die französischen und britischen Nachkommen der ursprünglichen ML haben unterschiedliche Entscheidungen getroffen und ihre Entscheidungen wurden im Laufe der Jahrzehnte an die modernen Varianten vererbt. Das ist also nur ein Vermächtnis, aber es beeinflusst die Redewendungen in diesen Sprachen.

Funktionen sind in der französischen CAML-Sprachfamilie (einschließlich OCaml) standardmäßig nicht rekursiv. Diese Auswahl erleichtert das Ersetzen von Funktions- (und Variablen-) Definitionen mithilfe vonlet in diesen Sprachen, da Sie im Hauptteil einer neuen Definition auf die vorherige Definition verweisen können. F # hat diese Syntax von OCaml geerbt.

Beispiel: Ersetzen der Funktion pbeim Berechnen der Shannon-Entropie einer Sequenz in OCaml:

let shannon fold p =
  let p x = p x *. log(p x) /. log 2.0 in
  let p t x = t +. p x in
  -. fold p 0.0

Beachten Sie, wie das Argument pfür die shannonFunktion höherer Ordnung pin der ersten Zeile des Körpers durch ein anderes und dann durch ein anderes ersetzt wirdp in der zweiten Zeile des Körpers wird.

Umgekehrt hat der britische SML-Zweig der ML-Sprachfamilie die andere Wahl getroffen, und die an SML fungebundenen Funktionen sind standardmäßig rekursiv. Wenn die meisten Funktionsdefinitionen keinen Zugriff auf vorherige Bindungen ihres Funktionsnamens benötigen, führt dies zu einfacherem Code. Allerdings sind superceded Funktionen aus verschiedenen Namen zu verwenden ( f1, f2usw.) , die den Umfang verpestet und macht es möglich, versehentlich invoke die falsche „Version“ einer Funktion. Und es gibt jetzt eine Diskrepanz zwischen implizit rekursiv fungebundenen Funktionen und nicht rekursiv valgebundenen Funktionen.

Haskell ermöglicht es, die Abhängigkeiten zwischen Definitionen abzuleiten, indem sie auf ihre Reinheit beschränkt werden. Dies lässt Spielzeugmuster einfacher aussehen, ist aber an anderer Stelle mit hohen Kosten verbunden.

Beachten Sie, dass die Antworten von Ganesh und Eddie rote Heringe sind. Sie erklärten, warum Gruppen von Funktionen nicht in einem Riesen platziert werden können, let rec ... and ...da dies Auswirkungen darauf hat, wann Typvariablen verallgemeinert werden. Dies hat nichts mit recder Standardeinstellung in SML zu tun , nicht jedoch in OCaml.

JD
quelle
3
Ich denke nicht, dass es sich um rote Heringe handelt: Ohne die Einschränkungen der Inferenz würden ganze Programme oder Module wahrscheinlich automatisch als gegenseitig rekursiv behandelt, wie es die meisten anderen Sprachen tun. Das würde die spezifische Entwurfsentscheidung darüber treffen, ob "rec" erforderlich sein sollte oder nicht.
GS - Entschuldigen Sie sich bei Monica
"... automatisch wie die meisten anderen Sprachen als gegenseitig rekursiv behandelt". BASIC, C, C ++, Clojure, Erlang, F #, Faktor, Forth, Fortran, Groovy, OCaml, Pascal, Smalltalk und Standard ML nicht.
JD
3
Für C / C ++ sind nur Prototypen für Vorwärtsdefinitionen erforderlich, bei denen es nicht wirklich darum geht, die Rekursion explizit zu markieren. Java, C # und Perl haben sicherlich eine implizite Rekursion. Wir könnten in eine endlose Debatte über die Bedeutung von "am meisten" und die Bedeutung jeder Sprache geraten, also lassen Sie uns einfach mit "sehr vielen" anderen Sprachen zufrieden sein.
GS - Entschuldigen Sie sich bei Monica
3
"C / C ++ erfordert nur Prototypen für Vorwärtsdefinitionen, bei denen es nicht wirklich darum geht, die Rekursion explizit zu markieren." Nur im Sonderfall der Selbstrekursion. Im allgemeinen Fall der gegenseitigen Rekursion sind Vorwärtsdeklarationen sowohl in C als auch in C ++ obligatorisch.
JD
2
Tatsächlich sind in C ++ in Klassenbereichen keine Vorwärtsdeklarationen erforderlich, dh statische Methoden können sich ohne Deklarationen gegenseitig aufrufen.
polkovnikov.ph
52

Ein entscheidender Grund für die explizite Verwendung von rec ist die Hindley-Milner-Typinferenz, die allen statisch typisierten funktionalen Programmiersprachen zugrunde liegt (wenn auch auf verschiedene Weise geändert und erweitert).

Wenn Sie eine Definition haben let f x = x, erwarten Sie, dass sie einen Typ hat 'a -> 'aund 'aan verschiedenen Stellen auf verschiedene Typen anwendbar ist . Aber ebenso, wenn Sie schreiben let g x = (x + 1) + ..., würden Sie erwarten x, als intim Rest des Körpers von behandelt zu werdeng .

Die Art und Weise, wie die Hindley-Milner-Folgerung mit dieser Unterscheidung umgeht, erfolgt durch einen expliziten Verallgemeinerungsschritt . An bestimmten Stellen bei der Verarbeitung Ihres Programms stoppt das Typsystem und sagt "OK, die Typen dieser Definitionen werden an dieser Stelle verallgemeinert, sodass alle freien Typvariablen in ihrem Typ frisch sind , wenn jemand sie verwendet instanziiert werden und somit wird keine anderen Verwendungen dieser Definition stören. "

Es stellt sich heraus, dass der sinnvolle Ort für diese Verallgemeinerung die Überprüfung eines gegenseitig rekursiven Satzes von Funktionen ist. Früher, und Sie verallgemeinern zu viel, was zu Situationen führt, in denen Typen tatsächlich kollidieren könnten. Später, und Sie werden zu wenig verallgemeinern und Definitionen erstellen, die nicht mit Instanzen von mehreren Typen verwendet werden können.

Was kann der Typprüfer tun, wenn er wissen muss, welche Definitionssätze sich gegenseitig rekursiv sind? Eine Möglichkeit besteht darin, einfach eine Abhängigkeitsanalyse für alle Definitionen in einem Bereich durchzuführen und sie in die kleinstmöglichen Gruppen zu ordnen. Haskell tut dies tatsächlich, aber in Sprachen wie F # (und OCaml und SML), die uneingeschränkte Nebenwirkungen haben, ist dies eine schlechte Idee, da möglicherweise auch die Nebenwirkungen neu angeordnet werden. Stattdessen wird der Benutzer aufgefordert, explizit zu markieren, welche Definitionen sich gegenseitig rekursiv sind, und somit durch Erweiterung, wo eine Verallgemeinerung erfolgen soll.

GS - Entschuldige dich bei Monica
quelle
3
Ähm, nein. Ihr erster Absatz ist falsch (Sie sprechen von der expliziten Verwendung von "und" und nicht von "rec"), und folglich ist der Rest irrelevant.
JD
5
Ich war mit dieser Anforderung nie zufrieden. Danke für die Erklärung. Ein weiterer Grund, warum Haskell im Design überlegen ist.
Bent Rasmussen
9
NEIN!!!! WIE KONNTE DAS PASSIEREN?! Diese Antwort ist einfach falsch! Bitte lesen Sie Harrops Antwort unten oder lesen Sie die Definition von Standard ML (Milner, Tofte, Harper, MacQueen - 1997) [S.24]
Lambdapower
9
Wie ich in meiner Antwort sagte, ist das Problem der Typinferenz einer der Gründe für die Notwendigkeit einer Aufzeichnung, anstatt der einzige Grund zu sein. Jons Antwort ist auch eine sehr gültige Antwort (abgesehen von dem üblichen abfälligen Kommentar zu Haskell); Ich glaube nicht, dass die beiden in Opposition sind.
GS - Entschuldigen Sie sich bei Monica
16
"Das Problem der Typinferenz ist einer der Gründe für die Notwendigkeit von rec". Die Tatsache, dass OCaml benötigt rec, SML jedoch nicht, ist ein offensichtliches Gegenbeispiel. Wenn aus den von Ihnen beschriebenen Gründen Typinferenz das Problem gewesen wäre, hätten OCaml und SML nicht unterschiedliche Lösungen wählen können. Der Grund ist natürlich, dass Sie darüber sprechen and, um Haskell relevant zu machen.
JD
10

Es gibt zwei Hauptgründe, warum dies eine gute Idee ist:

Wenn Sie rekursive Definitionen aktivieren, können Sie zunächst nicht auf eine vorherige Bindung eines gleichnamigen Werts verweisen. Dies ist oft eine nützliche Redewendung, wenn Sie beispielsweise ein vorhandenes Modul erweitern.

Zweitens sind rekursive Werte und insbesondere Sätze von gegenseitig rekursiven Werten viel schwerer zu begründen als Definitionen, die in der richtigen Reihenfolge ablaufen, wobei jede neue Definition auf dem aufbaut, was bereits definiert wurde. Es ist schön, beim Lesen eines solchen Codes die Garantie zu haben, dass neue Definitionen mit Ausnahme von Definitionen, die explizit als rekursiv gekennzeichnet sind, nur auf vorherige Definitionen verweisen können.

zrr
quelle
4

Einige Vermutungen:

  • letwird nicht nur zum Binden von Funktionen verwendet, sondern auch von anderen regulären Werten. Die meisten Werteformen dürfen nicht rekursiv sein. Bestimmte Formen rekursiver Werte sind zulässig (z. B. Funktionen, verzögerte Ausdrücke usw.). Daher ist eine explizite Syntax erforderlich, um dies anzuzeigen.
  • Es ist möglicherweise einfacher, nicht rekursive Funktionen zu optimieren
  • Der Abschluss, der beim Erstellen einer rekursiven Funktion erstellt wird, muss einen Eintrag enthalten, der auf die Funktion selbst verweist (damit die Funktion sich selbst rekursiv aufrufen kann). Dies macht rekursive Abschlüsse komplizierter als nicht rekursive Abschlüsse. Es kann also hilfreich sein, einfachere nicht rekursive Abschlüsse zu erstellen, wenn Sie keine Rekursion benötigen
  • Sie können eine Funktion anhand einer zuvor definierten Funktion oder eines gleichnamigen Werts definieren. obwohl ich denke, dass dies eine schlechte Praxis ist
  • Zusätzliche Sicherheit? Stellt sicher, dass Sie das tun, was Sie beabsichtigt haben. Wenn Sie beispielsweise nicht beabsichtigen, dass es rekursiv ist, aber versehentlich einen Namen innerhalb der Funktion mit demselben Namen wie die Funktion selbst verwendet haben, wird dies höchstwahrscheinlich beanstandet (es sei denn, der Name wurde zuvor definiert).
  • Das letKonstrukt ähnelt dem letKonstrukt in Lisp und Scheme; die nicht rekursiv sind. letrecIn Schema gibt es ein separates Konstrukt für rekursive Lasst uns
newacct
quelle
"Die meisten Formen von Werten dürfen nicht rekursiv sein. Bestimmte Formen von rekursiven Werten sind zulässig (z. B. Funktionen, verzögerte Ausdrücke usw.), daher ist eine explizite Syntax erforderlich, um dies anzuzeigen." Das gilt für F #, aber ich bin mir nicht sicher, wie wahr es für OCaml ist, wo Sie es tun können let rec xs = 0::ys and ys = 1::xs.
JD
4

Angesichts dessen:

let f x = ... and g y = ...;;

Vergleichen Sie:

let f a = f (g a)

Mit diesem:

let rec f a = f (g a)

Ersteres definiert neu f, um das zuvor definierte fauf das Ergebnis der Anwendung gauf anzuwenden a. Letztere Redefines fSchleife immer Anwendung gzua , was in der Regel nicht , was Sie wollen in ML - Varianten.

Das heißt, es ist eine Sache im Stil eines Sprachdesigners. Mach einfach mit.

James Woodyatt
quelle
1

Ein großer Teil davon ist, dass der Programmierer mehr Kontrolle über die Komplexität seiner lokalen Bereiche hat. Das Spektrum let, let*und let recbietet ein zunehmendes Maß an Stromversorgung und Kosten. let*und let recsind im Wesentlichen verschachtelte Versionen des einfachen let, so dass die Verwendung einer der beiden teurer ist. Mit dieser Einstufung können Sie die Optimierung Ihres Programms mikromanagen, indem Sie auswählen, welche Ebene Sie für die jeweilige Aufgabe benötigen. Wenn Sie keine Rekursion benötigen oder nicht auf frühere Bindungen verweisen können, können Sie auf eine einfache Erlaubnis zurückgreifen, um ein wenig Leistung zu sparen.

Es ähnelt den abgestuften Gleichheitsprädikaten in Schema. ( das heißt eq?, eqv?und equal?)

Evan Meagher
quelle