Abstrakte Interpretation - LinkFang.de





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 Speicherresourcen 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.

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

Zum Beispiel 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 ist hingegen für die Typbestimmung nicht interessant, 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öberten Sicht nach, so ist am Schluss klar, welchen Typ der Rückgabewert hat.

Weblinks

Software

Literatur

  • Principles of Program Analysis von Flemming Nielson, Hanne R. Nielson, Chris Hankin
  • Patrick Cousot, Radhia Cousot: Static Verification of Dynamic Properties of Variables. Technischer Bericht der Universite Scientifique et Medicale Grenoble, November 1975.
  • Patrick Cousot, Radhia Cousot: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, In Conference Record of the Sixth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 238–252, Los Angeles, California, 1977. ACM Press, New York.online

Kategorien: Programmierung

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Abstrakte Interpretation (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.