Können Haskell-Funktionen mit Korrektheitseigenschaften nachgewiesen / modellgeprüft / verifiziert werden?

72

Weiter zu den Ideen in: Gibt es nachweisbare reale Sprachen?

Ich weiß nichts über dich, aber ich habe es satt, Code zu schreiben, den ich nicht garantieren kann.

Nachdem ich die obige Frage gestellt und eine phänomenale Antwort erhalten habe (Danke an alle!), Habe ich beschlossen, meine Suche nach einer nachweisbaren, pragmatischen Herangehensweise an Haskell einzugrenzen . Ich habe mich für Haskell entschieden, weil es tatsächlich nützlich ist (es sind viele Web- Frameworks dafür geschrieben, dies scheint ein guter Maßstab zu sein) UND ich denke, es ist streng genug, funktional , dass es nachweisbar sein oder zumindest das Testen von Invarianten ermöglichen könnte.

Folgendes möchte ich (und konnte es nicht finden)

Ich möchte ein Framework, das eine Haskell-Funktion betrachten kann, hinzufügen, geschrieben in psudocode:

add(a, b):
    return a + b

- und prüfen Sie, ob bestimmte Invarienten über jeden Ausführungsstatus verfügen. Ich würde es vorziehen, einen formellen Beweis zu erbringen, aber ich würde mich mit so etwas wie einem Modellprüfer zufrieden geben.
In diesem Beispiel wäre der Invarient, dass bei gegebenen Werten a und b der Rückgabewert immer die Summe a + b ist .

Dies ist ein einfaches Beispiel, aber ich denke nicht, dass es unmöglich ist, dass ein solches Framework existiert. Es würde sicherlich eine Obergrenze für die Komplexität einer Funktion geben, die getestet werden könnte (10 Zeichenfolgeneingaben für eine Funktion würden sicherlich lange dauern!), Aber dies würde eine sorgfältigere Gestaltung von Funktionen fördern und unterscheidet sich nicht von der Verwendung anderer formaler Funktionen Methoden. Stellen Sie sich vor, Sie verwenden Z oder B, wenn Sie Variablen / Mengen definieren, stellen Sie verdammt sicher, dass Sie den Variablen die kleinstmöglichen Bereiche geben. Wenn Ihr INT niemals über 100 liegen wird, stellen Sie sicher, dass Sie es als solches initialisieren! Techniken wie diese und eine ordnungsgemäße Problemzerlegung sollten - glaube ich - eine zufriedenstellende Überprüfung einer rein funktionalen Sprache wie Haskell ermöglichen.

Ich bin noch nicht sehr erfahren mit formalen Methoden oder Haskell. Lassen Sie mich wissen, ob meine Idee richtig ist, oder denken Sie vielleicht, dass Haskell nicht geeignet ist? Wenn Sie eine andere Sprache vorschlagen, stellen Sie bitte sicher, dass diese den "has-a-web-framework" -Test besteht, und lesen Sie die ursprüngliche Frage :-)

0atman
quelle
8
@Steven: Wirklich? Warum sollte das so sein? Wenn nachgewiesen wurde, dass ein Code eine Eigenschaft hat, hat er immer diese Eigenschaft, unabhängig davon, mit welchem ​​anderen Code er interagiert, und Sie können sich bei anderen Beweisen auf diese Eigenschaft verlassen. Proofs sind auf eine Weise wiederverwendbar und kompositorisch, wie dies bei Tests nicht der Fall ist. Durch das Codieren von Proofs im Typsystem besteht keine Chance, dass sie nicht mehr mit dem Code selbst synchronisiert werden.
CA McCann
3
@Steven: Ja, ich stimme Camccann zu, ich muss nicht jede Kombination von Ziegeln in einem Haus testen. Schöne Ziege!
0atman
4
@Steven: Sie müssen nicht, das ist der springende Punkt! Wenn eine Funktion für alle möglichen Eingaben nachweislich korrekt ist, besteht die einzige Verpflichtung, sie zu verwenden, darin, Argumente des entsprechenden Typs bereitzustellen. Sich nicht um Integrationspunkte kümmern zu müssen, ist genau der Grund, warum typcodierte Proofs kompositorisch sind. Zu wissen, dass ein Teil des Codes garantiert niemals ausfällt oder Laufzeitfehler erzeugt, ist der Grund, warum statische Typisierung hilfreich ist.
CA McCann
14
@Steven: Persönlich würde ich lieber etwas länger damit verbringen, Code zu schreiben, der nicht kaputt gehen kann , anstatt unzuverlässigen Code zu schreiben und dann Zeit damit zu verschwenden, triviale Tests zu schreiben und mir Sorgen um alles zu machen, was schief gehen könnte ... aber für jeden das Richtige annehmen!
CA McCann
3
Vielen Dank für Ihre Ansichten Jungs, nehmen Sie es in ein Forum :-)
0atman

