Tabling — Brief ☧
Deep version → | Back to Streams →
Q: Let us return to the ancestor example from Datalog. A scribe wants to find all of Abraham's ancestors. The rule says: to find ancestors of X, find a parent of X, then find ancestors of that parent. So the scribe asks for Abraham's ancestors, which requires Terah's ancestors, which requires Nahor's ancestors, and so on up the line. What happens when the family tree has no more entries?
A: If the data is finite and the scribe is careful, he eventually runs out of parents and stops. But what if the records loop — say, a copying error links a later name back to an earlier one? Then the scribe would chase the same names around in circles forever.
Q: That sounds like a real problem. Have you ever looked up a word in a dictionary, only to find it defined in terms of another word, which is defined in terms of the first? Same trap.
A: Exactly. And even without loops, there is a second problem: redundant work. Suppose multiple queries need "ancestors of Jacob." Without coordination, each query recomputes the same answer from scratch.
Q: So how do you solve both problems — the circular trap and the redundant work?
A: The scribe keeps a table — a written record of every question he has already asked and every answer he has already found. When he encounters a query he has seen before, he looks up the table instead of recomputing. If the table has not changed since the last check, he knows the answer is complete and stops.
This is tabling (also called memoization for logic programs). It solves both problems at once:
- Loops: a repeated query hits the table instead of recursing infinitely
- Redundancy: each distinct query is computed only once, then reused
Q: Does tabling guarantee termination in all cases?
A: For Datalog-like programs — where the set of possible values is finite — yes, always. For general miniKanren with function symbols (which can create new terms indefinitely), tabling prevents redundant work but cannot guarantee termination over a truly infinite domain. The distinction mirrors the guardrails we saw in Datalog: more restrictions buy stronger guarantees.
What Tabling Does
| Without Tabling | With Tabling |
|---|---|
| Recomputes the same subgoal many times | Looks up cached answers |
| May loop on recursive queries | Detects repeated queries, terminates |
| Exponential time for some queries | Polynomial time complexity for Datalog |
| Like asking every elder the same question | Like writing answers in a book and consulting it |
SLG Resolution: The Algorithm
The standard tabling algorithm is called SLG resolution. Here is the flow:
graph TD
Q["New query: ancestor(abraham, X)?"]
Q --> CHECK{"Seen this query before?"}
CHECK -->|No| CREATE["Create table entry, start computing"]
CHECK -->|Yes| LOOKUP["Return cached answers + subscribe for new ones"]
CREATE --> COMPUTE["Derive new answers using rules"]
COMPUTE --> STORE["Store in table"]
STORE --> NOTIFY["Notify all subscribers"]
NOTIFY --> MORE{"Any new answers since last round?"}
MORE -->|Yes| COMPUTE
MORE -->|No| COMPLETE["Table complete — this query is done"]The key insight is the "subscribe" step: when a query finds an existing table, it does not just read the current answers — it registers to be notified if new answers appear later. This handles mutual recursion correctly: query A may depend on query B, and B on A, but neither loops because both are watching each other's tables.
The Bridge: Tabling IS Incremental Tensor Construction
This section deserves careful attention, because tabling is the conceptual bridge that connects the software world of streams and lazy evaluation to the hardware world of tensors and batch computation.
Each tabled relation is a sparse tensor being built incrementally:
- New query → create an empty tensor slice (all zeros — no known answers yet)
- Derive an answer → set a 1-bit in the tensor (this answer is now cached)
- No new answers → this slice of the tensor is complete (fixed point reached)
- Composed queries → tensor contraction using cached slices (reuse, not recompute)
This is why tabling is "The Bridge" between the lazy streams of miniKanren and the eager tensor computation on FPGA hardware. Streams discover answers one at a time, as if unrolling a scroll; tabling accumulates those answers into a growing data structure, like a scribe recording each discovery in a ledger; and once that ledger stabilizes (no new facts appear), it is the tensor the hardware operates on.
Think of it as a hash table of partial results that converges into a complete truth table — and that truth table is exactly the Boolean tensor the FPGA stores in its memory. The convergence process is Datalog-style fixed-point iteration, applied to the broader world of miniKanren queries. Tabling gives us the best of both worlds: the expressiveness and bidirectionality of miniKanren, with the guaranteed-termination and hardware-friendliness of Datalog.
Soli Deo Gloria