Warum verwenden wir in der funktionalen Programmierung persistente Datenstrukturen?

22

Die funktionale Programmierung verwendet persistente Datenstrukturen und unveränderliche Objekte. Meine Frage ist, warum es hier entscheidend ist, solche Datenstrukturen zu haben. Ich möchte auf einer niedrigen Ebene verstehen, was passieren würde, wenn die Datenstruktur nicht persistent ist. Würde das Programm öfter abstürzen?

gpuguy
quelle
es gibt eine ziemlich gute ausführliche diskussion darüber in abelson & sussman, struktur und interpretation von computerprogrammen
vzn

Antworten:

19

Wenn Sie mit unveränderlichen Datenobjekten arbeiten, haben Funktionen die Eigenschaft, dass sie jedes Mal, wenn Sie sie mit denselben Eingaben aufrufen, dieselben Ausgaben erzeugen. Dadurch ist es einfacher, Berechnungen zu konzipieren und zu korrigieren. Es macht sie auch einfacher zu testen.

Das ist nur ein Anfang. Da Mathematik schon seit langem mit Funktionen arbeitet, gibt es viele Argumentationstechniken, die wir aus der Mathematik ausleihen und für strenge Überlegungen zu Programmen verwenden können. Der aus meiner Sicht wichtigste Vorteil ist, dass die Typsysteme für Funktionsprogramme gut entwickelt sind. Wenn Sie also irgendwo einen Fehler machen, ist die Wahrscheinlichkeit sehr hoch, dass er als Typinkongruenz angezeigt wird. Daher sind typisierte Funktionsprogramme in der Regel viel zuverlässiger als imperative Programme.

Im Gegensatz dazu haben Sie bei der Arbeit mit veränderlichen Datenobjekten zunächst die kognitive Last, sich an die verschiedenen Zustände zu erinnern und diese zu verwalten, die das Objekt während einer Berechnung durchläuft. Sie müssen darauf achten, die Dinge in der richtigen Reihenfolge zu erledigen und sicherstellen, dass alle Eigenschaften, die Sie für einen bestimmten Schritt benötigen, zu diesem Zeitpunkt erfüllt sind. Es ist leicht, Fehler zu machen, und die Typsysteme sind nicht leistungsfähig genug, um diese Fehler abzufangen.

Mathematik hat nie mit veränderlichen Datenobjekten gearbeitet. Es gibt also keine Argumentationstechniken, die wir uns ausleihen könnten. In der Informatik wurden zahlreiche eigene Techniken entwickelt, insbesondere Floyd-Hoare Logic . Diese sind jedoch schwieriger zu meistern als die üblichen mathematischen Techniken. Die meisten Schüler können damit nicht umgehen und werden daher nur selten unterrichtet.

Um einen schnellen Überblick über die Unterschiede zwischen den beiden Paradigmen zu erhalten, lesen Sie bitte die ersten Handzettel in meinen Vorlesungsskripten zu den Prinzipien der Programmiersprachen .

Uday Reddy
quelle
Das macht für mich sehr viel Sinn. Vielen Dank, dass Sie Ihre PPTs geteilt haben. Teilen Sie auch Videoaufnahmen derselben?
gpuguy
@gpuguy. Ich benutze Powerpoint nicht so oft. Whiteboard ist mein Lieblingsmedium. Die Handouts sollten jedoch für sich selbst gut lesbar sein.
Uday Reddy
+1 Mathematik hat nie mit veränderlichen Datenobjekten gearbeitet. Auch der Link zu Ihrem Skript.
Guy Coder
15

Das korrekte Arbeiten mit persistenten Datenstrukturen ist einfacher als das Arbeiten mit veränderlichen Datenstrukturen. Ich würde sagen, das ist der Hauptvorteil.

