EFFICIENT ACCESS MECHANISMS FOR TABLED LOGIC PROGRAMS

The use of tabling in logic programming allows bottom-up evaluation to be incorporated in a top-down framework, combining advantages of both . At the engine level, tabling also introduces issues not present in p ure top-down evaluation, due to the need for subgoals and answers to a ccess tables during resolution. This article describes the design, imp lementation, and experimental evaluation of data structures and algori thms for high-performance table access. Our approach uses tries as the basis for tables. Tries, a variant of discrimination nets, provide co mplete discrimination for terms, and permit a lookup and possible inse rtion to be performed in a single pass through a term. In addition, a novel technique of substitution factoring is proposed. When substituti on factoring is used, the access cost for answers is proportional to t he size of the answer substitution, rather than to the size of the ans wer itself. Answer tries can be implemented both as interpreted struct ures and as compiled WAM-like code. When they are compiled, the speed of computing substitutions through answer tries is competitive with th e speed of unit facts compiled or asserted as WAM code. Because answer tries can also be created an order of magnitude more quickly than ass erted code, they form a promising alternative for representing certain types of dynamic code, even in Prolog systems without tabling. (C) 19 99 Elsevier Science Inc. All rights reserved.