Can Haskell Funktionen mit Korrektheit Eigenschaften bewährt / Modell-geprüft / überprüft werden?

https://stackoverflow.com/questions/4077970

28-09-2019
|

Frage

Anknüpfend an Ideen in: Gibt es beweisbar reale Welt Sprachen?

Ich weiß nicht, über Sie, aber ich bin krank Code zu schreiben, dass ich nicht garantieren kann.

Nach der obigen Frage zu stellen und bekommt eine phänomenale Antwort (Danke alle!) Ich habe beschlossen, meine Suche nach einem beweisbar, pragmatisch, Ansatz Haskell . Ich entschied mich für Haskell, weil es tatsächlich sinnvoll ist (es gibt viele web Frameworks denn es steht geschrieben, dies scheint eine gute Benchmark) und ich denke, es streng genug ist, funktionell , dass es beweisbar sein könnte, oder zumindest ermöglichen, die Prüfung von Invarianten.

Hier ist, was ich will (und wurde nicht gefunden)

Ich möchte einen Rahmen, der an einer Haskell-Funktion suchen, hinzufügen, in psudocode geschrieben:

add(a, b):
    return a + b

- und prüfen, ob bestimmte invarients über jeden Ausführungszustand zu halten. Ich würde für einigen formalen Beweis bevorzugen, aber ich für so etwas wie ein Model-Checker absetzen könnte.
In diesem Beispiel wären die invarient dass angegebene Werte a und b , der Rückgabewert ist immer die Summe a + b .

Dies ist ein einfaches Beispiel, aber ich glaube nicht, es ist ein Ding der Unmöglichkeit für einen Rahmen wie diese zu existieren. Es wäre sicherlich eine obere Grenze für die Komplexität einer Funktion sein, die getestet werden können (10 String-Eingänge auf eine Funktion wäre sicherlich eine lange Zeit in Anspruch nehmen!), Aber dieser vorsichtigen Entwurf von Funktionen würde fördern, und ist nicht anders als mit anderen formalen Methoden. Stellen Sie sich vor Z oder B verwendet wird, wenn Sie Variablen / Sets definieren, stellen Sie verdammt sicher, dass Sie die Variablen möglichst kleine Bereiche geben. Wenn Ihr INT wird nie über 100 gehen zu sein, stellen Sie sicher, dass Sie initialisieren es als solches! Techniken wie diese und die richtige Problemdekomposition sollten - ich glaube -. Ermöglichen zufriedenstellende Prüfung einer rein funktionalen Sprache wie Haskell

Ich bin - noch - nicht sehr erfahren mit formalen Methoden oder Haskell. Lassen Sie mich wissen, ob meine Idee ein Ton ist, oder vielleicht denken Sie, dass Haskell geeignet ist, nicht wahr? Wenn Sie eine andere Sprache vorschlagen, stellen Sie sicher, gibt sie die „has-a-Web-Framework“ zu testen und zu tun, um das Original lesen Frage : -)

Lösung

Nun, ein paar Dinge zu beginnen, da Sie die Haskell Route sind unter:

Sind Sie vertraut mit dem Curry-Howard Korrespondenz ? Es gibt Systeme für die maschinenüberprüft Beweise auf dieser Basis verwendet, die sind, in vielerlei Hinsicht einfach funktionalen Programmiersprachen mit sehr leistungsfähigen Systemen des Typs.
Sind Sie mit den Bereichen der abstrakten Mathematik vertraut, die Haskell-Code für die Analyse nützliche Konzepte zur Verfügung stellen? Verschiedene Varianten der Algebra und einige Bits der Kategorie Theorie kommen eine Menge auf.
Beachten Sie, dass Haskell, wie alle Turing-complete Sprachen, immer die Möglichkeit, nontermination hat. Im Allgemeinen ist es viel schwieriger, dass etwas zu beweisen, wird immer wahr sein, als es, dass entweder etwas wahr zu beweisen sein wird oder auf einem nicht terminierenden Wert ab.

Wenn Sie ernsthaft gehen für Beweis , nicht nur Testing , das ist die Art von Dingen, im Auge zu behalten. Die Grundregel ist dies: Machen ungültige Zustände Ursache Compiler-Fehler. Verhindern, dass ungültige Daten von in erster Linie codiert wird, dann lassen Sie die Typprüfer für Sie den mühsamen Teil tun.

Wenn Sie wollen, noch weiter gehen, wenn der Speicher mir den Beweis Assistent dient Coq eine hat „Extrakt zu Haskell“ -Funktion, die Sie beliebige Eigenschaften über kritische Funktionen belegen lassen, dann drehen Sie die Beweise in Haskell-Code.

