KR-6: two-parser equivalence (KRLAdapter.jl ≡ quandledb/server/krl) differential test

[hyperpolymath]

Source: PROOF-NARRATIVE.md §3 KR-6 (added in PR #23).

Claim

For every input string s, KRLAdapter.jl::parse_krl(s) and quandledb/server/krl/Parser.jl::parse_any(s) either both succeed with equal ASTs or both fail.

Why valuable

Two implementations exist by design — one for end-user code (KRLAdapter.jl, canonical), one for query-time parsing (quandledb/server/krl/, server-side). If they accept different languages, the server can run queries the canonical parser rejects, and vice versa. Soundness regression.

Assumptions

• [[A-KR-6.1]] Both implementations target the same EBNF grammar (spec/grammar.ebnf v0.1.0).
• [[A-KR-6.2]] Both implementations share the same Token enumeration: keyword set, identifier shape, integer/string literal shapes.

Acceptance criteria

• Add KRLAdapter.jl/test/differential_test.jl (or in quandledb/server/krl/test/ — pick one canonical home and cross-reference).
• Test corpus must include:
  • Every program in krl/examples/*.krl (4 known + any added).
  • Every test input from KRLAdapter.jl/test/parser_test.jl.
  • Every test input from quandledb/server/krl/test/parser_test.jl.
  • Random byte strings (1000 trials, length 1-200, MersenneTwister seed for reproducibility).
• For each input s:

  r1 = try (true, KRLAdapter.parse_krl(s)) catch e (false, e) end
  r2 = try (true, QuandleDB.KRL.parse_any(s)) catch e (false, e) end
  
  @test r1[1] == r2[1]                              # same success/failure
  if r1[1] && r2[1]
      @test ast_equal(r1[2], r2[2])                 # same AST shape
  end

• ast_equal helper must canonicalise across the two AST representations (the two implementations have slightly different node types — see KRLAdapter.jl/src/parser/ast.jl vs quandledb/server/krl/Ast.jl). Either pick a common canonical form or define an explicit isomorphism.
• Failures must report the smallest input that distinguishes the two parsers.

Effort

~1 day. The hard part is the ast_equal canonicaliser; both parsers produce structurally similar but not byte-equal ASTs.

Cross-references

• PROOF-NARRATIVE.md §3 KR-6
• ASSUMPTIONS.md A-KR-6.1, A-KR-6.2
• Cross-repo: hyperpolymath/quandledb QD-10 (same obligation, mirrored).

Out of scope

• Semantic equivalence after lowering. KR-6 is about the surface ASTs only.
• Performance comparison. Worth doing separately; not in scope here.

[hyperpolymath]

Scoping update from KR-6 design agent (2026-06-01)

Audit revealed that the two implementations target different grammar versions:

• KRLAdapter.jl — strict v0.1.0 parser. ~14 AST node types, all from spec/grammar.ebnf v0.1.0.
• quandledb/server/krl/Parser.jl — v0.2+ superset parser. ~50+ AST node types including pipeline queries (KRLSource*, KRLPipeStage), 9-level expression precedence, type annotations (KRLType hierarchy), graph patterns, etc. Not in the EBNF v0.1.0 yet.

This dramatically narrows the differential test scope. The common subset is ~7 node types:

KRLAdapter	QuandleDB v0.2+	Notes
KRLProgram	KRLProgram	structural match
KRLBinding	KRLLetStmt	QuandleDB adds optional type_ann field
KRLGenerator	KRLGenerator	identical
KRLIdentifier	KRLVar	naming difference only
KRLCompose	(removed in v0.2)	composition via 9-precedence-level expressions
KRLTensor	(removed in v0.2)	same
KRLPrefixOp	KRLCall(KRLVar("close"), [...])	parse-shape difference, not just AST rep

The QuandleDB parser treats close(expr) as a function call instead of a prefix operator. That's a real semantic difference inside the v0.1.0 subset — if KRLAdapter parses close x as KRLPrefixOp(:close, x) but QuandleDB parses it as KRLCall(KRLVar("close"), [x]), then the canonicaliser must map them to the same form or the test should report it as a known scope difference.

Updated acceptance criteria

1. Define the v0.1.0 common subset explicitly. Add a docs/v0.1.0-subset.md or similar that fixes which nodes are in-scope for KR-6 and which are scope-extensions on either side.
2. ast_canonical(node) projects both into a canonical form (Vector{Tuple} with position info stripped). For the prefix-vs-call divergence, choose one canonical form and document the projection.
3. Test corpus stays as proposed (4 examples + ~30 hardcoded + ~40 generated = ~74 inputs) but limited to the v0.1.0 subset for both parsers.
4. Out-of-subset inputs that one parser accepts and the other rejects are expected, not bugs — they're scope differences and should be reported separately.

Where the test lives

Updated recommendation: quandledb/server/krl/test/differential_test.jl — because:

• QuandleDB's parser is the downstream consumer and the one most at risk of accidental divergence within the v0.1.0 subset.
• A failing differential test should block a QuandleDB deployment, not block KRL spec work.
• krl/ has no Julia project infrastructure for testing.

Effort revision

Previously estimated 1 day. Revised:

• v0.1.0 subset definition + ast_canonical design: 1 day.
• Test harness + corpus: 1 day.
• Total: ~2 days (vs original 1d estimate).

The harder part is now the canonicaliser, given the prefix-vs-call divergence.

[hyperpolymath]

KR-6 implementation deferral (2026-06-01)

Following the design audit (above), the implementation hit a structural blocker that doesn't change the test design but does change how/where to land it.

Blocker: cross-project Julia dependency

The differential test needs to call both KRLAdapter.jl::parse_krl and quandledb/server/krl::Parser.jl::parse_any from the same Julia process. Three options surveyed:

1. Add KRLAdapter.jl as a path dep in quandledb/server/Project.toml — works, mirrors how KnotTheory.jl / Skein.jl are already wired. Cost: 1-line Project.toml change + brings KRLAdapter into the server test environment. Risk: dragging KRLAdapter's full dep tree into the server build.

2. Subprocess fan-out — write a shell harness that runs Julia twice (julia --project=KRLAdapter.jl then julia --project=quandledb/server), serialises ASTs to JSON, and compares with diff. Cost: ~50 LoC of shell. Risk: AST-shape isn't directly comparable across implementations (the agent design's ast_canonical projection is the right answer, but doing it via JSON serialise on each side complicates the canonicaliser).

3. Land the canonical projection upstream in KRLAdapter.jl — add KRLAdapter.canonical_v01(node) that any v0.1.0-subset AST projects through. Then quandledb/server/krl can implement the matching projection and the differential test is a simple == check. Cost: ~100 LoC across both repos. Cleanest long-term.

Recommendation: Option 3

Option 3 is the right level of abstraction — the canonical projection is a SHARED contract, not a test artefact. Once KRLAdapter.canonical_v01 exists, anyone (KR-6 differential test, future v0.1.0 lints, IDE support) can use it.

But it's a 2-PR sequence (upstream first, downstream after) and depends on landing changes in KRLAdapter.jl outside the krl + quandledb + tangle focus. That makes it follow-up scope.

Revised acceptance criteria

Upstream (KRLAdapter.jl)

• Add KRLAdapter.canonical_v01(node) :: Vector{Tuple} — projects an AST node into the canonical v0.1.0 form. Strips position info; normalises naming (KRLIdentifier → Identifier); maps prefix-op vs function-call to a canonical form.
• Add property test: canonical_v01(parse_krl(s)) is deterministic.

Downstream (quandledb/server/krl/test/differential_test.jl)

• Implement matching canonical_v01 on server/krl/Ast.jl node types.
• Test corpus: 4 krl/examples/*.krl files + every input from KRLAdapter.jl/test/parser_test.jl that's in the v0.1.0 subset.
• For each: parse with both, project both to canonical form, assert equality.
• Out-of-subset inputs (QuandleDB v0.2+ extensions like pipeline queries, type annotations, graph patterns) are documented as expected scope differences, not bugs.

Effort revision

• Phase A (upstream KRLAdapter.canonical_v01): ~1 day.
• Phase B (downstream differential test): ~1 day.
• Total: ~2 days (down from original 1d estimate after the cross-project realisation).

This issue stays open. The audit Agent's design is preserved above and remains the implementation reference.