Top-down and Bottom-up Evaluation Procedurally Integrated. Issue 3 (10th August 2018)

• Record Type: Journal Article
• Authors: WARREN, DAVID S.
• Editors: Dal Palu, Alessandro; Tarau, Paul
• Is Part Of: Theory and practice of logic programming. Volume 18:Issue 3/4(2018)
• Page Start: 706
• Page End: 721
• Publication Date: 2018-08-10
• Subjects: top-down, -- bottom-up, -- logic programming, -- tabling, -- Prolog, -- procedural interpretation; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068418000194
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: This paper describes how the Logic Programming System XSB combines top-down and bottom-up computation through the mechanisms of variant tabling and subsumptive tabling with abstraction, respectively. It is well known that top-down evaluation of logical rules in Prolog has a procedural interpretation as recursive procedure invocation (Kowalski 1986). Tabling adds the intuition of short-circuiting redundant computations (Warren 1992). This paper shows how to introduce into tabled logic program evaluation a bottom-up component, whose procedural intuition is the initialization of a data structure, in which a relation is initially computed and filled, on first demand, and then used throughout the remainder of a larger computation for efficient lookup. This allows many Prolog programs to be expressed fully declaratively, programs which formerly required procedural features, such as assert, to be made efficient.