Funktionale Programmierung - Unveränderlichkeit

12

Ich versuche zu verstehen, wie man mit unveränderlichen Daten in FP umgeht (speziell in F #, aber andere FPs sind auch in Ordnung) und die alte Gewohnheit des staatlich vollständigen Denkens (OOP-Stil) zu brechen. Ein Teil der ausgewählten Antwort auf die hier gestellte Frage wiederholte meine Suche nach möglichen Beschreibungen von Problemen, die durch zustandsbehaftete Darstellungen in OOP mit unveränderlichen in FP gelöst werden (zum Beispiel: Eine Warteschlange bei Produzenten und Verbrauchern). Irgendwelche Gedanken oder Links sind willkommen? Danke im Voraus.

Bearbeiten : Um die Frage ein wenig näher zu erläutern, wie würden unveränderliche Strukturen (z. B. Warteschlange) in FP auf mehrere Threads (z. B. Produzent und Konsument) gleichzeitig aufgeteilt

Venkram
quelle
Eine Möglichkeit, Parallelitätsprobleme zu lösen, besteht darin, jedes Mal Kopien der Warteschlange anzufertigen (etwas teuer, funktioniert aber).
Job
infoq.com/presentations/Functional-Data-Structures-in-Scala Vielleicht finden Sie diese Rede aufschlussreich.
Deadalnix

Antworten:

19

Obwohl dies manchmal so ausgedrückt wird, verhindert die funktionale Programmierung¹ keine Zustandsberechnungen. Was es tut, ist, den Programmierer zu zwingen, den Zustand explizit zu machen.

Nehmen wir zum Beispiel die Grundstruktur eines Programms mit einer imperativen Warteschlange (in einigen Pseudosprachen):

q := Queue.new();
while (true) {
    if (Queue.is_empty(q)) {
        Queue.add(q, producer());
    } else {
        consumer(Queue.take(q));
    }
}

Die entsprechende Struktur mit einer funktionalen Warteschlangendatenstruktur (immer noch in einer imperativen Sprache, um jeweils einen Unterschied anzugehen) würde folgendermaßen aussehen:

q := Queue.empty;
while (true) {
    if (q = Queue.empty) {
        q := Queue.add(q, producer());
    } else {
        (tail, element) := Queue.take(q);
        consumer(element);
        q := tail;
    }
}

Da die Warteschlange jetzt unveränderlich ist, ändert sich das Objekt selbst nicht. In diesem Pseudocode ist qselbst eine Variable; die Aufgaben q := Queue.add(…)undq := tail machen es auf ein anderes Objekt zeigen. Die Schnittstelle der Queue-Funktionen hat sich geändert: Jedes muss das neue Queue-Objekt zurückgeben, das sich aus der Operation ergibt.

In einer rein funktionalen Sprache, dh in einer Sprache ohne Nebeneffekte, müssen Sie all state explizit machen. Da Produzent und Konsument vermutlich etwas tun, muss auch hier ihr Zustand in der Aufruferschnittstelle stehen.

main_loop(q, other_state) {
    if (q = Queue.empty) {
        let (new_state, element) = producer(other_state);
        main_loop(Queue.add(q, element), new_state);
    } else {
        let (tail, element) = Queue.take(q);
        let new_state = consumer(other_state, element);
        main_loop(tail, new_state);
    }
}
main_loop(Queue.empty, initial_state)

Beachten Sie, wie jetzt jeder Zustand explizit verwaltet wird. Die Warteschlangenmanipulationsfunktionen nehmen eine Warteschlange als Eingabe und erzeugen eine neue Warteschlange als Ausgabe. Der Produzent und der Konsument geben auch ihren Staat durch.

Die gleichzeitige Programmierung passt nicht so gut in die funktionale Programmierung, passt aber sehr gut in die Umgebung funktionale Programmierung. Die Idee ist, eine Reihe separater Rechenknoten auszuführen und sie Nachrichten austauschen zu lassen. Jeder Knoten führt ein Funktionsprogramm aus, und sein Status ändert sich beim Senden und Empfangen von Nachrichten.

Wenn Sie das Beispiel fortsetzen, wird eine einzelne Warteschlange von einem bestimmten Knoten verwaltet. Verbraucher senden diesem Knoten eine Nachricht, um ein Element zu erhalten. Produzenten senden diesem Knoten eine Nachricht, um ein Element hinzuzufügen.

main_loop(q) =
    consumer->consume(q->take()) || q->add(producer->produce());
    main_loop(q)

Die einzige „industrialisierte“ Sprache, bei der die Parallelität stimmt³, ist Erlang . Das Erlernen von Erlang ist definitiv der Weg zur Aufklärung über die gleichzeitige Programmierung.

Jetzt schalten alle auf nebenwirkungsfreie Sprachen um!

¹ Dieser Begriff hat mehrere Bedeutungen. Ich denke, Sie meinen damit Programmieren ohne Nebenwirkungen, und das ist die Bedeutung, die ich auch benutze.
² Die Programmierung mit implizitem Status ist eine zwingende Programmierung . Objektorientierung ist ein völlig orthogonales Anliegen.
³ Entzündlich, ich weiß, aber ich meine es ernst. Threads mit Shared Memory sind die Assemblersprache für die gleichzeitige Programmierung. Die Weitergabe von Nachrichten ist viel einfacher zu verstehen, und das Fehlen von Nebenwirkungen wird deutlich, sobald Sie die Parallelität einführen.
Und das kommt von jemandem, der kein Fan von Erlang ist, aber aus anderen Gründen.

Gilles 'SO - hör auf böse zu sein'
quelle
2
+1 Viel umfassendere Antwort, obwohl man wohl darüber streiten könnte, dass Erlang keine reine FP-Sprache ist.
Rein Henrichs
1
@ Rein Henrichs: In der Tat. Tatsächlich ist Erlang von allen gegenwärtig existierenden Hauptsprachen diejenige, die die Objektorientierung am genauesten implementiert.
Jörg W Mittag
2
@ Jörg Einverstanden. Auch hier könnte man bestreiten, dass reine FP und OO orthogonal sind.
Rein Henrichs
Um eine unveränderliche Warteschlange in einer gleichzeitigen Software zu implementieren, müssen Nachrichten zwischen Knoten gesendet und empfangen werden. Wo werden ausstehende Nachrichten gespeichert?
Mouviciel
@ mouviciel Queue-Elemente werden in der Warteschlange für eingehende Nachrichten des Knotens gespeichert. Diese Nachrichtenwarteschlangenfunktion ist eine Grundfunktion einer verteilten Infrastruktur. Ein alternativer Infrastrukturentwurf, der sich gut für die lokale Parallelität eignet, jedoch nicht für verteilte Systeme, besteht darin, den Absender zu blockieren, bis der Empfänger bereit ist. Mir ist klar, dass dies nicht alles erklärt, es würde ein oder zwei Kapitel eines Buches über gleichzeitige Programmierung erfordern, um dies vollständig zu erklären.
Gilles 'SO - hör auf böse zu sein'
4

Das zustandsbehaftete Verhalten in einer FP-Sprache wird als Transformation von einem vorherigen Zustand in einen neuen Zustand implementiert. Eine Warteschlange ist beispielsweise eine Umwandlung von einer Warteschlange und einem Wert in eine neue Warteschlange mit dem Wert in der Warteschlange. Die Warteschlange ist eine Umwandlung von einer Warteschlange in einen Wert und eine neue Warteschlange, bei der der Wert entfernt wird. Konstrukte wie Monaden wurden entwickelt, um diese Zustandsumwandlung (und andere Ergebnisse der Berechnung) auf nützliche Weise zu abstrahieren

Rein Henrichs
quelle
3
Wenn es sich bei jedem Hinzufügen / Entfernen um eine neue Warteschlange handelt, wie würden sich zwei (oder mehr) asynchrone Vorgänge (Threads) die Warteschlange teilen? Ist es ein Muster, das Neuanlegen der Warteschlange zu abstrahieren?
Venkram
Parallelität ist eine ganz andere Frage. Ich kann in einem Kommentar keine ausreichende Antwort geben.
Rein Henrichs
2
@Rein Henrichs: "Kann in einem Kommentar keine ausreichende Antwort geben". Das bedeutet normalerweise, dass Sie die Antwort aktualisieren sollten, um die mit Kommentaren verbundenen Probleme zu beheben.
S.Lott
Parallelität kann auch monadisch sein, siehe haskells Control.Concurrency.STM.
Alternative
1
@ S.lott in diesem fall heißt das das das op eine neue frage stellen soll. Parallelität ist OT zu dieser Frage, bei der es um unveränderliche Datenstrukturen geht.
Rein Henrichs
2

... Probleme, die durch zustandsbehaftete Darstellungen in OOP mit unveränderlichen Darstellungen in FP gelöst werden (zB: Eine Warteschlange bei Produzenten & Konsumenten)

Ihre Frage ist, was als "XY-Problem" bezeichnet wird. Insbesondere ist das von Ihnen angegebene Konzept (Warteschlange bei Produzenten und Verbrauchern) tatsächlich eine Lösung und kein "Problem", wie Sie es beschreiben. Dies führt zu einer Schwierigkeit, da Sie nach einer rein funktionalen Implementierung von etwas fragen, das von Natur aus unrein ist. Meine Antwort beginnt mit einer Frage: Welches Problem möchten Sie lösen?

Es gibt viele Möglichkeiten, wie mehrere Produzenten ihre Ergebnisse an einen gemeinsamen Verbraucher senden können. Die vielleicht naheliegendste Lösung in F # besteht darin, den Verbraucher zu einem Agenten (aka MailboxProcessor) zu machen und die Produzenten Postihre Ergebnisse dem Konsumentenagenten zur Verfügung zu stellen. Dies verwendet intern eine Warteschlange und ist nicht rein (das Senden von Nachrichten in F # ist ein unkontrollierter Nebeneffekt, eine Verunreinigung).

Es ist jedoch sehr wahrscheinlich, dass das zugrunde liegende Problem eher dem Scatter-Gather-Muster aus der parallelen Programmierung entspricht. Um dieses Problem zu lösen, können Sie ein Array von Eingabewerten erstellen und diese dann Array.Parallel.mapüberlagern und die Ergebnisse mithilfe einer Reihe zusammenstellen Array.reduce. Alternativ können Sie Funktionen aus dem PSeqModul verwenden, um die Elemente von Sequenzen parallel zu verarbeiten.

Ich möchte auch betonen, dass an staatlichem Denken nichts auszusetzen ist. Reinheit hat Vorteile, ist aber kein Allheilmittel, und Sie sollten sich auch seiner Mängel bewusst werden. Genau aus diesem Grund ist F # keine reine Funktionssprache: Sie können also Verunreinigungen verwenden, wenn diese vorzuziehen sind.

Jon Harrop
quelle
1

Clojure hat ein sehr gut durchdachtes Konzept von Staat und Identität, das eng mit der Parallelität zusammenhängt. Die Unveränderlichkeit spielt eine wichtige Rolle. Alle Werte in Clojure sind unveränderlich und können über Referenzen aufgerufen werden. Referenzen sind mehr als nur einfache Zeiger. Sie verwalten den Zugriff auf Werte, und es gibt mehrere Typen mit unterschiedlicher Semantik. Eine Referenz kann geändert werden, um auf einen neuen (unveränderlichen) Wert zu verweisen, und eine solche Änderung ist garantiert atomar. Nach der Änderung arbeiten jedoch alle anderen Threads immer noch mit dem ursprünglichen Wert, zumindest bis sie wieder auf die Referenz zugreifen.

Ich empfehle Ihnen nachdrücklich, einen ausgezeichneten Artikel über Staat und Identität in Clojure zu lesen , der die Details viel besser erklärt, als ich es könnte.

Adam Byrtek
quelle