abstract interpretation

Also found in: Wikipedia.

abstract interpretation

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# <= (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.
References in periodicals archive ?
The firm envisaged a series of interconnected buildings that, when viewed from above, makes up an abstract interpretation of Arabic letters.
Al Bahlani's digital iPad art featured a modern, abstract interpretation of an Omani woman's traditional outfit, and it was part of her recent solo exhibition which Sarah had organised.
Microsoft s device driver verifier) and abstract interpretation (e.
Static analysis of software; the abstract interpretation.
In (Rodriguez-Carbonell & Kapur, 2007) a method using abstract interpretation and polynomial algebra is presented to generate polynomial loop invariants for so-called simple loops.
The chicken's painting is an abstract interpretation of fireworks done by dipping its feet into red, yellow and orange paints and letting her walk onto a black background.
Some specific topics include formal verification of computer systems by abstract interpretation, Newtonian program analysis, principles and applications of refinement types, modal fixed point logics, and implicit flows in malicious and nonmalicious code.
The architect, Kim Nielsen, has helpfully explained that, 'It is an abstract interpretation of a ship really--it's a big sculpture, it's a piece of art, not just a museum, and it will be there for everyone to enjoy whether they go inside or not.
Kennedy's piece is an abstract interpretation of a score by Jeffrey Stolet, professor of computer music.
It is an abstract interpretation of a ship really - it's a big sculpture, it's a piece of art, not just a museum, and will be there for everyone to enjoy whether they go inside or not.
You are invited to produce a new painting in any medium which may be traditional or contemporary, an interior or exterior scene, figurative or possibly an abstract interpretation.
The system is then able to construct an abstract interpretation of the scene, which is used to categorize different high-level typical situations (rooms, corridors, corners, and so on), that allow the robot to exhibit a non-reactive behaviour, depending on abstract properties of the environment.