abstract interpretation
abstract interpretation
(theory)The objects manipulated by the program (typically values andfunctions) are represented by points in some domain. Eachabstract domain point represents some set of real("concrete") values.
For example, we may take the abstract points "+", "0" and "-"to represent positive, zero and negative numbers and thendefine an abstract version of the multiplication operator, *#,which operates on abstract values:
*# | + 0 ----|------+ | + 0 -0 | 0 0 0- | - 0 +
An interpretation is "safe" if the result of the abstractoperation is a safe approximation to the abstraction of theconcrete result. The meaning of "a safe approximation"depends on how we are using the results of the analysis.
If, in our example, we assume that smaller values are saferthen the "safety condition" for our interpretation (#) is
a# *# b# <= (a * b)#
where a# is the abstract version of a etc.
In general an interpretation is characterised by the domainsused to represent the basic types and the abstract values itassigns to constants (where the constants of a languageinclude primitive functions such as *). The interpretation ofconstructed types (such as user defined functions, sum typesand product types) and expressions can be derivedsystematically from these basic domains and values.
A common use of abstract interpretation is strictness analysis.
See also standard interpretation.