Download PDFOpen PDF in browser

Top-down and Bottom-up Evaluation Procedurally Integrated

EasyChair Preprint no. 206

16 pagesDate: May 31, 2018

Abstract

This paper describes how 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.

Keyphrases: bottom-up, logic programming, procedural interpretation, Prolog, Tabling, top-down

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@Booklet{EasyChair:206,
  author = {David Scott Warren},
  title = {Top-down and Bottom-up Evaluation Procedurally Integrated},
  howpublished = {EasyChair Preprint no. 206},
  doi = {10.29007/94bv},
  year = {EasyChair, 2018}}
Download PDFOpen PDF in browser