Antworten:

61

Nun, ein paar Dinge, mit denen Sie beginnen sollten, da Sie die Haskell-Route nehmen:

  • Kennen Sie die Curry-Howard-Korrespondenz ? Es gibt Systeme, die auf dieser Grundlage für maschinengeprüfte Proofs verwendet werden und in vielerlei Hinsicht einfach funktionale Programmiersprachen mit sehr leistungsfähigen Typsystemen sind.

  • Kennen Sie die Bereiche der abstrakten Mathematik, die nützliche Konzepte für die Analyse von Haskell-Code bieten? Verschiedene Arten von Algebra und einige Teile der Kategorietheorie kommen häufig vor.

  • Denken Sie daran, dass Haskell, wie alle Turing-vollständigen Sprachen, immer die Möglichkeit der Nichtbeendigung hat. Im Allgemeinen ist es viel schwieriger zu beweisen, dass etwas immer wahr sein wird, als zu beweisen, dass entweder etwas wahr ist oder von einem nicht endenden Wert abhängt.

Wenn Sie ernsthaft nach Beweisen suchen und nicht nur testen , sollten Sie diese Dinge beachten. Die Grundregel lautet: Ungültige Zustände verursachen Compilerfehler. Verhindern Sie, dass ungültige Daten überhaupt verschlüsselt werden, und lassen Sie dann die Typprüfung den mühsamen Teil für Sie erledigen.

Wenn Sie noch weiter gehen möchten und der Speicher mir dient, verfügt der Proof-Assistent Coq über eine Funktion zum Extrahieren nach Haskell, mit der Sie beliebige Eigenschaften kritischer Funktionen nachweisen können. Verwandeln Sie die Proofs dann in Haskell-Code.

Oleg Kiselyov ist der Großmeister , wenn es darum geht , ausgefallene Systemaufgaben direkt in Haskell zu erledigen . Auf seiner Website finden Sie Beispiele für nette Tricks wie polymorphe Typen mit höherem Rang, um statische Beweise für die Überprüfung von Array-Grenzen zu codieren .

Für leichtere Dinge können Sie beispielsweise ein Zertifikat auf Typebene verwenden , um ein Datenelement als auf Richtigkeit geprüft zu markieren. Sie sind immer noch auf sich allein gestellt, um die Richtigkeit selbst zu überprüfen, aber anderer Code kann sich zumindest darauf verlassen, dass einige Daten tatsächlich überprüft wurden.

Ein weiterer Schritt, den Sie unternehmen können, indem Sie auf einfachen Überprüfungen und ausgefallenen Systemtricks aufbauen, besteht darin, die Tatsache zu nutzen, dass Haskell als Hostsprache zum Einbetten domänenspezifischer Sprachen gut funktioniert . Erstellen Sie zunächst eine sorgfältig eingeschränkte Subsprache (im Idealfall eine, die nicht vollständig ist), über die Sie nützliche Eigenschaften leichter nachweisen können, und verwenden Sie dann Programme in diesem DSL, um wichtige Kernfunktionen in Ihrem Gesamtprogramm bereitzustellen. Sie könnten beispielsweise beweisen, dass eine Funktion mit zwei Argumenten assoziativ ist, um eine parallelisierte Reduzierung einer Sammlung von Elementen mit dieser Funktion zu rechtfertigen (da die Reihenfolge der Funktionsanwendung keine Rolle spielt, sondern nur die Reihenfolge der Argumente).


