Heap-Bäume in Isabelle: Korrektheit von Push-Operationen mit AutoCorres verifizieren

Einleitung: Warum formale Verifikation von Heap-Strukturen?

Stell dir vor, du entwickelst eine Prioritätswarteschlange für eine KI-gesteuerte Spiellogik oder eine Finanz-App, die in Millisekunden die höchste Priorität aus Tausenden von Elementen extrahieren muss. Ein Fehler in der Push-Operation könnte dazu führen, dass die Sortierung verletzt wird – und dein Chatbot die falsche Antwort gibt oder deine Trading-App den falschen Auftrag ausführt. Mit Isabelle2024 und AutoCorres 1.11 kannst du solche Fehler von vornherein ausschließen. In diesem Tutorial zeige ich dir, wie du die Korrektheit einer Heap-Push-Operation beweist, basierend auf der Aufgabenstellung von COMP4161 Assignment 3.

Grundlagen: Tree-Heap und seine Invariante

Ein Tree-Heap ist ein binärer Baum, bei dem jeder Knoten einen Wert speichert. Die Heap-Eigenschaft besagt: Der Wert eines Elternknotens ist stets größer oder gleich (bzw. kleiner oder gleich, je nach Ordnung) den Werten aller Kinder. In Isabelle definieren wir das so:

datatype 'a tree = Node 'a 'a tree 'a tree | Empty

fun heap_tree_sorted :: "('a ⇒ 'a ⇒ bool) ⇒ 'a tree ⇒ bool" where
  "heap_tree_sorted ord Empty = True"
| "heap_tree_sorted ord (Node x left right) = (
    (∀y ∈ set (tree_elements left). ord x y) ∧
    (∀y ∈ set (tree_elements right). ord x y) ∧
    heap_tree_sorted ord left ∧ heap_tree_sorted ord right)"

Die Funktion tree_elements gibt alle Elemente in Preorder zurück. Die Invariante prüft, ob für jeden Knoten der Wert größer (im Sinne von ord) ist als alle Werte in seinen Teilbäumen.

Die Push-Operation: Funktional und in C

Die Push-Operation setzt einen neuen Wert an die Wurzel und schiebt ihn dann nach unten, bis die Heap-Eigenschaft wiederhergestellt ist. In Isabelle sieht die funktionale Version so aus:

fun heap_tree_push :: "('a ⇒ 'a ⇒ bool) ⇒ 'a ⇒ 'a tree ⇒ 'a tree" where
  "heap_tree_push ord x Empty = Empty"
| "heap_tree_push ord x (Node _ left right) = (
    if left ≠ Empty ∧ ord (tree_top left) x ∧ (right = Empty ∨ ord (tree_top left) (tree_top right))
    then Node (tree_top left) (heap_tree_push ord x left) right
    else if right ≠ Empty ∧ ord (tree_top right) x
    then Node (tree_top right) left (heap_tree_push ord x right)
    else Node x left right)"

In der C-Implementierung (gegeben in heap.c) wird die gleiche Logik mit Pointern umgesetzt. AutoCorres erzeugt daraus eine monadische Abstraktion, die wir in Isabelle verwenden können.

Frage 1: Beweis der Sortierungserhaltung

Deine erste Aufgabe: Beweise, dass heap_tree_push die Heap-Eigenschaft erhält. Das Lemma lautet:

lemma heap_tree_push_sorted:
  assumes "heap_tree_sorted ord t"
  shows "heap_tree_sorted ord (heap_tree_push ord x t)"

Der Beweis erfolgt durch Induktion über die Baumstruktur. Nutze auto, simp und sledgehammer. Ein typischer Fall: Wenn das linke Kind nicht leer ist und ord (tree_top left) x gilt, dann wird der Wert des linken Kindes an die Wurzel gesetzt und x rekursiv in den linken Teilbaum geschoben. Die Induktionshypothese liefert die Sortierung im linken Teilbaum. Mit find_theorems kannst du nützliche Lemmata über tree_elements und set finden.

Frage 2: Verifikation der C-Implementierung mit AutoCorres

Im zweiten Teil wird der C-Code mit dem C-Parser importiert und mit AutoCorres in eine monadische Form gebracht. Du arbeitest mit Typen wie tree_heap_C und Funktionen wie th_dom und th_vals. Die zentrale Datenstruktur ist der generische Speicher (Heap) der C-Welt.

Q2.1: Gleichheit von tree_heap_C-Strukturen

Beweise, dass zwei tree_heap_C-Werte genau dann gleich sind, wenn alle vier Felder übereinstimmen. Nutze find_theorems mit „tree_heap_C“ und „equality“.

Q2.2: Induktive Definition tree_in_C

Die Prädikate tree_in_C beschreiben, wann ein Baum im C-Speicher gültig ist. Du musst zeigen, dass tree_in_C unter bestimmten Operationen erhalten bleibt. Ein typischer Beweis verwendet die Induktionsregel von tree_in_C und die AutoCorres-Theorem über Speichertransformationen.

Praktische Tipps: Sledgehammer und Automatisierung

Erlaubt sind alle Standard-Taktiken: simp, auto, blast, force, fastforce. Sledgehammer ist nützlich, aber die vorgeschlagenen Beweise können auf deinem Rechner terminieren oder nicht. Wenn ein Beweis nicht terminiert, versuche, das Teilziel manuell zu vereinfachen, bevor du Sledgehammer erneut startest. Mit find_theorems kannst du automatisch generierte Lemmata entdecken – zum Beispiel über rel_tree oder tree_heap_C.

Trend-Beispiel: Wie ein Gaming-Leaderboard von Heaps profitiert

Stell dir vor, du entwickelst ein Echtzeit-Leaderboard für ein beliebtes Spiel wie Valorant oder Fortnite. Tausende Spieler pushen ständig neue Punktzahlen. Die höchste Punktzahl muss sofort abrufbar sein – genau das leistet ein Max-Heap. Mit formaler Verifikation stellst du sicher, dass nach jedem Push die Rangliste korrekt sortiert bleibt. Kein Cheater kann durch einen Programmierfehler an die Spitze gelangen!

Fazit

Mit Isabelle und AutoCorres kannst du komplexe Datenstrukturen wie Heaps formal verifizieren. Der Schlüssel liegt in der sorgfältigen Induktion und der geschickten Nutzung der automatischen Werkzeuge. Viel Erfolg bei deinem Assignment!