abstract interpretation


Also found in: Wikipedia.

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# <= (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 ?
One of these is Chizuco's abstract interpretation of her hometown, Shizouka City, with Mount Fuji as one of its more famous residents, in a piece, titled Landscape 0616-3.
The lobby reception has an abstract interpretation of the Silk Road map crafted using the string art technique, it added.
Inspired by the night time flight of our intrepid heroes, the fascia represents a modern-day abstract interpretation of the view the pair would have enjoyed as finally, their craft cleared the thick fog and cloud.
Blue encourages people to perceive information on a broader scale, leading to a more abstract interpretation, and red encourages people to perceive information from a narrower perspective, leading to a more concrete interpretation (Forster, 2009).
Rather than repeat other photographers' approaches, showing astronauts doing things, Miller said he concentrated on the station's physical attributes in a manner that's part documentary and part abstract interpretation.
It centers on practical application rather than just abstract interpretation. Critical literacy includes an explicit commitment to equity for the marginalized, acknowledging issues of power.
In this new book, Hause expresses his art aesthetic in traditional and sometimes an abstract interpretation of Native American myths and legends, continuing their tradition of storytelling in a new medium.
It was an abstract interpretation of being alone in a big space because I feel women are continuously put under pressure when living or going out alone.
1962-64, combines both aerial and atmospheric perspectives to evoke an especially abstract interpretation of the physical world.
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.