We present an implementation technique for a class of bottom-up logic procedures. The technique is called
code trees. It is intended to speed up most important and costly operations, such as subsumption and resolution. As an example, we consider the forward subsumption problem which is the bottleneck of many systems implementing first order logic.
In order to efficiently implement subsumption, we specialize subsumption algorithms at run time, using the
abstract subsumption machine. The abstract subsumption machine executes subsumption using sequences of instructions that are similar to the WAM instructions [31]. It gives an efficient implementation of the
clause at a time
subsumption problem. To implement subsumption on the
set at a time
basis we combine sequences of instructions in
code trees.
We show that this technique yields a new way of indexing clauses. Some experimental results are given.
The code trees technique may be used in various procedures, including OLDT-resolution, SLD-AL-resolution, bottom-up evaluation of logic programs and disjunctive logic programs.
Supported by Swedish TFR grant no. 93-409