Funktionale Programmierung: Richtige Vorstellungen zu Parallelität und Status?

21

FP-Befürworter haben behauptet, dass Parallelität einfach ist, weil ihr Paradigma einen veränderlichen Zustand vermeidet. Ich verstehe es nicht.

Stellen Sie sich vor, wir erstellen mit FP einen Multiplayer-Dungeon-Crawl (ein Roguelike), bei dem reine Funktionen und unveränderliche Datenstrukturen im Vordergrund stehen. Wir erzeugen einen Kerker, der aus Räumen, Gängen, Helden, Monstern und Beute besteht. Unsere Welt ist quasi ein Objektgraph von Strukturen und ihren Beziehungen. Wenn sich die Dinge ändern, wird unsere Darstellung der Welt geändert, um diese Änderungen widerzuspiegeln. Unser Held tötet eine Ratte, greift nach einem Kurzschwert usw.

Für mich trägt die Welt (aktuelle Realität) diese Staatsidee und ich vermisse, wie FP diese überwindet. Während unser Held handelt, verändern Funktionen den Zustand der Welt. Es scheint, dass jede Entscheidung (KI oder Mensch) auf dem gegenwärtigen Zustand der Welt basieren muss. Wo würden wir Parallelität zulassen? Es können nicht mehrere Prozesse gleichzeitig den Zustand der Welt verbessern, damit ein Prozess seine Ergebnisse nicht auf einen abgelaufenen Zustand stützt. Meiner Meinung nach sollte die gesamte Steuerung in einem einzigen Regelkreis erfolgen, damit wir immer den aktuellen Zustand verarbeiten, der durch unseren aktuellen Objektgraphen der Welt dargestellt wird.

Offensichtlich gibt es Situationen, die perfekt für die Parallelität geeignet sind (z. B. bei der Verarbeitung von isolierten Aufgaben, deren Status unabhängig voneinander sind).

Ich verstehe nicht, wie nützlich Parallelität in meinem Beispiel ist, und das kann das Problem sein. Ich kann die Behauptung irgendwie falsch darstellen.

Kann jemand diesen Anspruch besser vertreten?

Mario T. Lanza
quelle
1
Sie beziehen sich auf den gemeinsam genutzten Status. Der gemeinsam genutzte Zustand ist immer so, wie er ist, und erfordert immer eine bestimmte Form der Synchronisation. Die häufig bevorzugte Form unter reinen FP-Anwendern ist STM, mit der Sie den gemeinsam genutzten Speicher als lokalen Speicher behandeln können, indem Sie eine Abstraktionsschicht darüber haben, die den Zugriff transaktional macht Bedingungen werden automatisch behandelt. Eine andere Technik für das gemeinsame Gedächtnis ist das Weitergeben von Nachrichten, bei der Sie anstelle des gemeinsamen Gedächtnisses das lokale Gedächtnis und das Wissen anderer Akteure haben, um nach ihrem lokalen Gedächtnis zu fragen
Jimmy Hoffa,
1
Sie fragen sich also, wie die einfache Verwaltung des Status in einer Single-Thread-Anwendung durch die gleichzeitige Verwendung des gemeinsam genutzten Status erleichtert wird? Auf der anderen Seite eignet sich Ihr Beispiel eindeutig für die konzeptionelle Parallelität (ein Thread für jede AI-gesteuerte Entität), unabhängig davon, ob es auf diese Weise implementiert ist oder nicht. Ich bin verwirrt, was Sie hier fragen.
CA McCann
1
mit einem wort, reißverschlüsse
jk.
2
Jedes Objekt hätte seine eigene Sicht auf die Welt. Es wird letztendlich Konsistenz geben . Es ist wahrscheinlich auch so, wie die Dinge in unserer "realen Welt" mit dem Zusammenbruch der Wellenfunktion funktionieren .
Herzmeister
1
Möglicherweise finden Sie "rein funktionale Retrogames" interessant: prog21.dadgum.com/23.html
user802500

Antworten:

15

Ich werde versuchen, auf die Antwort hinzuweisen. Dies ist keine Antwort, nur eine einleitende Illustration. @jks Antwort zeigt auf die reale Sache, Reißverschlüsse.

