Abstrakte Interpretation

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

Man versucht herauszubekommen, was ein Programm macht (Analyse der Semantik) indem man die Anweisungen Schritt für Schritt nachvollzieht (Interpretation).

Ein Debugger würde manuell auf dieser vollen Detailstufe vom Anwender geführt werden.

Bei der abstrakten Interpretation konzentriert man sich nur 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.

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.

     function f()

          x = 4 + 5

          y = x * 3.14

          return y

 

Z.B. kann die Anweisung

    x = 4 + 5

 

als Berechnung

    int + int

 

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 interessiert hingegen nicht für die Typbestimmung, kann also weggelassen werden.

Weiter geht es mit

    y = x * 3.14

 

welches als

   int * real

 

mit Ergebniswert real aufgefasst würde.

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

Literatur

• Principles of Program Analysis von Flemming Nielson, Hanne R. Nielson, Chris Hankin category:Software