Denotational abstract interpretation of logic programs
Open Access
- 1 May 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 16 (3) , 607-648
Abstract
Logic-programming languages are based on a principle of separation “logic” and “control.”. This means that they can be given simple model-theoretic semantics without regard to any particular execution mechanism (or proof procedure, viewing execution as theorem proving). Although the separation is desirable from a semantical point of view, it makes sound, efficient implementation of logic-programming languages difficult. The lack of “control information” in programs calls for complex data-flow analysis techniques to guide execution. Since data-flow analysis furthermore finds extensive use in error-finding and transformation tools, there is a need for a simple and powerful theory of data-flow analysis of logic programs. This paper offers such a theory, based on F. Nielson's extension of P. Cousot and R. Cousot's abstract interpretation . We present a denotational definition of the semantics of definite logic programs. This definition is of interest in its own right because of its compactness. Stepwise we develop the definition into a generic data-flow analysis that encompasses a large class of data-flow analyses based on the SLD execution model. We exemplify one instance of the definition by developing a provably correct groundness analysis to predict how variables may be bound to ground terms during execution. We also discuss implementation issues and related work.Keywords
This publication has 25 references indexed in Scilit:
- Frameworks for abstract interpretationActa Informatica, 1993
- Abstract interpretation based on oldt resolutionThe Journal of Logic Programming, 1993
- Global flow analysis as a practical compilation toolThe Journal of Logic Programming, 1992
- Static analysis of logic programs for independent and parallelismThe Journal of Logic Programming, 1992
- Deriving descriptions of possible values of program variables by means of abstract interpretationThe Journal of Logic Programming, 1992
- Bottom-up dataflow analysis of normal logic programsThe Journal of Logic Programming, 1992
- Abstract interpretation and application to logic programsThe Journal of Logic Programming, 1992
- On derived dependencies and connected databasesThe Journal of Logic Programming, 1991
- A practical framework for theabstract interpretation of logic programsThe Journal of Logic Programming, 1991
- Denotational and operational semantics for prologThe Journal of Logic Programming, 1988