Abstract interpretation



abstract interpretation
theory
A partial execution of a program which gains information about its semantics (e.g. control structure, flow of information) without performing all the calculations. Abstract interpretation is typically used by compilers to analyse programs in order to decide whether certain optimisations or transformations are applicable.
The objects manipulated by the program (typically values and functions) are represented by points in some domain. Each abstract 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 then define 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 abstract operation is a safe approximation to the abstraction of the concrete 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 safer then the “safety condition” for our interpretation (#) is
a# *# b# where a# is the abstract version of a etc.
In general an interpretation is characterised by the domains used to represent the basic types and the abstract values it assigns to constants (where the constants of a language include primitive functions such as *). The interpretation of constructed types (such as user defined functions, sum types and product types) and expressions can be derived systematically from these basic domains and values.
A common use of abstract interpretation is strictness analysis.
See also standard interpretation.
(1994-11-08)

Tagged:

Read Also:

  • Abstract machine

    abstract machine 1. A processor design which is not intended to be implemented as hardware, but which is the notional executor of a particular intermediate language (abstract machine language) used in a compiler or interpreter. An abstract machine has an instruction set, a register set and a model of memory. It may provide instructions which […]

  • Abstract music

    . Historical Examples As a piece of abstract music, the movement appears long, but not if the dramatic situation be kept well in mind. The Pianoforte Sonata J.S. Shedlock This is the only one of the sonatas which, as abstract music, would be satisfactory without any programme. The Pianoforte Sonata J.S. Shedlock



  • Abstract machine notation

    abstract machine notation language (AMN) A language for specifying abstract machines in the B-Method, based on the mathematical theory of Generalised Substitutions. (1995-03-13)

  • Abstract noun

    a noun denoting something immaterial and abstract, as rest, dread, or transportation. a noun formed with a suffix that imparts such a meaning, as kindness. Contemporary Examples Glenn Beck did it before, although the abstract noun he chose to foist on the nation was “honor.” Sanity Is Overrated Tunku Varadarajan October 28, 2010 Historical Examples […]



Disclaimer: Abstract interpretation definition / meaning should not be considered complete, up to date, and is not intended to be used in place of a visit, consultation, or advice of a legal, medical, or any other professional. All content on this website is for informational purposes only.