ASAP Bottom-Up Analysis Tools

This toolset consists of a set of tools based on bottom-up analysis developed in the ASAP project and running in Ciao Prolog.

Bottom-up analysis has an elegant semantic basis based on the declarative semantics of logic programs, straightforward implementation, and flexible application. 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. Efficient algorithms for bottom-up analysis are at the heart of the toolkit. A systematic method for implementing analyses using the tools is then available.

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 goal-directed 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.

Abstract compilation can be achieved very flexibly, based on the construction of pre-interpretations based on arbitrary regular types.

Bottom-Up Analysis Tools

The main tools in BU are: These tools are built from basic operations and components; the main ones are as follows.


Download a tarfile containing the Prolog sources. Then consult the README file which contains a mini-manual.
John Gallagher,