Programming Logic

Mathematische Logik (Aristoteles, Boole) handelte von Wahrheit. "Alle Menschen sind sterblich." Programmier-Logik handelt von Zustandsänderung und Ressourcen. "Wenn ich in den Speicher schreibe, ist der alte Wert weg." Klassische Logik kann das schwer abbilden ($A \land A = A$. Aber $Geld \land Geld = 2 \cdot Geld$). Deshalb haben Informatiker spezielle Logiken erfunden, um über Programme zu sprechen. Hoare Logic war der Anfang. Separation Logic (für Pointer) und Dynamic Logic (für Java) sind die Weiterentwicklung.

Merksatz: Spezialisierte logische Systeme zur formalen Beschreibung und Analyse des Verhaltens von Computerprogrammen, insbesondere im Hinblick auf Korrektheit, Terminierung und Ressourcennutzung.

Wenn du über Pointer (Referenzen) nachdenkst. "Zeigen x und y auf das gleiche Objekt?" (Aliasing). Wenn ja, verändert x.val = 5 auch y.val. Das ist die Hölle für Beweise. Separation Logic führt den Operator * (separating conjunction) ein. $P * Q$ heißt: $P$ gilt für einen Teil des Speichers, $Q$ gilt für einen anderen Teil. Sie überlappen nicht. Damit kann man Pointer-Code endlich modular beweisen. Facebook nutzt das im Tool Infer, um Nullpointer in Android/iOS Apps massenhaft zu finden.

1. Dynamic Logic

Eine Erweiterung der Modallogik. $[program] \phi$: "Nach jeder Ausführung von program gilt $\phi$." $ \phi$: "Es gibt eine Ausführung von program, nach der $\phi$ gilt." Integriert Programmcode direkt in die logische Formel. Basis für den KeY Verifier (für Java).

2. Operational Semantics vs. Axiomatic Semantics

Operational: Beschreibt wie die Maschine es ausführt (Schritt für Schritt).
Axiomatic: Beschreibt was vorher/nachher gilt (Hoare Logic). Programming Logic nutzt meist die axiomatische Sicht.

1. Bi-Abduction: Automatisches Schließen von Lücken

Das Problem klassischer Logik-Beweiser: Sie brauchen "Pre-Conditions" (Annahmen). Bi-Abduction (genutzt in Facebooks Infer) findet diese Annahmen automatisch. Das Tool fragt: "Was müsste im Speicher stehen, damit diese Funktion nicht abstürzt?" Es generiert die fehlenden logischen Teile (Abduktion) und prüft gleichzeitig, was die Funktion hinterlässt. Dies erlaubt es, Millionen Zeilen Legacy-Code (C++) zu prüfen, ohne dass ein Mensch jemals eine einzige Zeile Logik-Formel händisch schreiben musste.

2. Rely-Guarantee Reasoning (Nebenläufigkeit)

Wenn zwei Threads gleichzeitig auf denselben Speicher zugreifen, bricht klassische Hoare-Logik zusammen. Rely-Guarantee führt zwei zusätzliche Bedingungen ein:

Rely: Was verspricht die Umgebung dem Thread? (z.B. "Niemand ändert Variable X").
Guarantee: Was verspricht der Thread der Umgebung? (z.B. "Ich schreibe nur in Y"). Solange beide ihre Versprechen halten, kann man den Code mathematisch beweisen. Das ist die Basis für die Verifikation von Betriebssystem-Kerneln (wie seL4), wo Race-Conditions tödlich wären.

3. Concurrent Separation Logic (CSL)

Die Krönung der Programmierlogik: Das Paket-Modell für Speicher. In CSL wird Ownership (siehe Rust) mathematisch als Logik-Ressource behandelt. Ein Thread kann ein "Teilstück des Heaps" besitzen. Wenn er fertig ist, übergibt er das Teilstück (via Message Passing) an einen anderen Thread. Der Witz: Durch die Logik wird bewiesen, dass zu jedem Zeitpunkt nur ein Thread die Schreibrechte hat. CSL ist der Grund, warum wir heute sicherere nebenläufige Programme bauen können, weil sie das Chaos von "Shared Memory" in eine geordnete Übergabe von mathematischen Fakten verwandelt.