Oh, eine letzte Sache. Einige Ratschläge zur Vermeidung der Fallstricke, die Haskell enthält und die Code sabotieren können, der ansonsten konstruktionssicher wäre: Ihre geschworenen Feinde hier sind allgemeine Rekursion , IOMonade und Teilfunktionen :

  • Letzteres ist relativ leicht zu vermeiden: Schreiben Sie sie nicht und verwenden Sie sie nicht. Stellen Sie sicher, dass jeder Satz von Mustern mit jedem möglichen Fall übereinstimmt, und verwenden Sie niemals erroroder undefined. Der einzige schwierige Teil ist das Vermeiden von Standardbibliotheksfunktionen, die Fehler verursachen können. Einige sind offensichtlich unsicher, wie fromJust :: Maybe a -> aoder, head :: [a] -> aaber andere können subtiler sein. Wenn Sie feststellen, dass Sie eine Funktion schreiben, die mit einigen Eingabewerten wirklich, wirklich nichts anfangen kann, lassen Sie zu, dass ungültige Zustände vom Eingabetyp codiert werden, und müssen dies zuerst beheben.

  • Die zweite ist auf oberflächlicher Ebene leicht zu vermeiden, indem Dinge durch verschiedene reine Funktionen gestreut werden, die dann aus einem IOAusdruck verwendet werden. Besser ist es, das gesamte Programm so weit wie möglich in reinen Code zu verschieben, damit es unabhängig mit allem außer der eigentlichen E / A ausgewertet werden kann. Dies wird meistens nur dann schwierig, wenn Sie eine Rekursion benötigen, die durch externe Eingaben gesteuert wird, wodurch ich zum letzten Punkt komme:

  • Worte an die Weisen: Begründete Rekursion und produktive Corecursion. Stellen Sie immer sicher, dass rekursive Funktionen entweder von einem Startpunkt zu einem bekannten Basisfall wechseln oder bei Bedarf eine Reihe von Elementen generieren. Im reinen Code besteht der einfachste Weg darin, entweder eine endliche Datenstruktur rekursiv zu reduzieren (z. B. anstatt einer Funktion, die sich direkt aufruft, während ein Zähler auf ein Maximum erhöht wird, eine Liste mit dem Bereich der Zählerwerte zu erstellen und zu falten ) oder rekursiv eine verzögerte Datenstruktur erzeugen (z. B. eine Liste progressiver Annäherungen an einen bestimmten Wert), während die beiden niemals sorgfältig direkt gemischt werden (z. B. nicht nur "das erste Element im Stream finden, das eine bestimmte Bedingung erfüllt"; dies ist möglicherweise nicht der Fall) Nehmen Sie stattdessen Werte aus dem Stream bis zu einer maximalen Tiefe und durchsuchen Sie die endliche Liste, wobei Sie den nicht gefundenen Fall entsprechend behandeln.

  • Wenn Sie die letzten beiden Elemente für die Teile, die Sie wirklich benötigen, IOmit allgemeiner Rekursion kombinieren, versuchen Sie, das Programm als inkrementelle Komponenten zu erstellen, und verdichten Sie dann alle umständlichen Bits zu einer einzigen "Treiber" -Funktion. Zum Beispiel könnten Sie eine GUI-Ereignisschleife mit einer reinen Funktion wie mainLoop :: UIState -> Events -> UIState, einem Exit-Test wie quitMessage :: Events -> Bool, einer Funktion zum Abrufen ausstehender Ereignisse getEvents :: IO Eventsund einer Aktualisierungsfunktion schreiben und updateUI :: UIState -> IO ()dann das Ding tatsächlich mit einer verallgemeinerten Funktion wie ausführen runLoopIO :: (b -> a -> b) -> b -> IO a -> (b -> IO ()) -> IO (). Auf diese Weise bleiben die komplizierten Teile wirklich rein, sodass Sie das gesamte Programm mit einem Ereignisskript ausführen und den resultierenden UI-Status überprüfen können, während Sie die umständlichen rekursiven E / A-Teile in einer einzigen abstrakten Funktion isolieren, die leicht zu verstehen ist und häufig unweigerlich korrekt ist durch Parametrizität .

CA McCann
quelle
Danke, denkst du, es ist möglich, Haskell direkt zu überprüfen?
0atman
1
@Oatman: Im Allgemeinen so viel wie möglich, um jede Programmiersprache zu überprüfen. Viele der Techniken, die verwendet werden können, um den zu untersuchenden Zustandsraum zu reduzieren oder zu vereinfachen, sind in Haskell aufgrund der Reinheit und der Typensicherheit einfach oder automatisch. Das Denken in Zustandsübergängen kann hier jedoch kontraproduktiv sein.
CA McCann
3
@Oatman: Wirklich, der Hauptvorteil von Haskell für diesen Zweck ist, wie viel Sie tun können, ohne auch nur externe Tools zu benötigen . Vermeiden Sie einfach IOallgemeine Rekursionen und Teilfunktionen, wo immer dies möglich ist (was für die meisten Programme "fast überall mit ein wenig Aufwand" ist).
CA McCann
@ Camccann: Ich mag die domänenspezifische Idee. Ein Dialekt von Haskell, der nachweisbar sein soll! Muss ich das ausprobieren oder wurde nach Ihrem Wissen bereits an etwas Ähnlichem gearbeitet?
0atman
1
Coq hat in der Tat eine "Auszug nach Haskell" -Funktion
Tom Crockett
21