Stellen Sie sich vor, Sie haben eine unveränderliche Baumstruktur. Sie möchten einen Knoten ändern, indem Sie ein untergeordnetes Element einfügen. Als Ergebnis erhalten Sie einen ganz neuen Baum.

Aber der größte Teil des neuen Baums ist genau der gleiche wie der alte Baum. Eine clevere Implementierung würde die meisten Baumfragmente wiederverwenden und Zeiger um den geänderten Knoten herum routen:

Aus Wikipedia

Okasakis Buch ist voller solcher Beispiele.

Ich nehme an, Sie können kleine Teile Ihrer Spielwelt bei jeder Bewegung angemessen verändern (eine Münze aufheben) und nur kleine Teile Ihrer Weltdatenstruktur (die Zelle, in der die Münze aufgehoben wurde) tatsächlich verändern. Teile, die nur zu früheren Staaten gehören, werden rechtzeitig mit dem Müll gesammelt.

Dies berücksichtigt wahrscheinlich einige Aspekte bei der angemessenen Gestaltung der Struktur der Datenspielwelt. Leider bin ich kein Experte in diesen Angelegenheiten. Auf jeden Fall muss es etwas anderes als eine NxM-Matrix sein, die man als veränderbare Datenstruktur verwenden würde. Wahrscheinlich sollte es aus kleineren Teilen bestehen (Korridore? Einzelne Zellen?), Die wie Baumknoten aufeinander zeigen.

9000
quelle
3
+1: Für den Hinweis auf Okasakis Buch. Ich habe es nicht gelesen, aber es steht auf meiner Aufgabenliste. Ich denke, was Sie dargestellt haben, ist die richtige Lösung. Alternativ können Sie Eindeutigkeitstypen berücksichtigen (Clean, en.wikipedia.org/wiki/Uniqueness_type ): Mit dieser Art von Typen können Sie Datenobjekte destruktiv aktualisieren, während die referenzielle Transparenz erhalten bleibt.
Giorgio
Hat es einen Vorteil, wenn Beziehungen über einen indirekten Verweis über Schlüssel oder IDs definiert werden? Das heißt, ich dachte, dass weniger tatsächliche Berührungen einer Struktur zu einer anderen weniger Änderungen an der Weltstruktur erfordern würden, wenn eine Änderung eintritt. Oder wird diese Technik in FP nicht wirklich eingesetzt?
Mario T. Lanza
9

Die Antwort von 9000 ist die halbe Antwort. Persistente Datenstrukturen ermöglichen es Ihnen, unveränderte Teile wiederzuverwenden.

Sie denken aber vielleicht schon: "Hey, was ist, wenn ich die Wurzel des Baumes wechseln möchte?" In dem gegebenen Beispiel bedeutet dies nun, dass alle Knoten geändert werden. Hier kommen Reißverschlüsse zum Einsatz. Mit ihnen kann das Element eines Fokus in O (1) geändert und der Fokus an eine beliebige Stelle in der Struktur verschoben werden.

Der andere Punkt bei Reißverschlüssen ist, dass es einen Reißverschluss für so ziemlich jeden gewünschten Datentyp gibt

jk.
quelle
Ich fürchte, ich werde einige Zeit brauchen, um mich mit "Reißverschlüssen" zu befassen, da ich am Rande eines jeden nur erforschenden FP stehe. Ich habe keine Erfahrung mit Haskell.
Mario T. Lanza
Ich werde heute später versuchen, ein Beispiel hinzuzufügen
jk.
4

Programme im funktionalen Stil bieten viele Möglichkeiten, die Parallelität zu nutzen. Jedes Mal, wenn Sie eine Sammlung transformieren, filtern oder aggregieren und alles rein oder unveränderlich ist, besteht die Möglichkeit, dass der Vorgang durch Parallelität beschleunigt wird.

Angenommen, Sie treffen AI-Entscheidungen unabhängig voneinander und in keiner bestimmten Reihenfolge. Sie wechseln sich nicht ab, sie treffen alle gleichzeitig eine Entscheidung und dann schreitet die Welt voran. Der Code könnte so aussehen:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

Sie haben eine Funktion, mit der Sie berechnen können, was ein Monster in einem bestimmten Weltzustand tun wird, und die Sie auf jedes Monster anwenden können, um den nächsten Weltzustand zu berechnen. Dies ist in einer funktionalen Sprache eine Selbstverständlichkeit, und der Compiler kann den Schritt "Auf jedes Monster anwenden" parallel ausführen.

