Wenn Sie formale Methoden für Software gelernt haben, wie nützlich haben Sie sie gefunden?

17

Wenn Sie in der Anwendung formaler Methoden (FM) für die Programmierung geschult wurden :

  • Wie nützlich hast du es gefunden?
  • Was umfasste Ihr FM-Training (z. B. einen Kurs, ein Buch)?
  • Welche FM-Tools verwenden Sie?
  • Welche Geschwindigkeits- / Qualitätsvorteile hat es Ihnen gegenüber der Nichtnutzung von FM gebracht?
  • Welche Art von Software erstellen Sie mit FM?
  • Und wenn Sie FM jetzt nicht direkt nutzen, hat es sich zumindest gelohnt, es zu lernen?

Ich bin neugierig, so viele Erfahrungen / Meinungen zu FM zu hören, wie in dieser Community zu finden sind. Ich fange an darüber zu lesen und möchte mehr wissen.

Hintergrund

Programmierung und Softwareentwicklung / -engineering gehören zu den neuesten menschlichen Fähigkeiten / Berufen auf der Erde. Daher überrascht es nicht, dass das Gebiet noch nicht ausgereift ist. Dies zeigt sich in der Hauptausgabe unseres Gebiets als Code, der in der Regel spät und fehleranfällig ist. Die Unreife der Branche zeigt sich auch in dem großen Produktivitätsspielraum (mindestens 10: 1) zwischen durchschnittlichen und Spitzencodierern. Solche düsteren Tatsachen werden in der Literatur gut behandelt und durch Bücher wie Steve McConnells Code Complete eingeführt .

Die Verwendung formaler Methoden (FM) wurde von großen Software- / CS-Experten (z. B. dem verstorbenen E. Dijkstra ) vorgeschlagen, um eine der Hauptursachen für Fehler zu ermitteln: das Fehlen mathematischer Strenge bei der Programmierung. Dijkstra zum Beispiel sprach sich dafür aus, dass die Studenten gemeinsam ein Programm und dessen Beweise entwickeln .

FM scheint in Europa in CS-Lehrplänen viel häufiger zu sein als in den USA. Aber in den letzten Jahren haben neue "leichte" FM-Ansätze und Werkzeuge wie Alloy einige Aufmerksamkeit erregt. Trotzdem ist FM in der Industrie weit davon entfernt, gebräuchlich zu sein, und ich hoffe hier auf ein Feedback, warum.

Aktualisieren

Bisher (14.10.2010) hat noch niemand von den 6 Antworten klar für die Verwendung von FM in der "realen Welt" argumentiert. Ich bin wirklich neugierig, ob jemand das kann und will. oder vielleicht zeigt FM wirklich die Kluft zwischen Wissenschaft (FM ist die Zukunft!) und Industrie (FM ist meistens nutzlos).

Limist
quelle
In Bezug auf Ihr Update hat sich möglicherweise niemand für die Verwendung von FM in der "realen" Arbeit ausgesprochen, da es nur sehr wenige Anwendungsfälle für diese in der realen Arbeit gibt
Richard,

Antworten:

8

Absolut nutzlos für nichts Nicht-Triviales.

Ich hatte einen Kurs mit dem treffenden Titel "Formale Methoden", der sich auf Legierung konzentrierte - ich kann unmöglich sehen, dass ich das irgendwo verwende. Hatte eine andere Klasse, die sich auf die gleichzeitige Modellierung mit LTSA konzentrierte - ebenfalls nutzlos.

Das Problem ist, dass die meisten Fehler und Probleme in der Software (zumindest nach meiner Erfahrung) auf Komplexität zurückzuführen sind, die unterhalb der Abstraktionsebene dieser Tools auftritt.

Fischtoaster
quelle
Danke für das Teilen; Würden Sie sagen, dass das Training in FM zumindest für Ihre spätere Arbeit hilfreich war, z. B. Ihnen dabei geholfen hat, klarer zu denken? Oder nicht?
Limist
@limist: Das glaube ich wirklich nicht. Ich meine, ich mochte Alloy ein bisschen, aber ich denke nicht, dass es nützlich war, nur zu erweitern, wie ich denke.
Fishtoaster
2
Dies ist genau die Antwort, die ich gegeben hätte. Der vollkommen überflüssigste Kurs, den ich an der Universität besucht habe, und nicht etwas, auf das ich jemals zurückgesehen habe und das ich froh war, dass ich es gelernt habe. Ich denke, die Wurzel des Problems liegt darin, dass die formale Spezifikation komplexer sein muss als der Code, um sie korrekt zu modellieren. Für jeden entfernt komplexen Code ist es also eine äußerst mühsame Aufgabe, ein formales Modell davon zu erstellen, bis zu dem Punkt, den ich kann Ich kann mir nicht vorstellen, dass jemand außerhalb des Hardware-Designs oder einer ähnlich unwiderruflichen Arbeit dies tun möchte oder kann.
Glenatron
1
Das ist enttäuschend. Ich stellte mir vor, dass es nützlich sein könnte, um zu testen, ob Sie ein einigermaßen vollständiges Modell hatten. Während die eigentlichen Bugs meistens unterhalb des Modells liegen (die Mutexe versauen oder was auch immer), nahm ich an, dass es nützlich wäre, Alloy zu verwenden, um Fehler im Modell selbst zu finden. (Intuitiv scheint es weniger nützlich zu sein, einen Proof-Assistenten zu verwenden. Ich würde erwarten, dass Gegenbeispiele nützlicher sind, und das scheint eher im Bereich von Dingen wie Alloy zu liegen (obwohl ich es im Idealfall gut finde, wenn es möglich wäre um beide im selben System
Bruce Stephens
7

Ich habe einen Hintergrund in CSP (Communicating Sequential Processes). Nicht um mein eigenes Horn zu betäuben, sondern um meine Masterarbeit über zeitgesteuertes CSP zu schreiben, insbesondere das "Kompilieren" von Spezifikationen, die in formalen Methoden geschrieben wurden, in ausführbares C ++. Ich kann sagen, dass ich Erfahrung mit formalen Methoden habe. Nachdem ich mein Studium abgeschlossen und einen Job in der Branche bekommen hatte, habe ich überhaupt keine formalen Methoden angewendet. Formale Methoden sind noch zu theoretisch, um in der Industrie angewendet zu werden. Formale Methoden haben im Bereich eingebetteter Systeme eine praktische Anwendung gefunden. Zum Beispiel verwendet die NASA formale Methoden in ihren Projekten. Ich würde spekulieren, dass formale Methoden in der Branche noch lange nicht weit verbreitet sind. Es ist einfach nicht sinnvoll, Softwarespezifikationen in formalen Methoden zu schreiben und sie dann "menschlich" nach Ihrem Wahlrahmen zu interpretieren. Klares Englisch und Diagramme funktionieren besser, während Unit- und Integrationstests die Korrektheit des Codes ziemlich gut "überprüfen" konnten. Meiner Ansicht nachformale Methoden werden noch einige Zeit in der akademischen Welt verbleiben .

ysolik
quelle
Vielen Dank für Ihre Mitteilung. Ich werde Sie um ein Follow-up bitten, das häufig zu diesem Thema wiederholt wird. F: Würden Sie sagen, dass das Training in FM für Ihre spätere Arbeit zumindest hilfreich war, z. Oder nicht?
Limist
Herzlichen Glückwunsch an Ihre Meister!
Chris
@limist: Ich würde sagen, dass es eine sehr gute theoretische Erfahrung war, aber ich fand in der Branche sehr wenig praktische Anwendung.
Ysolik
4

Zustandsdiagramme und Petrinetze sind nützlich für die Modellierung und Analyse von Protokollen und Echtzeitsystemen. Zuerst helfen sie beim Entwerfen einer Lösung. Zweitens helfen sie dabei, Testfälle für aufregende Software in ganz bestimmten Situationen zu finden.

mouviciel
quelle
4

Ich habe ein paar Bücher über formale Methoden gelesen und einige angewandt. Meine unmittelbare Reaktion war: "Gee, diese Bücher sagen mir, wie man ein guter Programmierer ist, solange ich ein perfekter Mathematiker bin." Eine weitere Schwäche ist, dass Sie die Gleichwertigkeit nur mit einer anderen formalen Beschreibung nachweisen können. Das Schreiben einer formalen Spezifikation für ein Programm ist gleichbedeutend mit dem Schreiben eines Programms in einer höheren Sprache, und es gibt keine Möglichkeit, die Einführung von Fehlern in einer relativ großen Spezifikation zu vermeiden.

Ich habe formale Methoden nie in großem Maßstab funktionieren lassen. Sie können hilfreich sein, wenn es darum geht, kleine und schwierige Dinge zu korrigieren und mich davon zu überzeugen, dass sie korrekt sind. Auf diese Weise kann ich mit etwas größeren Bausteinen arbeiten und manchmal etwas mehr erledigen.

Eine Sache, die ich aufgegriffen habe und die allgemeiner nützlich ist, ist das Konzept einer Invariante, eine Aussage über ein Programm und seinen Zustand, die immer wahr ist. Alles, woraus Sie schließen können, ist gut.

Wie oben angedeutet, bin ich kein perfekter Mathematiker, und deshalb enthalten meine Beweise manchmal Fehler. Nach meiner Erfahrung handelt es sich jedoch in der Regel um große blöde Fehler, die leicht zu fassen und zu beheben sind.

David Thornley
quelle
4

Ich habe einen Abschluss in formaler Programmanalyse gemacht, bei dem wir uns auf die operative Semantik konzentrierten. Ich habe meine Abschlussarbeit über die seL4-Bemühungen verfasst und die von ihnen verwendeten formalen Methoden überprüft. Mein wichtigstes Argument in Bezug auf die Praktikabilität war, dass es von geringem Wert ist. Sie müssen nicht nur das Programm schreiben, Sie müssen auch den Beweis schreiben. Beeindruckend. Zwei Fehlerquellen. Nicht nur einer. Darüber hinaus gab es enorme Einschränkungen für den eigentlichen Code. Es ist sehr schwierig, einen physischen Computer einschließlich E / A formal zu beschreiben .

Paul Nathan
quelle
Ich habe einmal einen Stich bei der Beschreibung von E / A im Tape-Stil gesehen. Der Autor hatte keine Lösung, um Dateien mit wahlfreiem Zugriff förmlich zu beschreiben, und begnügte sich damit, sie schlecht zu sagen.
David Thornley
1
@ David: Diese Dateien mit wahlfreiem Zugriff. Schlechte Nachrichten. Du willst sie nicht benutzen. =)
Paul Nathan
3

Ich habe mir TLA + im letzten Jahr selbst beigebracht und benutze es seitdem. Es ist eines der ersten Werkzeuge, nach denen ich bei jedem Projektstart greife. Der Fehler, den die meisten Menschen machen, besteht darin, dass sie annehmen, dass formale Methoden alles oder nichts sind: Entweder verwenden Sie keine formalen Methoden oder Sie haben eine vollständige Überprüfung. Es gibt jedoch etwas zwischen ihnen: formale Spezifikation , bei der Sie überprüfen, ob eine abstrakte Spezifikation Ihres Projekts Ihre Invarianten nicht zerstört. Im Gegensatz zur Verifizierung ist die Spezifikation praktisch genug, um in der Industrie eingesetzt zu werden.

Spezifikationssprachen sind ausdrucksvoller als Programmiersprachen. Hier ist zum Beispiel eine (sehr) einfache PlusCal-Spezifikation für einen verteilten Datenspeicher:

process node \in 1..5 \* Nodes
variables online = TRUE,
          stored \in SUBSET data; \* Some set
begin 
  Transfer:
    either
      with node \in Nodes, datum \in stored do
        node.stored := node.stored \union {datum};
      end
    or \* crash
      online := FALSE;
    end either;
end process;

Dieses Snippet gibt an, dass fünf Knoten gleichzeitig ausgeführt werden und Übertragungen in einer beliebigen Reihenfolge ausgeführt werden, wobei jede Übertragung ein beliebiges Datenelement an einen beliebigen Knoten ist. Darüber hinaus haben wir angegeben, dass eine bestimmte Übertragung fehlschlagen und den Knoten zum Absturz bringen kann. Und wir können all diese Verhaltensweisen im TLA + -Modellprüfer simulieren! Auf diese Weise können wir testen, ob unsere Anforderungen ungeachtet der Reihenfolge, der Ausfallraten usw. noch immer erfüllt sind. Apropos, fügen wir ein paar Anforderungen hinzu. Erstens, dass wir niemals Daten an einen Offline-Knoten übertragen:

[][\A node \in Nodes: ~online => UNCHANGED node.stored]_vars

In unserer vereinfachten Version findet die Modellprüfung einen Fehlerstatus. Wir können auch angeben, "dass sich ein bestimmtes Datenelement in mindestens einem Online-Knoten befindet":

\A d \in data: \E n \in Nodes: n.online /\ d \in n.stored

Welches wird auch scheitern. Viel Glück beim Testen!

Die Haupteinschränkung der Spezifikation besteht darin, dass sie unabhängig von Ihrem tatsächlichen Code existiert. Es kann Ihnen nur sagen, dass Ihr Design korrekt ist, nicht, dass Sie es richtig implementiert haben. Aber es ist schneller zu spezifizieren als zu verifizieren, und es erkennt Fehler, die zu subtil zum Testen sind, und ich finde, dass es die Mühe wert ist. Nahezu jeder Code, der Parallelität oder mehrere Systeme umfasst, ist ein guter Ort für eine formale Spezifikation.

Hovercouch
quelle
1

Ich habe in einer Abteilung bei ICL gearbeitet, bevor sie von Fujitsu aufgekauft wurden. Sie hatten einige große Regierungsverträge, die den Nachweis erforderten , dass die Software wie angekündigt funktionierte. Sie bauten daher eine Maschine, die die in Z geschriebene formale Spezifikation entsprach und den Code während der Ausführung mit einem großen grünen oder roten Licht für Bestanden validierte. Scheitern.

Es war eine erstaunliche Sache, aber, wie der geschätzte @FishToaster hervorhebt , war es für nichts Nicht-Triviales nutzlos.

JBRWilkinson
quelle
0
  1. " Wie nützlich hast du es gefunden? "

Die Anwendung von Petri-Netzen zur Computerprogrammierung ist sehr nützlich. Ich habe „Net Elements and Annotations“ erstellt, eine Methode, die auf Petri Nets basiert (Chionglo, 2014). Ich wende die Methode seit 2014 an, um JavaScript-Programme zu schreiben, die die Acrobat / JavaScript-API für PDF-Formularanwendungen verwenden.

  1. Was beinhaltete Ihr FM-Training (z. B. einen Kurs, ein Buch)? "

Ich habe im Selbststudium auf Petri-Netzen „trainiert“. Ich las die Kapitel über Petri-Netze aus dem Lehrbuch „Petri-Netze und Grafcet: Werkzeuge zur Modellierung diskreter Ereignissysteme“ (David und Alla, 1992). Ich habe auch Forschungsarbeiten über Petri-Netze gelesen. Nachdem ich „Net Elements and Annotations“ erstellt und dokumentiert hatte, übte ich mich einige Wochen in der Anwendung der Methode.

  1. Welche FM-Tools verwenden Sie? "

Ich zeichne Petri-Net-Diagramme mit PowerPoint. Ich erstelle die Formularansicht von Anmerkungen mit Word. Ich erstelle Tokenspiele als PDF-Formularanwendungen auch mit Acrobat und Notepad. Nach dem Hinzufügen der Einträge in das Formular erfolgt die Übersetzung dieser Einträge in JavaScript-Code systematisch. Somit sollte es möglich sein, die Übersetzung zu automatisieren. Wenn die „Einträge“ zu den Grafikobjekten in PowerPoint hinzugefügt wurden, sollte es auch möglich sein, diese systematisch in JavaScript-Code zu übersetzen und diese Übersetzung ebenfalls zu automatisieren. Ich verwende auch eine Reihe von Work-in-Progress-Tools, mit denen diese Übersetzungen ausgeführt und zusätzliche Ressourcen zum Erstellen von PDF-Formularanwendungen erstellt werden (Chionglo, 2018; 2017).

  1. Welche Geschwindigkeits- / Qualitätsvorteile hat es Ihnen gegenüber der Nichtnutzung von FM gebracht? "

Ich kann JavaScript-Programme mit "Net Elements and Annotations" schneller schreiben als ein JavaScript-Programm ohne "Net Elements and Annotations". Und bei großen Programmen kann ich die Codierung beenden und später (oder viel später) zur Codierung zurückkehren, ohne mich zu fragen, wo ich fortfahren soll (Chionglo, 2019). In einigen Fällen kann ich JavaScript-Programme mit „Net Elements and Annotations“ schreiben, die JavaScript-Programme jedoch nicht ohne „Net Elements and Annotations“. Ich hätte zum Beispiel keine nicht-rekursiven Implementierungen von rekursiven Funktionen ohne die Verwendung von „Net Elements and Annotations“ erstellen können (Chionglo, 2019b; 2018b; 2016). Dies gilt mit oder ohne Work-in-Progress-Tools.

  1. " Welche Art von Software erstellen Sie mit FM? "

Ich verwende "Net Elements and Annotations", um JavaScript-Programme zu erstellen, die die Acrobat / JavaScript-API für PDF-Formularanwendungen verwenden. Ich kann die Methode auch anwenden, um JavaScript-Programme für HTML-Dokumente zu erstellen und Arduino-Skizzen zu erstellen (Chionglo, 2019c; 2019d).

  1. " Und wenn Sie FM jetzt nicht direkt nutzen, hat es sich zumindest gelohnt, es zu lernen? " Nicht zutreffend.

Verweise

Chionglo, JF (2019b). Berechnung des N-ten Terms einer rekursiven Relation: Verwenden einer nicht rekursiven Funktion - Eine Antwort auf eine Frage bei Mathematics Stack Exchange. < https://www.academia.edu/38496025/Computing_the_N-th_Term_of_a_Recursive_Relation_Using_a_Non-Recursive_Function_A_Reply_to_a_Question_at_Mathematics_Stack_Exchange >.

Chionglo, JF (2019c). Logik, Simulation und Skizze zur Steuerung von Flammeneffekten: Eine Antwort auf eine Anfrage im Arduino Community Forum. https://www.academia.edu/40342956/Flame_Effect_Control_Logic_Simulation_and_Sketch_A_Reply_to_a_Request_at_the_Arduino_Community_Forum .

Chionglo, JF (2019). Wie fahre ich nach einer langen Pause mit dem Codieren einer Anwendung fort? Antwort auf „Woher wissen Sie, wo Sie nach einer zweiwöchigen Pause aufgehört haben, Ihre Codes zu ändern?“ - Software Engineering Stack Exchange. https://www.academia.edu/39705042/How_I_Continue_Coding_an_Application_after_a_Long_Break_Reply_to_How_do_you_know_where_you_stopped_in_your_codes_after_a_2-week_break_Software_Engineering_Stack_Exchange .

Chionglo, JF (2019d). Steuerlogik ein- und ausblenden: Inspiriert von einer Frage beim Stapelüberlauf. < https://www.academia.edu/40283015/Show-and-Hide_Control_Logic_Inspired_by_a_Question_at_Stack_Overflow >.

Chionglo, JF (2018b). Ein Petri-Netz-Modell für die Fakultät einer Zahl und eine nicht-rekursive JavaScript-Funktion zur Berechnung. <>.

Chionglo, JF (2018). Create Hyper Form ™ - Ein laufender Workflow: Aktualisierung der Net Programming Research. https://www.academia.edu/37697498/Create_Hyper_Form_-A_Workflow_in_Progress_Update_on_the_Net_Programming_Research .

Chionglo, JF (2017). Netzprogrammierung: Ein Forschungsvorschlag: Zur Entwicklung von PDF-Formularanwendungen mit PowerPoint und Acrobat. https://www.academia.edu/33374809/Net_Programming_A_Research_Proposal_For_Developing_PDF_Form_Applications_with_PowerPoint_and_Acrobat. .

Chionglo, JF (2016). Ein Petrinetzmodell zur Berechnung der Fibonacci-Zahl. https://www.academia.edu/31748108/A_Petri_Net_Model_for_Computing_the_Fibonacci_Number.

Chionglo, JF (2014). Netzelemente und Anmerkungen für die Computerprogrammierung: Berechnungen und Interaktionen in PDF. https://www.academia.edu/26906314/Net_Elements_and_Annotations_for_Computer_Programming_Computations_and_Interactions_in_PDF .

David, R. und H. Alla. (1992). Petri-Netze und Grafcet: Werkzeuge zur Modellierung von Discrete-Event-Systemen. Upper Saddle, New Jersey: Prentice Hall.

John Frederick Chionglo
quelle