Schleifenvarianten

Schleifenvarianten sind ein Konzept aus der formalen Verifikation von Programmen, mit dem die Termination von Schleifen begründet wird. Eine Schleifenvariante ist eine Funktion oder ein Maß, das dem Programmzustand zugeordnet wird und bei jeder Iteration einer Schleife strikt kleiner wird. Der Wertebereich der Variante liegt in einer wohldefinierten, wohlgeordneten Menge, wodurch endliche Abfolgen von Abnahmen garantiert sind und eine unendliche Schleife ausgeschlossen wird.

In der Praxis dient die Variante dazu, einen Beleg für die Beendigung der Schleife zu liefern. Typischerweise wird eine numerische Variante verwendet, etwa der nichtnegative natürliche Zahlenwert n, der in jeder Iteration um mindestens eins abnimmt, bis er null erreicht. Komplexere Schleifen lassen sich mit mehrdimensionalen Varianten absichern, etwa lexikografisch geordnete Paare wie (i, j): in jeder Iteration muss dieser Paarwert kleiner werden, sodass eine endliche Abfolge unvermeidlich ist.

Variantenarten reichen von einfachen numerischen Varianten über mehrdimensionale Lexikografie bis hin zu allgemeineren ordinalen Varianten. Die Wahl der Variante hängt von der Struktur der Schleife ab: Bei einfachen Zählschleifen genügt oft eine einzelne natürliche Zahl; verschachtelte Schleifen oder Schleifen, die mehrere Rekursionsebenen kontrollieren, profitieren von lexikografischen oder ordinalen Varianten.

Schleifenvarianten stehen im Zusammenhang mit Terminationsbeweisen in der Programmlogik und sind Teil vieler formaler Methoden, darunter Hoare-Kalkül-Erweiterungen und Verifikationswerkzeuge. Sie ergänzen Schleifeninvarianten, die die Richtigkeit der Berechnung sicherstellen, indem sie die Abfolge der Zustände begrenzen, während Varianten die Faktorsicherung der Beendigung liefern. Einschränkungen bestehen darin, dass eine gültige Variante vorhanden und deren Abnahme tatsächlich garantiert sein muss; ohne eine geeignete Variante kann die Terminierung eines Programms nicht formal bewiesen werden.