TL;DR
This paper introduces a novel, lightweight implementation of tabling for Prolog, achieved by leveraging delimited control. This approach significantly lowers the barrier to entry for Prolog systems wanting to support tabling, as it requires minimal changes to the Prolog engine and is implemented entirely in Prolog itself.
What Problem Does This Paper Address?
Tabling is a powerful extension to Prolog that enhances its declarative nature, improves termination properties, and can significantly boost performance by memoizing results. Despite these advantages, most Prolog systems do not implement tabling. This is primarily due to the substantial engineering effort required by existing implementations, which often necessitate deep modifications to the Prolog engine (like those in XSB or Yap). This high cost makes tabling inaccessible for many Prolog systems. The paper aims to bridge this gap by providing an implementation that is easy to integrate and maintain.
Methods
The core innovation of this paper is the use of delimited control as the primary mechanism for implementing tabling. Delimited control, a concept originating from functional programming and recently introduced to Prolog, allows for fine-grained manipulation of program control flow.
The authors' approach involves a shallow program transformation. Instead of altering the Prolog engine, tabled predicates are wrapped with a new predicate, table/2. This table/2 predicate acts as an intermediary, managing the tabling logic.
Key aspects of their method include:
- Delimited Continuations (
reset/shift): These built-ins are used to capture and manage suspended computations. When a tabled predicate is called,reset/3sets up a context. If a recursive call to a tabled predicate is encountered (a "follower"),shift/1captures the remaining computation as a continuation and yields control. - Leader/Follower Model: Calls to tabled predicates are categorized as "leaders" (those with non-tabled ancestors) and "followers" (those with tabled ancestors). Leaders initiate answer computation, while followers suspend and yield control via
shift/1. - Scheduling Components: A leader and its followers form a "scheduling component." The system manages multiple such components concurrently.
- Completion Phase: After initial answer collection, a "completion" phase computes the least fixpoint of the program, ensuring all possible answers are found. This phase uses dependencies recorded during the suspension of followers.
- Data Structures: The implementation relies on a global repository of tables (implemented as a trie, or "call trie") to store results and a worklist for managing the completion phase.
Datasets
Not discussed in the paper. The paper focuses on the implementation of tabling itself and evaluates its performance on a set of standard Prolog benchmarks.
Key Insights and Ideas
- Tabling as a Library: The most significant insight is that tabling can be effectively implemented as a library using existing Prolog features (delimited control) rather than requiring core engine modifications. This drastically reduces the implementation complexity and makes tabling accessible to a much wider range of Prolog systems.
- Delimited Control as a Unifying Primitive: The paper demonstrates the power of delimited control beyond its typical use cases, showing its suitability for managing complex control flow patterns inherent in tabling, particularly for handling recursive calls and suspensions.
- Lightweight Transformation: The "shallow program transformation" is key. It avoids complex program analysis or meta-interpretation, making the integration process much simpler.
- Leader/Follower Distinction: This elegantly handles the interaction between new tabled calls and ongoing computations, ensuring correct suspension and resumption.
- Fixpoint Computation via Dependencies: The completion phase, driven by dependencies, is a clever way to ensure termination and completeness for programs that might otherwise not terminate with standard SLD resolution.
Key Results
The paper presents a functional implementation of tabling in under 600 lines of Prolog code. While raw performance is not the primary goal, the implementation achieves reasonable performance, especially considering its lightweight nature.
- Implementation Effort: The entire tabling library, including control flow, data structures (tries and worklists), and glue code, amounts to 577 lines of Prolog code. This is significantly less than the effort required for deep engine modifications.
- Performance Comparison: The implementation was compared against established tabling systems like XSB, B-Prolog, Yap, and Ciao. While it is generally slower than these systems (e.g., 8 to 38 times slower than XSB), its performance is considered "very reasonable" given the stark contrast in implementation complexity. The paper highlights that XSB, for instance, is significantly faster but requires much more memory.
Limitations and Future Work
- Performance Trade-off: The authors acknowledge that there is a trade-off between the simplicity of their implementation and runtime performance. Their system is not as fast as highly optimized, engine-integrated tabling systems.
- Continuation Copying: Continuations are copied using
copy_term/2, which can be inefficient. A specializedcopy_continuation/2could improve performance. - Static Analysis: The system does not statically identify strongly connected components in the scheduling component, which could allow for further optimization of the completion phase.
- Substitution Factoring: Their trie implementation does not use substitution factoring, which is a technique used in some state-of-the-art implementations to improve trie efficiency.
- Future Work: The authors suggest extending their approach with mode-directed tabling, which they believe would require only a small change to the trie structure. They also mention the potential for optimizing continuation copying and exploring static analysis for strongly connected components.
Summary updated