Natürlich können wir theoretisch alles, was wir mit persistenten Datenstrukturen tun, auch mit veränderlichen tun und umgekehrt. In vielen Fällen verursachen persistente Datenstrukturen zusätzliche Kosten, in der Regel, weil Teile davon kopiert werden müssen. Diese Überlegungen hätten persistente Datenstrukturen vor 30 Jahren viel weniger attraktiv gemacht, als Supercomputer über weniger Speicher als Ihr Mobiltelefon verfügten. Heutzutage scheinen die größten Engpässe bei der Herstellung von Software die Entwicklungszeit und die Wartungskosten zu sein. Daher sind wir bereit, einen Teil der Effizienz bei der Ausführung für die Effizienz bei der Entwicklung zu opfern.

Warum ist es einfacher, persistente Datenstrukturen zu verwenden? Weil Menschen Aliasing und andere unerwartete Interaktionen zwischen verschiedenen Teilen eines Programms schlecht nachverfolgen können . Sie denken automatisch, weil zwei Dinge aufgerufen werden xund ydann nichts in commmon haben. Schließlich muss man sich bemühen, herauszufinden, dass "der Morgenstern" und "der Abendstern" wirklich dasselbe sind. In ähnlicher Weise kann leicht vergessen werden, dass sich eine Datenstruktur ändern kann, weil andere Threads damit arbeiten, oder weil wir eine Methode aufgerufen haben, die die Datenstruktur ändert, usw. Viele dieser Bedenken treten bei der Arbeit einfach nicht auf persistente Datenstrukturen.

Persistente Datenstrukturen haben auch andere technische Vorteile. Es ist normalerweise einfacher, sie zu optimieren. Zum Beispiel können Sie eine persistente Datenstruktur jederzeit auf einen anderen Knoten in Ihrer Cloud kopieren, wenn Sie dies wünschen. Sie müssen sich keine Sorgen um die Synchronisierung machen.

Andrej Bauer
quelle
Wenn es so viele Vorteile hat, warum nicht auch persistente Datenstrukturen in imperativen Sprachen verwenden?
gpuguy
4
Vielleicht werden Sie bald fragen: "Warum imperative Sprachen verwenden?"
Andrej Bauer
4
Im Ernst, es gibt Datenstrukturen, die nur schwer durch dauerhafte zu ersetzen sind. Beispielsweise sind Zahlenkalkulationsprogramme, die Arrays und Matrizen verwenden, mit herkömmlichen Datenstrukturen viel schneller, da die Hardware für diese Art von Dingen optimiert ist.
Andrej Bauer
1
@gpuguy. Persistente Datenstrukturen können und sollten auch in imperativen Sprachen verwendet werden, wenn sie anwendbar und geeignet sind. Um sie verwenden zu können, sollte die Sprache die auf Garbage Collection basierende Speicherverwaltung unterstützen. Viele moderne Sprachen haben das: Java, C #, Scala, Python, Ruby, Javascript usw.
Uday Reddy
Ein großer Vorteil ist wohl die abstraktere Oberfläche im Vergleich zu veränderlichen Datenstrukturen. Sie können Dinge unter der Haube ändern (z. B. Unveränderlichkeit oder referenzielle Integrität), müssen dies aber nicht.
Raphael
2

Wenn man die Antworten anderer hinzufügt und einen mathematischen Ansatz verstärkt, hat die funktionale Programmierung auch eine schöne Synergie mit der relationalen Algebra und Galois Connections.

Dies ist im Bereich der formalen Methoden äußerst nützlich.
Zum Beispiel:

  • Formale Nachweise bei der Programmüberprüfung werden durch Extended Static Checking vereinfacht;
  • Eine Reihe von Eigenschaften aus der relationalen Algebra sind für die SAT-Lösung mit Werkzeugen wie Alloy nützlich.
  • Galois Connections ermöglicht einen kalkulatorischen Ansatz für die Softwarespezifikation, wie in diesem Blog unter Bezugnahme auf ein Papier von Shin-Cheng Mu und José Nuno Oliveira zu sehen ist.
  • Galois-Verbindungen (und funktionale Programmierung) können im Design by Contract-Modus verwendet werden, da sie ein allgemeineres Konzept als Hoare Logic darstellen.