In einer imperativen Sprache würden Sie mit größerer Wahrscheinlichkeit jedes Monster durchlaufen und seine Auswirkungen auf die Welt anwenden. Dies ist nur einfacher, da Sie sich nicht mit Klonen oder kompliziertem Aliasing befassen möchten. Der Compiler kann in diesem Fall die Monsterberechnungen nicht parallel ausführen, da frühe Monsterentscheidungen sich auf spätere Monsterentscheidungen auswirken.

Craig Gidney
quelle
Das hilft schon einiges. Ich kann sehen, dass es in einem Spiel von großem Vorteil wäre, wenn Monster gleichzeitig entscheiden, was sie als Nächstes tun.
Mario T. Lanza
4

Hören ein paar Reiche Hickey spricht - diese insbesondere - meine Verwirrung gelindert. In einem hat er angegeben, dass es in Ordnung ist, dass gleichzeitig ablaufende Prozesse möglicherweise nicht den aktuellsten Status haben. Das musste ich hören. Was mir schwerfiel, war, dass Programme tatsächlich in Ordnung wären, wenn sie Entscheidungen auf Momentaufnahmen der Welt stützen würden, die inzwischen von neueren abgelöst wurden. Ich habe mich immer wieder gefragt, wie es mit der gleichzeitigen FP darum ging, Entscheidungen auf der Grundlage des alten Staates zu treffen.

In einem Bankenantrag würden wir niemals eine Entscheidung auf der Grundlage einer Momentaufnahme des Staates treffen wollen, die inzwischen durch eine neuere ersetzt wurde (eine Rücknahme ist erfolgt).

Diese Parallelität ist einfach, da das FP-Paradigma einen veränderlichen Zustand vermeidet. Dies ist eine technische Behauptung, die nichts über die logischen Vorzüge der Entscheidungsgrundlage für einen möglicherweise alten Zustand aussagt. FP modelliert letztendlich immer noch den Zustandswechsel. Daran führt kein Weg vorbei.

Mario T. Lanza
quelle
0

FP-Befürworter haben behauptet, dass Parallelität einfach ist, weil ihr Paradigma einen veränderlichen Zustand vermeidet. Ich verstehe es nicht.

