Warum korrelieren Funktionsprogramme zwischen Kompilierungserfolg und Korrektheit?

12

Seit 4 Jahren beschäftige ich mich mit funktionaler Programmierung, seit ich mit LINQ arbeite. Kürzlich habe ich reinen funktionalen C # -Code geschrieben und aus erster Hand festgestellt, was ich über funktionale Programme gelesen habe - dass sie nach dem Kompilieren in der Regel korrekt sind.

Ich habe versucht, einen Finger darauf zu legen, warum dies der Fall ist, aber es ist mir nicht gelungen.

Eine Vermutung ist, dass Sie beim Anwenden von OO-Prinzipien eine "Abstraktionsschicht" haben, die in funktionalen Programmen nicht vorhanden ist, und diese Abstraktionsschicht ermöglicht, dass die Verträge zwischen Objekten korrekt sind, während die Implementierung falsch ist.

Hat jemand darüber nachgedacht und den zugrunde liegenden abstrakten Grund für die Korrelation zwischen Kompilierungserfolg und Programmkorrektheit in der funktionalen Programmierung gefunden?

Aaron Anodide
quelle
9
Lisp ist eine funktionale Sprache, es gibt jedoch keine nennenswerten Überprüfungen der Kompilierungszeit. Gleiches gilt für einige andere funktionale Sprachen. Eine genauere Charakterisierung der Sprachen, über die Sie sprechen, wäre: Sprachen mit leistungsfähigen formalen Systemen (mindestens Hindley-Milner-Systeme).
1
@delnan Ich würde nicht sagen, dass Lisp eine funktionale Programmiersprache ist, obwohl sie zum Schreiben von funktionalem Programmcode verwendet werden kann. Clojure, die ein Lisp-Dialekt ist, ist eine funktionale Programmiersprache
Sakisk
2
Ich bin mit @delnan einverstanden. Diese Aussage bezieht sich eher auf statisch typisierte funktionale Programmiersprachen, insbesondere auf Haskell, das das Hindley-Milner-System verwendet. Ich denke, dass die Hauptidee ist, dass, wenn Sie die Typen richtig machen, das Vertrauen, dass Ihr Programm korrekt ist, erhöht wird.
Sakisk
1
Funktionscode kann genauso viele Abstraktionen und Indirektionen aufweisen wie Ihr typischer Mainstream-OOP-Code (wenn nicht mehr). Der Teufel steckt im Detail - weniger Nebenwirkungen und keine Null bedeuten weniger unsichtbaren Zustand und weniger Chancen, Fehler zu machen. Beachten Sie, dass Sie dieselben Prinzipien in den gängigen imperativen Sprachen anwenden können, es ist nur arbeitsintensiver und häufig ausführlicher (z. B. wenn Sie finalauf alles eingehen müssen ).
Doval
1
Keine vollständige Antwort, aber die Typisierung des Programms ist eine grobe Form der formalen Überprüfung des Programms. Im Allgemeinen weisen objektorientierte Programme entweder komplizierte oder sehr einfache Typsysteme auf, da die Substitution berücksichtigt werden muss - in den meisten Fällen werden sie der Einfachheit halber als nicht sinnvoll angesehen. Die ML-ähnlichen Systeme können CH in vollem Umfang nutzen, sodass Sie einen Proof nur in Typen codieren und den Compiler als Proof-Checker verwenden können.
Maciej Piechotka

Antworten:

12

Ich kann diese Antwort als jemand schreiben, der vieles beweist. Für mich ist Korrektheit nicht nur das, was funktioniert, sondern auch das, was funktioniert und leicht zu beweisen ist.

In vielerlei Hinsicht ist die funktionale Programmierung restriktiver als die imperative Programmierung. Schließlich hindert Sie nichts daran, eine Variable in C niemals zu mutieren! In der Tat lassen sich die meisten Funktionen in FP-Sprachen mit nur wenigen Kernfunktionen leicht beschreiben. Es läuft alles auf Lambdas, Funktionsanwendung und Mustererkennung hinaus!

Da wir den Pfeifer jedoch im Voraus bezahlt haben, haben wir viel weniger zu tun und wir haben viel weniger Möglichkeiten, wie etwas schief gehen kann. Wenn Sie ein 1984-Fan sind, ist Freiheit in der Tat Sklaverei! Durch die Verwendung von 101 verschiedenen Tricks für ein Programm müssen wir über Dinge nachdenken, als ob eines dieser 101 Dinge passieren kann! Das ist wirklich schwer, wie sich herausstellt :)

Wenn Sie mit einer Sicherheitsschere anstelle eines Schwertes beginnen, ist das Laufen weniger gefährlich.

Nun schauen wir uns Ihre Frage an: Wie passt das alles in das "es kompiliert und funktioniert!" Phänomene. Ich denke, ein großer Teil davon ist der gleiche Grund, warum es einfach ist, Code zu beweisen! Wenn Sie Software schreiben, konstruieren Sie schließlich einen informellen Beweis dafür, dass sie korrekt ist. Aus diesem Grund ist das, was durch Ihre natürlichen handwavy Beweise und den eigenen Begriff der Korrektheit (typechecking) des Compilers abgedeckt wird, ziemlich viel.

Wenn Sie Features und komplizierte Interaktionen zwischen ihnen hinzufügen, nimmt die Anzahl der vom Typsystem nicht überprüften Elemente zu. Ihre Fähigkeit, informelle Beweise zu erstellen, scheint sich jedoch nicht zu verbessern! Dies bedeutet, dass durch Ihre Erstinspektion mehr herausrutschen kann, das später aufgefangen werden muss.

Daniel Gratzer
quelle
1
Ich mag Ihre Antwort, aber ich sehe nicht, wie es die Frage des OP beantwortet
Sakisk
1
@faif Erweitert meine Antwort. TLDR: Jeder ist Mathematiker.
Daniel Gratzer
"Durch die Verwendung von 101 verschiedenen Tricks für ein Programm müssen wir über die Dinge nachdenken, als ob eines dieser 101 Dinge passieren kann!": Ich habe irgendwo gelesen, dass man ein Genie sein muss, um mit Mutation zu programmieren, weil man es behalten muss viele Informationen in Ihrem Kopf.
Giorgio
12

der zugrunde liegende abstrakte Grund für die Korrelation zwischen Kompilierungserfolg und Programmkorrektheit in der funktionalen Programmierung?

Veränderlicher Zustand.

Compiler prüfen die Dinge statisch. Sie stellen sicher, dass Ihr Programm gut strukturiert ist, und das Typensystem bietet einen Mechanismus, mit dem sichergestellt werden kann, dass die richtigen Werte an den richtigen Stellen zulässig sind. Das Typensystem versucht auch sicherzustellen, dass die richtige Art von Semantik an der richtigen Art von Stellen zulässig ist.

Sobald Ihr Programm state einführt, wird diese letztere Einschränkung weniger nützlich. Sie müssen sich nicht nur um die richtigen Werte an den richtigen Stellen kümmern, sondern auch berücksichtigen, dass sich dieser Wert an beliebigen Punkten Ihres Programms ändert. Sie müssen die Semantik Ihres Codes berücksichtigen, die sich neben diesem Status ändert.

Wenn Sie die funktionale Programmierung gut machen, gibt es keinen (oder nur einen sehr geringen) veränderlichen Zustand.

Es gibt jedoch einige Debatten über die Ursache hier - wenn Programme ohne Status nach dem Kompilieren häufiger arbeiten, weil der Compiler mehr Fehler feststellen kann, oder wenn Programme ohne Status nach dem Kompilieren häufiger arbeiten, weil dieser Programmierstil weniger Fehler erzeugt.

Nach meiner Erfahrung ist es wahrscheinlich eine Mischung aus beidem.

Telastyn
quelle
2
"Meiner Erfahrung nach ist es wahrscheinlich eine Mischung aus beidem.": Ich habe die gleiche Erfahrung. Die statische Typisierung fängt Fehler beim Kompilieren ab, auch wenn eine imperative Sprache (z. B. Pascal) verwendet wird. In FP erleichtert die Vermeidung von Veränderlichkeit und die Verwendung eines deklarativeren Programmierstils das Nachdenken über Code. Wenn eine Sprache beides bietet, erhalten Sie beide Vorteile.
Giorgio
7

Vereinfacht ausgedrückt bedeutet die Einschränkung, dass es weniger richtige Möglichkeiten gibt, Dinge zusammenzusetzen, und erstklassige Funktionen erleichtern das Ausklammern von Dingen wie Schleifenstrukturen. Nehmen Sie die Schleife aus dieser Antwort , zum Beispiel:

for (Iterator<String> iterator = list.iterator(); iterator.hasNext();) {
    String string = iterator.next();
    if (string.isEmpty()) {
        iterator.remove();
    }
}

Dies ist zufällig die einzige sichere zwingende Möglichkeit in Java, ein Element aus einer Auflistung zu entfernen, während Sie sie durchlaufen. Es gibt viele Möglichkeiten, die sehr genau aussehen, aber falsch sind. Menschen, die sich dieser Methode nicht bewusst sind, gehen manchmal verschlungene Wege, um das Problem zu vermeiden, wie beispielsweise das Durchlaufen einer Kopie.

Es ist nicht sonderlich schwierig, diese generische Version zu erstellen. StringsOhne erstklassige Funktionen können Sie das Prädikat (die Bedingung in der if) jedoch nicht ersetzen. Daher wird dieser Code in der Regel kopiert und eingefügt und leicht modifiziert.

Kombinieren Sie erstklassige Funktionen , die Ihnen geben Fähigkeit , das Prädikat als Parameter übergeben, mit der Einschränkung der Unveränderlichkeit , dass es sehr ärgerlich , wenn man nicht macht, und Sie kommen mit einfachen Bausteinen wie filter, wie in diesem Scala Code das macht das selbe:

list filter (!_.isEmpty)

Überlegen Sie sich nun, was das Typsystem für Sie beim Kompilieren im Fall von Scala überprüft. Diese Überprüfungen werden jedoch auch von dynamischen Typsystemen durchgeführt, wenn Sie es zum ersten Mal ausführen:

  • listmuss ein Typ sein, der die filterMethode unterstützt , nämlich eine Auflistung.
  • Die Elemente von listmüssen eine isEmptyMethode haben, die einen Booleschen Wert zurückgibt.
  • Die Ausgabe wird eine (möglicherweise) kleinere Sammlung mit der gleichen Art von Elementen sein.

Welche anderen Möglichkeiten stehen dem Programmierer zur Verfügung, wenn diese Dinge überprüft wurden? Ich habe versehentlich das vergessen !, was einen äußerst offensichtlichen Testfallfehler verursachte. Das ist so ziemlich der einzige Fehler, den ich machen konnte, und ich habe ihn nur gemacht, weil ich direkt aus Code übersetzt habe, der auf die Umkehrbedingung getestet wurde.

Dieses Muster wird immer wieder wiederholt. Mit erstklassigen Funktionen können Sie Dinge mit präziser Semantik in kleine wiederverwendbare Dienstprogramme umwandeln. Einschränkungen wie die Unveränderlichkeit geben Ihnen den Anstoß dazu, und die Überprüfung der Parameter dieser Dienstprogramme lässt nur wenig Raum, um sie zu vermasseln.

Dies alles hängt natürlich davon ab, dass der Programmierer weiß, dass die Vereinfachungsfunktion filterbereits vorhanden ist und dass er sie finden kann oder den Vorteil erkennt, selbst eine zu erstellen. Versuchen Sie, dies überall selbst zu implementieren, indem Sie nur die Schwanzrekursion verwenden, und Sie befinden sich wieder in dem Boot mit der gleichen Komplexität wie die imperative Version, nur noch schlimmer. Nur weil Sie es sehr einfach schreiben können , heißt das nicht, dass die einfache Version offensichtlich ist.

Karl Bielefeldt
quelle
"Nachdem diese Dinge überprüft wurden, welche anderen Möglichkeiten stehen dem Programmierer noch zur Verfügung?": Dies bestätigt irgendwie meine Erfahrung, dass (1) statische Typisierung + (2) funktionaler Stil weniger Möglichkeiten lassen, Dinge zu vermasseln. Infolgedessen neige ich dazu, ein korrektes Programm schneller zu bekommen und weniger Komponententests zu schreiben, wenn ich FP verwende.
Giorgio
2

Ich glaube nicht, dass es einen signifikanten Zusammenhang zwischen der Kompilierung der funktionalen Programmierung und der Laufzeitkorrektheit gibt. Es kann eine gewisse Korrelation zwischen statisch typisierter Kompilierung und Laufzeitkorrektheit geben, da Sie möglicherweise zumindest die richtigen Typen haben, wenn Sie nicht casten.

Der Aspekt der Programmiersprache, der, wie Sie beschreiben, eine erfolgreiche Kompilierung mit der Richtigkeit des Laufzeittyps in Verbindung bringen kann, ist die statische Typisierung, und das auch dann, wenn Sie die Typprüfung nicht mit Casts schwächen, die nur zur Laufzeit (in Umgebungen mit Microsoft) bestätigt werden können stark typisierte Werte oder Stellen (z. B. Java oder .Net) oder überhaupt nicht (in Umgebungen, in denen die Typinformationen verloren gehen oder die nur schwach typisiert sind, z. B. C und C ++).

Die funktionale Programmierung an sich kann jedoch auch auf andere Weise hilfreich sein, z. B. um gemeinsame Daten und einen veränderlichen Zustand zu vermeiden.

Beide Aspekte zusammen haben möglicherweise eine signifikante Korrelation in Bezug auf die Korrektheit, aber Sie müssen sich darüber im Klaren sein, dass das Fehlen von Kompilierungs- und Laufzeitfehlern streng genommen nichts über die Korrektheit im weiteren Sinne aussagt, da das Programm tut, was es tun soll, und schnell versagt über ungültige Eingabe oder unkontrollierbaren Laufzeitfehler. Dazu benötigen Sie Geschäftsregeln, Anforderungen, Anwendungsfälle, Zusicherungen, Komponententests, Integrationstests usw. Letztendlich bieten sie meiner Meinung nach viel mehr Sicherheit als funktionale Programmierung, statische Typisierung oder beides.

acelent
quelle
Dies. Die Richtigkeit eines Programms kann nicht durch eine erfolgreiche Kompilierung beurteilt werden. Wenn ein Compiler die oft widersprüchlichen und ungenauen Anforderungen jeder Person verstehen könnte, die zu den Spezifikationen des Programms beigetragen hat, könnte eine erfolgreiche Kompilierung möglicherweise als Richtigkeit angesehen werden. Aber dieser mythische Compiler würde keinen Programmierer brauchen! Während es eine etwas höhere Gesamtkorrelation zwischen Kompilierung und Korrektheit für funktionale und imperative Programme geben mag , ist dies ein so kleiner Teil des Gesamtkorrektheitsurteils, dass ich es für im Grunde irrelevant halte
Jordan Rieger
2

Erklärung für Manager:

Ein Funktionsprogramm ist wie eine große Maschine, an der alles angeschlossen ist, Schläuche, Kabel. [Einen Wagen]

Ein prozedurales Programm ist wie ein Gebäude mit Räumen, in denen sich eine kleine Maschine befindet, die Teilprodukte in Behältern lagert und Teilprodukte von anderen Orten bezieht. [Eine Fabrik]

Wenn also die funktionierende Maschine bereits zusammenpasst, muss sie etwas produzieren. Wenn ein prozeduraler Komplex abläuft, haben Sie möglicherweise bestimmte Effekte übersehen, Chaos eingeführt und die Funktionsfähigkeit nicht garantiert. Selbst wenn Sie eine Checkliste haben, in der alles korrekt integriert ist, sind so viele Zustände und Situationen möglich (herumliegende Teilprodukte, überlaufende Eimer, fehlende), dass Garantien schwer zu geben sind.


Im Ernst, der prozedurale Code spezifiziert die Semantik des gewünschten Ergebnisses nicht so sehr wie der funktionale Code. Prozedurale Programmierer können leichter durch Code und Daten aus dem Weg gehen und verschiedene Methoden einführen, um eine Sache zu tun (von denen einige unvollkommen sind). In der Regel werden externe Daten erstellt. Funktionale Programmierer brauchen möglicherweise länger, wenn das Problem komplexer wird.

Eine stark typisierte funktionale Sprache kann noch bessere Daten- und Flussanalysen durchführen. Bei einer prozeduralen Sprache muss das Ziel eines Programms häufig als formale Korrektheitsanalyse außerhalb des Programms definiert werden.

Joop Eggen
quelle
1
Bessere Anologie: Funktionale Programmierung ist wie ein Helpdesk ohne Kunden - alles ist wunderbar (solange Sie nicht den Zweck oder die Effizienz in Frage stellen).
Brendan,
@Brendan Car & Factory bildet keine so schlechte Analogie. Es wird versucht zu erklären, warum (kleine) Programme in einer funktionalen Sprache mit höherer Wahrscheinlichkeit funktionieren und weniger fehleranfällig sind als eine "Fabrik". Aber zur Rettung von OOP kommt zu sagen, dass eine Fabrik mehrere Dinge produzieren kann und größer ist. Ihr Vergleich ist passend; Wie oft man hört, kann FP enorm parallelisieren und optimieren, aber in der Tat (kein Wortspiel) liefert es langsame Ergebnisse. Ich halte mich immer noch an FP.
Joop Eggen
Funktionale Programmierung im Maßstab funktioniert für eine en.wikipedia.org/wiki/Spherical_cow ziemlich gut .
Den
@Den ich selbst würde keine Machbarkeitsprobleme befürchten, wenn ich an einem großen FP-Projekt arbeite. Ich liebe es sogar. Die Verallgemeinerung hat ihre Grenzen. Aber da diese letzte Aussage auch eine Verallgemeinerung ist ... (Danke für die kugelförmige Kuh)
Joop Eggen