Orchestrata Ultimate › Plans › swi-tabling-capabilities

SWI-Prolog Tabling & Evaluation Capabilities — Authoritative Catalog

Source: plans/swi-tabling-capabilities.md at 8a2cb42ad · last changed 2026-07-27 · first committed 2026-07-10 · 581 lines.

Prose pending.

Plan text

SWI-Prolog Tabling & Evaluation Capabilities — Authoritative Catalog

Target runtime: SWI-Prolog 10.0.2, driven from Python via janus-swi. Scope: tabling (SLG resolution) and adjacent evaluation features that are "free" correctness/performance wins for a codebase doing transitive closures over dynamic facts, requirement-graph joins, governance/ownership recursion, and per-request assert → query → retract fact lifecycles.

Every claim below cites the SWI-Prolog reference-manual section it comes from. Sections referenced (all under pldoc/man?section=): tabling, tabling-subsumptive, tabling-incremental, tabling-monotonic, tabling-mode-directed, tabling-restraints, tabling-shared, WFS, tabling-preds.

Load-bearing project constraint (memory: Governance Prolog migrated to janus): keep variable-bearing rules in .pl files loaded via consult, and only assertz ground facts from Python. All tabling directives below belong in the .pl source, not in strings asserted at runtime.

0. Mental model (§tabling)

Tabling = SLG resolution = memoization of a predicate's answers in an answer trie. Two distinct wins, per §tabling:

1. Memoization — "Re-evaluation of a tabled predicate is avoided by memoizing the answers." Repeated identical subgoals are answered from the trie, not recomputed.
2. Termination on recursion — "Left recursion, a goal calling a variant of itself recursively and thus looping under normal Prolog SLD resolution is avoided by suspending the variant call and resuming it with answers from the table." This makes naive transitive-closure clauses (path(X,Z):-path(X,Y),edge(Y,Z)) terminate and run in polynomial time instead of looping forever.

The universal gotcha (§tabling): do not table predicates with side effects (I/O, assertz, format, sending CXP packets) and do not table infinite-answer predicates — "If you table predicates with infinitely many solutions you simply run out of (table) memory." A tabled predicate is a pure relation; side effects belong in untabled driver predicates.

Base directive:

:- table path/2.                 % single predicate
:- table (path/2, reach/2).      % multiple, comma list in parens

1. Variant tabling — the default (§tabling)

What it does

Creates one table per call variant. Per §tabling-subsumptive: "A call (term) is a variant of another call (term) if there is a renaming of variables that makes the two terms equal." So path(a,X), path(b,X), path(X,Y) each get their own table; path(a,X) and path(a,Y) share one (renaming).

Syntax (works on 10.x)

:- table ancestor/2.

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

When to use

The default for every recursive/derived relation: transitive closures, reachability, requirement-graph joins, ownership chains. It is the single biggest correctness win — it turns non-terminating left-recursive Datalog into terminating, deduplicated, polynomial evaluation.

Gotchas

• No cuts across the tabled boundary; cuts inside a tabled clause are local and can make tables incomplete — avoid ! in tabled predicates.
• Answer order is not the Prolog clause order (§tabling user note: "a tabled predicate may well change the order of solutions if used as generator"). Never rely on solution order from a tabled predicate.
• Every distinct bound call pattern allocates a table; a workload that calls path(k, _) for thousands of distinct k builds thousands of tables (see §2 subsumptive and §7 restraints/abolish for mitigation).

2. Subsumptive tabling — as subsumptive (§tabling-subsumptive)

What it does

Instead of a table per variant, answers a specific query from a more general table. Per §tabling-subsumptive it "answers a query using answers from a more general table" — e.g. p(42) is resolved by running trie_gen/2 over the existing p(_) table rather than computing a fresh table for p(42).

Syntax

:- table p/1 as subsumptive.

Or globally: :- set_prolog_flag(table_subsumptive, true).

When to use

