shenffi/CasEngine: nondeterministic evaluation of shaken shen-cas slice (wrong answers + in-session perf degradation)

[pyrex41]

Summary

Running the tree-shaken shen-cas slice through shenffi::CasEngine, evaluation is nondeterministic relative to the reference Shen kernel. The same input yields one of three outcomes — correct, unreduced (inert leftover), or silently wrong — selected by process/boot state. The same machinery also degrades in performance the longer a session runs. The reference evaluator (the identical CAS program under ShenScript) is correct and deterministic, so the divergence is introduced by shen-rust's execution, not by the shen-cas rules.

This is the root cause of the now-closed shen-cas issues pyrex41/shen-cas#5 (wrong/unreduced D[ArcTan[x],x]) and pyrex41/shen-cas#6 (Integrate latency), both retargeted here.

Decisive repro — two fresh boots in one process disagree

crates/shenffi/examples/cas_bench.rs (run on a large-stack thread, as the README requires):

use shenffi::CasEngine;
fn main() {
    std::thread::Builder::new().stack_size(512*1024*1024)
        .spawn(|| {
            let mut e1 = CasEngine::boot().unwrap();
            println!("e1 D[x,x]         = {}", e1.reduce("D[x,x]"));
            println!("e1 D[ArcTan[x],x] = {}", e1.reduce("D[ArcTan[x],x]"));
            let mut e2 = CasEngine::boot().unwrap();
            println!("e2 D[x,x]         = {}", e2.reduce("D[x,x]"));
            println!("e2 D[ArcTan[x],x] = {}", e2.reduce("D[ArcTan[x],x]"));
        }).unwrap().join().unwrap();
}

Observed:

e1 D[x,x]         = [D x x]                                  <- inert (rule didn't fire)
e1 D[ArcTan[x],x] = [Times [D x x] [Power [Plus [Power x 2] 1] -1]]   <- unreduced
e2 D[x,x]         = 1
e2 D[ArcTan[x],x] = 1                                        <- WRONG (correct: (1+x^2)^-1)

	engine 1 (1st boot)	engine 2 (2nd boot)	reference (ShenScript)
D[x,x]	[D x x] (inert)	1	1 ✓
D[ArcTan[x],x]	[Times [D x x] [Power…-1]]	1 (wrong)	(1+x^2)^-1 ✓

Each CasEngine is freshly booted (own Interp), so it is not memo-priming/history. Both share the process, and 8 separate process launches all agreed — so it is not a per-process RandomState seed either. The only discriminating variable is boot order within the process, i.e. process-global state that survives across Interp::new() / boot_from_kl_source.

Why this points at intern/hash state

The guarded calculus rules both modes hinge on (D[x,x] → 1 guarded by SameQ, D[c,x] → 0 by FreeQ) evaluate through the CAS's content-eq → content-hash, and the CAS's normal-form memo is content-hash-keyed. shen-cas deliberately uses a self-contained polynomial rolling hash (base 31, large-prime modulus) precisely because host hash is unsafe across ports (see shen-cas HANDOFF.md "Portable content hash"). If shen-rust computes that rolling hash with fixed-width integer wraparound (vs ShenScript's number type) the modular arithmetic diverges → collisions; and if symbol interning / a global symbol table is not reset per boot, the collision set shifts by boot order — exactly the observed behavior.

Second symptom — monotonic in-session perf degradation

The identical Integrate[x^4,x] call, repeated 8× in one process:

#0 4.08s  #1 5.08s  #2 5.23s  #3 16.28s  #4 14.81s  #5 14.49s  #6 13.64s  #7 14.00s

Same input, same process, climbing 4s → 16s and plateauing — a state-accumulation cost (content-hash-keyed nf-memo / store growth), the same machinery as above. The reference (ShenScript, a slower interpreter) does these in <1.2s, so this is a native-vs-interpreter performance inversion. On the app's single long-lived worker thread this reads as a progressive slowdown / "hang."

Suggested investigation

1. Is shen-rust's number/integer arithmetic for the CAS's rolling hash arbitrary-precision, or does it wrap at i64? Wraparound would produce host-specific collisions.
2. Is the symbol intern table (and any global hash/symbol state) reset on each Interp::new() / boot_from_kl_source? The two-boot divergence says some global state leaks.
3. Profile the nf-memo / store under repeated reduction in one boot (the 4s→16s climb) — is content-hash recomputed over growing state, or are map lookups degrading?

Expected

CasEngine::reduce should match the reference byte-for-byte and be boot-order- and history-independent: D[x,x] → 1, D[ArcTan[x],x] → (1+x^2)^-1, every boot, every call.

Provenance

Found while evaluating shen-cas #5/#6 against the shipped slice; cross-checked against the pure-Shen reference via shen-cas/scripts/shenscript-run.js.

[pyrex41]

Resolved — root-caused to two distinct causes, neither a shen-rust evaluation bug

Thanks for the unusually precise repro. Investigated end-to-end against the embedded slice (cas-engine in shen-calc, linked to this interpreter). Both symptoms are fixed; the diagnosis is not what the report's leading hypotheses guessed, so the trail is worth recording.

shen-rust runs the kernel faithfully

First, the hypotheses in the issue are ruled out:

• hash / rolling-hash i64 overflow — shen-rust's kernel hash is byte-for-byte identical to the reference. Verified by invoking (hash Str 1000000007) directly: x→120, [D x x]→245772256, ArcTan→502040601, … all match the ShenScript algorithm. The CAS hash bottoms out in shen.prodbutzero, which self-guards (multiply→add past 1e10), so it never overflows; shen-rust's * also checked_muls with float-promotion. No divergence here.
• Symbol-intern / global state leak across boots — Interp::new() builds a fresh Interner every boot and interns true/false first, so they are always SymId(0)/SymId(1). The BOOLEAN_SYM_IDS OnceLock therefore always holds (0,1) — latent, but harmless, and not the cause.

Symptom 1 (wrong / boot-order-dependent answers) — unsound memo in shen-cas

The bug is shen-cas's normal-form memo, not the interpreter. nf-cache-key was [content-hash, basis], looked up by assoc — i.e. O(1) equality by hash alone, with no structural verification. The kernel hash (shen.prodbutzero, a product of char codes that degrades to addition past 1e10) collides readily for distinct long content-strings. On a collision the memo returns another term's cached normal form; which wrong/inert value wins depends on insertion order → boot/session-dependent answers (e.g. D[ArcTan[x],x] leaving the inner [D x x] inert).

Proof: disabling the memo (nf-lookup always misses) makes every case correct — D[ArcTan[x],x] → (1+x²)⁻¹, D[x+x,x] → 2, etc.

Fix (shen-cas, store.shen/core.shen): carry the canonical expression in the cache key — [hash, basis, (alpha-canonicalize E)] — so assoc rejects a hash collision structurally. Hash+basis stay a cheap fast-fail prefix; equal-canonical-form terms still share an entry, so memo effectiveness is preserved. content-eq/SameQ share the same hash-only-equality weakness (latent, not yet triggered) and warrant the same treatment.

Symptom 2 (monotonic slowdown → OOM) — grow-only heap, fixed by opting into GC

This one is squarely in shen-rust's domain, and it is by-design, not a bug. Localized by elimination:

• An O(1) shen.dict-backed memo made zero difference.
• Clearing *normal-form-cache* + *intern-table* between top-level reduces didn't help.
• A fresh thread+boot per reduce is flat.

So the climb is per-session growth of the grow-only thread-local heap — every reduce allocates cells that are never reclaimed on a long-lived engine. shen-rust already ships a correct request-mode GC (collects at depth-0 safepoints); it is simply off by default for embeddings and opt-in via SHEN_RUST_GC=<floor-nodes> (honored by Interp::new for a fresh sole interp; arm64 macOS/Linux; refuses under JIT or beside live sibling interps).

Fix (shen-calc cas-engine): a CasEngine is exactly that long-lived, fresh-sole-interp case, so boot_shaken opts into request-mode GC. Result: no climb, no OOM, identical results — and the regression test's wall time dropped 263s → ~26s.

Verification

cas-engine/tests/issue8_memo_soundness.rs reduces a battery in one long-lived engine (the failing session path; a fresh-thread-per-case harness masks it) and asserts two boots agree:

D[x,x]            = 1
D[ArcTan[x],x]    = [Power [Plus [Power x 2] 1] -1]
D[x+x,x]          = 2
D[2*x,x]          = 2
D[Sin[x],x]       = [Cos x]
D[x^3,x]          = [Times [Power x 2] 3]
Integrate[x^2,x]  = [Times [Power x 3] [1 / 3]]

All correct, every boot, every call.

Fixes landed

• shen-cas — fix(store): make normal-form memo sound (carry expr in cache key)
• shen-calc / cas-engine — sound-memo slice patch + issue shenffi/CasEngine: nondeterministic evaluation of shaken shen-cas slice (wrong answers + in-session perf degradation) #8 regression test; request-mode GC opt-in for the perf symptom

Leftover shen-rust notes (latent, no action required for this issue)

• value_hash hashes symbols by SymId rather than name (non-portable / boot-fragile if intern_static ordering ever changes); harmless today.
• gc_enable_request_mode is pub(crate), so the only embedding hook is the SHEN_RUST_GC env var. A small pub fn Interp::enable_request_gc(floor) would let embedders opt in without the env-var dance.

Closing — resolved in shen-cas + shen-calc; no shen-rust evaluation change required.

[pyrex41]

Resolved via shen-cas#9 (sound nf-memo) + the shen-calc cas-engine GC opt-in for the perf symptom. No shen-rust evaluation change required — the interpreter ran the kernel faithfully. Details in the comment above.