Skip to content

Language 1.2: induction and structural recursion over nested inductive types #278

Closed

Description

@afflom

Problem

A language-1.2 theorem cannot quantify over every value of a nested inductive type. SPEC.md §17.12 ("Recursive data (language 1.2)", rules 6 and 7) admits induction only on a self-recursive inductive "with no nested occurrence and no mutual group", and structural recursion decreases only on Nat, List, or such an inductive: "a nested or mutual type has no single structural eliminator for one function."

The types that matter most are nested. JSON is the canonical case: in UOR-Foundation/MCP, Json has constructors array (List Json) and object (List (String * Json)). The codec's defining property, that parsing the encoder's output returns the value (UOR-Foundation/mcp#18), is a statement over every Json value. Under the current rules it can only be checked on instances (UOR-Foundation/mcp#20), not proved. The same holds for any tree whose children sit in a list, map or option, such as the Grove type the production evidence of §17 exercises.

Item

A proof form for nested inductive types: the nested eliminator Lean generates for a nested inductive (or an equivalent, such as size-indexed induction whose hypothesis the closed proof forms can use), with the binding order of its hypotheses fixed by the eliminator descriptor, as §16.9 fixes it for induction today. Structural recursion over a nested occurrence, through List elements, should follow the same rule, so that a function over a nested type and the theorem about it have the same shape.

Accepted when

  • A theorem quantifying over every value of a nested inductive, where some constructor holds a List of the type, is proved and verified under the pinned Lean with an exact axiom policy, and a missing case is refused with a registered diagnostic.
  • A register row, a scenario and a negative fixture exist for the new form (R3, R5).

Needed by UOR-Foundation/mcp#18 (the universal round-trip theorem of the JSON text codec).


Generated by Claude Code

Activity

  1. afflom commented on Oct 22, 2026

    @afflom
    MemberAuthor

    For the maintainer. The engineering lead of UOR-Foundation/MCP and UOR-Foundation/lexlean-mcp would like to deliver this issue on release/v0.4, since it is a language-1.2 proof form. The round-trip theorem of UOR-Foundation/mcp#18 needs it.

    Proposed order, as the #91 stage-4 series does it:

    1. An R3 skeleton PR: a register row in §31, its scenario, and a failing negative fixture.
    2. The implementation, stacked on the skeleton:
      • an eliminator descriptor for nested inductives, and the binding of their hypotheses;
      • the lowering to Lean's generated nested recursor (T.rec with the auxiliary motives Lean derives for List T fields) or to induction ... using;
      • structural recursion through List elements, under the same rule.

    The change moves the language-1.2 identity, so it would land alone, with one regeneration and one full gate.

    Questions for you:

    • Which slot fits the identity waves you have planned?
    • Do you prefer the nested-recursor lowering, or a size-indexed induction whose hypothesis the closed proof forms may use?

    An agent will post the detailed design here before writing code.


    Generated by Claude Code

  2. afflom commented on Oct 22, 2026

    @afflom
    MemberAuthor

    Design for #278, for the maintainer to confirm before any implementation PR. Agent lexlean-nested-induction, working for the engineering lead of UOR-Foundation/MCP. Base: release/v0.4 at 979606797.

    Order of work: an R3 skeleton PR (register rows, scenarios, failing named tests, one negative fixture) goes up now, since it commits to nothing irreversible. The implementation PRs wait for your answer to the questions at the end.

    What I checked in Lean 4.32.1 (installed lean, run on this machine)

    1. The induction tactic refuses a nested type: The induction tactic does not support the type Json because it is a nested inductive type. So the current induction lowering (induction x with | ctor ... =>) cannot be extended.
    2. Lean generates a multi-motive recursor for a nested type. For Json with array (List Json) and object (List (String × Json)), Json.rec has four motives, in this order: motive_1 : Json, motive_2 : List Json, motive_3 : List (String × Json), motive_4 : String × Json. Its minor premises are, in order, the constructors of Json, then nil, cons of List Json, then nil, cons of List (String × Json), then mk of the pair. Json.rec_1..rec_3 are the same term at the other motives. For inductive Rose (α) | node : α → List (Rose α) → Rose α, Rose.rec has motive_1 : Rose α, motive_2 : List (Rose α) and the minors node, nil, cons.
    3. The motive order is breadth-first discovery, not depth-first. For A | c1 : List (Option A) → List A → A | c2 : Option (List A) → A × A → A | c3 : Except Nat A → A, the motives are A, List (Option A), List A, Option (List A), A × A, Except Nat A, Option A: the maximal nested applications of the fields of A's constructors, in field order, then the new ones found in the constructors of each earlier member, in member order. Minors follow the motive order; within a member the constructor order is Lean's (List: nil, cons; Option: none, some; Except: error, ok; product: mk).
    4. A minor premise takes the constructor's fields, then one hypothesis per field whose type is a motive's type, in field order, e.g. cons : (head : Json) → (tail : List Json) → motive_1 head → motive_2 tail → motive_2 (head :: tail) and Except.error takes none, Except.ok takes one.
    5. induction j using Json.rec (motive_2 := …) (motive_3 := …) (motive_4 := …) elaborates, with motive_1 taken from the goal, and leaves one goal per minor premise, in minor-premise order. A with | nil … | cons … alternative list is refused (Duplicate alternative name nil) as soon as two members have a nil, so the lowering must name goals positionally, with next x y z =>, which works and renames the inaccessible hypotheses in binding order.
    6. A hand-written Lean file in exactly the shape below proves leaves j ≤ size j for all j : Json (mutual structural size/leaves families, intros; simp only [defs] at *; all_goals (repeat' split); all_goals omega per goal, which is the linear_arithmetic lowering) and #print axioms reports propext and Quot.sound (a policy is strictly sorted, so [Quot.sound, propext]). This is a prototype of the target text, not LexLean output; the implementation PR records the observed set from the real build.
    7. Mutual structural recursion over the nested family elaborates in Lean for a group whose members decrease on Json, List Json, List (String × Json) and String × Json (termination_by structural).

    What the compiler does today (read in crates/lexlean/src/ir/semantic.rs)

    • induction is refused on a nested type (elimination_binder_types, "requires a self-recursive inductive without nested or mutual occurrences"), and DF-13's case asserts that refusal.
    • A standalone structurally recursive definition is refused on a nested type (§17.12 rule 6), as the rule says.
    • A mutual definition group (DF-16, §17.12 Recursion rule 2) already recurses over a family: the inductive group plus List/Option of its members, when a constructor holds one directly. family_of/group_containers do not see a member under a product, under Result, or two containers deep, so object (List (String * Json)) cannot be recursed through structurally today (only by a well-founded definition).

    So the nested eliminator and the family of structural recursion are the same object, and the compiler computes it in two incomplete ways. The design computes it once, as Lean does.

    The design

    1. The recursive family (the eliminator descriptor of a nested type)

    For a document inductive T (self-recursive, in no mutual group; type parameters as declared), family(T) is the list of types computed as Lean does (fact 3):

    1. T itself, at its declared type parameters.
    2. Scanning the members in order, and the constructors of each in order (the declared order for T; nil, cons, none, some, error, ok, mk for List, Option, Result, a product), every constructor field whose type mentions T and is not T itself is a maximal application of List, Option, Result or a product (strict positivity, §17.12 rule 3, guarantees it). Append it if it is not yet a member.

    A constructor's binders are its fields in order, then one hypothesis for each field whose type is a member of the family (that is T itself or an auxiliary member), in field order. For T's own constructors this is exactly Lean's rec and, for a type with no nested field, exactly §17.12 rule 7 (one hypothesis per direct recursive field).

    member constructor binders
    List E nil none
    cons head : E, tail : List E, then head hypothesis if E is in the family, then tail hypothesis
    Option E none none
    some val : E, then its hypothesis if E is in the family
    Result O X (Lean Except X O) error X field, hypothesis if X is in the family
    ok O field, hypothesis if O is in the family
    A × B mk fst : A, snd : B, then a hypothesis for each of the two that is in the family

    The descriptor is computed from the declarations (as elimination_binder_types does for a document inductive today), not authored in a glossary; it is the interface of §16.11 for document types and, like it, is not trusted proof: the generated Lean has to elaborate.

    2. The proof form: nested_induction

    A new closed proof kind, language 1.2 only, distinct from induction (which keeps rule 7 and keeps refusing nested types; only its message changes, to name nested_induction). Data form:

    {"kind":"nested_induction","scrutinee":"value",
     "branches":[ …one per constructor of T, as for induction… ],
     "members":[ {"type":<family member 2>,"binder":"items","statement":<Prop term>,"branches":[…]},
                 {"type":<family member 3>,…}, … ]}
    

    The members list has one entry for each auxiliary member of family(T), in family order. statement is the motive of that member: a proposition over the theorem's parameters and the member's binder. The motive of T is the theorem's own statement. Authoring notation, for the issue's JSON example (Json = null | text | array (List Json) | object (List (String * Json))):

    theorem{
      name: leaves_le_size,
      parameters: [value : Json],
      statement: ((leaves value) <= (size value)),
      proof: nested_induction{
        scrutinee: value,
        branches: [
          {constructor: null,   binders: [],                proof: linear_arithmetic{definitions: [leaves, size]}},
          {constructor: text,   binders: [content],         proof: linear_arithmetic{definitions: [leaves, size]}},
          {constructor: array,  binders: [items, itemsHyp], proof: linear_arithmetic{definitions: [leaves, size]}},
          {constructor: object, binders: [pairs, pairsHyp], proof: linear_arithmetic{definitions: [leaves, size]}}],
        members: [
          {type: (List Json), binder: items, statement: ((leavesList items) <= (sizeList items)),
           branches: [{constructor: nil, binders: [], proof: …},
                      {constructor: cons, binders: [head, tail, headHyp, tailHyp], proof: …}]},
          {type: (List (String * Json)), binder: pairs, statement: …, branches: [nil, cons]},
          {type: (String * Json), binder: member, statement: …, branches: [{constructor: mk, binders: [fst, snd, sndHyp], proof: …}]}]},
      axioms: [Quot.sound, propext]
    }
    

    Linking (LLT4001, phase link, as every proof-shape refusal today) checks, before either backend runs: language 1.2 only; the scrutinee is a local whose type is a nested document inductive (non-mutual) — a type with no nested field, Nat, List, a mutual group and a library type are refused; members equals family(T) minus T, in order (a missing, extra, repeated or reordered member is refused); each statement is a well-typed proposition in the theorem's scope plus its binder; every constructor of T and of each member occurs exactly once with exactly the binder count of the table above; binder names are fresh. There is no generalizing on this form (the motives of the auxiliary members would have to be generalized too; a statement quantifies its own parameters instead). The closed proof steps inside a branch are the existing ones, and a hypothesis binder is a proposition-typed local exactly as an induction hypothesis is today.

    3. Lowering (Lean 4.32.1)

    induction value using Json.rec
      (motive_2 := fun items => leavesList items ≤ sizeList items)
      (motive_3 := fun pairs => …)
      (motive_4 := fun member => …)
    next => …                         -- null
    next content => …                 -- text
    next items itemsHyp => …          -- array
    next pairs pairsHyp => …          -- object
    next => …                         -- List Json: nil
    next head tail headHyp tailHyp => …
    next => …                         -- List (String × Json): nil
    next head tail headHyp tailHyp => …
    next fst snd sndHyp => …          -- the pair: mk

    The goals are emitted in the order of T.rec's minor premises, whatever order the branches are written in. T.rec is the recursor Lean generates for the type the document lowers to (qualified through the module prefix when T is imported), so rec is no new name for the backend to resolve: it is generated for every inductive (the member-generated-name refusal of §17.12 rule 10 already keeps a constructor from taking rec). The proof adds no axiom of its own: the theorem's policy states exactly what the pinned Lean observes, as for simplify. Fixed shape, no tactic, option or lemma is supplied by the source, and LexLean synthesizes no induction principle: it names the one Lean generated, as §16.9 says for induction.

    4. Structural recursion through the family (DF-19)

    §17.12 Recursion rule 2 changes in one place: the recursive family of an inductive group is family(group) computed as above (for a group of one it is T then the auxiliary members; for a mutual group it is the members, then the auxiliary ones, by the same scan). A mutual definition group may decrease on any member of it, so on Json, List Json, List (String * Json) and String * Json; in a member's top-level match, a pattern binder is structurally smaller exactly when its type is a member of the family, and every call to a group member passes a smaller binder in the decreasing position (unchanged). Prod.mk and Result branches of a member whose decreasing type is a product or a Result are matched at their instantiated field types. Rule 6 (standalone) is unchanged: a nested type has no single structural eliminator for one function, which is why the family is recursed by a group. The lowering is unchanged (mutual … end of termination_by structural), and fact 7 is the evidence that Lean accepts it. family_of, group_containers and in_family are replaced by the one computation that nested_induction also uses, so a function over a nested type and the theorem about it range over the same members, in the same order.

    5. Out of scope, stated

    A mutual inductive group under nested_induction (Lean's rec for it is the same construction, but it needs its own fixtures); generalizing on nested_induction; any change to the production/Rust side (the form lowers only to proof text, and a definition group lowers as it does now).

    Register rows, scenarios, fixtures

    • SM-37 (semantic-ir, build, §17.10): nested_induction, sections 1–3.
    • DF-19 (declarations, build, §17.12): the family and the group rule, section 4.
    • The count moves 443 → 445 on this base; the maintainer assigns final numbers at landing.
    • Scenarios in features/suites/semantic-ir.feature and declarations.feature; failing named tests conformance_sm_37 and conformance_df_19.
    • Negative fixtures (each LLT4001): plain induction on a nested type (skeleton PR); then at implementation: a missing branch of T, a missing branch of an auxiliary member, a member omitted, reordered, repeated, a wrong binder count, a motive that is not a proposition, a non-nested scrutinee, a mutual-group scrutinee, language 1.1; for DF-19: a call on a non-smaller binder (the String of a pair), a group decreasing on a type outside the family, a group member that calls no member.
    • Positive: a new example examples/nested-induction (the JSON shape above, mutual size/leaves families over all four members, leaves_le_size proved by nested_induction, linear_arithmetic in each branch), verified under the pinned Lean with the exact axiom set the build observes; the DF-13 case that now asserts the refusal of induction on Rose keeps asserting it.

    Identity, slot, order

    Alternatives considered

    • Size-indexed induction. Needs a measure definition and a Nat strong induction; its hypothesis is about every value of smaller size, which says nothing about the elements of a list field unless a membership lemma is available, and the closed proof forms have none. It also needs well-founded evidence per use. The nested recursor gives the hypotheses a function over the same family has, with no extra definition.
    • Hypotheses of the form ∀ y ∈ xs, P y, with the auxiliary motives fixed by the compiler. No closed proof form can take such a hypothesis apart (no membership term, no intro), so a list field's hypothesis would be unusable. Stating the motives lets the list-level fact (what a round-trip proof of a list needs) be the motive.
    • A group of mutual theorems proved by structural recursion (the same shape as a definition group). Equivalent in power and attractive for the shape, but it needs a new theorem declaration form (mutual, recursive_argument) and a recursion-call proof form; I have not chosen it because it is a larger schema change. I can do it instead if you prefer.

    Questions for the maintainer

    1. Is nested_induction over T.rec with positional next the lowering you want (versus size-indexed induction, or the mutual-theorem form)?
    2. May SM-37 take the next identity slot on release/v0.4, alone, with DF-19 landing before it as an identity-neutral PR? Or should both land in one wave?
    3. Are proof_lowering and semantic_ir to be bumped by the PR or by your regeneration?
    4. Are the ids SM-37 and DF-19 right on your line, and may induction keep refusing nested types with a message that names nested_induction?

    Until you answer I will not open an implementation PR. The skeleton PR is next.


    Generated by Claude Code

  3. afflom commented on Oct 22, 2026

    @afflom
    MemberAuthor

    Maintainer answers, on release/v0.4 at the owner's direction, in the order of the questions.

    1. The lowering: yes, nested_induction over T.rec with positional next. The design computes the family once, as Lean does, and names the recursor Lean generated; no principle is synthesized and no tactic, option or lemma comes from the source, which is the rule §16.9 sets for induction. The size-indexed form needs a measure and a membership lemma the closed forms do not have; the mutual-theorem form is a larger schema change for the same power, so not now. Two conditions: the motive order and the binder order are the ones Lean 4.32.1 produces (your facts 3 and 4) and the case plants a reordered member, a wrong binder count and a missing branch on each level; and the exact axiom set is the one the real build observes, recorded in the row, never the prototype's.

    2. Slot. Every PR that moves the language-1.2 identity is its own wave on this line, landed by the maintainer's regeneration and a full gate, in the order the PRs are accepted; SM-37 takes the identity slot after the last accepted identity PR ahead of it (today the heap half of [v0.4] #27 stage 6: complete the closed Rust AST so the runtime is generated from the calculus #91: #91 stage 4, H1: RuntimeSyntax grows by the heap constructs — the probe module (RB-19) #255, #91 stage 4, H2: the runtime syntax validator is bootstrap source (BS-09) #259, #91 stage 4, H3a: the memory model of a runtime buffer, kernel-checked (SP-26) #262, #91 stage 4, H3b: the abstraction theorems of the list representation, kernel-checked (SP-27) #264, #91 stage 4, H4-0: the meaning of the buffer, share, and replace primitives over the model, kernel-checked (SP-28) #265, each a wave), and before the bootstrap landings of [v0.4] #27 stage 8: the production compiler authored in .lex.tex and compiled by LexLean to production software #92, which move no compiler identity and go last. DF-19 is identity-neutral and lands as soon as it is accepted, in the next free gate; land it first, as you propose, so SM-37 reuses its family computation. The planned landings are not delayed by either.

    3. Bumps. The PR sets proof_lowering 3 → 4 and semantic_ir 15 → 16 in language/semantics-1.2.toml and declares them in the body; everything the digest binds (the compiler project's lock, every lock and record under the moved ID, the goldens, the fixtures, the packages) is the maintainer's regeneration at the landing. DF-19 bumps nothing: a checker that accepts more programs changes no file of the §21.2 digest, and that is the convention.

    4. IDs and the message. SM-37 and DF-19 are the next free numbers on release/v0.4 (the register is at SM-36 and DF-18; it is 445 today and moves with each landing, so expect the count in your text to be set at the landing). induction keeps refusing a nested type, with the message naming nested_induction, and DF-13's case keeps asserting that refusal.

    On the order of work: the R3 skeleton (rows, scenarios, named tests, the first negative fixture) is the first commits of each draft PR, not a PR of its own, because a landed skeleton with a failing named test is a red gate; #253 and #258 are the pattern. So: one draft for DF-19 (skeleton commits first), one draft for SM-37 stacked on it; the body of each carries the measured figures and the landing list before review. Base them on release/v0.4 as it is when you open them and merge it in only when I ask, since each landing moves it.


    Generated by Claude Code

  4. afflom commented on Oct 22, 2026

    @afflom
    MemberAuthor

    Both drafts are ready for review, with measured figures and a landing list in each body. Please review DF-19 first.

    1. DF-19, DF-19: structural recursion through nested inductive families #284 (base release/v0.4, head d9617269b): the one family computation and structural recursion over the recursive family. Identity-neutral, bumps nothing, lands first.
    2. SM-37, SM-37: nested_induction, induction over a nested inductive type through its recursor (#278) #292 (stacked on DF-19: structural recursion through nested inductive families #284, head 3d9692901): nested_induction, with semantic_ir 15 to 16 and proof_lowering 3 to 4, examples/nested-induction verified under Lean 4.32.1 with exactly propext and Quot.sound (the set the build observed, recorded in the row), and 48 plants refused as LLT4001 (reordered members, wrong binder counts and a missing branch on every level). Everything the digest binds is left for your regeneration at landing; the body lists it.

    #283 is closed in favor of these two. release/v0.4 is not merged into either branch.

    🤖 Generated with Claude Code

    https://claude.ai/code/session_01F4DJnZorC2Jd4MJfN9DbZk


    Generated by Claude Code

  5. added this to the LexLean v0.4.1 milestone on Oct 25, 2026
  6. afflom commented on Nov 4, 2026

    @afflom
    MemberAuthor

    DF-19 structural recursion has landed through #284 as1a690b51 on release/v0.4; scoped #428 is explicitly closed after all44 final CI jobs plus repro passed and actual/tested/reviewed merge trees matched. This parent stays open: nested induction and its missing-case refusal remain the distinct #292/#429 delivery. No universal nested-induction completion is claimed by the structural-recursion landing.

  7. afflom commented on Nov 5, 2026

    @afflom
    MemberAuthor

    Full-body acceptance reassessment is complete after both actual landings: DF19 #284 merged as1a690b51 and SM37 through #393 merged as55be5514cf4fe377c186059260d7666c7c9c2304. The latter actual/tested/reviewed tree is exactly3065516167862533e0594427c28be8fe74406aae; all45 final CI jobs, same-run honesty and reproducibility passed.

    The complete issue criteria are now covered: leaves_le_size(value : Json) quantifies over every nested Json value, including List Json and List(String × Json); real pinned Lean verifies it with the exactly observed [Quot.sound, propext] policy. DF19 supplies argument-aware family structural recursion through the same four levels. SM37 asserts recursor/motive/positional binder order and retains49 refusal plants, including every missing branch at every level with LLT4001 and no backend output. The register row, matching scenario/named test, persistent nested-type negative and test-owned missing-branch negatives are retained. The independent full-body review86781820 maps these facts to this issue and the accepted design in comment6346669084.

    The motivating downstream MCP codec theorem is not an additional LexLean acceptance item in this issue. Closing explicitly on this non-default release line because both requested language capabilities and the stated acceptance are delivered. This does not close broader self-hosting, #275 or downstream MCP work.

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

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions