Skip to content

utf8_decode, split_exact, format_decimal and String length force Classical.choice on every caller #381

Open

Description

@afflom

Problem

A language-1.2 definition or theorem that applies utf8_decode, split_exact, format_decimal, parse_decimal, or length on String must state Classical.choice in its axiom policy, and so must everything that calls it. A project that keeps its policies free of Classical.choice cannot use these primitives. For example, it cannot use utf8_decode to turn input into a String, so it has to write its own table-driven conversion.

This is a design request, not a conformance defect:

  • §17.12 lets a computational definition declare a nonempty exact policy for trusted dependencies in its fixed Lean implementation.
  • §17.12 Runtime bounds says outright that "the split and the decoder pin Classical.choice", so split_exact_fits and utf8_decode_length observe it too.
  • §17.17 requires every production root theorem to observe exactly Classical.choice, Quot.sound and propext, so this request only concerns declaration policies, not certificates.

#301 asks for evaluation and laws for the text primitives and does not address their axiom set.

The format_decimal case differs from the others. Nothing in the SPEC pins it, and the dependency comes from how LexLean's runtime is arranged rather than from what the function needs.

Reproduction

Run at pinned 3877351 (lexlean 0.4.0, language 1.2, Lean 4.32.1). origin/main and origin/release/v0.5 were read, not run: language/runtime-1.2/library/src/Portable.lex.tex is unchanged from the pin, and compiler/expected/verify/audit/output.txt on release/v0.5 lists the same axioms.

A project with language = "1.2" and the builtin lexicon sources lexlean.std.bool and lexlean.std.nat, with one module holding one definition and no axioms member:

\begin{lexlean}{M}
\useglossary{lexlean.std.nat@1.2.0}
\title{Natural number addition}
\begin{semanticmodule}
definition{
  name: f,
  parameters: [n : UInt8],
  result: String,
  body: (prim format_decimal n : String),
  executable: true
}
\end{semanticmodule}
\end{lexlean}
error[LLV7005]: `K1.M.f` violates its none axiom policy: observed [Classical.choice, Quot.sound, propext]

The same probe, one primitive at a time:

Body Observed axioms
prim utf8_decode b Classical.choice, Quot.sound, propext
prim length s on String Classical.choice, Quot.sound, propext
prim split_exact s d (4 : UInt32) Classical.choice, Quot.sound, propext
prim format_decimal n at UInt8 and at Int Classical.choice, Quot.sound, propext
prim parse_decimal s at UInt8 Classical.choice, Quot.sound, propext
prim join xs sep propext
prim utf8_encode s, prim equal on String or Bytes none

Where the axioms come from

#print axioms under Lean 4.32.1:

  • From Lean core: String.fromUTF8? and ByteArray.validateUTF8, String.toList and String.length (whose body is b.toList.length), String.splitOn, String.toInt? all report [propext, Classical.choice, Quot.sound].
  • From the runtime, for format_decimal: toString at UInt8 has no axioms, toString at Int has [propext], and LexLeanRuntime.formatDecimal and LexLeanRuntime.Decimal.format have none. But Decimal bundles parse and format in one instance, and instDecimalOfFixedOfToString and instDecimalInt report [propext, Classical.choice, Quot.sound]. Their parse uses String.toInt?. Formatting pays for parsing.

Proposed direction

  1. format_decimal: separate format from parse in the runtime (two classes or two instances), so format_decimal observes nothing at fixed widths and propext at Int. This change does not touch any sentence of the SPEC.
  2. utf8_decode: define it without String.fromUTF8?. As a feasibility check, a 28-line plain-Lean decoder over List UInt8 that builds with String.ofList and accepts only if the re-encoding equals the input depends on [propext, Quot.sound]. #eval agreed with String.fromUTF8? on the eight byte sequences tried: overlong, surrogate, above U+10FFFF, 0xFF, truncated, lone continuation, ⊕, a. It has not been proved equal to String.fromUTF8?, and that proof, the preservation lemmas that depend on it, and the §17.12 sentence above would be part of the work.
  3. length on String and split_exact: the same question. These depend on String.toList and String.splitOn; no replacement has been tried.

If the maintainers prefer to keep the choice dependency for items 2 and 3, that is a reasonable answer, since §17.12 already states it for the split and the decoder. Item 1 stands on its own either way.

Accepted when

  • format_decimal at a fixed width verifies with no axioms member.
  • If item 2 is accepted, utf8_decode verifies with a policy that does not name Classical.choice, and §17.12 Runtime bounds and utf8_decode_length state what then holds.
  • Existing fixtures for these primitives keep their outcomes.
  • A register row and fixture cover this (R3).

Activity

  1. afflom commented on Nov 3, 2026

    @afflom
    MemberAuthor

    Read-only triage confirms #396's slice/join/closed-decision work does not resolve these four dependencies. In current v0.5 and #396, Decimal still couples formatting to the instance containing String.toInt? parsing; String length, split_exact and utf8_decode still call String.length, String.splitOn and String.fromUTF8? respectively. Committed audit records corroborate the choice-bearing dependencies; no fresh runtime result is claimed.

    The narrowest next change is isolating language-1.2 format_decimal from parsing evidence (first check whether direct ToString suffices). It needs an actual native-1.2 authoring→verify regression with exact axiom policy, numeric boundaries and unchanged parsing refusals; existing legacy SM-18/19 coverage does not establish this. Keep frozen older-language runtime bytes and coordinate any runtime edit with #396's v0.5 integration wave.

    Decoder/split replacements also touch the explicitly pinned §17.12 contract and preservation laws, so a small sample corpus alone is insufficient. String length must retain its character-count contract. No policy weakening, duplicate #396 patch or separate regeneration has been started; #301/#376 remain open.

  2. afflom commented on Nov 3, 2026

    @afflom
    MemberAuthor

    Formatting isolation is now tracked as scoped #434 (SM-39), assigned to the maintainer for release/v0.5. Source analysis found a complete four-source change: the native runtime, both native preservation graphs, and the production certificate constructor. Some Decimal evidence nodes are shared by formatting and parsing, so a runtime-only or global node replacement would break existing parse proofs.

    We are preparing the native language-1.2 row/scenario/regression before implementation; legacy SM-19 is insufficient evidence for this policy change. No test, identity regeneration or build is claimed, and no competing writer will start while Host owns the validation phase. This parent remains open for the other primitives and design decisions.

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

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions