Abstract
Traditional implementations of tabling in logic programming require extensive, low-level modifications to the Prolog engine. This paper introduces a novel, lightweight approach that implements tabling as a high-level library using delimited control. By leveraging the reset and shift primitives, the authors achieve a functional tabling system in under 600 lines of pure Prolog, offering a portable and maintainable alternative to engine-level implementations.
Introduction
In standard Prolog, SLD resolution is efficient but prone to infinite loops when encountering left recursion or cycles in data. Tabling (or memoization) solves this by storing sub-query results and suspending computations when cycles are detected. However, implementing tabling has historically required "surgical" changes to the Warren Abstract Machine (WAM), involving thousands of lines of complex C code. This paper explores whether tabling can be implemented as a high-level library without modifying the core engine.
Methodology: Tabling via Delimited Control
The authors utilize delimited control, specifically the primitives reset/3 and shift/1, to manage execution flow:
reset(Goal, Cont, Term): Establishes a boundary for the computation ofGoal. If ashiftoccurs, the remaining computation is captured inCont.shift(Term): Pauses execution and returns the current continuation to the nearestresetpoint.
The Implementation Strategy
- Source Transformation: Tabled predicates are split into a wrapper (handling table logic) and a worker (performing computation).
- Cycle Detection and Suspension: When a redundant ancestor call is detected, the library uses
shift/1to suspend the branch. - Dependency Tracking: Suspended continuations are stored as dependencies within the table data structures.
- Completion Phase: The library enters a fixed-point loop, repeatedly resuming suspended continuations with new answers until no further results can be generated.
Experimental Evaluation
The implementation was evaluated using standard logic programming benchmarks, including path problems, classic recursive tasks (like n-reverse and ping pong), and database-style joins. The library, running on hProlog, was compared against native tabling systems such as XSB, B-Prolog, and Ciao.
Key Results and Insights
- Conciseness: The entire control flow logic for tabling was reduced to just 60 lines of code, with the total library comprising 577 lines of Prolog. This is a massive reduction compared to traditional engine-level implementations.
- Performance: While the library-based approach is slower than native implementations, the overhead is considered reasonable for many applications. As shown in the benchmark table, the implementation is generally 8 to 38 times slower than XSB (the industry standard) and stays within a factor of 4 to 14 compared to Ciao.
- Portability: By relying on general-purpose delimited control primitives rather than WAM-specific hacks, the approach is easily portable to any Prolog system supporting
reset/shift.
Limitations and Future Work
The primary trade-off for this high-level approach is performance; it is significantly slower than native C-based implementations, making it less suitable for massive database queries or high-performance theorem proving. Additionally, the high-level nature of the library may introduce more memory overhead than low-level WAM management. Future work involves amortizing the development effort of delimited control by using these primitives to implement other advanced features, such as effect handlers.
Summary updated