Für ausgefallene Art Sytemdateien direkt in Haskell zu tun, Oleg Kiselyov ist der Großmeister . Sie können Beispiele auf seiner Website von netten Tricks wie höherrangigen polymorphe Typen zu kodieren statischen Beweisen finden, Längenprüfung .

Für leichtere Sachen, können Sie Dinge tun, wie einen Typ mit -Level Zertifikat eine Dateneinheit zu markieren, wie auf Richtigkeit überprüft worden sind. Du bist immer noch auf eigene Faust für die Richtigkeit Prüfung selbst, aber auch anderer Code kann zumindest verläßt sich auf dem Wissen, dass einige Daten in der Tat geprüft.

Ein weiterer Schritt können Sie, von leichter Überprüfung und ausgefallene Art System Tricks Aufbau aus, ist die Tatsache zu nutzen, dass Haskell funktioniert gut als Host-Sprache für die Einbettung von domänenspezifische Sprachen ; erstes Konstrukt eine sorgfältig beschränkt Subsprache (idealerweise eine, die Turing-complete ist nicht), über die Sie leichter nützliche Eigenschaften unter Beweis stellen können, dann Programme verwenden in diesen DSL Kernstücken der Kernfunktionalität in Ihrem gesamten Programm. Zum Beispiel könnte man beweisen, dass eine zwei Argument Funktion assoziativ ist, um parallelisierten Reduktion einer Sammlung von Gegenständen zu rechtfertigen, dass die Funktion (da die Reihenfolge der Funktionsanwendung spielt keine Rolle, nur die Reihenfolge der Argumente).

Oh, eine letzte Sache. Einige Ratschläge zur Vermeidung der Gefahren, dass Haskell enthält, welcher Code sabotieren, die sonst sicher-by-Konstruktion wäre: Ihre Erzfeinde sind hier allgemeine Rekursion , IO Monade und Teilfunktionen :

Die letzte ist relativ leicht zu vermeiden: Verwenden Sie sie nicht schreiben, und verwenden Sie sie nicht. Stellen Sie sicher, dass jeder Satz von Muster passt Griffe jeden denkbaren Fall, und nie error oder undefined verwenden. Der einzige schwierige Teil ist die Vermeidung von Standard-Bibliotheksfunktionen, die zu Fehlern führen können. Einige sind offensichtlich unsicher, wie fromJust :: Maybe a -> a oder head :: [a] -> a aber andere können subtiler sein. Wenn Sie sich selbst eine Funktion zu schreiben finden, dass wirklich, kann wirklich nicht tunalles mit einigen Eingabewerten, dann sind Sie damit ungültige Zustände durch den Eingangstyp und Bedarf codiert werden, dass zu beheben, zuerst.
Die zweite ist leicht zu vermeiden auf einer oberflächlichen Ebene von Material durch verschiedene reine Funktionen Streuung, die dann von einem IO Ausdruck verwendet werden. Besser ist es, so viel wie möglich, das gesamte Programm bewegt sie in reinen Code, so dass es unabhängig mit allem, was ausgewertet werden kann, aber das tatsächlichen I / O. Dies wird meist heikel nur, wenn Sie die Rekursion benötigen, die von externem Eingang angesteuert sind, die mich zum letzten Punkt bringt:
Wörter im Zusammenhang mit den Weisen: Fundierte Rekursion und produktive corecursion . Achten Sie immer darauf, dass rekursive Funktionen werden entweder von einem Ausgangspunkt zu einem bekannten Basisfall, oder sind eine Reihe von Elementen auf Nachfrage zu erzeugen. In der reinen Code, der einfachste Weg, dies entweder durch rekursiv zu tun, um eine endliche Datenstruktur kollabiert (zB statt einer Funktion selbst direkt beim Inkrementieren eines Zählers bis zu einem Maximal Aufruf, erstellen Sie eine Liste den Bereich der Zählerwerte halten und klappen ) oder rekursiv eine faule Datenstruktur (zB einer Liste von progressiven Annäherungen bis zu einem gewissen Wert), während sorgfältig nie die zwei direkt Mischen zu erzeugen (zB nicht nur „das erste Element treffen eine Bedingung im Stream finden“, es könnte nicht existieren. Stattdessen nehmen Werte aus dem Strom bis zu einem gewissen maximalen Tiefe, dann die endliche Liste suchen, die Handhabung des nicht-gefunden Falles angemessen).
Die letzten beiden Elemente kombinierend, für die Teile, wo man wirklich Notwendigkeit IO mit allgemeinen Rekursion tun, versuchen Sie das Programm als inkrementelle Komponenten zu bauen, dann kondensieren alle die peinliche Bits in einer einzigen „Fahrer“ Funktion. Zum Beispiel könnten Sie eine GUI-Ereignisschleife mit einer reinen Funktion wie mainLoop :: UIState -> Events -> UIState, einen Ausgang Test wie quitMessage :: Events -> Bool schreiben, eine Funktion anstehender Ereignisse getEvents :: IO Events zu erhalten, und einer Update-Funktion updateUI :: UIState -> IO (), dann führen Sie eigentlich das Ding mit einer verallgemeinerten Funktion wie runLoopIO :: (b -> a -> b) -> b -> IO a -> (b -> IO ()) -> IO (). Dies hält die komplizierte Teile wirklich rein, so dass Sie das ganze Programm mit einem Ereignisse Skript und überprüfen Sie den resultierenden UI Zustand läuft, während die peinlichen rekursive E / A-Teile in eine einzige, abstrakte Funktion zu isolieren, die leicht zu verstehen sind und wird oft unweigerlich richtig von Parametrizität .

Andere Tipps

Wahrscheinlich die nächste Sache, was Sie fragen für Haskabelle , ein Werkzeug, die Isabelle mit dem Beweis Assistenten kommt die Haskell-Dateien in Isabelle Theorien übersetzen und lässt Sie Dinge über sie beweisen. Soweit ich dieses Tool zu verstehen ist innerhalb der HOL entwickelt - ML - Haskell Projekt und die Dokumentationsseite einige Informationen über die Theorie hinter enthält.

Ich bin nicht schrecklich mit diesem Projekt vertraut und ich weiß nicht sehr viel über das, was mit ihm geschehen ist. Aber ich weiß, Brian Huffman mit diesen Dingen herumgespielt wurde, überprüft seine Papiere und Gespräche, sollten sie relevante Sachen enthalten.

Ich bin nicht sicher, ob Sie für das, was fragen, ist eigentlich das, was dich glücklich macht. : -)

Modell-Überprüfung eine Allzweck-Sprache ist wiehert nicht möglich, da Modelle müssen Domain-spezifisch sein, praktisch zu sein. Aufgrund Gödels Unvollständigkeitssatz, gibt es einfach kein Verfahren zum automatischen Beweis zu finden, in einer ausreichend ausdrucks Logik.

Das bedeutet, dass Sie auf Schreib Beweise selbst , das wirft die Frage auf, ob der Aufwand lohnt sich die Zeit damit verbracht. Natürlich schafft der Aufwand etwas sehr wertvoll, nämlich die Gewissheit, dass Ihr Programm korrekt ist. Die Frage ist nicht, ob dies ein Must-Have, aber ob die Zeit zu verbracht ist groß ein Kosten. Die Sache über Beweise, dass, während Sie kann ein „intuitiv“ zu verstehen, dass Ihr Programm korrekt ist , ist es oft sehr schwierig, dieses Verständnis zu formalisieren als Beweis. Das Problem mit dem intuitiven Verständnis ist, dass es um einen versehentlichen Fehler (Tippfehler und andere dumme Fehler) sehr anfällig ist. Dies ist das grundlegende Dilemma korrekte Programme zu schreiben.

Also, Forschung über das Programm Korrektheit ist alles, um es einfacher Beweise zu formalisieren und ihre Richtigkeit automatisch zu überprüfen. Die Programmierung ist ein integraler Bestandteil der „Leichtigkeit der Formalisierung“; es ist sehr wichtig für Schreibprogramme in einem Stil, der über leicht zu Grunde. Derzeit haben wir folgendes Spektrum:

Imperative Sprache wie C, C ++, Fortran, Python: Sehr schwer, hier etwas zu formalisieren. Unit-Tests und allgemeine Überlegungen sind die einzige Möglichkeit, zumindest eine gewisse Sicherheit zu bekommen. Statische Typisierung Fänge nur triviale Fehler (was viel besser als sie nicht fangen!).
rein funktionale Sprachen wie Haskell, ML: Ausdruck Typ-System hilft Fang nicht-triviale Fehlern und Irrtümern. Proving Korrektheit von Hand für Schnipsel von bis zu irgendwo um 200 Zeilen praktisch ist, würde ich sagen. (Habe ich einen Beweis für mein Betrieb Paket , zum Beispiel.) Quickcheck Testen ist ein billiger Ersatz für formalisierte Beweise.
Unselbständig typisierten Sprachen und Beweisassistenten wie Agda, Epigramm, Coq: Proving ganze Programme korrekt ist möglich dank automatisierter Hilfe bei Nachweis Formalisierung und Entdeckung. Allerdings ist die Belastung immer noch hoch.

