Fast and Precise Regular Approximations of Logic Programs
The MIT Press eBooks · 1994
A practical procedure for computing a regular approximation of a logic program is given. Regular approximations are useful in a variety of tasks in debugging, program specialisation and compile-time optimisation. The algorithm shown here incorporates optimisations taken from deductive database fixpoint algorithms and efficient bottom-up abstract interpretation techniques. Frameworks for defining regular approximations have been put forward in the past, but the emphasis has usually been on theoretical aspects. Our results contribute mainly to the development of effective analysis tools that can be applied to large programs. Precision of the approximation can be greatly improved by applying query-answer transformations to a program and a goal, thus capturing some argument dependency information. A novel technique is to use transformations based on computation rules other than left-to-right to improve precision further. We give performance results for our procedure on a range of programs.