Wahrscheinlich ist Haskabelle das nächste, was Sie verlangen , ein Tool, das mit dem Proof-Assistenten Isabelle geliefert wird , mit dem Haskell-Dateien in Isabelle-Theorien übersetzt werden können und mit denen Sie Dinge über sie beweisen können. Soweit ich weiß, wurde dieses Tool im Rahmen des HOL-ML-Haskell-Projekts entwickelt und die Dokumentationsseite enthält einige Informationen zur dahinter stehenden Theorie.

Ich bin mit diesem Projekt nicht besonders vertraut und weiß nicht viel darüber, was damit gemacht wurde. Aber ich weiß, dass Brian Huffman mit diesen Dingen herumgespielt hat, seine Papiere und Vorträge durchgesehen hat, sie sollten relevante Dinge enthalten.

svenningsson
quelle
Danke, ich werde es überprüfen, obwohl ich wirklich nach einer reinsprachigen Methode zur Modellprüfung suche. Die Übersetzung von einer formaleren Sprache nach Haskell ist für den allgemeinen Gebrauch nicht optimal.
0atman
6
Nein, es ist umgekehrt. Haskell wird nach Isabelle übersetzt. Es ist vielleicht immer noch nicht optimal, aber es ist wahrscheinlich besser für Ihre Zwecke als der Coq-Ansatz zur Erzeugung von Haskell.
Svenningsson
Oh oh oooh! Entschuldigung, ich habe Ihre Antwort falsch gelesen. Hmm, das ist ungewöhnlich und nützlicher!
0atman
19

Ich bin mir nicht sicher, ob das, wonach Sie fragen, tatsächlich das ist, was Sie glücklich machen wird. :-)

Die Modellprüfung einer Allzwecksprache ist nahezu unmöglich, da Modelle domänenspezifisch sein müssen, um praktisch zu sein. Aufgrund des Unvollständigkeitssatzes von Gödel gibt es einfach keine Methode, um automatisch Beweise in einer ausreichend aussagekräftigen Logik zu finden.

Dies bedeutet, dass Sie selbst Beweise schreiben müssen , was die Frage aufwirft, ob der Aufwand die aufgewendete Zeit wert ist. Natürlich schafft der Aufwand etwas sehr Wertvolles, nämlich die Gewissheit, dass Ihr Programm korrekt ist. Die Frage ist nicht, ob dies ein Muss ist, sondern ob der Zeitaufwand zu hoch ist. Die Sache mit Beweisen ist, dass Sie zwar ein "intuitives" Verständnis dafür haben, dass Ihr Programm korrekt ist , es jedoch oft sehr schwierig ist, dieses Verständnis als Beweis zu formalisieren . Das Problem beim intuitiven Verstehen ist, dass es sehr anfällig für versehentliche Fehler (Tippfehler und andere dumme Fehler) ist. Dies ist das grundlegende Dilemma beim Schreiben korrekter Programme.

Bei der Erforschung der Programmkorrektheit geht es darum, die Formalisierung von Proofs und die automatische Überprüfung ihrer Korrektheit zu vereinfachen. Die Programmierung ist ein wesentlicher Bestandteil der "Leichtigkeit der Formalisierung"; Es ist sehr wichtig, Programme in einem Stil zu schreiben, über den man leicht nachdenken kann. Derzeit haben wir folgendes Spektrum:

  • Imperative Sprache wie C, C ++, Fortran, Python: Es ist sehr schwierig, hier etwas zu formalisieren. Unit-Tests und allgemeine Überlegungen sind der einzige Weg, um zumindest eine gewisse Sicherheit zu erhalten. Bei der statischen Eingabe werden nur geringfügige Fehler abgefangen (was viel besser ist, als sie nicht abzufangen!).

  • Rein funktionierende Sprachen wie Haskell, ML: Expressive Type System hilft dabei, nicht triviale Fehler und Irrtümer zu erkennen. Der Nachweis der Korrektheit von Hand ist praktisch für Schnipsel mit bis zu 200 Zeilen, würde ich sagen. (Ich habe zum Beispiel einen Proof für mein Betriebspaket erstellt .) Quickcheck- Tests sind ein billiger Ersatz für formalisierte Proofs.

  • Abhängig getippte Sprachen und Proof-Assistenten wie Agda, Epigram, Coq: Dank der automatisierten Hilfe bei der Formalisierung und Ermittlung von Proofs ist es möglich, ganze Programme korrekt zu beweisen. Die Belastung ist jedoch immer noch hoch.

