Abstract interpretation

The abstract interpretation is a method from the field of program analysis.

The aim of abstract interpretation is to get information about the behavior of programs (analysis of semantics) by abstracting portions of the program and the instructions retraces step by step ( interpretation).

In abstract interpretation, one focuses on some aspects of the execution of the instructions, you can be quite a bit of information sent away ( abstraction), ultimately, giving an approximation of the program semantics, but can completely sufficient for the desired purpose.

Many properties of programs are not computable, ie you can not specify a program that computes in finite time with finite memory resources for any program. Through an approximation, so the omission of some information, you can ask though by specific properties no longer cleared, but other properties in the coarsened view are only predictable.

Example

A compiler would like to analyze what has a specific function for a return type. To this end, all it takes is a coarsened Understand (read: abstract interpretation ) of the calculations.

Function f ()          x = 4 5          y = x * 3:14          return y For example, the statement

X = 4 5 as calculation

Int int be "int" x viewed with result type for the variable. It extends the information that 4 and 5 are each integers (here the type " int " ) are, their precise value, however, is for the type determination not interesting, so can be omitted.

It continues with

Y = x * 3:14 which as

Int * real would "real " construed with result value.

If one goes through all the instructions of the function in this coarsened visibility, so is the conclusion obvious what type of return value.