Abstract. Abstract interpretation is a theory of semantics approximation which is used for the con struction of semantics-based program analysis algorithms (sometimes called "data flow analysis"), the comparison of formal semantics (e.g., construction of a denotational semantics from an operational one), the design of proof methods, etc. Automatic program analysers are used for determining statically conservative approximations of dy namic properties of programs. Such properties of the run-time behavior of programs are useful for debug ging (e.g., type inference), code optimization (e.g., compile-time garbage collection, useless occur-check elimination), program transformation (e.g., partial evaluation, parallelization), and even program cor rectness proofs (e.g., termination proof). After a few simple introductory examples, we recall the classical framework for abstract interpretation of programs. Starting from a standard operational semantics formalized as a transition system, classes of program properties are first encapsulated in collecting semantics expressed as fixpoints on partial orders representing concrete program properties. We consider invariance properties characterizing the descendant states of the initial states (corresponding to top/down or forward analyses), the ascendant states of the final states (corresponding to bottom/up or backward analyses) as well as a combination of the two. Then we choose specific approximate abstract properties to be gathered about program behaviors and express them as elements of a poset of abstract properties. The correspondence between concrete and abstract properties is established by a concretization and abstraction function that is a Galois connection formalizing the loss of information. We can then constructively derive the abstract program properties from the collecting semantics by a formal computation leading to a fixpoint expression in terms of abstract operators on the domain of abstract properties. The design of the abstract interpreter then involves the choice of a chaotic iteration strategy to solve this abstract fixpoint equation. We insist on the compositional design of this abstract interpreter, which is formalized by a series of propositions for designing Galois connections (such as Moore families, decomposition by partitioning, reduced product, down-set completion, etc.). Then we recall the convergence acceleration methods using widening and narrowing allowing for the use of very expressive infinite domains of abstract properties. We show that this classical formal framework can be applied in extenso to logic programs. For simplicity, we use a variant of SLD-resolution as the standard operational semantics. The first example is groundness analysis, which is a variant of Mellish mode analysis. It is extended to a combination of top/down and bottom/up analyses. The second example is the derivation of constraints among argument sizes, which involves an infinite abstract domain requiring the use of convergence acceleration methods. We end up with a short thematic guide to the literature on abstract interpretation of logic programs.
They also propose to use it for the analysis of logic programs REF .
R.: Abstract interpretation and application to logic programs
Journal of Logic Programming
Computer Science