Wird der Code -Beweis für die Korrektheit jemals Mainstream gehen? [abgeschlossen

Question

Alle bis auf die trivialsten Programme sind mit Fehlern gefüllt, und alles, was es verspricht, sie zu entfernen, ist äußerst verlockend. Im Moment sind Korrektheitsergebnisse Code extrem esoterisch, hauptsächlich aufgrund des schwierigsten Lernens und der zusätzlichen Anstrengung, die es erfordert, ein Programm richtig zu beweisen. Denken Sie, dass der Code -Beweis jemals abheben wird?

Answer 1

Nicht wirklich in diesem Sinne, aber reine funktionelle Programmierung ist in dieser Domäne gut. Wenn Sie Haskell verwenden, ist es wahrscheinlich, dass Ihr Programm korrekt ist, wenn der Code kompiliert. Außer von IO ist ein gutes Typsystem eine gute Hilfe.

Auch das Programmieren zum Vertrag kann hilfreich sein. Sehen Microsoft -Code -Verträge

Answer 2

Alle außer den trivialsten Programmen

kann nicht vollständig als korrekt mit angemessener Anstrengung geprüft werden. Für jeden formalen Nachweis der Korrektheit benötigen Sie mindestens eine formelle Spezifikation, und diese Spezifikation muss vollständig und korrekt sein. Dies ist in der Regel nichts, was Sie für die meisten realen Programme leicht erstellen können. Versuchen Sie beispielsweise, eine solche Spezifikation für so etwas wie die Benutzeroberfläche dieser Diskussionsseite zu schreiben, und Sie wissen, was ich meine.

Hier fand ich einen schönen Artikel zum Thema:

http://www.encyclopedia.com/doc/1o11-programcorrectness.html

Answer 3

Das Problem mit formalen Beweisen ist, dass es das Problem nur einen Schritt zurückschiebt.

Zu sagen, dass ein Programm korrekt ist, ist gleichbedeutend mit der Aussage, dass ein Programm das tut, was es tun sollte. Wie definieren Sie, was das Programm tun soll? Sie geben es an. Und wie definieren Sie, was das Programm in Randfällen tun soll, die die Spezifikation nicht abdeckt? Nun, dann müssen Sie die Spezifikation detaillierter machen.

Nehmen wir also an, Ihre Spezifikation wird schließlich detailliert genug, um das richtige Verhalten aller Aspekte des gesamten Programms zu beschreiben. Jetzt brauchen Sie eine Möglichkeit, Ihre Beweiswerkzeuge zu verstehen. Sie müssen also die Spezifikation in eine formelle Sprache umsetzen, die das Proof -Tool verstehen kann ... Hey, warte eine Minute!

Answer 4

Die formelle Überprüfung hat einen langen Weg zurückgelegt, aber in der Regel sind die neuesten Forschungen in der Branche/weit verbreiteten Tools zurückgeblieben. Hier sind einige jüngste Bemühungen in diese Richtung:

Spec# http://research.microsoft.com/en-us/projects/specsharp/Dies ist eine Erweiterung von C#, die Codeverträge (Vor-/Postbedingungen und Invarianten) unterstützt und diese Verträge verwenden kann, um verschiedene Arten der statischen Analyse durchzuführen.

Ähnliche Projekte wie dies bestehen für andere Sprachen wie JML für Java und Eiffel hat dies so ziemlich eingebaut.

Noch weiter gehen, Projekte mögen wie zuschlagen und sprengen Kann verwendet werden, um bestimmte Verhaltenseigenschaften mit minimaler Programmiererannotation/-intervention zu überprüfen, kann jedoch nicht mit der vollen Allgemeinheit moderner Sprachen umgehen (Dinge wie Ganzzahlüberlauf/Zeigerarithmetik werden nicht modelliert).

Ich glaube, dass wir viel mehr dieser Techniken sehen werden, die in Zukunft in der Praxis verwendet werden. Die Hauptbarriere ist, dass Programminvarianten ohne manuelle Anmerkungen schwer zu schließen sind, und Programmierer sind normalerweise nicht bereit, diese Anmerkungen bereitzustellen, da dies zu mühsam/zeitaufwändig ist.

Answer 5

Es entsteht nicht eine Methode, um den Code ohne umfangreiche Entwickler automatisch zu beweisen.

Answer 6

Etwas Formale Methoden Werkzeuge (wie z. Frama-C Für kritische eingebettete C-Software kann) als (Sort-of) angesehen werden, oder zumindest einen (Korrektheit) Nachweis einer bestimmten Software bereitzustellen oder zumindest zu überprüfen. (Frama-C überprüfen, dass ein Programm seiner formalisierten Spezifikation in gewissem Sinne gehorcht und respektiert explizit kommentierte Invarianten im Programm).

In einigen Sektoren sind solche formalen Methoden möglich, z. B. als Do-178c für kritische Software in zivilen Flugzeugen. In einigen Fällen sind solche Ansätze möglich und hilfreich.

Natürlich ist es sehr kostspielig, weniger fehlerhafte Software zu entwickeln. Der formale Methodenansatz ist jedoch für eine Art Software sinnvoll. Wenn Sie pessimistisch sind, denken Sie vielleicht, dass der Fehler vom Code in seine formale Spezifikation verschoben wird (die möglicherweise einige "Fehler" hat, da das Formalisieren des beabsichtigten Verhaltens einer Software schwierig und fehleranfällig ist).

Answer 7

Ich bin über diese Frage gestoßen und denke, dass dieser Link interessant sein könnte:

Industrielle Anwendungen von Astrée

Das Fehlen von RTE in einem System von Airbus mit mehr als 130.000 Code -Zeilen im Jahr 2003 scheint nicht schlecht zu sein, und ich frage mich, dass es irgendjemand sagen wird, dass dies keine reale Welt ist.

Answer 8

Nein. Das gemeinsame Sprichwort dafür lautet: "In Theorie sind Theorie und Praxis gleich. In der Praxis, nicht."

Ein sehr einfaches Beispiel: Tippfehler.

Tatsächlich findet das Ausführen des Codes durch Unit -Tests fast sofort, und ein zusammenhängender Satz von Tests negiert die Notwendigkeit formeller Beweise. Alle Anwendungsfälle - gute, schlechte, Fehler- und Kantenfälle - sollten in den Unit -Tests aufgezählt werden.

Insbesondere wenn sich die Anforderungen ändern oder der Algorithmus aktualisiert wird, um einen Fehler zu beheben, ist der formelle Beweis eher veraltet, wie es häufig Code -Kommentare erhalten.

Answer 9

Ich denke, dass die Grenzen für Korrektheitserkennungen aufgrund der Problem stoppen Könnte das größte Hindernis für Korrektheitsergebnisse sein, die zum Mainstream werden.

Answer 10

Es wird bereits von allen benutzt. Jedes Mal, wenn Sie die Typ -Überprüfung Ihrer Programmiersprache verwenden, führen Sie im Grunde genommen einen mathematischen Nachweis für die Richtigkeit Ihres Programms durch. Dies funktioniert bereits sehr gut. Sie müssen nur korrekte Typen für jede von Ihnen verwendete Funktion und Datenstruktur auswählen. Je genauer der Typ ist, desto besser werden Sie überprüft. Die vorhandenen Typen, die in Programmiersprachen verfügbar sind, haben bereits leistungsstarke Tools, um fast jedes mögliche Verhalten zu beschreiben. Dies funktioniert in jeder verfügbaren Sprache. C ++ und die statischen Sprachen führen nur die Überprüfungen in der Kompilierungszeit durch, während dynamischere Sprachen wie Python dies beim Ausführen des Programms machen. Die Überprüfung existiert in all diesen Sprachen noch. (C ++ unterstützt beispielsweise bereits die Überprüfung der Nebenwirkungen auf die gleiche Weise wie Haskell, aber Sie müssen sich nur dafür entscheiden, sie zu verwenden.)