7 Tabled execution (SLG resolution)
All Application Manual Name SummaryHelp

  • Documentation
    • Reference manual
      • Introduction
      • Overview
      • Initialising and Managing a Prolog Project
      • Built-in Predicates
      • SWI-Prolog extensions
      • Modules
      • Tabled execution (SLG resolution)
        • Example 1: using tabling for memoizing
        • Example 2: avoiding non-termination
        • Answer subsumption or mode directed tabling
        • Tabling for impure programs
        • Variant and subsumptive tabling
        • Well Founded Semantics
        • Incremental tabling
        • Monotonic tabling
        • Shared tabling
        • Tabling restraints: bounded rationality and tripwires
        • Tabling predicate reference
        • About the tabling implementation
      • Constraint Logic Programming
      • CHR: Constraint Handling Rules
      • Multithreaded applications
      • Coroutining using Prolog engines
      • Foreign Language Interface
      • Using SWI-Prolog in your browser (WASM)
      • Deploying applications
      • Packs: community add-ons
      • The SWI-Prolog library
      • Hackers corner
      • Compatibility with other Prolog dialects
      • Glossary of Terms
      • SWI-Prolog License Conditions and Tools
      • Summary
      • Bibliography
    • Packages

7 Tabled execution (SLG resolution)

This chapter describes SWI-Prolog's support for Tabled execution for one or more Prolog predicates, also called SLG resolution. Tabling a predicate provides two properties:

  1. Re-evaluation of a tabled predicate is avoided by memoizing the answers. This can realise huge performance enhancements as illustrated in section 7.1. It also comes with two downsides: the memoized answers are not automatically updated or invalidated if the world (set of predicates on which the answers depend) changes and the answer tables must be stored (in memory).

  2. Left recursion, a goal calling a variant of itself recursively and thus looping under the normal Prolog SLD resolution is avoided by suspending the variant call and resuming it with answers from the table. This is illustrated in section 7.2.

Tabling is particularly suited to simplify inference over a highly entangled set of predicates that express axioms and rules in a static (not changing) world. When using SLD resolution for such problems, it is hard to ensure termination and avoid frequent recomputation of intermediate results. A solution is to use Datalog style bottom-up evaluation, i.e., applying rules on the axioms and derived facts until a fixed point is reached. However, bottom-up evaluation typically derives many facts that are never used. Tabling provides a goal oriented resolution strategy for such problems and is enabled simply by adding a table/1 directive to the program.


Section Index


7.1 Example 1: using tabling for memoizing
7.2 Example 2: avoiding non-termination
7.3 Answer subsumption or mode directed tabling
7.4 Tabling for impure programs
7.5 Variant and subsumptive tabling
7.6 Well Founded Semantics
7.6.1 Well founded semantics and the toplevel
7.7 Incremental tabling
7.8 Monotonic tabling
7.8.1 Eager and lazy monotonic tabling
7.8.2 Tracking new answers to monotonic tables
7.8.3 Monotonic tabling with external data
7.9 Shared tabling
7.9.1 Abolishing shared tables
7.9.2 Status and future of shared tabling
7.10 Tabling restraints: bounded rationality and tripwires
7.10.1 Restraint subgoal size
7.10.2 Restraint answer size
7.10.3 Restraint answer count
7.11 Tabling predicate reference
7.12 About the tabling implementation
7.12.1 Status of tabling