Top-down and Bottom-up Evaluation Procedurally Integrated

EasyChair Preprint 206

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: Prolog, Tabling, bottom-up, logic programming, procedural interpretation, top-down

@booklet{EasyChair:206,
  author    = {David Scott Warren},
  title     = {Top-down and Bottom-up Evaluation Procedurally Integrated},
  doi       = {10.29007/94bv},
  howpublished = {EasyChair Preprint 206},
  year      = {EasyChair, 2018}}