Skip to content

Certificate A is rejected by the kernel for a recursive function with a list parameter before its recursive argument #314

Closed

Description

@afflom

Certificate A of a production root is rejected by the Lean kernel (LLV7013, "application type mismatch" in a __rel_N declaration) for a recursive function whose recursive argument is not the first parameter, when a parameter before it is a List and the arm of the recursive match matches that list. Found while exporting RustAssemble of #92 step 4; the sibling defect of #310 (that one is in certificate B).

Minimal project (one module, no source package; lexlean.toml as in #310, entrypoints = ["src/Mini.lex.tex"], module_prefix = "LexLeanBoot", language 1.2; lexlean lock; production build of LexLeanBoot.Mini.tailOf for rust-std). About 3.5 minutes.

\begin{lexlean}{Mini}
\useglossary{lexlean.std.nat@1.2.0}
\title{Natural number addition}
\begin{semanticmodule}
inductive{
  name: Ty,
  type_parameters: [],
  parameters: [],
  constructors: [
    {name: TUnit, fields: []},
    {name: TBool, fields: []},
    {name: TNat, fields: []},
    {name: TInt, fields: []},
    {name: TFixed, fields: [Nat]},
    {name: TString, fields: []},
    {name: TBytes, fields: []},
    {name: TOrdering, fields: []},
    {name: TOption, fields: [Ty]},
    {name: TResult, fields: [Ty, Ty]},
    {name: TList, fields: [Ty]},
    {name: TPair, fields: [Ty, Ty]},
    {name: TAdt, fields: [Nat]},
    {name: TFn, fields: [Ty, Ty]},
    {name: TNil, fields: []},
    {name: TCons, fields: [Ty, Ty]}
  ]
}

inductive{
  name: Par,
  type_parameters: [],
  parameters: [],
  constructors: [{name: ParNil, fields: []}, {name: ParCons, fields: [Nat, Nat, Par]}]
}

definition{
  name: paramsOf,
  parameters: [names : (List Nat), types : Ty, body : Nat, known : Ty, position : Nat, empty : Nat],
  result: Par,
  body: (match types
    | Ty.TUnit => (ctor Par.ParNil)
    | Ty.TBool => (ctor Par.ParNil)
    | Ty.TNat => (ctor Par.ParNil)
    | Ty.TInt => (ctor Par.ParNil)
    | Ty.TFixed u5x0 => (ctor Par.ParNil)
    | Ty.TString => (ctor Par.ParNil)
    | Ty.TBytes => (ctor Par.ParNil)
    | Ty.TOrdering => (ctor Par.ParNil)
    | Ty.TOption u9x0 => (ctor Par.ParNil)
    | Ty.TResult u10x0 u10x1 => (ctor Par.ParNil)
    | Ty.TList u11x0 => (ctor Par.ParNil)
    | Ty.TPair u12x0 u12x1 => (ctor Par.ParNil)
    | Ty.TAdt u13x0 => (ctor Par.ParNil)
    | Ty.TFn u14x0 u14x1 => (ctor Par.ParNil)
    | Ty.TNil => (ctor Par.ParNil)
    | Ty.TCons head tail => (match names
      | List.nil => (ctor Par.ParNil)
      | List.cons name rest => (ctor Par.ParCons name 0 (paramsOf rest tail body known (position + 1) empty)))),
  executable: true,
  recursive_argument: types
}

definition{
  name: tailOf,
  parameters: [names : (List Nat), types : Ty],
  result: Par,
  body: (paramsOf names types 0 (ctor Ty.TUnit) 0 0),
  executable: true,
  production: {effects: [allocation, overflow, recursion], targets: [rust-std]}
}
\end{semanticmodule}
\end{lexlean}

Error:

certificate A: `LexLeanPreserve.C….R0` was rejected in `__rel_1` of root `LexLeanBoot.Mini.tailOf`: error: native core declaration '…R0.__rel_1':
  (kernel) application type mismatch
    failed to pretty print expression (use 'set_option pp.rawOnError true' for raw representation)
  argument has type
    LexLeanPreservation.Conv __prog
      [(5, …value.nat empty), (4, …nat position), (3, __enc_0 known), (2, …nat body), (1, __enc_0 …Ty.TUnit), (0, LexLeanPreservation.encList …value.nat names)]
      (LexLeanTarget.TargetSyntax.Expr.match (…Ty.adt 1) (…Expr.var 1) [Arm.arm (Shape.adt 0) [] (Expr.build (Shape.adt 0) …

Measured variants (each a full export of the same shape; all else equal):

Change Result
none (names : (List Nat) first, types second and recursive, the TCons arm matches names) rejected
the recursive argument types first exports
the TCons arm does not match names exports
names is a Nat, not a list exports

Workaround in the tree: paramsOf of bootstrap/src/RustAssemble.lex.tex takes the recursive argument first. See also #310.

Refs #92.


Generated by Claude Code

Activity

  1. added
    bugSomething isn't working
    self-hostingLexLean compiling itself: compiler in .lex.tex, certified, built by its own pipeline
    on Oct 24, 2026
  2. added this to the LexLean v0.5 milestone on Oct 25, 2026
  3. afflom commented on Oct 25, 2026

    @afflom
    MemberAuthor

    Maintainer: confirmed as a defect of the certificate A emitter (the __rel_N declaration for a recursive function whose recursive argument is not the first parameter, when an earlier List parameter is matched in the recursive arm), the sibling of #310, mine to own, placed on v0.5 for the same reasons: the refusal is honest (LLV7013, no unsound acceptance), BS-14 carries a stated workaround, and the fix moves the preservation library and so the compiler-semantics ID, which the v0.4 line cannot afford another wave for. The two are fixed together, with the minimal projects of #310 and #314 as the negative-turned-positive fixtures and the workarounds removed in the same PR. The owner can pull them into v0.4 by saying so here.


    Generated by Claude Code

  4. added a commit that references this issue on Nov 3, 2026
  5. afflom commented on Nov 5, 2026

    @afflom
    MemberAuthor

    Delivered through merged #393, commit 55be5514, on release/v0.4. The actual merge parents are c613290 + reviewed head050e9657, and actual/tested/reviewed tree 3065516167862533e0594427c28be8fe74406aae is identical. Final CI passed all45 jobs, including honesty, required hosts, complete normative cases/plants and Atlas; reproducibility passed. Final evidence review retained independent source/artifact/semantic and final acceptance reviews.

    The original certificate failure is covered by the retained SP32/SP33 regressions and successful complete normative preservation partition, with official final-identity artifacts and the actual final gate.

    Closing explicitly because this accepted landing targets a non-default release branch.

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

    bugSomething isn't workingself-hostingLexLean compiling itself: compiler in .lex.tex, certified, built by its own pipeline

    Type

    No type

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions