page 1  (18 pages)
2to next section

A Bottom-Up Analysis Toolkit1

J.P. Gallagher

Department of Computer Science, University of Bristol

Queen's Building, University Walk, Bristol BS8 1TR, U.K.



Bottom-up analysis has an elegant semantic basis, straightforward implementation, and flexible application. Several recent studies indicate good prospects for flexible and efficient analysis systems based on bottom-up core semantics. In addition, goal-directed or top-down analyses can be simulated through the use of query-answer transformations, of which the so-called magic set" method is one. These transformations can also serve to increase precision with respect to bottom-up analysis. A toolkit of bottom-up analysis tools and query-answer transformations has been built up, based on a number of experiments over three years. These tools and aspects of their implementation will be described. Efficient algorithms for bottom-up analysis are at the heart of the toolkit. A systematic method for implementing analyses using the tools is then set out. The method is based on (i) abstract compilation of a program into a domain program", (ii) computation of (an approximation to) the model of the domain program, and (iii) use of various query-answer transformations to simulate goaldirected analysis and improve precision. Stages (ii) and (iii) can also be used directly on the original program in some applications. If the domain program has a finite model, then a precise model can be computed in step (ii). If the model is infinite or very large, methods of approximation including regular approximation and others can be used. The question of precision and complexity of bottom-up and goal-directed analysis will also be discussed.

1 Bottom-Up Abstract Interpretation of Logic Programs

Bottom-up semantics defines the meaning of a logic program, without reference to an initial goal, as the closure of an immediate consequences" operator that computes instances of clause heads from solutions to the bodies. There are several variations of this method [MS88], [CDY94], [BMLM94], [AG94].
Bottom-up semantics is the focus of this paper, but the use of tools to simulate top-down semantics in a bottom-up framework is an important point that will also be discussed [DR94], [CDY94].

1.1 Components of a Bottom-Up Toolkit

A set of tools has been implemented in Prolog and used in several abstract interpretation experiments [dWG94], [GdW94], [SG94]. Others have adopted a similar approach using tools similar to one or more

1Invited talk given at WAILL: The Workshop on Abstract Interpretation of Logic Languages; Eilat, Israel, June 18-19, 1995