Beispiel

{p}P{q}[P]ϕpϕq[P]

  • [P]P
  • ϕpϕq)pq

Dieser Ansatz ermöglicht auch die Berechnung der schwächsten Vorbedingung und der stärksten Nachbedingung , was in einer Reihe von Situationen nützlich ist.

afsantos
quelle
2

Ich möchte auf einer niedrigen Ebene verstehen, was passieren würde, wenn die Datenstruktur nicht persistent ist.

Betrachten wir einen Pseudozufallszahlengenerator mit einem riesigen Zustandsraum (wie " Mersenne Twister " mit einem Zustand von 2450 Bytes) als Datenstruktur. Wir wollen wirklich keine Zufallszahl mehr als einmal verwenden, daher scheint es wenig Grund zu geben, diese als unveränderliche persistente Datenstruktur zu implementieren. Fragen wir uns nun, was im folgenden Code schief gehen könnte:

mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

Die meisten Programmiersprachen geben nicht die Reihenfolge an, in der MonteCarloIntegral_Bulkund MonteCarloIntegral_Boundaryausgewertet werden soll. Wenn beide einen Verweis auf ein veränderbares mt_gen als Argument verwenden, kann das Ergebnis dieser Berechnung plattformabhängig sein. Schlimmer noch, es könnte Plattformen geben, auf denen das Ergebnis zwischen verschiedenen Läufen überhaupt nicht reproduzierbar ist.

Man kann eine effiziente veränderbare Datenstruktur für mt_gen entwerfen, so dass jede Verschachtelung der Ausführung von MonteCarloIntegral_Bulkund MonteCarloIntegral_Boundary"ein korrektes" Ergebnis ergibt, eine andere Verschachtelung jedoch im Allgemeinen zu einem anderen "korrekten" Ergebnis führt. Diese Nichtreproduzierbarkeit macht die entsprechende Funktion "unrein" und führt auch zu einigen anderen Problemen.

Die Nichtreproduzierbarkeit kann vermieden werden, indem eine feste sequentielle Ausführungsreihenfolge erzwungen wird. In diesem Fall kann der Code jedoch so angeordnet werden, dass immer nur ein einziger Verweis auf mt_gen verfügbar ist. In einer typisierten funktionalen Programmiersprache könnten Eindeutigkeitstypen verwendet werden, um diese Einschränkung zu erzwingen, wodurch sichere veränderbare Aktualisierungen auch im Kontext von rein funktionalen Programmiersprachen ermöglicht werden. Das alles klingt vielleicht nett und gut, aber zumindest theoretisch sind Monte-Carlo-Simulationen peinlich parallel, und unsere "Lösung" hat gerade dieses Eigentum zerstört. Dies ist nicht nur ein theoretisches Problem, sondern ein sehr reales praktisches Problem. Wir müssen jedoch die Funktionalität unseres Pseudozufallszahlengenerators und die Folge der von ihm erzeugten Zufallszahlen ändern, und keine Programmiersprache kann dies automatisch für uns tun. (Natürlich können wir auch eine andere Pseudozufallszahlenbibliothek verwenden, die bereits die erforderliche Funktionalität bietet.)

Auf einer niedrigen Ebene führen veränderbare Datenstrukturen leicht zu einer Nichtreproduzierbarkeit (und damit zu Verunreinigungen), wenn die Ausführungsreihenfolge nicht sequentiell und fest ist. Eine typische zwingende Strategie, um mit diesen Problemen umzugehen, besteht darin, sequentielle Phasen mit fester Ausführungsreihenfolge zu haben, in denen sich veränderbare Datenstrukturen ändern, und parallele Phasen mit willkürlicher Ausführungsreihenfolge, in denen alle gemeinsam genutzten veränderlichen Datenstrukturen konstant bleiben.


