Umgang mit Zustandsproblemen in der funktionalen Programmierung

18

Ich habe gelernt, wie man hauptsächlich vom OOP-Standpunkt aus programmiert (wie die meisten von uns, da bin ich mir sicher), aber ich habe viel Zeit damit verbracht, zu lernen, wie man Probleme auf funktionale Weise löst. Ich habe ein gutes Verständnis für die Lösung von Rechenproblemen mit FP, aber wenn es um kompliziertere Probleme geht, greife ich immer wieder auf veränderbare Objekte zurück. Wenn ich zum Beispiel einen Partikelsimulator schreibe, möchte ich, dass Partikel- "Objekte" mit einer veränderlichen Position aktualisiert werden. Wie werden inhärent "zustandsbehaftete" Probleme normalerweise mit funktionalen Programmiertechniken gelöst?

functional-programming Andrew Martin
quelle
4
Der erste Schritt ist wahrscheinlich die Erkenntnis, dass Probleme nicht von Natur aus zustandsbezogen sind.
Telastyn
4
Einige Probleme sind inhärent statusbehaftet, z. B. das Schreiben in eine Datenbank oder das Zeichnen einer GUI. Was wäre am Beispiel meines Partikelsimulators eine alternative Denkweise? Es erscheint mir ineffizient, jedes Mal neue Partikel zurückzugeben, wenn ihre Position aktualisiert wird, um einen Zustand zu vermeiden, und es ist kein gutes Modell für die reale Welt.
Andrew Martin
4
Mit Ausnahme des Datenbankbeispiels sind diese Probleme möglicherweise nicht inhärent statusbezogen. Zum Beispiel für die GUI - Programmierung, verwenden Sie wirklich wandelbaren Zustand als schlecht, implizites Modell der Zeit ; Mit funktionaler reaktiver Programmierung können Sie die Zeit explizit modellieren, ohne sich auf den Status zu verlassen, indem Sie Streams von Ereignissen bereitstellen, die Sie kombinieren können.
Tikhon Jelvis
1
Es gibt eine einfachere Lösung: Wenn Sie zu einem Problem kommen, das mit FP-Techniken nicht einfach modelliert werden kann, verwenden Sie keine funktionale Programmierung, um es zu lösen. Das richtige Werkzeug für den Job und all das ...
Mason Wheeler
1
@ AndrewMartin Kein gutes Modell der realen Welt? Die in der Physik verwendete Mathematik zur Modellierung der realen Welt ist rein funktional. Mit einem guten Garbage Collector ist das Zuweisen eines Objekts so billig wie das Anstoßen eines Zeigers, und die Erfassungszeit ist proportional zur Anzahl der aktiven Objekte. Ich wette, die Hauptursache für Ineffizienzen bei der funktionalen Programmierung ist die Verwendung von Datenstrukturen, die nicht Cache-effizient sind. Verknüpfte Listen und Binärbäume sind keine herausragenden Faktoren für die Cache-Effizienz.
Doval

Antworten:

20

Funktionale Programme verarbeiten den Status sehr gut, erfordern jedoch eine andere Sichtweise. Für Ihr Positionsbeispiel ist zu berücksichtigen, dass Ihre Position eine Funktion der Zeit anstelle eines festen Werts ist . Dies funktioniert gut für Partikel, die einem festen mathematischen Pfad folgen. Sie benötigen jedoch eine andere Strategie, um mit einer Änderung des Pfads umzugehen, z. B. nach einer Kollision.

Die grundlegende Strategie besteht darin, Funktionen zu erstellen, die einen Zustand annehmen und den neuen Zustand zurückgeben . Ein Partikelsimulator wäre also eine Funktion, die eine SetAnzahl von Partikeln als Eingabe verwendet und Setnach einem Zeitschritt eine neue Anzahl von Partikeln zurückgibt . Dann rufen Sie diese Funktion einfach wiederholt auf, wobei der Eingang auf das vorherige Ergebnis gesetzt ist.

Karl Bielefeldt
quelle
5
+1 Es ist in Ordnung, einen Zustand in FP zu haben, nur keinen veränderlichen Zustand.
Jhewlett
1
Danke für diesen Einblick. Meine Sorgen über Ineffizienz wurden von @logc vereitelt. Die technischen Details, wie der Zustand transformiert wird, sind ein Implementierungsproblem auf niedriger Ebene, das die Sprache selbst lösen soll. Ich habe gesehen, wie Rich Hickey in einem Video erklärt hat, wie er das mit Clojure macht.
Andrew Martin
1
@jhewlett: Genauer gesagt: FP hat einen Zustand, sogar einen veränderlichen Zustand, aber sie repräsentieren ihn nicht mit veränderlichen Variablen.
Giorgio
9

Wie von @KarlBielefeldt festgestellt, besteht der funktionale Ansatz für ein solches Problem darin, es als Rückgabe eines neuen Zustands von einem vorherigen Zustand zu betrachten. Die Funktionen selbst enthalten keine Informationen, sodass sie den Status m immer auf den Status n aktualisieren .