Workloads that issue many specific queries (reachable(root, leaf_i)) whose answers are all subsumed by one general computation (reachable(root, _)). §tabling-subsumptive reports the general vs. subsumptive contrast on its example: variant tabling took ~150M inferences / 13.256 s (quadratic — one table per specific call), subsumptive took 140,066 inferences / 0.015 s. This is the fix for "one table per bound key" blowup.

Gotchas (§tabling-subsumptive)

1. Correctness only for pure programs: "only provides correct support if instances (more specific) queries indeed provide answers that are consistent with the more general query. This is true for pure programs, but not guaranteed for arbitrary Prolog programs." If the predicate's answers depend on the binding pattern (e.g. a guard that behaves differently when an arg is bound), subsumptive tabling is wrong.
2. Lookup overhead: "Finding more generic tables is more complicated and expensive" and extracting the matching subset "can be expensive."
3. More call-graph dependencies can slow table completion.

Use it when the general call is cheap to fully materialize and specific queries are many; avoid it when the general call is unbounded/huge (materializing all of p(_) to answer one p(42) is a loss).

3. Incremental tabling — as incremental + dynamic-as-incremental (§tabling-incremental)

What it does

Keeps tables consistent with the dynamic facts they were derived from, via an Incremental Dependency Graph (IDG). When you assert/retract an incremental dynamic predicate, all dependent tables are marked invalid and lazily re-evaluated on next call, bottom-up. If a re-evaluated table is unchanged, that fact propagates and cascading re-evaluation is skipped.

Syntax (both sides MUST opt in)

:- table (p/1, q/1) as incremental.
:- dynamic([d/1], [incremental(true)]).

p(X) :- q(X).
q(X) :- d(X), X < 10.
d(1).

After assert(d(100)): §tabling-incremental — both p/1 and q/1 tables are marked invalid; re-running p(X) re-evaluates q/1 first (100 fails X<10, so no change), and the unchanged result prevents re-evaluating p/1.

When to use

This is the central feature for assert → query → retract fact lifecycles over derived relations. It lets you keep a warm transitive-closure/derived-fact table across many edits instead of abolish-ing and recomputing from scratch on every fact change.

Gotchas / constraints

• All dynamic predicates in the dependency chain must be declared incremental (incremental(true)), and all tabled predicates that consume them must be as incremental. Mixing a plain dynamic fact into an incremental table silently breaks invalidation — the table won't be told the fact changed.
• Invalidation granularity is the whole table, not the clause (§tabling-incremental: "invalidating and re-evaluation is done at the level of tables"). A one-fact change can force full re-evaluation of an affected table. For high-churn single-fact additions, consider monotonic tabling (§4).
• Cannot be combined with shared tabling (§tabling-shared: shared tables "cannot handle well-founded semantics or incremental tabling").
• Lazy by default: re-evaluation happens at query time, so the cost lands on the next reader, not the writer.

4. Monotonic tabling — as monotonic (§tabling-monotonic)

What it does

For monotonic programs (adding facts only ever adds answers, never removes them), propagates the consequences of an assertion forward through the IDG without invalidating/recomputing the table — strictly cheaper than incremental when the change is purely additive.

Syntax

:- table connected/2 as monotonic.
:- dynamic link/2 as monotonic.

% lazy variant — queue the update, apply on next call:
:- table p/1 as (monotonic, lazy).

Feeding external/streamed edges (from library(increval)), call after the data update:

:- use_module(library(increval)).
on_new_edge(X, Y) :- incr_propagate_calls(link(X, Y)).

Eager vs lazy (§tabling-monotonic)

• Eager (default): "an asserted clause is immediately propagated through the dependency network" — the writer pays; readers are always warm.
• Lazy (as (monotonic,lazy)): "dependent monotonic or incremental tables are invalidated and the answer is queued"; re-evaluated on the next call.

When to use

Append-only graphs: monotonically growing containment/dependency/ownership edges where you add edges and want derived closures to stay warm with minimal work per add.

Gotchas / constraints (§tabling-monotonic)

• No negation — "can only deal with monotonic programs, in particular it does not deal with negation."
• Retraction falls back to incremental: "When using retract/1 on a dynamic monotonic predicate, all dependent tables and dependency links are invalidated and marked for normal incremental update." So retracts lose the monotonic advantage — fine if retracts are rare.
• Dependency rule: "A tabled predicate that depends on a monotonic tabled predicate must be tabled monotonic or incremental."
• Manual status: "Monotonic tabling is experimental and incomplete." Treat as a targeted optimization for append-heavy paths, validated against an incremental baseline — not a default.

5. Mode-directed tabling / answer subsumption / aggregation (§tabling-mode-directed)

What it does

Designates some arguments as outputs that are aggregated rather than tabled keys, so the table keeps a single aggregated value per key group instead of every answer. Per §tabling-mode-directed this is the fix for "there are infinitely many routes if there are cycles in the network and each new route found will be added to the answer table" — aggregation collapses those to one best value and makes cyclic-graph queries terminate.

Syntax & full mode table (§tabling-mode-directed)

:- table predicate(+Mode1, +Mode2, +AggMode).

Canonical shortest-path example (§tabling-mode-directed, verbatim shape)

:- table connection(_, _, lattice(shortest/3)).

shortest(P1, P2, P) :-
    length(P1, L1),
    length(P2, L2),
    ( L1 < L2 -> P = P1 ; P = P2 ).

connection(X, Y, [X, Y]) :- connection(X, Y).
connection(X, Y, P) :-
    connection(X, Z, P0),
    connection(Z, Y),
    append(P0, [Y], P).

lattice(shortest/3) runs shortest/3 on every newly found path, retaining only the shortest — so a cyclic network yields a finite table and a min-hop answer.

Min-hop-count / reachability-with-cost variants:

:- table hops(_, _, min).        % keep the minimum hop count per (From,To)
hops(X, Y, 1) :- edge(X, Y).
hops(X, Y, N) :- edge(X, Z), hops(Z, Y, N0), N is N0 + 1.

When to use

Shortest/cheapest-path, min-hop reachability, "does a path exist + what's the best cost", cheapest-owner, highest-priority-requirement-satisfying. Any query of the form "aggregate over all derivations" where you want the aggregate, not the enumeration.

Gotchas

• The aggregation predicate (lattice/po) must be a correct semilattice/partial order or the table can be non-deterministic/incorrect.
• Aggregation loses the individual answers — if you also need the enumeration, table a separate variant predicate.
• min/max use standard order of terms, not numeric compare, unless the term is a bare number; wrap costs as plain numbers or use lattice/3 with an explicit comparator.

6. Well-founded semantics & tabled negation — tnot/1 (§WFS)

What it does

Gives a three-valued logic — true / false / undefined — so recursive programs with negation have a well-defined model instead of looping or giving wrong answers. §WFS: undefined "is neither true nor false in the well formed model."

Syntax (§WFS, verbatim)

:- table p/0, q/0.
p :- tnot(q).
q :- tnot(p).

% the canonical paradox -> undefined, not a loop:
:- table undefined/0.
undefined :- tnot(undefined).

tnot(Goal) "must be a goal associated with a tabled predicate." For non-ground or non-tabled negation use not_exists/1 (§tabling-preds: "Handles tabled negation for non-ground (floundering) Goal as well as non tabled goals"; its helper is tabled_call/1, defined tabled_call(Goal) :- call(Goal)).

Introspecting undefined answers (§WFS)

• call_residual_program(:Goal, -Program) — Goal's truth status + residual program ([] if unconditionally true).
• call_delays(:Goal, -Condition) — the condition under which Goal holds.
• delays_residual_program(:Condition, -Program) — clauses for the conditional answers.
• Flag toplevel_list_wfs_residual_program — when true, prints why answers are undefined.

When to use

Governance/ownership recursion with negation-as-failure over recursive relations: "a resource is denied unless some ancestor grants it," "conflict = A blocks B and B blocks A." Plain \+/1 uses a cut and, per §tabling, "one may end up with incomplete tables and incorrect results" — tnot/1 is the correct construct whenever negation sits inside a tabled recursive cycle.

Gotchas