Andrej Bauer sprach das Aliasing für veränderbare Datenstrukturen an. Interessanterweise haben verschiedene imperative Sprachen wie Fortran und C unterschiedliche Annahmen über das erlaubte Aliasing von Funktionsargumenten, und die meisten Programmierer sind sich überhaupt nicht bewusst, dass ihre Sprache ein Aliasing-Modell hat.

Unveränderlichkeit und Wertsemantik werden möglicherweise leicht überbewertet. Wichtiger ist, dass das Typsystem und das logische Framework (wie das abstrakte Maschinenmodell, das Aliasing-Modell, das Concurrency-Modell oder das Speicherverwaltungsmodell) Ihrer Programmiersprache eine ausreichende Unterstützung für das "sichere" Arbeiten mit "effizienten" Daten bieten Strukturen. Die Einführung der "Verschiebungssemantik" in C ++ 11 mag aus theoretischer Sicht einen großen Rückschritt in Bezug auf Reinheit und "Sicherheit" bedeuten, in der Praxis ist es jedoch umgekehrt. Das Typensystem und der logische Rahmen der Sprache wurden erweitert, um große Teile der mit der neuen Semantik verbundenen Gefahr zu beseitigen. (Und selbst wenn raue Kanten bleiben, heißt das nicht, dass dies nicht durch ein "besseres"


Uday Reddy sprach das Problem an, dass Mathematik niemals mit veränderlichen Datenobjekten funktioniert und dass die Typsysteme für Funktionsprogramme für unveränderliche Datenobjekte gut entwickelt sind. Dies erinnerte mich an Jean-Yves Girards Erklärung, dass Mathematik nicht für die Arbeit mit veränderlichen Objekten verwendet wird, wenn er versucht, lineare Logik zu motivieren.

Man könnte sich fragen, wie man das Typsystem und den logischen Rahmen von funktionalen Programmiersprachen erweitern kann, um "sicher" mit "effizienten" wandelbaren nicht persistenten Datenstrukturen arbeiten zu können. Ein Problem könnte sein, dass klassische Logik und Boolesche Algebren möglicherweise nicht das beste logische Framework für die Arbeit mit veränderlichen Datenstrukturen sind. Vielleicht sind lineare Logik und kommutative Monoide für diese Aufgabe besser geeignet? Vielleicht sollte ich lesen, was Philip Wadler über lineare Logik als Typsystem für funktionale Programmiersprachen zu sagen hat ? Aber selbst wenn die lineare Logik dieses Problem nicht lösen kann, heißt das nicht, dass das Typsystem und der logische Rahmen einer funktionalen Programmiersprache nicht erweitert werden können, um "sicher" und "effizient" zu sein.

Thomas Klimpel
quelle
@ DW Sie haben wahrscheinlich Recht, dass diese Antwort keine eigenständige Antwort ist. Derzeit wird nur auf bestimmte Punkte eingegangen, die in den Antworten von Uday Reddy und Andrej Bauer angesprochen wurden. Ich denke, ich kann es so ändern, dass es eigenständig ist, und direkt auf die Frage antworten: "Ich möchte auf einer niedrigen Ebene verstehen, was passieren würde, wenn die Datenstruktur nicht dauerhaft ist." Teil der Frage. Ich würde einen Pseudozufallszahlengenerator mit einem riesigen Zustandsraum (wie "Mersenne Twister" mit 2450-Byte-Zustand) als Datenstruktur betrachten und Dinge erklären, die schief gehen können.
Thomas Klimpel
@ DW Ich habe nicht das Gefühl, dass eine der Antworten auf diese Frage wirklich die Frage beantwortet. Insbesondere gibt es nicht viel darüber, was persistente Datenstrukturen wirklich sind (außer unveränderlich zu sein) und wie sie implementiert werden.
Guildenstern