Ich denke, Sie finden dies ineffizient, weil Sie davon ausgehen, dass der vorherige Zustand im Speicher gehalten werden muss, während der neue Zustand berechnet wird. Beachten Sie, dass die Wahl zwischen dem Schreiben eines vollständig neuen Status oder dem erneuten Schreiben des alten Status ein Implementierungsdetail aus Sicht einer funktionalen Sprache ist.

Angenommen, ich habe eine Liste mit einer Million Ganzzahlen und möchte die zehnte um eine Einheit erhöhen. Es ist verschwenderisch, die gesamte Liste mit einer neuen Nummer an der zehnten Stelle zu kopieren. Dies ist jedoch nur die konzeptionelle Beschreibung der Operation für den Sprachkompilierer oder -interpreter. Dem Compiler oder Interpreter steht es frei, die erste Liste zu nehmen und nur die zehnte Position zu überschreiben.

Der Vorteil der Beschreibung des Vorgangs auf diese Weise besteht darin, dass der Compiler die Situation beurteilen kann, in der viele Threads dieselbe Liste an verschiedenen Positionen aktualisieren möchten. Wenn die Operation als "Gehe zu dieser Position und überschreibe, was du findest" beschrieben wird, ist es der Programmierer, nicht der Compiler, der dafür verantwortlich ist, sicherzustellen, dass Überschreibungen nicht kollidieren.

Nach alledem gibt es sogar in Haskell eine staatliche Monade , mit deren Hilfe Situationen modelliert werden können, in denen das "Beibehalten des Zustands" eine intuitivere Lösung für ein Problem darstellt. Beachten Sie jedoch auch, dass einige Probleme, die Sie als " inhärent statusbehaftet, wie das Schreiben in eine Datenbank " empfinden, unveränderliche Lösungen wie Datomic aufweisen . Dies kann überraschend sein, bis Sie verstehen, dass es sich um ein Konzept handelt, nicht unbedingt um dessen Umsetzung.

logc
quelle
4
Ich denke, der Ausschnitt über die Aktualisierung einer großen Liste ist irreführend; Ich kenne keinen Compiler, der diese Optimierung tatsächlich für Sie ausführt. Selbst wenn der Compiler dies könnte, ist dies nur in Fällen möglich, in denen Sie nicht an früheren Versionen der Liste festhalten. Die eigentliche Lösung besteht darin, eine Listendatenstruktur zu verwenden, bei der nicht das gesamte Objekt kopiert werden muss, um ein einzelnes Element zu ändern.
Doval
@Doval: "Auch wenn der Compiler dies könnte, ist dies nur in Fällen möglich, in denen Sie nicht an früheren Versionen der Liste festhalten.": Dies erinnert mich an eindeutige Typen in Clean.
Giorgio
4

Wenn man das richtige mentale Modell abonniert, kann man besser über den Zustand nachdenken und ihn verwalten. Meiner Meinung nach ist das beste mentale Modell das Daumenkino . Sobald Sie auf diese Schaltfläche klicken, werden Sie verstehen, dass FP sich stark auf persistente Datenstrukturen stützt, die den Zustand der Welt erfassen, und dass Funktionen verwendet werden, um diesen Zustand ohne jede Veränderung zu ändern.

Rich Hickey beleuchtet diese Ideen:

Es gibt noch andere Gespräche, aber dies sollte Sie in die richtige Richtung leiten.

Mario T. Lanza
quelle
3

Beim Schreiben von großen und mittelgroßen Anwendungen habe ich es oft als nützlich empfunden, zwischen zustandsbehafteten und zustandslosen Abschnitten der Anwendung zu unterscheiden.

Die Klassen / Datenstrukturen im statusbehafteten Abschnitt speichern die Daten der Anwendung, und die Funktionen in diesem Abschnitt arbeiten mit impliziter Kenntnis der Daten der Anwendung.

Die Klassen / Datenstrukturen / Funktionen im Abschnitt "Zustandslos" sollen die rein algorithmischen Aspekte der Anwendung unterstützen. Sie haben keine implizite Kenntnis der Daten der Anwendung. Sie arbeiten rein funktional. Die zustandsbehafteten Teile der Anwendung können eine Zustandsänderung als Nebenwirkung der Ausführung von Funktionen im zustandslosen Abschnitt der Anwendung erfahren.

Der schwierigste Teil besteht darin, herauszufinden, welche Klassen / Funktionen in den zustandslosen Abschnitt und welche Klassen / Funktionen in den zustandsbehafteten Abschnitt gestellt werden sollen, und die Disziplin zu haben, sie in separate Dateien / Bibliotheken zu legen.

R Sahu
quelle
Wie beantwortet dies die Frage? (nicht-downvoting)
kravemir
@kravemir, ob Sie eine Anwendung mit OOP oder FP schreiben, Sie müssen verstehen, wo der Status der Anwendung liegt.
R Sahu