Wie funktionieren funktionale Programmiersprachen?

92

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.)

Laser
quelle
Mögliches Duplikat von stackoverflow.com/questions/1916692/…
Chris Conway
4
Das ist eine gute Frage, denn auf systemischer Ebene benötigt ein Computer den Status, um nützlich zu sein. Ich habe ein Interview mit Simon Peyton-Jones (einem der Entwickler hinter Haskell) gesehen, in dem er sagte, dass ein Computer, auf dem immer nur völlig zustandslose Software lief, nur eines erreichen kann: Heiß werden! Viele gute Antworten unten. Es gibt zwei Hauptstrategien: 1) Machen Sie eine unreine Sprache. 2) Machen Sie einen listigen Plan, um den Zustand zu abstrahieren, was Haskell tut, indem Sie im Wesentlichen eine neue, leicht veränderte Welt erschaffen, anstatt die alte zu modifizieren.
schadet
14
Hat SPJ dort nicht über Nebenwirkungen gesprochen, nicht über den Zustand? Reine Berechnungen haben viele Zustände, die in Argumentbindungen und im Aufrufstapel enthalten sind, aber ohne Nebenwirkungen (z. B. E / A) können sie nichts Nützliches bewirken. Die beiden Punkte sind wirklich sehr unterschiedlich - es gibt jede Menge reinen, zustandsbehafteten Haskell-Codes, und die StateMonade ist sehr elegant; Auf der anderen Seite IOwird ein hässlicher, schmutziger Hack nur widerwillig eingesetzt.
CA McCann
4
Camccann hat es richtig. Es gibt viel Zustand in funktionalen Sprachen. Es wird nur explizit verwaltet, anstatt "gruselige Fernwirkung" wie in imperativen Sprachen.
Nur meine richtige Meinung
1
Hier kann es zu Verwirrung kommen. Vielleicht brauchen Computer Effekte, um nützlich zu sein, aber ich denke, hier geht es um Programmiersprachen, nicht um Computer.
Conal

Antworten:

80

Wenn funktionale Programmiersprachen keinen Status speichern können, wie machen sie dann einige einfache Dinge wie das Lesen von Eingaben eines Benutzers (ich meine, wie "speichern" sie diese) oder das Speichern von Daten für diese Angelegenheit?

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

let x = func value 3.14 20 "random"
in ...

Mir wird garantiert, dass der Wert von ximmer gleich ist in ...: nichts kann es möglicherweise ändern. Wenn ich eine Funktion habe f :: String -> Integer(eine Funktion, die eine Zeichenfolge verwendet und eine Ganzzahl zurückgibt), kann ich sicher sein, dass fdas 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, dass xdas immer so ist x, und Sie müssen sich keine Sorgen machen, dass jemand x := foo barirgendwo 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:

main :: IO ()
main = do str <- getLine
          let no = fst . head $ reads str :: Integer
          ...

Dies sagt uns, dass maines 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 ein do. Somit getLinekehrt ein IO 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 das Stringheraus IO Stringund speichert es in str- 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 mit let no = .... Wir können dann beide nound strin der verwenden .... Wir haben also unreine Daten (von getLinein str) 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 minimumSpanningTreeFunktion 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-Aktion IO typeist dieselbe wie eine Funktion RealWorld -> (type, RealWorld), die die reale Welt übernimmt und sowohl ein Objekt vom Typ typeals auch das modifizierte zurückgibt RealWorld. Wir definieren dann ein paar Funktionen, damit wir diesen Typ verwenden können, ohne verrückt zu werden:

return :: a -> IO a
return a = \rw -> (a,rw)

(>>=) :: IO a -> (a -> IO b) -> IO b
ioa >>= fn = \rw -> let (a,rw') = ioa rw in fn a rw'

Die erste ermöglicht es uns, über E / A-Aktionen zu sprechen, die nichts bewirken: Es return 3handelt sich um eine E / A-Aktion, die die reale Welt nicht abfragt und nur zurückkehrt 3. 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 mainin die folgenden gewöhnlichen Funktionsanwendungen umwandeln:

main = getLine >>= \str -> let no = (fst . head $ reads str :: Integer) in ...

Die Haskell-Laufzeit beginnt mainmit der Initiale RealWorldund 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 returnund >>=- sehr allgemein ist. Es heißt Monade und doNotation returnund >>=arbeitet mit einem von ihnen. Wie Sie hier gesehen haben, sind Monaden nicht magisch; Alles, was magisch ist, ist, dass doBlöcke zu Funktionsaufrufen werden. Der RealWorldTyp 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 mainFunktion 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.)

Antal Spector-Zabusky
quelle
6
Das, was mich immer an Haskell interessiert (was ich gemacht habe und tapfere Lernanstrengungen unternehme), ist die Hässlichkeit der Syntax. Es ist, als hätten sie die schlimmsten Teile jeder anderen Sprache genommen, sie in einen Eimer geworfen und sich wütend gerührt. Und diese Leute werden sich dann über die zugegebenermaßen (stellenweise) seltsame Syntax von C ++ beschweren!
19
Neil: Wirklich? Ich finde Haskells Syntax tatsächlich sehr sauber. Ich bin neugierig; Worauf beziehen Sie sich insbesondere? (Für das, was es wert ist, stört mich C ++ auch nicht wirklich, außer der Notwendigkeit, > >in Vorlagen zu tun .)
Antal Spector-Zabusky
6
Meines Erachtens ist Haskells Syntax zwar nicht so sauber wie beispielsweise Scheme, aber sie beginnt nicht mit der abscheulichen Syntax selbst der schönsten der geschweiften Klammern zu vergleichen, von denen C ++ zu den schlechtesten gehört . Keine Berücksichtigung des Geschmacks, nehme ich an. Ich glaube nicht, dass es eine Sprache gibt, die jeder syntaktisch ansprechend findet.
CA McCann
8
@NeilButterworth: Ich vermute, Ihr Problem ist weniger die Syntax als vielmehr die Funktionsnamen. Wenn Funktionen wie >>=oder $mehr hätten, wo stattdessen aufgerufen bindund und apply, 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.
sepp2k
5
@camcann: Nun, Punkt, aber was ich meinte ist: Die grundlegende Syntax des Schemas ist (functionName arg1 arg2). Wenn Sie die Parens entfernen, handelt es sich um functionName arg1 arg2die Hashkell-Syntax. Wenn Sie Infix-Operatoren mit willkürlich schrecklichen Namen zulassen, erhalten Sie, arg1 §$%&/*°^? arg2was noch mehr wie Haskell ist. (Ich necke übrigens nur, ich mag eigentlich Haskell).
sepp2k
23

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 .

Norman Ramsey
quelle
4
Soweit ich das beurteilen kann, ist diese IOGeschichte ( World -> (a,World)) ein Mythos, wenn sie auf Haskell angewendet wird, da dieses Modell nur rein sequentielle Berechnungen erklärt, während Haskells IOTyp 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 werden World -> PowerSet [(a,World)], was Nichtdeterminismus und Verschachtelung ermöglicht.
Conal
1
@Conal: Ich denke, die IO-Geschichte lässt sich ziemlich gut auf Nichtdeterminismus und Interleaving verallgemeinern. Wenn ich mich recht erinnere, gibt es eine ziemlich gute Erklärung in der Zeitung "Awkward Squad". Aber ich kenne kein gutes Papier, das die wahre Parallelität klar erklärt.
Norman Ramsey
3
So wie ich es verstehe, gibt das "Awkward Squad" -Papier den Versuch auf, das einfache Bezeichnungsmodell von IOdh World -> (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.
Conal
+1 Dies hat mir geholfen, IO-Monaden viel besser zu verstehen und die Frage zu beantworten.
CaptainCasey
Die meisten Haskell-Compiler definieren tatsächlich IOals RealWorld -> (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.
Jeremy List
19

Ich breche eine Kommentarantwort auf eine neue Antwort ab, um mehr Platz zu schaffen:

Ich hab geschrieben:

Soweit ich das beurteilen kann, ist diese IOGeschichte ( World -> (a,World)) ein Mythos, wenn sie auf Haskell angewendet wird, da dieses Modell nur rein sequentielle Berechnungen erklärt, während Haskells IOTyp 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 werden World -> PowerSet [(a,World)], was Nichtdeterminismus und Verschachtelung ermöglicht.

Norman schrieb:

@Conal: Ich denke, die IO-Geschichte lässt sich ziemlich gut auf Nichtdeterminismus und Interleaving verallgemeinern. Wenn ich mich recht erinnere, gibt es eine ziemlich gute Erklärung in der Zeitung "Awkward Squad". Aber ich kenne kein gutes Papier, das die wahre Parallelität klar erklärt.

@Norman: Verallgemeinert in welchem ​​Sinne? Ich schlage vor, dass das normalerweise gegebene Bezeichnungsmodell / die Erklärung World -> (a,World)nicht mit Haskell übereinstimmt, IOda es Nichtdeterminismus und Parallelität nicht berücksichtigt. Es mag ein komplexeres Modell geben, das passt, wie zum Beispiel World -> 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, da IOes von Tausenden von FFI-importierten imperativen API-Aufrufen bevölkert wird. Und IOerfüllt als solches seinen Zweck:

Offenes Problem: Die IOMonade ist zu Haskells Sünde geworden. (Wenn wir etwas nicht verstehen, werfen wir es in die IO-Monade.)

(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 auf

Stattdessen werden wir jedoch eine operationelle Semantik anwenden, die auf Standardansätzen für die Semantik von Prozesskalkülen basiert.

Dieses 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.

Conal
quelle
Danke für die längere Antwort. Ich glaube, ich wurde von unseren neuen operativen Oberherren einer Gehirnwäsche unterzogen. Left Mover und Right Mover usw. haben es möglich gemacht, einige nützliche Theoreme zu beweisen. Haben Sie ein Bezeichnungsmodell gesehen , das für Nichtdeterminismus und Parallelität verantwortlich ist? Ich habe nicht.
Norman Ramsey
1
Mir gefällt, wie 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- IOMythos sehe, besteht darin, diese inhärente Komplexität zu verschleiern und ihren Sturz zu demotivieren.
Conal
Obwohl ich sehe, warum dies World -> (a, World)nicht der Fall ist, ist mir nicht klar, warum der Ersatz die World -> PowerSet [(a,World)]Parallelität usw. ordnungsgemäß modelliert. Für mich bedeutet dies, dass Programme in IOso etwas wie der Listenmonade ausgeführt werden sollten und sich auf jedes zurückgegebene Element des Satzes anwenden durch die IOAktion. Was vermisse ich?
Antal Spector-Zabusky
3
@Absz: Erstens ist mein vorgeschlagenes Modell World -> PowerSet [(a,World)]nicht richtig. Versuchen wir es World -> PowerSet ([World],a)stattdessen. PowerSetgibt 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, abevor alle Zwischenzustände durchlaufen werden. Definieren Sie stattdessen use World -> PowerSet (Computation a)wheredata Computation a = Result a | Step World (Computation a)
Conal
Ich sehe immer noch kein Problem mit World -> (a, World). Wenn der WorldTyp 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 Ergebnis Worldist 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 von Worldnicht konstruiert und manipuliert werden können.
Rotsor
17

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:

plus3 x = succ(succ(succ x)) 

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:

g  λ f. (f (f (succ 0)))

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:

(g plus3) =  f. (f (f (succ 0)))(λ x . (succ (succ (succ x)))) 
= ((λ x. (succ (succ (succ x)))((λ x. (succ (succ (succ x)))) (succ 0)))
 = ((λ x. (succ (succ (succ x)))) (succ (succ (succ (succ 0)))))
 = (succ (succ (succ (succ (succ (succ (succ 0)))))))

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.

PJT
quelle
@tuckster: Ich habe schon einige Male Lambda-Kalkül studiert ... und ja, der Artikel AlligatorEggs macht für mich Sinn. Aber ich kann das nicht mit Programmierung in Verbindung bringen. Für mich ist Labda-Kalkül im Moment wie eine separate Theorie, die einfach da ist. Wie werden die Konzepte der Lambda-Rechnung in Programmiersprachen verwendet?
Lazer
3
@eSKay: Haskell ist ein Lambda-Kalkül mit einer dünnen Schicht syntaktischen Zuckers, damit es eher wie eine normale Programmiersprache aussieht. Die Sprachen der Lisp-Familie sind auch dem untypisierten Lambda-Kalkül sehr ähnlich, für das Alligator Eggs steht. Der Lambda-Kalkül selbst ist im Wesentlichen eine minimalistische Programmiersprache, ähnlich einer "funktionalen Programmierassemblersprache".
CA McCann
@eSKay: Ich habe ein bisschen hinzugefügt, wie es mit einigen Beispielen zusammenhängt. Ich hoffe das hilft!
PJT
Wenn Sie von meiner Antwort abziehen möchten, können Sie bitte einen Kommentar dazu hinterlassen, warum ich versuchen kann, meine Antwort zu verbessern. Danke dir.
PJT
14

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 scanfund diese irgendwo zu speichern, schreiben Sie stattdessen eine Funktion, um zu sagen, was Sie mit dem Ergebnis tun würden, scanfwenn Sie es hätten, und übergeben Sie diese dann Funktion zur E / A-API. Genau das >>=macht es, wenn Sie die IOMonade 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.

sigfpe
quelle
8

(Einige funktionale Sprachen erlauben unreine Funktionen.)

Bei rein funktionalen Sprachen wird die reale Interaktion normalerweise als eines der Funktionsargumente wie folgt aufgenommen:

RealWorld pureScanf(RealWorld world, const char* format, ...);

Verschiedene Sprachen haben unterschiedliche Strategien, um die Welt vom Programmierer weg zu abstrahieren. Haskell verwendet zum Beispiel Monaden, um das worldArgument 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:

int compute_sum_of_squares (int min, int max) {
  int result = 0;
  for (int i = min; i < max; ++ i)
     result += i * i;  // modify "result" in place
  return result;
}

Sie integrieren den Modifikationsteil in einen Funktionsaufruf und wandeln Schleifen normalerweise in Rekursionen um:

int compute_sum_of_squares (int min, int max) {
  if (min >= max)
    return 0;
  else
    return min * min + compute_sum_of_squares(min + 1, max);
}
kennytm
quelle
Oder einfach nur computeSumOfSquares min max = sum [x*x | x <- [min..max]];-)
Fredoverflow
@Fred: Listenverständnis ist nur ein syntaktischer Zucker (und dann müssen Sie die Listenmonade im Detail erklären). Und wie setzen Sie um sum? Rekursion ist weiterhin erforderlich.
Kennytm
3

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 .

Shaun
quelle
9
Und denken Sie daran, dass es nichts gibt Stateoder Monadden 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.
Conal
1

haskell:

main = do no <- readLn
          print (no + 1)

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).

sepp2k
quelle
@ sepp2k: warum, was schadet es, sie zu ändern?
Lazer
@eSKay Wenn Sie die Variablen nicht ändern können, wissen Sie, dass sie immer gleich sind. Dies erleichtert das Debuggen und zwingt Sie dazu, einfachere Funktionen zu erstellen, die nur eines und sehr gut können. Es hilft auch sehr bei der Arbeit mit Parallelität.
Henrik Hansen
9
@eSKay: Funktionale Programmierer glauben, dass der veränderbare Zustand viele Möglichkeiten für Fehler mit sich bringt und es schwieriger macht, über das Verhalten von Programmen nachzudenken. Wenn Sie beispielsweise einen Funktionsaufruf haben 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).
sepp2k
6
Es sind nicht nur funktionale Programmierer, die veränderlichen Zuständen und Nebenwirkungen misstrauen. Unveränderliche Objekte und die Trennung von Befehlen und Abfragen werden von einigen OO-Programmierern sehr geschätzt, und fast jeder hält veränderbare globale Variablen für eine schlechte Idee. Sprachen wie Haskell bringen die Idee nur weiter, dass die meisten ...
CA McCann
5
@eSKay: Es ist nicht so sehr schädlich, dass Mutationen schädlich sind, sondern dass es viel einfacher wird, modularen und wiederverwendbaren Code zu schreiben, wenn Sie sich bereit erklären, Mutationen zu vermeiden. Ohne einen gemeinsamen veränderlichen Status wird die Kopplung zwischen verschiedenen Teilen des Codes explizit und es ist viel einfacher, Ihr Design zu verstehen und zu pflegen. John Hughes erklärt dies besser als ich; Nehmen Sie seine Arbeit Warum funktionale Programmierung wichtig ist .
Norman Ramsey