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 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 the French computer scientist working couple Patrick Cousot and Radhia Cousot in the late 1970s.^[1]^[2]

^ Cousot, Patrick; Cousot, Radhia (1977). "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints" (PDF). Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977. ACM Press. pp. 238–252. doi:10.1145/512950.512973. S2CID 207614632.
^ Cousot, Patrick; Cousot, Radhia (1979). "Systematic Design of Program Analysis Frameworks" (PDF). Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, USA, January 1979. ACM Press. pp. 269–282. doi:10.1145/567752.567778. S2CID 1547466.

[1] Cousot, Patrick; Cousot, Radhia (1977). "Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints" (PDF). Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977. ACM Press. pp. 238–252. doi:10.1145/512950.512973. S2CID 207614632.

[CCPOPL79-2] Cousot, Patrick; Cousot, Radhia (1979). "Systematic Design of Program Analysis Frameworks" (PDF). Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, USA, January 1979. ACM Press. pp. 269–282. doi:10.1145/567752.567778. S2CID 1547466.

[1]

[2]