Ich wollte diese allgemeine Frage als jemand einschätzen, der ein funktionierender Neuling ist, aber über die Jahre hinweg Nebenwirkungen in meinen Augen hatte, und ich möchte sie aus allen möglichen Gründen mildern, auch aus einfacheren (oder speziell "sichereren" Gründen. weniger fehleranfällig "). Wenn ich zu meinen funktionalen Kollegen schaue und sehe, was sie tun, wirkt das Gras ein bisschen grüner und riecht zumindest in dieser Hinsicht besser.

Serielle Algorithmen

Zu Ihrem speziellen Beispiel: Wenn Ihr Problem serieller Natur ist und B erst nach Abschluss von A ausgeführt werden kann, können Sie A und B konzeptionell nicht parallel ausführen, egal was passiert. Sie müssen einen Weg finden, um die Ordnungsabhängigkeit wie in Ihrer Antwort zu unterbrechen, indem Sie parallele Züge mit dem alten Spielstatus ausführen, oder Sie müssen eine Datenstruktur verwenden, mit der Teile davon unabhängig modifiziert werden können, um die in den anderen Antworten vorgeschlagene Ordnungsabhängigkeit zu beseitigen oder so etwas. Aber es gibt definitiv einige konzeptionelle Designprobleme wie diese, bei denen man nicht unbedingt alles so einfach multithreaden kann, weil die Dinge unveränderlich sind. Einige Dinge werden nur serieller Natur sein, bis Sie einen intelligenten Weg finden, um die Auftragsabhängigkeit zu brechen, falls dies überhaupt möglich ist.

Einfachere Parallelität

In vielen Fällen gelingt es uns jedoch nicht, Programme mit Nebenwirkungen an Stellen zu parallelisieren, die möglicherweise die Leistung erheblich verbessern, weil sie möglicherweise nicht threadsicher sind. Einer der Fälle, in denen das Eliminieren des veränderlichen Zustands (oder genauer gesagt der externen Nebenwirkungen) viel hilft, wie ich sehe, ist, dass er "möglicherweise threadsicher" in "definitiv threadsicher" verwandelt oder möglicherweise nicht .

Um diese Aussage ein wenig konkreter zu machen, überlege ich, dass ich Ihnen die Aufgabe gebe, eine Sortierfunktion in C zu implementieren, die einen Komparator akzeptiert und diese verwendet, um ein Array von Elementen zu sortieren. Es ist allgemein gehalten, aber ich gehe davon aus, dass es für Eingaben mit einer solchen Größenordnung (Millionen von Elementen oder mehr) verwendet wird, dass es zweifellos von Vorteil ist, immer eine Multithread-Implementierung zu verwenden. Können Sie Ihre Sortierfunktion mit mehreren Threads ausführen?

Das Problem ist, dass Sie nicht können, weil die Komparatoren Ihre Sortierfunktion möglicherweise aufruftNebenwirkungen verursachen, es sei denn, Sie wissen, wie sie für alle möglichen Fälle implementiert (oder zumindest dokumentiert) sind, was ohne eine Degeneralisierung der Funktion unmöglich ist. Ein Komparator könnte etwas Ekelhaftes tun, wie eine globale Variable in einer nicht-atomaren Weise zu modifizieren. 99,9999% der Komparatoren tun dies möglicherweise nicht, aber wir können diese verallgemeinerte Funktion nicht einfach wegen der 0,00001% der Fälle, die Nebenwirkungen verursachen könnten, multithreaden. Infolgedessen müssen Sie möglicherweise sowohl eine Single-Thread- als auch eine Multithread-Sortierfunktion anbieten und die Verantwortung auf die Programmierer übertragen, die sie verwenden, um auf der Grundlage der Threadsicherheit zu entscheiden, welche verwendet werden soll. Und die Leute könnten immer noch die Single-Thread-Version verwenden und Möglichkeiten zum Multithreading verpassen, weil sie möglicherweise auch unsicher sind, ob der Komparator thread-sicher ist.

Es gibt eine ganze Menge Denkvermögen, das in die Rationalisierung der Thread-Sicherheit von Dingen involviert sein kann, ohne überall Sperren zu werfen, die verschwinden können, wenn wir nur harte Garantien hatten, dass Funktionen für jetzt und für die Zukunft keine Nebenwirkungen verursachen. Und es gibt Angst: praktische Angst, denn jeder, der ein paar Mal zu oft eine Race-Bedingung debuggen musste, würde wahrscheinlich zögern, Multithreading-Vorgänge durchzuführen, bei denen er nicht zu 110% sicher sein kann, dass sie thread-sicher sind und dies auch bleiben werden. Selbst für die paranoidsten (von denen ich wahrscheinlich zumindest an der Grenze bin) bietet die reine Funktion das Gefühl der Erleichterung und des Vertrauens, das wir sicher parallel nennen können.

Und das ist einer der Hauptfälle, in denen ich es als so vorteilhaft betrachte, wenn Sie eine harte Garantie dafür erhalten, dass solche Funktionen thread-sicher sind, die Sie mit reinen funktionalen Sprachen erhalten. Die andere ist, dass funktionale Sprachen oftmals die Schaffung von Funktionen fördern, die in erster Linie frei von Nebenwirkungen sind. Sie können beispielsweise persistente Datenstrukturen bereitstellen, bei denen es recht effizient ist, eine massive Datenstruktur einzugeben und dann eine brandneue auszugeben, bei der nur ein kleiner Teil der Daten vom Original abweicht, ohne das Original zu berühren. Diejenigen, die ohne solche Datenstrukturen arbeiten, möchten diese möglicherweise direkt ändern und verlieren dabei etwas Threadsicherheit.

Nebenwirkungen

Trotzdem bin ich mit einem Teil nicht einverstanden, obwohl ich meinen funktionellen Freunden gebührenden Respekt entgegenbringe (die ich für super cool halte):

[...] weil ihr Paradigma einen veränderlichen Zustand vermeidet.

Es ist nicht unbedingt Unveränderlichkeit, die Parallelität so praktisch macht, wie ich es sehe. Es sind Funktionen, die Nebenwirkungen vermeiden. Wenn eine Funktion ein Array zum Sortieren eingibt, es kopiert und dann die Kopie zum Sortieren des Inhalts mutiert und die Kopie ausgibt, ist sie genauso threadsicher wie eine Funktion, die mit einem unveränderlichen Array-Typ arbeitet, selbst wenn Sie dieselbe Eingabe übergeben Array von mehreren Threads darauf. Ich denke also, dass es immer noch einen Platz für veränderbare Typen gibt, wenn man sozusagen sehr parallelen Code erstellt, obwohl unveränderliche Typen eine Menge zusätzlicher Vorteile bieten, einschließlich beständiger Datenstrukturen, die ich nicht so sehr für ihre unveränderlichen Eigenschaften verwende, sondern für Vermeiden Sie die Kosten für das Kopieren von Inhalten, um Funktionen ohne Nebenwirkungen zu erstellen.

Und es ist oft mit einem Mehraufwand verbunden, Funktionen in Form von Mischen und Kopieren einiger zusätzlicher Daten, möglicherweise einer zusätzlichen Indirektionsebene und möglicherweise einer GC für Teile einer persistenten Datenstruktur, frei von Nebenwirkungen zu machen eine 32-Core-Maschine und ich denke, der Austausch lohnt sich wahrscheinlich, wenn wir sicherer mehr Dinge parallel tun können.


quelle
1
"Veränderlicher Status" bedeutet immer den Status auf Anwendungsebene und nicht die Prozedurebene. Das Eliminieren von Zeigern und Übergeben von Parametern als Kopierwerte ist eine der in FP gebackenen Techniken. Aber jede nützliche Funktion muss den Status auf einer bestimmten Ebene ändern - der Punkt der funktionalen Programmierung besteht darin, sicherzustellen, dass der veränderbare Status, der dem Aufrufer gehört, nicht in die Prozedur eintritt und Mutationen die Prozedur nur durch die Rückgabewerte verlassen! Es gibt jedoch nur wenige Programme, die viel leisten können, ohne den Status zu ändern, und die Fehler schleichen sich immer wieder an der Schnittstelle ein.
Steve
1
Um ehrlich zu sein, erlauben die meisten modernen Sprachen die Verwendung eines funktionalen Programmierstils (mit ein wenig Disziplin), und natürlich gibt es Sprachen, die sich funktionalen Mustern widmen. Aber es ist ein weniger recheneffizientes Muster und wird im Volksmund als Lösung für alle Übel überbewertet, so wie es die Objektorientierung in den 90er Jahren war. Die meisten Programme sind nicht an rechenintensive Berechnungen gebunden, die von einer Parallelisierung profitieren würden, und dies liegt häufig an der Schwierigkeit, das Programm auf eine Weise zu überlegen, zu entwerfen und zu implementieren, die für eine parallele Ausführung geeignet ist.
Steve
1
Die meisten Programme, die sich mit veränderlichen Zuständen befassen, tun dies, weil sie dies aus dem einen oder anderen Grund tun müssen. Und die meisten Programme sind nicht falsch, weil sie den gemeinsam genutzten Status verwenden oder ihn anomal aktualisieren. Dies liegt normalerweise daran, dass sie unerwarteten Datenmüll als Eingabe erhalten (der eine Datenmüllausgabe bestimmt) oder weil sie ihre Eingaben falsch verarbeiten (falsch im Sinne des Zwecks) erreicht werden). Funktionale Muster tragen wenig dazu bei.
Steve
1
@Steve Ich stimme Ihnen vielleicht auf halbem Weg zu, da ich auf der Seite bin, nur nach Möglichkeiten zu suchen, um Dinge in Sprachen wie C oder C ++ threadsicherer zu machen, und ich glaube nicht, dass wir wirklich voll werden müssen -geblasen rein funktional dazu. Aber ich finde einige der Konzepte in FP zumindest nützlich. Ich habe gerade eine Antwort geschrieben, wie ich PDS hier nützlich finde, und der größte Vorteil, den ich an PDS finde, ist eigentlich nicht die Thread-Sicherheit, sondern Dinge wie Instanzen, zerstörungsfreies Bearbeiten, Ausnahmesicherheit, einfaches Rückgängigmachen usw.: