Warum korrelieren Funktionsprogramme zwischen Kompilierungserfolg und Korrektheit?

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?

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.

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.

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.

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.

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.