Wenn funktionale Programmiersprachen keinen Status speichern können, wie machen sie dann einfache Dinge wie das Lesen von Eingaben eines Benutzers? Wie "speichern" sie die Eingabe (oder speichern sie irgendwelche Daten für diese Angelegenheit?)
Zum Beispiel: Wie würde sich dieses einfache C-Ding in eine funktionierende Programmiersprache wie Haskell übersetzen lassen?
#include<stdio.h>
int main() {
int no;
scanf("%d",&no);
return 0;
}
(Meine Frage wurde von diesem ausgezeichneten Beitrag inspiriert: "Ausführung im Königreich der Substantive" . Durch das Lesen konnte ich besser verstehen, was genau objektorientierte Programmierung ist, wie Java sie auf eine extreme Weise implementiert und wie funktionale Programmiersprachen sind Kontrast.)
State
Monade ist sehr elegant; Auf der anderen SeiteIO
wird ein hässlicher, schmutziger Hack nur widerwillig eingesetzt.Antworten:
Wie Sie gesehen haben, hat die funktionale Programmierung keinen Status - aber das bedeutet nicht, dass sie keine Daten speichern kann. Der Unterschied besteht darin, dass ich eine (Haskell) -Anweisung nach dem Vorbild von schreibe
Mir wird garantiert, dass der Wert von
x
immer gleich ist in...
: nichts kann es möglicherweise ändern. Wenn ich eine Funktion habef :: String -> Integer
(eine Funktion, die eine Zeichenfolge verwendet und eine Ganzzahl zurückgibt), kann ich sicher sein, dassf
das Argument nicht geändert oder globale Variablen geändert oder Daten in eine Datei geschrieben werden usw. Wie sepp2k in einem Kommentar oben sagte, ist diese Nichtveränderlichkeit sehr hilfreich, um über Programme nachzudenken: Sie schreiben Funktionen, die Ihre Daten falten, spindeln und verstümmeln, geben neue Kopien zurück, damit Sie sie miteinander verketten können, und Sie können sicher sein, dass keine vorhanden sind von diesen Funktionsaufrufen kann alles "schädliche" tun. Sie wissen, dassx
das immer so istx
, und Sie müssen sich keine Sorgen machen, dass jemandx := foo bar
irgendwo zwischen der Erklärung von geschrieben hatx
und seine Verwendung, weil das unmöglich ist.Was ist nun, wenn ich Eingaben von einem Benutzer lesen möchte? Wie KennyTM sagte, ist die Idee, dass eine unreine Funktion eine reine Funktion ist, die die ganze Welt als Argument weitergegeben hat und sowohl ihr Ergebnis als auch die Welt zurückgibt. Natürlich möchten Sie dies nicht wirklich tun: Zum einen ist es schrecklich klobig, und zum anderen, was passiert, wenn ich dasselbe Weltobjekt wiederverwenden? Das wird also irgendwie abstrahiert. Haskell behandelt es mit dem IO-Typ:
Dies sagt uns, dass
main
es sich um eine E / A-Aktion handelt, die nichts zurückgibt. Das Ausführen dieser Aktion bedeutet, ein Haskell-Programm auszuführen. Die Regel lautet, dass E / A-Typen einer E / A-Aktion niemals entkommen können. In diesem Zusammenhang führen wir diese Aktion mit eindo
. SomitgetLine
kehrt einIO String
, die auf zwei Arten gedacht werden kann: Erstens, als eine Aktion , die, wenn sie ausgeführt wird , eine Zeichenfolge erzeugt; zweitens als eine Zeichenfolge, die von IO "verdorben" wird, da sie unrein erhalten wurde. Der erste ist korrekter, aber der zweite kann hilfreicher sein. Das<-
nimmt dasString
herausIO String
und speichert es instr
- aber da wir uns in einer E / A-Aktion befinden, müssen wir es wieder einpacken, damit es nicht "entkommen" kann. Die nächste Zeile versucht, eine Ganzzahl (reads
) zu lesen und erfasst die erste erfolgreiche Übereinstimmung (fst . head
); das ist alles rein (kein IO), also geben wir ihm einen Namen mitlet no = ...
. Wir können dann beideno
undstr
in der verwenden...
. Wir haben also unreine Daten (vongetLine
instr
) und reine Daten (let no = ...
) gespeichert .Dieser Mechanismus für die Arbeit mit E / A ist sehr leistungsfähig: Mit ihm können Sie den reinen, algorithmischen Teil Ihres Programms von der unreinen Seite der Benutzerinteraktion trennen und dies auf Typebene erzwingen. Ihre
minimumSpanningTree
Funktion kann möglicherweise an keiner anderen Stelle in Ihrem Code etwas ändern oder eine Nachricht an Ihren Benutzer schreiben und so weiter. Es ist sicher.Dies ist alles, was Sie wissen müssen, um IO in Haskell verwenden zu können. Wenn das alles ist, was Sie wollen, können Sie hier aufhören. Aber wenn Sie verstehen wollen, warum das funktioniert, lesen Sie weiter. (Und beachten Sie, dass dieses Zeug spezifisch für Haskell ist - andere Sprachen wählen möglicherweise eine andere Implementierung.)
Das schien also wahrscheinlich ein kleiner Betrug zu sein, der dem reinen Haskell irgendwie Unreinheit verlieh. Aber es ist nicht so - es stellt sich heraus, dass wir den E / A-Typ vollständig in reinem Haskell implementieren können (solange wir den erhalten
RealWorld
). Die Idee ist folgende: Eine E / A-AktionIO type
ist dieselbe wie eine FunktionRealWorld -> (type, RealWorld)
, die die reale Welt übernimmt und sowohl ein Objekt vom Typtype
als auch das modifizierte zurückgibtRealWorld
. Wir definieren dann ein paar Funktionen, damit wir diesen Typ verwenden können, ohne verrückt zu werden:Die erste ermöglicht es uns, über E / A-Aktionen zu sprechen, die nichts bewirken: Es
return 3
handelt sich um eine E / A-Aktion, die die reale Welt nicht abfragt und nur zurückkehrt3
. Der>>=
Operator, ausgesprochen "bind", ermöglicht es uns, E / A-Aktionen auszuführen. Es extrahiert den Wert aus der E / A-Aktion, leitet ihn und die reale Welt durch die Funktion und gibt die resultierende E / A-Aktion zurück. Beachten Sie, dass dies>>=
unsere Regel erzwingt, dass die Ergebnisse von E / A-Aktionen niemals entkommen dürfen.Wir können das Obige dann
main
in die folgenden gewöhnlichen Funktionsanwendungen umwandeln:Die Haskell-Laufzeit beginnt
main
mit der InitialeRealWorld
und wir sind fertig! Alles ist rein, es hat nur eine ausgefallene Syntax.[ Bearbeiten: Wie @Conal hervorhebt, ist dies nicht das, was Haskell verwendet, um E / A auszuführen . Dieses Modell bricht ab, wenn Sie Parallelität hinzufügen oder sich die Welt während einer E / A-Aktion auf irgendeine Weise ändern kann. Daher ist es für Haskell unmöglich, dieses Modell zu verwenden. Es ist nur für die sequentielle Berechnung genau. So kann es sein, dass Haskells IO ein bisschen ausweicht; Auch wenn es nicht so ist, ist es sicherlich nicht ganz so elegant. Siehe @ Conals Beobachtung, was Simon Peyton-Jones in Tackling the Awkward Squad [pdf] , Abschnitt 3.1 sagt ; er stellt vor, was in diesem Sinne einem alternativen Modell gleichkommen könnte, lässt es dann aber wegen seiner Komplexität fallen und geht einen anderen Weg.]
Dies erklärt wiederum (ziemlich genau), wie IO und die Veränderlichkeit im Allgemeinen in Haskell funktionieren. Wenn dies alles ist, was Sie wissen möchten, können Sie hier aufhören zu lesen. Wenn Sie eine letzte Dosis Theorie wünschen, lesen Sie weiter - aber denken Sie daran, dass wir zu diesem Zeitpunkt wirklich weit von Ihrer Frage entfernt sind!
Die letzte Sache: Es stellt sich heraus, dass diese Struktur - ein parametrischer Typ mit
return
und>>=
- sehr allgemein ist. Es heißt Monade unddo
Notationreturn
und>>=
arbeitet mit einem von ihnen. Wie Sie hier gesehen haben, sind Monaden nicht magisch; Alles, was magisch ist, ist, dassdo
Blöcke zu Funktionsaufrufen werden. DerRealWorld
Typ ist der einzige Ort, an dem wir Magie sehen. Typen wie[]
der Listenkonstruktor sind ebenfalls Monaden und haben nichts mit unreinem Code zu tun.Sie wissen jetzt (fast) alles über das Konzept einer Monade (mit Ausnahme einiger Gesetze, die erfüllt sein müssen, und der formalen mathematischen Definition), aber Ihnen fehlt die Intuition. Es gibt eine lächerliche Anzahl von Monaden-Tutorials online; Ich mag dieses , aber Sie haben Optionen. Dies wird Ihnen jedoch wahrscheinlich nicht helfen . Der einzige wirkliche Weg, um die Intuition zu erlangen, besteht darin, sie zu verwenden und zum richtigen Zeitpunkt einige Tutorials zu lesen.
Sie benötigen diese Intuition jedoch nicht, um IO zu verstehen . Das allgemeine Verständnis von Monaden ist das i-Tüpfelchen, aber Sie können jetzt IO verwenden. Sie können es verwenden, nachdem ich Ihnen die erste
main
Funktion gezeigt habe. Sie können IO-Code sogar so behandeln, als wäre er in einer unreinen Sprache! Aber denken Sie daran, dass es eine funktionale Repräsentation gibt: Niemand betrügt.(PS: Entschuldigung für die Länge. Ich bin ein bisschen weit gegangen.)
quelle
> >
in Vorlagen zu tun .)>>=
oder$
mehr hätten, wo stattdessen aufgerufenbind
und undapply
, würde Hashkell-Code viel weniger wie Perl aussehen. Ich meine, der Hauptunterschied zwischen Haskell- und Schemasyntax besteht darin, dass Haskell Infix-Operatoren und optionale Parens hat. Wenn die Leute keine übermäßigen Infix-Operatoren verwenden würden, würde Haskell einem Schema mit weniger Parens sehr ähnlich sehen.(functionName arg1 arg2)
. Wenn Sie die Parens entfernen, handelt es sich umfunctionName arg1 arg2
die Hashkell-Syntax. Wenn Sie Infix-Operatoren mit willkürlich schrecklichen Namen zulassen, erhalten Sie,arg1 §$%&/*°^? arg2
was noch mehr wie Haskell ist. (Ich necke übrigens nur, ich mag eigentlich Haskell).Viele gute Antworten hier, aber sie sind lang. Ich werde versuchen, eine hilfreiche kurze Antwort zu geben:
Funktionale Sprachen setzen den Status an denselben Stellen wie C: in benannten Variablen und in Objekten, die auf dem Heap zugeordnet sind. Die Unterschiede sind:
In einer funktionalen Sprache erhält eine "Variable" ihren Anfangswert, wenn sie in den Gültigkeitsbereich gelangt (durch einen Funktionsaufruf oder eine Let-Bindung), und dieser Wert ändert sich danach nicht mehr . In ähnlicher Weise wird ein auf dem Heap zugewiesenes Objekt sofort mit den Werten aller seiner Felder initialisiert, die sich danach nicht ändern.
"Zustandsänderungen" werden nicht durch Mutieren vorhandener Variablen oder Objekte behandelt, sondern durch Binden neuer Variablen oder Zuweisen neuer Objekte.
IO funktioniert mit einem Trick. Eine Nebeneffektberechnung, die eine Zeichenfolge erzeugt, wird durch eine Funktion beschrieben, die eine Welt als Argument verwendet und ein Paar zurückgibt, das die Zeichenfolge und eine neue Welt enthält. Die Welt enthält den Inhalt aller Festplatten, den Verlauf jedes jemals gesendeten oder empfangenen Netzwerkpakets, die Farbe jedes Pixels auf dem Bildschirm und ähnliches. Der Schlüssel zum Trick ist, dass der Zugang zur Welt sorgfältig eingeschränkt wird, so dass
Kein Programm kann eine Kopie der Welt erstellen (wo würden Sie sie ablegen?)
Kein Programm kann die Welt wegwerfen
Mit diesem Trick kann es eine einzigartige Welt geben, deren Zustand sich im Laufe der Zeit entwickelt. Das Sprachlaufzeitsystem, das nicht in einer funktionalen Sprache geschrieben ist, implementiert eine Nebeneffektberechnung, indem die vorhandene einzigartige Welt aktualisiert wird, anstatt eine neue zurückzugeben.
Dieser Trick wird von Simon Peyton Jones und Phil Wadler in ihrem wegweisenden Artikel "Imperative Functional Programming" wunderbar erklärt .
quelle
IO
Geschichte (World -> (a,World)
) ein Mythos, wenn sie auf Haskell angewendet wird, da dieses Modell nur rein sequentielle Berechnungen erklärt, während HaskellsIO
Typ Parallelität enthält. Mit "rein sequentiell" meine ich, dass sich nicht einmal die Welt (das Universum) zwischen dem Beginn und dem Ende einer imperativen Berechnung ändern darf, außer aufgrund dieser Berechnung. Zum Beispiel, während Ihr Computer tuckert, kann Ihr Gehirn usw. nicht. Parallelität kann durch etwas Ähnliches gehandhabt werdenWorld -> PowerSet [(a,World)]
, was Nichtdeterminismus und Verschachtelung ermöglicht.IO
dhWorld -> (a,World)
(dem populären und anhaltenden "Mythos", auf den ich mich bezog) zu verallgemeinern , und gibt stattdessen eine operative Erklärung. Einige Leute mögen operative Semantik, aber sie lassen mich völlig unzufrieden. Bitte sehen Sie meine längere Antwort in einer anderen Antwort.IO
alsRealWorld -> (a,RealWorld)
, aber anstatt die reale Welt tatsächlich darzustellen, ist es nur ein abstrakter Wert, der weitergegeben werden muss und schließlich vom Compiler optimiert wird.Ich breche eine Kommentarantwort auf eine neue Antwort ab, um mehr Platz zu schaffen:
Ich hab geschrieben:
Norman schrieb:
@Norman: Verallgemeinert in welchem Sinne? Ich schlage vor, dass das normalerweise gegebene Bezeichnungsmodell / die Erklärung
World -> (a,World)
nicht mit Haskell übereinstimmt,IO
da es Nichtdeterminismus und Parallelität nicht berücksichtigt. Es mag ein komplexeres Modell geben, das passt, wie zum BeispielWorld -> PowerSet [(a,World)]
, aber ich weiß nicht, ob ein solches Modell ausgearbeitet und angemessen und konsistent gezeigt wurde. Ich persönlich bezweifle, dass ein solches Tier gefunden werden kann, daIO
es von Tausenden von FFI-importierten imperativen API-Aufrufen bevölkert wird. UndIO
erfüllt als solches seinen Zweck:(Aus Simon PJs POPL-Vortrag Das Tragen des Haarhemdes Tragen des Haarhemdes : eine Retrospektive über Haskell .)
In Abschnitt 3.1 von Tackling the Awkward Squad zeigt Simon, worauf es nicht ankommt
type IO a = World -> (a, World)
, einschließlich "Der Ansatz lässt sich nicht gut skalieren, wenn wir Parallelität hinzufügen". Dann schlägt er ein mögliches alternatives Modell vor und gibt dann den Versuch der denotationalen Erklärung aufDieses Versäumnis, ein genaues und nützliches Bezeichnungsmodell zu finden, ist der Grund dafür, warum ich Haskell IO als eine Abkehr vom Geist und den tiefen Vorteilen dessen sehe, was wir "funktionale Programmierung" nennen oder was Peter Landin genauer als "denotative Programmierung" bezeichnet. . Siehe Kommentare hier.
quelle
World -> PowerSet [World]
klar der Nichtdeterminismus und die Parallelität im Interleaving-Stil erfasst werden. Diese Domänendefinition sagt mir, dass die gleichzeitige imperative Mainstream-Programmierung (einschließlich der von Haskell) unlösbar ist - buchstäblich exponentiell komplexer als sequentiell. Der große Schaden, den ich im Haskell-IO
Mythos sehe, besteht darin, diese inhärente Komplexität zu verschleiern und ihren Sturz zu demotivieren.World -> (a, World)
nicht der Fall ist, ist mir nicht klar, warum der Ersatz dieWorld -> PowerSet [(a,World)]
Parallelität usw. ordnungsgemäß modelliert. Für mich bedeutet dies, dass Programme inIO
so etwas wie der Listenmonade ausgeführt werden sollten und sich auf jedes zurückgegebene Element des Satzes anwenden durch dieIO
Aktion. Was vermisse ich?World -> PowerSet [(a,World)]
nicht richtig. Versuchen wir esWorld -> PowerSet ([World],a)
stattdessen.PowerSet
gibt die Menge der möglichen Ergebnisse an (Nichtdeterminismus).[World]
ist eine Folge von Zwischenzuständen (nicht die Liste / Nichtdeterminismus-Monade), die eine Verschachtelung (Thread-Planung) ermöglicht. Und([World],a)
ist auch nicht ganz richtig, da es den Zugriff ermöglicht,a
bevor alle Zwischenzustände durchlaufen werden. Definieren Sie stattdessen useWorld -> PowerSet (Computation a)
wheredata Computation a = Result a | Step World (Computation a)
World -> (a, World)
. Wenn derWorld
Typ wirklich die ganze Welt umfasst, enthält er auch die Informationen zu allen gleichzeitig ablaufenden Prozessen und auch den 'zufälligen Keim' aller Nichtdeterminismus. Das ErgebnisWorld
ist eine Welt mit fortgeschrittener Zeit und einer gewissen Interaktion. Das einzige wirkliche Problem bei diesem Modell scheint zu sein, dass es zu allgemein ist und die Werte vonWorld
nicht konstruiert und manipuliert werden können.Die funktionale Programmierung leitet sich aus der Lambda-Rechnung ab. Wenn Sie die funktionale Programmierung wirklich verstehen möchten, besuchen Sie http://worrydream.com/AlligatorEggs/.
Es ist eine "unterhaltsame" Art, Lambda-Kalkül zu lernen und Sie in die aufregende Welt der funktionalen Programmierung zu entführen!
Wie hilfreich die Kenntnis von Lambda Calculus bei der funktionalen Programmierung ist.
Lambda Calculus ist also die Grundlage für viele reale Programmiersprachen wie Lisp, Scheme, ML, Haskell, ....
Angenommen, wir möchten eine Funktion beschreiben, die jeder Eingabe drei hinzufügt, damit wir schreiben:
Lesen Sie "plus3 ist eine Funktion, die, wenn sie auf eine beliebige Zahl x angewendet wird, den Nachfolger des Nachfolgers des Nachfolgers von x ergibt"
Beachten Sie, dass die Funktion, die einer beliebigen Zahl 3 hinzufügt, nicht plus3 heißen muss. Der Name „plus3“ ist nur eine praktische Abkürzung für die Benennung dieser Funktion
(
plus3 x) (succ 0) ≡ ((λ x. (succ (succ (succ x)))) (succ 0))
Beachten Sie, dass wir das Lambda-Symbol für eine Funktion verwenden (ich denke, es sieht aus wie ein Alligator, von dem ich vermute, dass die Idee für Alligator-Eier stammt).
Das Lambda-Symbol ist der Alligator (eine Funktion) und das x ist seine Farbe. Sie können sich x auch als Argument vorstellen (Lambda-Kalkül-Funktionen haben eigentlich nur ein Argument), den Rest können Sie sich als Hauptteil der Funktion vorstellen.
Betrachten Sie nun die Abstraktion:
Das Argument f wird an einer Funktionsposition (in einem Aufruf) verwendet. Wir nennen eine Funktion höherer Ordnung, weil sie eine andere Funktion als Eingabe verwendet. Sie können sich die anderen Funktionsaufrufe f als " Eier " vorstellen . Wenn wir nun die beiden Funktionen oder " Alligatoren " verwenden, die wir erstellt haben, können wir so etwas tun:
Wenn Sie bemerken, können Sie sehen, dass unser λ f Alligator unseren λ x Alligator und dann den λ x Alligator frisst und stirbt. Dann wird unser λ x Alligator in den Alligator-Eiern des λ f wiedergeboren. Dann wiederholt sich der Vorgang und der λ x Alligator links frisst nun den anderen λ x Alligator rechts.
Dann können Sie diese einfachen Regeln von „verwenden Alligators “ Essen „ Alligators “ eine Grammatik zu entwerfen und damit Funktions Programmiersprachen waren geboren!
Wenn Sie also Lambda Calculus kennen, werden Sie verstehen, wie funktionale Sprachen funktionieren.
quelle
Die Technik zur Handhabung des Zustands in Haskell ist sehr einfach. Und Sie müssen Monaden nicht verstehen, um sie in den Griff zu bekommen.
In einer Programmiersprache mit Status haben Sie normalerweise irgendwo einen Wert gespeichert, etwas Code wird ausgeführt, und dann haben Sie einen neuen Wert gespeichert. In imperativen Sprachen befindet sich dieser Zustand nur irgendwo "im Hintergrund". In einer (reinen) Funktionssprache machen Sie dies explizit, also schreiben Sie explizit die Funktion, die den Zustand transformiert.
Anstatt also einen Status vom Typ X zu haben, schreiben Sie Funktionen, die X X zuordnen. Das war's! Sie wechseln vom Denken über den Status zum Überlegen, welche Operationen Sie für den Status ausführen möchten. Sie können diese Funktionen dann miteinander verketten und auf verschiedene Weise kombinieren, um ganze Programme zu erstellen. Natürlich können Sie nicht nur X auf X abbilden. Sie können Funktionen schreiben, um verschiedene Datenkombinationen als Eingabe zu verwenden und am Ende verschiedene Kombinationen zurückzugeben.
Monaden sind unter vielen ein Werkzeug, um dies zu organisieren. Aber Monaden sind eigentlich nicht die Lösung des Problems. Die Lösung besteht darin, über Zustandstransformationen statt über Staat nachzudenken.
Dies funktioniert auch mit E / A. In der Tat passiert Folgendes: Anstatt Eingaben vom Benutzer mit einem direkten Äquivalent von zu erhalten
scanf
und diese irgendwo zu speichern, schreiben Sie stattdessen eine Funktion, um zu sagen, was Sie mit dem Ergebnis tun würden,scanf
wenn Sie es hätten, und übergeben Sie diese dann Funktion zur E / A-API. Genau das>>=
macht es, wenn Sie dieIO
Monade in Haskell verwenden. Sie müssen also niemals das Ergebnis einer E / A irgendwo speichern - Sie müssen nur Code schreiben, der angibt, wie Sie es transformieren möchten.quelle
(Einige funktionale Sprachen erlauben unreine Funktionen.)
Bei rein funktionalen Sprachen wird die reale Interaktion normalerweise als eines der Funktionsargumente wie folgt aufgenommen:
Verschiedene Sprachen haben unterschiedliche Strategien, um die Welt vom Programmierer weg zu abstrahieren. Haskell verwendet zum Beispiel Monaden, um das
world
Argument zu verbergen .Aber der reine Teil der funktionalen Sprache selbst ist bereits vollständig, was bedeutet, dass alles, was in C machbar ist, auch in Haskell machbar ist. Der Hauptunterschied zur imperativen Sprache besteht darin, die vorhandenen Zustände zu ändern:
Sie integrieren den Modifikationsteil in einen Funktionsaufruf und wandeln Schleifen normalerweise in Rekursionen um:
quelle
computeSumOfSquares min max = sum [x*x | x <- [min..max]]
;-)sum
? Rekursion ist weiterhin erforderlich.Funktionssprache kann Zustand speichern! Sie ermutigen oder zwingen Sie normalerweise nur, dies ausdrücklich zu tun.
Schauen Sie sich zum Beispiel Haskells State Monad an .
quelle
State
oderMonad
den Zustand ermöglicht, da beide als einfache, allgemeine und funktionale Werkzeuge definiert sind. Sie erfassen nur relevante Muster, sodass Sie das Rad nicht so sehr neu erfinden müssen.könnte nützlich sein, Funktionsprogrammierung für den Rest von uns
quelle
haskell:
Natürlich können Sie Variablen in funktionalen Sprachen Dinge zuweisen. Sie können sie einfach nicht ändern (daher sind im Grunde alle Variablen Konstanten in funktionalen Sprachen).
quelle
f(x)
und den Wert von x sehen möchten, müssen Sie nur zu der Stelle gehen, an der x definiert ist. Wenn x veränderlich wäre, müssten Sie auch überlegen, ob es einen Punkt gibt, an dem x zwischen seiner Definition und seiner Verwendung geändert werden könnte (was nicht trivial ist, wenn x keine lokale Variable ist).