Automata-driven indexing of prolog clauses

Indexing Prolog clauses is an important optimization step that reduces the number of clauses on which unification will be performed and can avoid the pushing of a choice point. It is quite desirable to increase the number of functors used in indexing as this can considerably reduce the size of the filtered set. However, doing so can cause an enormous increase in code size and running time if indexing is done naively. This paper describes new and efficient indexing techniques that utilize all the functors in the clause heads and the goal. The salient feature of these techniques is that the selected clause head unifies (modulo nonlinearity) with the goal. In unification (modulo nonlinearity) all the variables in the terms being unified are assumed to be unique, so the only operation performed is of matching their constant portions. So use of our indexing techniques can result in sharper discrimination, fewer choice points, and reduced backtracking. These techniques have been incorporated into a Prolog compiler and using this compiler the run-time performance of a broad spectrum of Prolog programs has been improved.