Meiner Meinung nach ist der aktuelle Sweet-Spot für die korrekten Programme zu schreiben ist rein funktionale Programmierung . Wenn Leben auf der Richtigkeit des Programms ab, gehen Sie besser einen Level höher und einen Beweis Assistenten verwenden.

Sounds wie Sie wollen ESC / Haskell: http://research.microsoft.com/en-us/um/people/simonpj/papers/verify/index.htm

Oh, und Agda hat nun einen Web-Framework (Proof of Concept, mindestens): http://www.reddit.com/r/haskell/comments/d8dck/lemmachine_a_web_framework_in_agda/

Haben Sie einen Blick auf Quick Check? Es kann einige der Dinge, bieten die Sie benötigen.

http://www.haskell.org/haskellwiki/Introduction_to_QuickCheck

Ihr scheinbar einfaches Beispiel, add (a, b), ist tatsächlich schwer zu überprüfen -. Gleitkomma, Überlauf, Unterlauf, Interrupts, ist der Compiler überprüft, ist die Hardware überprüft, etc

Habit ist ein vereinfachtes Dialekt von Haskell, die Eigenschaften für den Nachweis Programm ermöglicht.

Hume ist eine Sprache mit 5 Stufen, je mehr limitedand daher leichter zu überprüfen:

Full Hume
  Full recursion
PR−Hume
  Primitive Recursive functions
Template−Hume
  Predefined higher−order functions
  Inductive data structures
  Inductive  Non−recursive first−order functions
FSM−Hume
  Non−recursive data structures
HW−Hume
  No functions
  Non−recursive data structures

Natürlich ist die populärste Methode heute für die Programmeigenschaften beweisen, ist Unit-Tests, die starke Sätze liefert, aber diese Sätze sind zu spezifisch. "Typen als schädlich", Pierce, schieben 66

Hier finden Sie Zeno . Unter Angabe der Wiki-Seite:

Zeno ist ein automatisiertes System Beweis für Haskell Programmeigenschaften; am Imperial College in London von William Sonnex, Sophia Drossopoulou und Susan Eisenbach entwickelt. Ziel ist es, das allgemeine Problem der Gleichheit zwischen zwei Haskell Begriffen, für jeden Eingabewert zu lösen.

Viele Programmverifikation heute verfügbaren Tools sind der Modellprüfung Vielfalt; Lage, sehr schnell einen sehr großen, aber endlichen Suchraum zu durchqueren. Diese sind gut geeignet, um Probleme mit einer großen Beschreibung, aber keine rekursiven Datentypen. Zeno auf der anderen Seite ist so konzipiert, Eigenschaften über einen unendlichen Suchraum zu induktiv beweisen, sondern nur diejenigen mit einer kleinen und einfachen Spezifikation.

Es ist sicherlich möglich zu beweisen, einige Eigenschaften von Haskell Programme formal. Ich habe so meine FP-Prüfung zu tun hatte: zwei Ausdrücke gegeben, beweisen, dass sie die gleiche Funktion bezeichnen. Es ist nicht möglich, dies im Allgemeinen zu tun, da Haskell Turing-vollständig ist, also entweder jede mechanische Prover einen Beweis Assistenten (halbautomatisch mit Benutzerführung) oder einen Modellprüfer sein müßte.

Es hat Versuche in dieser Richtung gewesen, siehe z.B. P-Logik: Eigenschaft Überprüfung für Haskell Programme oder < a href = "http://mizar.org/trybulec65/14.pdf" rel = "nofollow"> die Richtigkeit funktionaler Programme Proving Mizar verwenden. Beide sind wissenschaftliche Arbeiten beschreiben Methoden mehr als Implementierungen.

Einige jüngsten Bemühungen von MSR Cambridge: http://research.microsoft.com /en-us/um/people/simonpj/papers/verify/hcc-popl.pdf

Das Tool AProVE ist (zumindest) in der Lage Beendigung von Haskell-Programmen zu beweisen, das ist Teil Richtigkeit beweisen. /: Weitere Informationen finden Sie im dieses Papier ( kürzere Version ).

Abgesehen davon, können Sie in abhängigen Typen interessiert sein . Hier wird das Typ-System erweitert und verwendet, um falsche Programme unmöglich zu machen.

Sie können das Tool verwenden hs-to-coq Haskell größtenteils automatisch in Coq zu konvertieren, und verwenden Sie dann die volle Leistung des Coq Assistent beweisen Code Haskell zu überprüfen. Sehen Sie sich die Papiere https://arxiv.org/abs/1803.06960 und https://arxiv.org/abs/1711.09286 für einige weitere Informationen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow