Skip to content

Notation proofs cannot state bounds on split_exact, UTF-8 length or UInt32 checked_add #263

Closed

Description

@afflom

Problem

A language-1.2 model can't prove that its own defensive error branches are unreachable. Example: UOR-Foundation/prism-code has three public response codes guarded by input limits.

  • too-many-lines: the limit is 4097 lines from split_exact, and a request is capped at 4096 bytes.
  • line-overflow: UInt32 checked_add in a line counter.
  • response too-large: the response grows by about 3 times the request, against a limit of 16384.

These are unreachable for any admitted request, but the notation proof language (SPEC §16) has no lemmas relating split_exact piece count to byte length, UTF-8 encoded length to string length, or checked_add to bounds. Raw Lean is not allowed (§16.12).

Ask

Ship runtime-library lemmas that notation proofs can cite:

  • the piece count of split_exact s sep is at most byte_length s + 1;
  • the UTF-8 byte length is bounded by the encoded length;
  • checked_add a b = some _ when a + b < 2^32.

With those, downstream models can prove such branches dead instead of carrying unprovable code.

Acceptance criteria

  • A 1.2 notation module can prove ∀ r, byte_length r ≤ 4096 → (split_exact r "\n").length ≤ 4097 without raw Lean.
  • The lemmas are documented in SPEC §16 and covered by a conformance case.

Filed by the prism-code team (prism-code#12).


Generated by Claude Code

Activity

  1. humuhumu33 commented on Oct 22, 2026

    @humuhumu33
    Contributor

    Claiming this one. Scope: exactly the three runtime-library lemmas the issue asks for (split_exact piece count, UTF-8 byte length, UInt32 checked_add), stated over the runtime's own definitions, kernel-checked, citable from a language-1.2 notation proof, with a conformance case mirroring prism-code's three guards. Targeting release/v0.5; say if you want it on another line.

  2. humuhumu33 commented on Oct 23, 2026

    @humuhumu33
    Contributor

    Draft PR: #296 (targets release/v0.5). It ships the three lemmas as registered laws of LexLeanRuntime.Laws: split_exact_fits, utf8_decode_length and checked_add_fits. Each is kernel-checked. A 1.2 module in fold-laws mirrors prism-code's three guards and proves each branch unreachable by law. Row PF-24.

    One design point for @afflom: Lean does not expose the body of String.splitOn, so the decoder of core module 2 now imports Init.Data.String.Legacy in full (SPEC §17.10). The PR body has the details and the alternative. Please say if you want it done another way.

  3. added 2 commits that reference this issue on Oct 24, 2026
  4. humuhumu33 commented on Oct 24, 2026

    @humuhumu33
    Contributor

    Delivered by #296, merged into release/v0.5 at 80bf4ba: row PF-24 with the three runtime-bound laws, kernel-checked, and the fold-laws module that proves prism-code's three guards dead. The decoder-import question stays with the maintainer, recorded on #296. Closed by hand because the merge is on a release line.

  5. self-assigned this
    on Oct 24, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

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