Begriff
Hoare Logic
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Wie beweist man, dass ein Programm immer funktioniert?
Nicht durch Testen (Tests finden nur Fehler, beweisen aber nicht deren Abwesenheit).
Tony Hoare erfand ein System aus drei Teilen (Hoare-Tripel):
{P} C {Q}.
- P (Precondition): Was muss vorher wahr sein? (z. B. "x ist größer als 0").
- C (Code): Das Programm.
- Q (Postcondition): Was ist nachher garantiert wahr? (z. B. "y ist das Doppelte von x"). Wenn du beweisen kannst, dass aus P durch C immer Q folgt, ist dein Code korrekt. Mathematisch.
Merksatz: Ein formales System mit einer Menge von logischen Regeln, um die Korrektheit von Computerprogrammen rigoros zu beweisen.
In "Design by Contract" (Eiffel, Java JML, Spec#).
Du schreibst @Requires(x > 0) und @Ensures(result == x * 2).
Moderne Tools (Dafny, F*) nutzen Hoare Logic unter der Haube, um deinen Code während des Tippens zu prüfen.
1. Loop Invariant
Der schwerste Teil.
Wie beweist man eine while-Schleife?
Man muss eine Formel finden (Invariante), die:
- Vor der Schleife wahr ist.
- In jedem Durchlauf wahr bleibt.
- Nach der Schleife (zusammen mit der Abbruchbedingung) das Ergebnis beweist. Das Finden dieser Formel ist oft Kunst, keine Mechanik.
2. Total Correctness
Normales Hoare Logic beweist "Partial Correctness": Falls das Programm terminiert, ist das Ergebnis richtig. Aber terminiert es auch? (Endlosschleife?). Total Correctness beweist beides. (Viel schwerer).
1. Weakest Precondition (wp-Kalkül)
Wie automatisiert man Beweise in Code? Edsger W. Dijkstra baute Hoare-Logik um, in dem er es von "hinten nach vorne" las (Backward Chaining). Der Weakest Precondition (wp) Kalkül fragt nicht: "Welche Kondition hat das Programm vorweg?", sondern: "Ich will am Ende Zustand $Q$ haben. Was ist die formal schwächste (allgemeinste) Voraussetzung $P$, die ich dem System geben muss, dass es in $Q$ rutscht?" Formel bei Variablenzuweisung: $wp(x := E, Q) = Q[E/x]$. Die mathematische Substitutionsanalyse erlaubt SAT-Solvern (wie Z3), Millionen Codezeilen algebraisch auf Security-Injektionen oder Integer-Overflows rückwärts zu zermahlen, da der Solver im Baum evaluiert, bis er am Start auf ein unerfüllbares Axiom (Contradiction) schlägt.
2. Separation Logic und Zeiger-Chaos
Ein gigantischer Blind-Spot im alten Hoare-System: Memory Pointers.
Hoare wusste Null über Aliasing (zwei Pointers A und B auf das selbe Byte in C-Rams). Wenn der Code *A = 5 ausführt, versagt traditionelle Logik, denn der Zustand von *B mutierte magisch ohne eigenen Frame-Call.
Forscher Reynolds und O'Hearn sprengten diese Limitierung in den 2000ern mit der Separation Logic. Sie führten das trennende Konjunktion-Zeichen $\ast$ (Separating Conjunction) ein. Der Term $P \ast Q$ bedeutet: "Der Ram erfüllt Zustand P UND Zustand Q, verlangt aber mathematisch zwingend, dass P und Q physisch disjunkte Heap-Bereiche einnehmen!". Das ermöglichte die erste voll-mechanisierte Beweisführung kompletter Linux-C-Kernel Trees gegen Memory Leaks .
3. Proof-Carrying Code (PCC)
Ein extrem radikales Sicherheitskonzept (Genutzt in Ethereum Smart Contracts / K-Framework Verifizierungen).
Wer garantiert dem Betriebssystem, dass ein fremd herutergeladenes Maschinen-Modul das System nicht infiziert?
Beim Proof-Carrying Code liefert der Entwickler nicht nur den .bin Maschinen-Code, sondern einen mathematisch kryptographischen Hoare-Logik-Theorem-Beweis mit auf der Platinen-Leiterplatte.
Das Host-System verschwendet keine Sandbox, sondedern verifiziert nur den Hoare-Proof via Coq-Typechecker in wenigen Millisekunden ("Der Speicher wird nicht out-of-bounds betreten"). Ist der Beweis logisch stichhaltig, darf der Fremdcode sofort vollen unlimitierten Kernel-Access in Ring 0 haben, da die absolute theoretische Korrektheit jenseits jedweden Zweifels verifiziert wurde.
Quick-Check
Macht das wer?
Für normale Apps: Nein (zu teuer). Für Raketensteuerungen, Atomkraftwerke und Smart Contracts (Milliardenwerte): Ja, absolut.Tony Hoare?
Der Erfinder von Quicksort. Und der Erfinder vonnull("My billion-dollar mistake"). Ein Riese der Informatik.Warum nicht immer?
Der Beweis dauert oft 10x länger als das Programmieren. Und wenn sich die Spec ändert, fängst du von vorne an.