Practical program analysis using general purpose logic programming systems—a case study
Steven Dawson, C. R. Ramakrishnan, David Scott Warren · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1996
Many analysis problems can be cast in the form of evaluating minimal models of a logic program. Although such formulations are appealing due to their simplicity and declarativeness, they have not been widely used in practice because, either existing logic programming systems do not guarantee completeness, or those that do have been viewed as too inefficient for integration into a compiler. The objective of this paper is to re-examine this issue in the context of recent advances in implementation technologies of logic programming systems.We find that such declarative formulations can indeed be used in practical systems, when combined with the appropriate tool for evaluation. We use existing formulations of analysis problems --- groundness analysis of logic programs, and strictness analysis of functional programs --- in this case study, and the XSB system, a table-based logic programming system, as the evaluation tool of choice. We give experimental evidence that the resultant groundness and strictness analysis systems are practical in terms of both time and space. In terms of implementation effort, the analyzers took less than 2 man-weeks (in total), to develop, optimize and evaluate. The analyzer itself consists of about 100 lines of tabled Prolog code and the entire system, including the components to read and preprocess input programs and to collect the analysis results, consists of about 500 lines of code.
Cited by 97 works. doi:10.1145/231379.231399
Authors
References
- Compilers: Principles, Techniques, and Tools
- Principles of database and knowledge-base systems
- A theory of type polymorphism in programming
- Symbolic Boolean manipulation with ordered binary-decision diagrams
- Automatic discovery of linear restraints among variables of a program
- The principle type-scheme of an object in combinatory logic
- Magic sets and other strange ways to implement logic programs (extended abstract)
- The Principal Type-Scheme of an Object in Combinatory Logic
- Magic Sets and Other Strange Ways to Implement Logic Programs.
- Abstract interpretation and optimising transformations for applicative programs