IMPLEMENTATION OF TABLED EVALUATION WITH DELAYING IN PROLOG

Unlike SLD resolution as implemented in Prolog, tabled evaluation with delaying guarantees termination for function-free logic programs, avo ids repeated computation of identical subqueries, and handles recursio n through negation. It is often used in query processing and nonmonoto nic reasoning where termination is required. This paper presents a new technique for incorporating tabled evaluation into existing Prolog sy stems. It requires neither time consuming modifications of a Prolog en gine nor metainterpretation that can enormously slow down program exec ution. Instead, using a program transformation approach, the technique allows effective use of the advanced Prolog technology. The transform ed program uses tabling primitives implemented externally in C that pr ovide direct control over the search strategies. This brings efficienc y as well as portability across Prolog systems. Experiences with a pro totype implementation indicate that the approach results in a flexible and pragmatic method for query processing and nonmonotonic reasoning on top of Prolog. Performance measurements show that the method is eff icient for practical applications.