On Delphi lemmas and other memoing techniques for deterministic logic programs

AbstractThree orthogonal memoing techniques for deterministic logic programs are introduced and evaluated on the basis of their empirical performance. They share the same basic idea: efficient memoing is achieved by losing information gracefully, i.e., memoing benefits from a form of abstraction.Abstract answers are most general computed answers of deterministic logic programs obtained through repeated applications of a simple clause composition operator. After describing a meta-interpreter returning abstract answers, we derive a class of program transformations that compute abstract answers more efficiently: they are ideal lemmas due to their goal-independent nature. For this reason, their “hit rate” is usually higher than in the case of conventional memoing.Indexing by structural properties of terms is an effective way to speed up the retrieval of lemmas, especially in the case of simple programs using linear recursion.Delphi lemmas add a self-adjusting control mechanism on the amount of memoing. Answers are memoized only by acquiescence of an oracle. We show that random oracles perform surprisingly well as Delphi lemmas tend naturally to cover the “hot spots” of the program