Extension table built‐ins for prolog
Changguan Fan, Suzanne Wagner Dietrich · Software Practice and Experience · 1992
Abstract The ET* algorithm is a complete evaluation strategy for Datalog programs, which are logic programs without function symbols. The ET* algorithm uses extension tables and depth‐first iterative deepening to provide the evaluation of pure function‐free logic programs as declarative specifications. Extension tables are a memo facility that the algorithm uses both to cut infinite derivation paths for complete evaluation and to optimise the evaluation of logic programs. The original implementation of the ET* algorithm incorporated extension tables as part of the Prolog database using the built‐in predicates assert and retract. The advantage of implementing the extension table using the Prolog database is the portability of the ET* algorithm. There are several disadvantages, however, with this approach. One disadvantage is the cost associated with the built‐in predicates assert and retract, which are known to be expensive operations in most current Prolog systems. Another disadvantage is the differences across implementations in the semantics that these built‐ins provide for dynamic predicates. This paper presents an efficient implementation of extension tables as a global data structure in Prolog, which includes a set of built‐in primitives for manipulating the extension table. The ET* algorithm is updated to reflect the utilisation of the global extension table data structure. The implementations of the ET* algorithm are compared using time and space performance on a variety of benchmark programs.