Meiner Meinung nach ist der derzeitige Sweet Spot für das Schreiben korrekter Programme die rein funktionale Programmierung . Wenn das Leben von der Richtigkeit Ihres Programms abhängt, sollten Sie eine Stufe höher gehen und einen Proof-Assistenten verwenden.

Heinrich Apfelmus
quelle
Um ein möglicherweise falscher Pedant zu sein, meinen Sie wahrscheinlich "keine effiziente Methode", da man nur ausführlich längere Proofs aufzählen und testen könnte, wahrscheinlich abhängig von einer zunehmenden Menge an "Kraftstoff", um Fallstricke zu vermeiden :-)
sclv
6
@sclv: Und hier ist eine Methode zur Lösung des Halteproblems: Führen Sie das Programm einfach auf unbestimmte Zeit aus und warten Sie, bis es jemals angehalten wird. Woher wissen Sie, wann Sie aufhören müssen, Beweise aufzuzählen? Kurz gesagt, Sie können auf diese Weise nach Beweisen suchen , aber Sie können nicht zwischen "kein Beweis existiert" und "noch kein Beweis gefunden" unterscheiden.
CA McCann
Ich habe eine geeignete Definition von "Methode" gewählt, die bereits die Effizienzbedenken berücksichtigt. ;-)
Heinrich Apfelmus
1
Außerdem überprüft die SmallCheck Bibliothek von Haskell eine Eigenschaft ausführlich auf einen Wertebereich für eine Enum. Sehr praktisch für "einmalige" (nicht für jeden Build neu berechnete) Beweise für einige EnumEigenschaften.
recursion.ninja
5

Klingt so, als ob Sie ESC / Haskell möchten: http://research.microsoft.com/en-us/um/people/simonpj/papers/verify/index.htm

Oh, und Agda hat jetzt ein Webframework (zumindest Proof of Concept): http://www.reddit.com/r/haskell/comments/d8dck/lemmachine_a_web_framework_in_agda/

sclv
quelle
ESC / Haskell sieht gut aus, obwohl die Implementierung theoretisch und etwas begrenzt ist, basierend auf meinem Durchblättern des Papiers. Eine großartige Ressource - danke!
0atman
Irgendeine Idee, wann ESC / Haskell in ghc verfügbar sein wird?
dan_waterworth
@dan_waterworth - Ich kenne leider keine Pläne in diese Richtung.
sclv
Schade, ich könnte es wirklich für ein Projekt tun, an dem ich arbeite. Danke für die Antwort.
dan_waterworth
4

Haben Sie sich Quickcheck angesehen? Es kann einige der Dinge bieten, die Sie brauchen.

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

Jonno_FTW
quelle
Ja, ich denke, es sieht fantastisch aus und wäre definitiv die Grundlage für weitere Forschung für mich.
0atman
2
smallcheck auch - smallcheck ist wie Quickcheck, konzentriert sich jedoch darauf, "kleine" Fälle ausführlich auf einen konfigurierbaren Begriff von "klein" zu testen.
Mokus
1
Ich erinnere mich, dass ein Paket, das automatisch Quickcheck-Tests basierend auf algebraischen Eigenschaften erzeugt, wie die Angabe eines Verteilungsgesetzes für zwei Funktionen, zu Checks führt, die f x (g y z)immer gleich sind g (f x y) (f x z).
CA McCann
Schauen Sie sich auch Lazy Smallcheck an, der Haskells faule Bewertung nutzt.
Robin Green
3

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

Habit ist ein vereinfachter Dialekt von Haskell, mit dem Programmeigenschaften nachgewiesen werden können.

Hume ist eine Sprache mit 5 Stufen, die jeweils eingeschränkter und daher leichter zu überprüfen sind:

Voller Hume
  Volle Rekursion
PR - Hume
  Primitive rekursive Funktionen
Template-Hume
  Vordefinierte Funktionen höherer Ordnung
  Induktive Datenstrukturen
  Induktive nicht rekursive Funktionen erster Ordnung