• Never use \+/1 / not/1 inside a tabled recursive predicate — §tabling: "There is no negation in SWI-Prolog's tabling. As not/1 uses a cut, one may end up with incomplete tables and incorrect results." Use tnot/1 (or not_exists/1).
• undefined is a real answer value: a governance query can come back undefined (paradoxical rules). Decide a policy — treat undefined as deny, or surface it — and test for it via call_delays/2. From janus this means a solution may be conditional; check for residual delays rather than assuming binary true/false.
• Cannot combine with shared tabling (§tabling-shared).

7. Restraint / bounded rationality — guaranteed termination (§tabling-restraints)

What it does

Bounds tabling resources so evaluation always terminates even on cyclic or unbounded graphs, marking capped results undefined (under WFS) rather than looping or OOM-ing. Three restraint dimensions (§tabling-restraints):

1. Answer count — max_answers(N) / flag max_answers_for_subgoal. Cap answers per subgoal; overflow marks the extra derivations answer_count_restraint (undefined).
2. Subgoal size — attribute subgoal_abstract(Size); oversized compound subterms are replaced by variables. Example: p(s(s(s(s(s(0)))))) abstracted to size 3.
3. Answer size — attribute answer_abstract(Size); caps answer-substitution size.

Syntax (§tabling-restraints, verbatim)

:- table p/2 as max_answers(3).

Combine with other modes/attributes in the as (...) list, e.g. :- table path/3 as (incremental, max_answers(1000)).

Global flags & actions (§tabling-restraints)

Tripwire mechanism (§tabling-restraints): on trigger, calls hook prolog:tripwire/2; if it fails, applies the configured action — warning (print + continue), error (throw resource_error(tripwire(Wire,Context))), or suspend (print + break level).

Undefinedness markers: radial_restraint marks results undefined when subgoal/answer size restraints fire; answer_count_restraint marks them undefined when max_answers fires — enabling bounded_rationality mode to distinguish capped answers from clean ones. Helper: size_abstract_term/3, e.g. size_abstract_term(1, ret(f(x), x(y(Z))), ret(f(x), x(_))).

Example of a capped result carrying its restraint (§tabling-restraints):

?- p(1000000, X).
X = 3 ; X = 2 ; X = 1 ;
p(1000000, X) :- answer_count_restraint.   % remaining answers are undefined

When to use

Any query over untrusted / unbounded / potentially cyclic external graph data where you must guarantee a bounded response time — request-scoped closures over facts a client just asserted. Restraint is the safety valve that turns "might OOM / might loop" into "always returns, possibly with undefined tail."

Gotchas

• Capped answers are undefined, not absent — callers must handle three-valued results (same discipline as §6). Silently treating a capped table as complete is a correctness bug.
• Size abstraction changes the subgoal, so an abstracted table answers a more general query than asked — verify that's acceptable for the relation.

8. Shared / concurrent tabling — as shared (§tabling-shared)

What it does

Lets multiple threads share one table instead of each maintaining a private copy — directly relevant to the free-threaded (no-GIL) Python 3.14t runtime driving Prolog via janus across worker threads.

Syntax

:- table (p/1, q/2) as shared.

Semantics (§tabling-shared)

A thread hitting a shared variant sees one of three states:

• Complete — use answers immediately.
• Fresh/non-existent — thread claims ownership and populates it.
• Incomplete — if owned by this thread, continue; if owned by another, wait — "unless there is a cycle of threads waiting for each other's table," which raises a deadlock exception, abandoning the current SCC and letting another thread take over.

Abolishing (§tabling-shared): "abolishing a shared table has no effect on the semantics of the tabled predicates" — incomplete tables are marked for destruction on completion; waiters then see a fresh table.

When to use

Read-heavy derived relations that are stable across requests (e.g. a static requirement/spec graph, code-intelligence closures) and are queried concurrently by many worker threads. One thread computes, all share.

Gotchas / constraints (§tabling-shared)

• Mutually exclusive with WFS and incremental tabling: "Shared tabling currently ... cannot handle well-founded semantics or incremental tabling." So you cannot make a table both shared and incremental, nor shared and use tnot. Shared tabling suits static shared knowledge; per-request mutable closures stay private+incremental.
• "Only answer reclamation occurs; table structures persist" — memory of the trie skeleton is not fully reclaimed.
• Abolishing shared tables "may cause unnecessary thread waiting."

9. Lifecycle & introspection predicates (§tabling-preds)

Verbatim signatures/descriptions:

Lifecycle patterns for assert → query → retract (per-request)

• Prefer incremental tabling (§3) so you never manually abolish — asserts/retracts invalidate exactly the affected tables and re-evaluate lazily.
• If a request uses a plain (non-incremental) tabled derived predicate over facts it mutates, you must clear stale tables. Use the narrowest abolish: abolish_table_subgoals(path(RequestScope, _)) — never abolish_all_tables/0 per request (it nukes every other request's warm tables and any static shared knowledge).
• current_table/2 is the introspection hook to check whether a variant is already materialized (from janus: probe before deciding to recompute vs. reuse).

10. janus-swi integration notes

• All directives (:- table ..., :- dynamic ... as incremental) live in the .pl source consulted at load — not in runtime-asserted strings (project rule: only assertz ground facts from Python; keep rules/directives in files).
• A tabled query called from Python (janus.query_once / janus.query) returns memoized answers; side-effecting predicates must stay untabled — never table a predicate that emits CXP packets, logs, or writes the KG.
• Three-valued results (WFS §6, restraint §7) cross the boundary as conditional answers with residual delays. From Python, a governance decision may be undefined — detect via call_delays/2 / call_residual_program/2 and apply an explicit policy (recommend: undefined ⇒ deny + escalate), rather than treating the row as false.
• Under the free-threaded runtime, mark static shared knowledge as shared (§8); keep per-request mutable closures private + as incremental (they are mutually exclusive).

11. Ranked opportunities for THIS codebase

Workload shape: (a) transitive containment/dependency closures over dynamic facts, (b) requirement-graph joins, (c) governance/ownership recursion, (d) per-request assert → query → retract fact lifecycles.

Tier 1 — adopt now (biggest correctness + perf win, low risk)

1. Variant tabling on every recursive/derived relation (§tabling). Containment closures, dependency reachability, requirement joins, ownership chains. Converts non-terminating left recursion into terminating polynomial evaluation and dedups answers. This is the headline free win. Cost: none beyond declaring :- table. Trap avoided: remove any \+/cut inside these predicates first (§6).

2. Incremental tabling for the per-request assert→query→retract lifecycle (§3). Exactly the "warm derived table that survives fact edits" pattern. Declare the derived predicates as incremental and every dependent dynamic fact dynamic([f/n],[incremental(true)]). Eliminates the recompute-from-scratch cost on each fact change. Trap: one non-incremental dynamic dep silently breaks invalidation → stale wrong answers. Mutually exclusive with shared (§8) and WFS (§6).

3. tnot/1 for governance/ownership recursion with negation (§6/WFS). Any rule of the form "deny unless an ancestor grants," "mutual-block conflict." Using \+ here is an active correctness bug (§tabling: incomplete tables, incorrect results). Free correctness win; cost = handle the possible undefined result (deny+escalate policy).

Tier 2 — high value, targeted

4. Mode-directed aggregation for shortest/cheapest/min-hop path & reachability-with-cost (§5). Replaces "enumerate all paths then aggregate in Python" with a single lattice(shortest/3) / min table that terminates on cyclic graphs and returns the best value directly. Big win wherever a closure query really wants an aggregate.

5. Restraint (max_answers, size abstraction) on any closure over client-supplied / potentially-cyclic graph data (§7). Guarantees bounded, always-returning queries for per-request asserted facts. Ship it as the safety valve on request-scoped tabled predicates. Cost = treat capped/undefined tails correctly (same handling as §6).

6. Subsumptive tabling where many specific keys are subsumed by one general closure (§2) — e.g. thousands of reachable(root, leaf_i) from one reachable(root,_). Turns per-key quadratic table blowup into one table. Only for pure relations; verify answers don't depend on binding pattern.

Tier 3 — situational

7. Shared tabling for static shared knowledge under the no-GIL runtime (§8): stable spec/requirement graph, code-intelligence closures queried by many worker threads. One thread computes, all share. Cannot be combined with incremental or WFS — so only for read-only static graphs, never per-request mutable closures.

8. Monotonic tabling for append-only edge streams (§4): if containment/dependency edges are added and rarely retracted, as monotonic keeps closures warm more cheaply than incremental. Experimental/incomplete — validate against an incremental baseline; retracts fall back to incremental anyway.

Traps to avoid (explicitly)

• Never table a side-effecting predicate (§tabling) — CXP emit, KG write, logging, assertz. Tabling caches answers and suppresses re-execution; side effects vanish or duplicate unpredictably.
• Never use \+/not/1/cut inside a tabled recursive predicate (§tabling/§WFS) — incomplete tables, wrong results. Use tnot/1/not_exists/1.
• Never abolish_all_tables/0 per request (§9) — it destroys every other request's warm tables and all static shared knowledge. Use abolish_table_subgoals/1 scoped to the request, or (better) incremental tabling so no manual abolish is needed.
• Don't mix incremental derived tables with non-incremental dynamic deps (§3) — invalidation silently won't fire.
• Don't combine shared with incremental/WFS (§8) — unsupported; pick per table.
• Don't rely on tabled solution order (§1) — tabling reorders answers.
• Don't table infinite-answer predicates without restraint (§tabling/§7) — OOM; bound with max_answers/size abstraction or aggregate with mode-directed tabling.

12. Applied status + next targets in THIS repo (2026-07-10)

DONE (shipped, verified)

• kg_relevance.pl (SPEC-106 FR-006) — contains/2, shares_requirement/2, shares_requirement_with_root/1, defines_from_root/1 tabled as incremental; all 7 projected dynamic facts as incremental. Tier 1 #1+#2. \+ kept OUT of the tabled predicates (they live in untabled core_for/2/kg_relevance_tier/2), avoiding trap §6/§2. Chose incremental over abolish_all_tables per trap #3. Verified: 15 tests + cross-refinement janus proof.
• knowledge.pl — depends_on_transitive/2 tabled as incremental (depends_on/2 made incremental). Tier 1 #1. Fixed a latent NON-TERMINATION bug (the A \= B guard does not stop a->b->a cycles). Verified: governance suite 95 green + janus cycle-termination proof.

NEXT TARGETS (ranked, with concrete repo anchors)

1. Restraint on knowledge.pl:ownership_chain/3 (Tier 2 #5, §7). It builds an unbounded list ([AgentId|Rest]) over the same cyclic owns/depends_on graph — plain tabling would enumerate infinite lists on a cycle. Add :- table ownership_chain/3 as (max_answers(N)) (or size abstraction) so it terminates bounded. Handle the capped/undefined tail as deny+escalate.
2. tnot/1 audit before tabling any negation-bearing governance predicate (Tier 1 #3, §6). constitutional.pl:assess_harm/3 has SELF-referential negation (\+ assess_harm(...) inside assess_harm/3); it is safe ONLY while untabled. Do NOT table it (or ethics.pl harm rules) without converting the self-negation to tnot/1 — else incomplete tables/wrong results. Currently cheap ground-fact lookups → leave untabled.
3. Mode-directed aggregation for min-hop / shortest escalation path (Tier 2 #4, §5). agents.pl:escalation_path/3 and cxp.pl:escalation_path/2 + any future min-containment-depth need — replace enumerate-then-aggregate with a lattice(shortest/3)/min table that terminates on cyclic graphs.
4. Shared tabling for static KG closures under the no-GIL (3.14t) runtime (Tier 3 #7, §8). Spec/requirement/code-intelligence closures are read-only and queried by many worker threads — as shared lets one thread compute, all share. BLOCKED on the concurrency model: PrologBridge is single-worker-thread today; revisit if/when queries fan out across threads. Cannot combine with incremental/WFS, so only for static graphs.

Related

• Plans
• Orchestrata Ultimate — project index
• Workflow
• Tasks