Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

(kernel) unknown constant in mutually recursive definition #2628

Closed
nomeata opened this issue Oct 5, 2023 · 2 comments · Fixed by #2902
Closed

(kernel) unknown constant in mutually recursive definition #2628

nomeata opened this issue Oct 5, 2023 · 2 comments · Fixed by #2902
Assignees
Labels
bug Something isn't working

Comments

@nomeata
Copy link
Collaborator

nomeata commented Oct 5, 2023

Description

In some (possibly not-well-founded) mutually recursive definitions, we get (kernel) unknown constant.

Context

I stumbled over this while trying to help someone on Zulip.

Steps to Reproduce

MWE:

mutual
  inductive Thing : Type
    | Bag : Object → Thing
  inductive Object : Type
    | Bike : Object
    | Box : Thing -> Object
end

mutual
  def sizeOfThing : Thing → Nat
    | .Bag o => 1 + sizeOfObject o
  def sizeOfObject : Object → Nat
    | .Bike => 42
    | .Box t => 1 + sizeOfThing t
end

axiom Nat.add_mod (a b n : Nat) : (a + b) % n = ((a % n) + (b % n)) % n

mutual
theorem aboutThings : ∀ t, sizeOfThing t % 2 = 1
  | .Bag o => by
    unfold sizeOfThing
    rw [Nat.add_mod, aboutObjects /- o-/]
    rfl

theorem aboutObjects : ∀ o, sizeOfObject o % 2 = 0
  | .Bike => rfl
  | .Box t => by
    unfold sizeOfObject
    rw [Nat.add_mod, aboutThings t]
    rfl
end
decreasing_by sorry

This prints

(kernel) unknown constant 'aboutObjects'
declaration uses 'sorry'

The kernel error goes away if I use aboutObjects o in the call to rw, i.e. with an explicit argument.

Expected behavior: No kernel errors.

Actual behavior: The kernel prints an error

Versions

~/build/lean/mathlib4 $ lean --version
Lean (version 4.2.0-rc1, commit a62d2fd49796, Release)

Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

@nomeata nomeata added the bug Something isn't working label Oct 5, 2023
@nomeata nomeata changed the title (kernel) unknown constant in mutually recursive definitoin (kernel) unknown constant in mutually recursive definition Oct 5, 2023
@nomeata
Copy link
Collaborator Author

nomeata commented Nov 16, 2023

Smaller reproducer:

opaque myId : (Nat → Nat) → (Nat → Nat) := id

mutual
def foo : Nat → Nat
  | .zero => 0
  | .succ n => (myId bar) n
def bar : Nat → Nat
  | .zero => 0
  | .succ n => foo n
end
termination_by foo n => n; bar n => n

The recursive call seems to be missing an argument. Maybe packDomain, or a pass before packDomain needs to eta-expand.

@nomeata nomeata self-assigned this Nov 16, 2023
@nomeata
Copy link
Collaborator Author

nomeata commented Nov 16, 2023

<internal monologe>
This code seems to be related:

    let isBad (e : Expr) : Bool :=
      match isAppOfPreDef? e with
      | none   => false
      | some i => e.getAppNumArgs > fixedPrefix + 1 || preDefsNew[i]!.declName != preDefs[i]!.declName
    if let some bad := valueNew.find? isBad then
      if let some i := isAppOfPreDef? bad then
        throwErrorAt preDef.ref "well-founded recursion cannot be used, function '{preDef.declName}' contains application of function '{preDefs[i]!.declName}' with #{bad.getAppNumArgs} argument(s), but function has arity {arities[i]!}"

but I am not sure I follow: Why should it be bad if a call has more arguments? As #2892 shows that can be perfectly fine if the result type happens to be a function type. Will dive a bit deeper here, and cook up a few test cases.

NB: replaceRecApps does eta-expand as needed. So other passes should do so as well.
</internal monologe>

nomeata added a commit that referenced this issue Nov 17, 2023
The `packMutual` code ought to reliably replace all recursive calls to
the functions in `preDefs`, even when they are under- or over-applied.
Therefore eta-expand if need rsp. keep extra arguments around.

Needs a tweak to `Meta.transform` to avoid mistaking the `f` in
`f x1 x2` as a zero-arity application.

Includes a test case.

This fixes #2628 and #2883.
nomeata added a commit that referenced this issue Nov 17, 2023
The `packMutual` code ought to reliably replace all recursive calls to
the functions in `preDefs`, even when they are under- or over-applied.
Therefore eta-expand if need rsp. keep extra arguments around.

Needs a tweak to `Meta.transform` to avoid mistaking the `f` in
`f x1 x2` as a zero-arity application.

Includes a test case.

This fixes #2628 and #2883.
github-merge-queue bot pushed a commit that referenced this issue Nov 22, 2023
The `packMutual` code ought to reliably replace all recursive calls to
the functions in `preDefs`, even when they are under- or over-applied.
Therefore eta-expand if need rsp. keep extra arguments around.

Needs a tweak to `Meta.transform` to avoid mistaking the `f` in
`f x1 x2` as a zero-arity application.

Includes a test case.

This fixes #2628 and #2883.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant