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 redu ce the size of the filtered set. However, doing so can cause an enormo us increase in code size and running time if indexing is done naively. This paper describes new and efficient indexing techniques that utili ze all the functors in the clause heads and the goal. The salient feat ure of these techniques is that the selected clause head unifies (modu le nonlinearity) with the goal. In unification (module nonlinearity) a ll 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 discriminati on, fewer choice points, and reduced backtracking. These techniques ha ve been incorporated into a Prolog compiler and using this compiler th e run-time performance of a broad spectrum of Prolog programs has been improved.