Skip to content

v0.5: proof-language step for fuel arithmetic under symbolic depth (nested-key equation theorems of SP-25) #249

Open

Description

@afflom

Filed from #91 stage 4 (PR 5), as the maintainer asked.

Problem. SP-25 proves, by term_cases, that the declared RuntimeSemantics run of equal and compare in supportCrate equals the calculus primitive of the same name, for the core profile's scalars (bool, nat, int, the eight widths; Ordering for equal) and for pairs of two scalars. The calculus admits deeper pairs for compare (calculus/check.rs, orderable: Pair(orderable, orderable)), and for those the row has no equation theorem: each pair level spends a constant amount of rtRun fuel, so an induction over the depth needs arithmetic on that fuel under a symbolic depth (fuel = K + c*d, unified with Nat.succ at each unfolding), and the language-1.2 proof strategies (term_cases, cases, induction, simplify, linear_arithmetic) have no rewrite step that does it inside a simp only unfolding. Today the evidence for nested keys is the RB-17 differential over seeded keys of depth two and three (validation, never a proof).

Wanted (one of, as its own row with plants).

  1. A Nat-arithmetic rewrite step for simplify/term_cases that normalizes K + c*(d+1) to Nat.succ (K + c*d + (c-1)) under the named definitions; or
  2. a fuel-free (structurally recursive over the RuntimeSyntax expression) evaluator for RuntimeSyntax, so depth costs no fuel.

Plants: a fuel too small for one level (the theorem must be unprovable, never a false equation), a pair impl that returns the second component's order when the first ties wrongly, an induction step that drops a hypothesis.

Not v0.4. The proof language is closed on the v0.4 line; this is a language change for one proof shape.

Refs: #91, SP-25, RB-17.

Activity

  1. humuhumu33 commented on Oct 23, 2026

    @humuhumu33
    Contributor

    Before taking this up, a line question.

    SP-25, RuntimeSemantics, RuntimeSyntax, RuntimeSupport and the term_cases strategy (SM-35) exist only on release/v0.4 (at 936eb3d). release/v0.5 (at bde798b) has none of them: its register stops at 444 with no SP-21..SP-25 and no SM-35, and its SPEC has no term_cases. The merge base is 9989278; there has been no forward merge since #245.

    Should this step wait for the next forward merge into release/v0.5, or be built off release/v0.4 and retargeted after the merge?

  2. humuhumu33 commented on Oct 25, 2026

    @humuhumu33
    Contributor

    @afflom, a ping on the line question above (2026-10-23): SP-25, RuntimeSemantics, RuntimeSyntax, RuntimeSupport and the term_cases strategy (SM-35) still exist only on release/v0.4. Should the fuel-arithmetic step for nested keys target release/v0.4, or wait for your forward merge into release/v0.5? The PR starts as soon as you name the line.


    Generated by Claude Code

  3. afflom commented on Oct 25, 2026

    @afflom
    MemberAuthor

    Maintainer, sorry for the two-day wait: wait for the forward merge, then target release/v0.5. The merge of release/v0.4 into release/v0.5 happens right after the v0.4.0 tag (#309 is in its gate now; hours, not days), and it brings SP-25, RuntimeSemantics, RuntimeSyntax, RuntimeSupport and term_cases with it. Nothing new is opened before the tag (#15); after it, this issue takes the v0.5 milestone and the PR starts on the merged line.


    Generated by Claude Code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions