Abstrakte Interpretation
# Abstrakte Interpretation

Die abstrakte Interpretation ist eine Methode aus dem Bereich der Programmanalyse.

Ziel der abstrakten Interpretation ist es Informationen über das Verhalten von Programmen (Analyse der Semantik) zu bekommen, indem man von Teilen des Programms abstrahiert und die Anweisungen Schritt für Schritt nachvollzieht (Interpretation).

Bei der abstrakten Interpretation konzentriert man sich auf Teilaspekte der Ausführung der Anweisungen, man lässt einiges an Information geschickt weg (Abstraktion), erhält letztlich eine Näherung an die Programmsemantik, die aber für den gewünschten Zweck vollkommen ausreichen kann.

Viele Eigenschaften von Programmen sind nicht berechenbar, d. h. man kann kein Programm angeben, welches sie in endlicher Zeit mit endlichen Speicherressourcen für beliebige Programme berechnet. Durch eine Approximation, also das Weglassen von einigen Informationen, kann man zwar Fragen nach bestimmten Eigenschaften gar nicht mehr klären, dafür werden aber andere Eigenschaften in der vergröberten Sicht erst berechenbar.

Das Verfahren stammt von Radhia Cousot und Patrick Cousot.

## Beispiel

Ein Compiler möchte analysieren, was für einen Rückgabetyp eine bestimmte Funktion hat. Dazu reicht schon ein vergröbertes Nachvollziehen (sprich: abstrakte Interpretation) der Berechnungen.

Zum Beispiel kann die Anweisung

als Berechnung

mit Ergebnistyp „int“ für die Variable x betrachtet werden. Es reicht die Information, dass 4 und 5 jeweils ganze Zahlen (also hier vom Typ „int“) sind, ihr genauer Wert ist hingegen für die Typbestimmung nicht interessant, kann also weggelassen werden.

Weiter geht es mit

welches als

mit Ergebniswert „real“ aufgefasst würde.

Vollzieht man alle Anweisungen der Funktion in dieser vergröberten Sicht nach, so ist am Schluss klar, welchen Typ der Rückgabewert hat.

