Click on the title to obtain a gzip-ed PostScript version of the paper (140K).
This version is almost identical to the JLP version.
Abstract:
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
pure top-down evaluation, due to the need for subgoals and answers to
access tables during resolution. This article describes the design,
implementation, and experimental evaluation of data structures and
algorithms for high-performance table access.
Our approach uses tries as the basis for tables. Tries, a
variant of discrimination nets, provide complete discrimination for
terms, and permit a lookup and possible insertion to be performed in a
single pass through a term. In addition, a novel technique of
substitution factoring is proposed. When substitution
factoring is used, the access cost for answers is proportional to the
size of the answer substitution, rather than to the size of the answer
itself.
Answer tries can be implemented both as interpreted structures and as
compiled WAM-like code. When they are compiled, the speed of
computing substitutions through answer tries is competitive with the
speed of unit facts compiled or asserted as WAM code. Because answer
tries can also be created an order of magnitude more quickly than
asserted code, they form a promising alternative for representing
certain types of dynamic code, even in Prolog systems without tabling.