FSM-Hume
  Nicht rekursive Datenstrukturen
HW - Hume
  Keine Funktionen
  Nicht rekursive Datenstrukturen

Natürlich ist die derzeit beliebteste Methode zum Nachweis von Programmeigenschaften das Testen von Einheiten, das starke Theoreme liefert, aber diese Theoreme sind zu spezifisch. "Typen, die als schädlich angesehen werden", Pierce, Folie 66

ja.
quelle
1
Arithmetik kann ein Problem sein. Theoretisch können Sie Garantien geben, wenn Sie die Größe aller Ergebnisse kennen, einschließlich der Zwischenergebnisse. Praktisch eignen sich viele Berechnungen nicht dafür. Ohne Ganzzahlen beliebiger Größe ist es schwierig, die Richtigkeit der Arithmetik zu beweisen. Berücksichtigen Sie für Gleitkommazahlen docs.sun.com/source/806-3568/ncg_goldberg.html (Was jeder Informatiker über Gleitkommazahlen wissen sollte), und dies, nachdem viele sehr kluge Leute versucht haben, Gleitkommazahlen nachvollziehbar zu machen .
David Thornley
3

Schauen Sie sich Zeno an . Zitieren der Wiki-Seite:

Zeno ist ein automatisiertes Proofsystem für die Eigenschaften des Haskell-Programms. entwickelt am Imperial College London von William Sonnex, Sophia Drossopoulou und Susan Eisenbach. Ziel ist es, das allgemeine Problem der Gleichheit zwischen zwei Haskell-Termen für jeden Eingabewert zu lösen.

Viele der heute verfügbaren Tools zur Programmüberprüfung sind von der Modellprüfungsvariante. in der Lage, einen sehr großen, aber endlichen Suchraum sehr schnell zu durchqueren. Diese eignen sich gut für Probleme mit einer großen Beschreibung, jedoch ohne rekursive Datentypen. Zeno hingegen wurde entwickelt, um Eigenschaften über einen unendlichen Suchraum induktiv zu beweisen, aber nur solche mit einer kleinen und einfachen Spezifikation.

Petr
quelle
2

Es ist sicherlich möglich, einige Eigenschaften von Haskell-Programmen formal nachzuweisen . Ich musste dies bei meiner FP-Prüfung tun: Beweisen Sie mit zwei Ausdrücken, dass sie dieselbe Funktion bezeichnen. Dies ist im Allgemeinen nicht möglich, da Haskell Turing-vollständig ist. Daher müsste jeder mechanische Prüfer entweder ein Proof-Assistent (halbautomatisch mit Benutzerführung) oder ein Modellprüfer sein.

Es wurden Versuche in diese Richtung unternommen, siehe z. B. P-Logik: Eigenschaftsüberprüfung für Haskell-Programme oder Nachweis der Richtigkeit von Funktionsprogrammen mit Mizar . Beide sind wissenschaftliche Arbeiten, die mehr Methoden als Implementierungen beschreiben.

Fred Foo
quelle
Ich möchte hinzufügen, dass ich mich bei der Prüfung zumindest wie ein mechanischer Theorembeweiser fühlte ;)
Fred Foo
Oh, das zweite Ergebnis auf Google für "Mizar Haskell" ist DIESE SO FRAGE !! 1 :-(
0atman
Dies war ein kurzer Durchlauf durch Google und CiteseerX. Dieses Mizar-Papier wurde in einer akademischen Zeitschrift veröffentlicht, wenn auch nicht in einer hochkarätigen.
Fred Foo
@Oatman: Das bedeutet nicht viel. Stack Overflow hat verrückten Google-Saft. Fragen zu Nischenthemen können Primärquellen leicht übertreffen.
CA McCann
Ganz richtig, aber die Informationen zu Mizar sind sehr dürftig, nicht das bereits existierende Paket, auf das ich gehofft hatte. Ich werde es meiner Leseliste hinzufügen!
0atman
1

Das Tool AProVE kann (zumindest) die Beendigung von Haskell-Programmen nachweisen, was Teil des Nachweises der Richtigkeit ist. Weitere Informationen finden Sie in diesem Dokument ( kürzere Version ).

Abgesehen davon könnten Sie an abhängigen Typen interessiert sein . Hier wird das Typsystem erweitert und verwendet, um falsche Programme unmöglich zu machen.

C-Otto
quelle