⏺ Stage A is built and green. Summary: #20
Loading…
Add table
Add a link
Reference in a new issue
No description provided.
Delete branch "fact-table-stage-A"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
What landed
Runtime (crates/runtime/src/builtins/facts.rs, + mod.rs): plg_rt_fact_first
/ plg_rt_fact_next / fact_scan — a generic full-scan lookup that mirrors
between/3's nondeterministic shape: a control frame holds the snapshot args
point captures pre-binding marks so backtracking undoes the delivered row.
The helpers find/bind/push-CP and return; delivery to the continuation is a
musttail in the generated IR (see below).
Codegen (crates/compiler/src/codegen/facts.rs, + program.rs routing &
decls, mod.rs): a qualifying predicate emits one .rodata table of immediate
words (row-major, program order) + a tiny entry fn and _ftr retry fn that
call the runtime lookup and musttail the continuation. Registered under the
normal pred_symbol, so call/findall/query dispatch reach it like any
predicate — no registry change.
The key design point: delivery is a musttail in the generated entry/retry
functions, not a Rust call to k. A Rust helper calling k would leave its
frame on the C stack per recursion level — overflowing on recursion through
a fact predicate. Returning first keeps the constant-stack guarantee.
(Recorded in memory so Stages B/C preserve it.)
Checkpoints
corpus runs findall/call/recursive path over fact predicates); the
family.pl suite passes unchanged.
table + two functions, compiles in ~125ms.
predicates).
backtracking, ground true/false, int columns both directions, --limit,
findall/call re-entry, recursive rule over the edge table, a
compound-column fact staying per-clause in the same binary, undefined →
existence_error. Plus deep_recursion_runs_in_constant_c_stack already
recurses 2000-deep through a fact table under a 512KB stack.
Tests: 3 golden-IR tests repointed to non-qualifying inputs (preserving
their per-clause/indexing coverage) + 1 new fact-table golden test, per
your "repoint + add" choice. Full workspace green, clippy + fmt clean.
Two honest notes
the card's "atom/int/float." Float and big-int are boxed scalars
(non-immediate), so they need the same column-encoding work as compounds —
I folded them into the deferred Stage C rather than half-encode floats now.
Verified the fallback: big(i64::MAX) and coords(origin, point(0,0)) both
stay per-clause and work.
runtime → undefined plg_rt_fact_*); a rebuild refreshed it. Known stable
limitation, not a regression.
Deferred to follow-ups: first-arg index + binary search (Stage B),
compound/float/big columns (Stage C), and the dedicated 100k compile-time +
fact-table-vs-per-clause size benchmarks the design lists as confirming
evidence.
Review — Fact-table compilation, Stage A
Substantial PR, and the architectural calls are right. The headline decision — delivery is a
musttailin the generated entry/retry IR, NOT a Rust call tokfrom the runtime helper — is exactly the discipline that keeps recursion through a fact predicate constant-stack. The runtime helper finds/binds/pushes-CP and returns; the IR'sdeliver:block tail-calls. Without this, a recursivepath/2over anedgetable would overflow the C stack proportional to recursion depth. Worth the prominent placement in the doc comments.Other strong calls:
is_fact_predicateruns per(functor, arity); mixed programs compile with per-predicate routing. No all-or-nothing.plg_rt_fact_first). N solutions don't allocate N frames.pred_symbol, socall/findall/query dispatch reach it like any other predicate.is_fact_predicatenarrows columns to atom + i61-integer. Compound/float/big-int correctly fall back to per-clause (proven bycompound_column_predicate_stays_per_clause). Half-encoding floats now would have been the wrong scope expansion.if i + 1 < nrows { push_cp(...) }saves an allocation when the matching row is the last.Issues below, ordered by impact.
Real concerns
1. Stage A full-scan with no first-arg index is correct but doesn't yet test the headline claim. The design's compile-time win (O(1) data emission vs O(N) functions) is structurally argued and the structural argument is sound. But the runtime claim — that fact-table queries stay reasonable at 100k facts — leans on Stage B's binary-search index, which isn't here. A
parent(tom, X)against a 100k-row table scans all 100k rows linearly per solution. Checkpoint 2 in FACT_TABLE.md asks for "a 100k-fact predicate compiles in roughly constant data-emission time; record IR size + clang time before/after." The PR has 5000 facts compiling in ~125ms structurally but no measured 100k number. Worth either landing the benchmark now (it's a one-off shell script — doesn't need to be CI) or marking checkpoint 2 explicitly as "structurally ✅, measurement deferred" in the doc. Right now FACT_TABLE.md and the PR description both call it ✅, which is ahead of the evidence.2. The
unsafe transmute::<usize, ContFn>is repeated at two sites.facts.rs:Each one is the same invariant: "a heap cell stores a ContFn we wrote via
ptrtointin the IR." A helper:documents the invariant once and centralizes the unsafe surface. Stage B/C will add more raise sites; centralizing now is cheap.
3. The double-unify-and-rewind on a matching row is correct but wasteful.
fact_scan's match path:rewind_to(clean_t, clean_h)undoes step 1push_cp(retry, frame)captures clean trail heightThat's
2Nunifications per matching row in the success case. For a 100k-fact predicate where every row matches (e.g.findall(X, fact(X), L)), that's 200k unification ops where 100k would suffice. A future optimization can:trail_mark = m.trail.len()before the first unifypush_cp(retry, frame)records the captured mark as the restore-pointDefer to Stage B alongside the index, but worth noting now while the design is fresh. The current shape is correct; that's what matters for Stage A.
Small observations
4. The asymmetry between
plg_rt_fact_firstandplg_rt_fact_next.firstsavesm.k_fn/m.k_env/m.qbarrierinto the frame but does not restore them afterfact_scan(it relies on the invariant thatm.k_fnis untouched at the timedeliver:reads it).nextdoes restore them because the solve driver may have overwritten them between CP push and CP pop. The asymmetry is correct, but a one-line comment infirstsaying "no restore needed: the caller's k_fn is still in m.k_fn from the entry frame" would save a future reader the analysis I just did.5. The
i64-as-pointer ABI is consistent with the rest of the runtime (all heap cells are u64;ptrtoint/inttoptrround-trips). Worth knowing that Rust'sextern "C"could accept*const Word/ContFndirectly on the Rust side and the IR could passptr— eliminating twoas usize as *const Wordcasts at the cost of a non-uniform ABI. Current shape is the right trade-off for v1; flag for a future "type the FFI better" pass.6. Empty fact predicates fall back to per-clause.
is_fact_predicatereturnsfalseforclauses.is_empty(). A 0-row table would actually work (the loop infact_scandoesn't execute), but the per-clause path already handles empty predicates correctly so the asymmetry is fine. Worth a one-line comment justifying the exclusion ("empty predicates are routed viadynamic_only/ per-clause; we don't need to duplicate the path here") so it doesn't read like an accidental gap.7. Build.rs mtime archive-staleness bit again. Author flagged it explicitly: "stale embedded runtime → undefined
plg_rt_fact_*; a rebuild refreshed it. Known stable limitation, not a regression." Confirmed real, not just theoretical (PR #15 review #3). Each new runtime ABI addition is one more opportunity to hit it. Worth tracking — the longer this lives, the more dev-loop friction it adds, and the easier it is for a future contributor to spend hours debugging "undefined symbol" when the actual fix iscargo clean -p plg-runtime.8. The golden-IR test migration is well-handled.
fact_compiles_to_unify_and_continuation_jump,multi_clause_predicate_pushes_choice_points, andfirst_arg_indexing_emits_switchwere all repointed to compound-column inputs that don't qualify for the fact-table path — preserving per-clause and indexing coverage rather than discarding it. The newfact_predicate_compiles_to_rodata_tabletest pins the new shape. The "repoint + add" choice was the right one.9. The
# Safetydoc comments on the FFI fns state the contract concretely (table layout, retry_ptr provenance). Good — future contributors adding raising helpers have a template.10. Concerns I would NOT flag (correctly out of scope): Stage B's first-arg index, Stage C's float/big-int/compound columns, the deferred
unsafebounds-elision seam. All are explicitly recorded in FACT_TABLE.md as later work, and the PR description names them.What's good
facts.rsdocuments why — not just what — so it survives a future "this could be cleaner if Rust called k directly" refactor pressure.findall/callre-entry, recursive rule over a fact table,--limit, the compound-column fallback, and undefined → existence_error. Strong end-to-end pinning.deep_recursion_runs_in_constant_c_stackis the right test for the musttail claim — 2000-deep recursion under a 512KB stack. The fact-table path now participates in that, so any future regression that breaks the musttail discipline shows up there.compound_column_predicate_stays_per_clausepins the fallback. Future Stage C can add encoded compounds without unwinding a half-baked float path.m.rewind_to(clean_t, clean_h)at the bottom of the failed-row branch) keeps the trail/heap clean across attempted rows. Failed rows don't accumulate residue for subsequent rows to dig out of.get_uncheckedthis loop" pressure has a documented "not without a profile" check.Suggested order
#1 (measure or doc-downgrade checkpoint 2) and #2 (centralize the ContFn transmute) are worth doing before merge — small and they close out the most prominent rough edges. #3+ are observations and follow-ups.