Abstract Interpretation

In computer science, abstract interpretation is a theory of sound approximation of the semantics of computer programs, based on monotonic functions over ordered sets, especially lattices. It can be viewed as a partial execution of a computer program which gains information about its semantics (e.g. control-flow, data-flow) without performing all the calculations.

Its main concrete application is formal static analysis, the automatic extraction of information about the possible executions of computer programs; such analyses have two main usages:

  • inside compilers, to analyse programs in order to decide whether certain optimizations or transformations are applicable;
  • for debugging or even the certification of programs against classes of bugs.

Abstract interpretation was formalized by Patrick Cousot and Radhia Cousot in the late 70s.

Read more about Abstract InterpretationIntuition, Abstract Interpretation of Computer Programs, Formalization, Examples of Abstract Domains, Tools

Other articles related to "abstract interpretation, abstract, interpretation":

Static Program Analysis - Formal Methods
... used include denotational semantics, axiomatic semantics, operational semantics, and abstract interpretation ... for gathering information about the possible set of values Abstract interpretation models the effect that every statement has on the state of an abstract machine (i.e ... This abstract machine over-approximates the behaviours of the system the abstract system is thus made simpler to analyze, at the expense of incompleteness (not every property true of the original system is true of the ...
Sparse Conditional Constant Propagation
... The algorithm operates by performing abstract interpretation of the code in SSA form ... During abstract interpretation, it typically uses a flat lattice of constants for values and a global environment mapping SSA variables to values in ... The crux of the algorithm comes in how it handles the interpretation of branch instructions ...
Approaches To Strictness Analysis - Forward Abstract Interpretation
... Strictness analysis can be characterized as a forward abstract interpretation which approximates each function in the program by a function that maps divergence properties of the arguments onto ... In the classical approach pioneered by Alan Mycroft, the abstract interpretation used a two-point domain with 0 denoting the set considered as a subset of ...
Abstract Interpretation - Tools
... Astrée Abstract Rewriting Machine Polyspace CodeSonar Coverity Prevent Klocwork Insight Parasoft Jtest Parasoft C/C++test Red Lizard's Goanna ...

Famous quotes containing the word abstract:

    But the abstract conception
    Of private experience at its greatest intensity
    Becoming universal, which we call “poetry,”
    May be affirmed in verse.
    —T.S. (Thomas Stearns)