`simp` produces a term that doesn't typecheck when used with `WellFounded.fix`
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 9.2k
- Forks
- 990
- Avg merge
- 1d 17h
- Merged PRs (30d)
- 175
Description
Prerequisites
- Put an X between the brackets on this line if you have done all of the following:
- Checked that your issue isn't already filed.
- Reduced the issue to a self-contained, reproducible test case.
Description
simp sometimes generates a proof that doesn't typecheck
Steps to Reproduce
prelude -- optional
import Init.WF
import Init.WFTactics
import Init.Data.Nat.Basic
namespace Nat'
protected def modCore (y : Nat) : Nat → Nat → Nat
| Nat.zero, x => x
| Nat.succ fuel, x => if 0 < y ∧ y ≤ x then Nat'.modCore y fuel (x - y) else x
protected def mod' (x y : @& Nat) : Nat :=
Nat'.modCore y x x
@[simp] theorem zero_mod' (b : Nat) : Nat'.mod' 0 b = 0 := rfl
end Nat'
namespace Nat
private def gcdF' (x : Nat) : (∀ x₁, x₁ < x → Nat → Nat) → Nat → Nat :=
match x with
| 0 => fun _ y => y
| succ x => fun f y => f (Nat'.mod' y (succ x)) sorry (succ x)
noncomputable def gcd' (a b : Nat) : Nat :=
WellFounded.fix (measure id).wf gcdF' a b
@[simp] theorem gcd'_zero_left (y : Nat) : gcd' 0 y = y :=
rfl
theorem gcd'_succ (x y : Nat) : gcd' (succ x) y = gcd' (Nat'.mod' y (succ x)) (succ x) :=
rfl -- replace with `id rfl` and everything is ok
-- VVVVVVVVVVVVVVV error here
@[simp] theorem gcd'_zero_right (n : Nat) : gcd' n 0 = n := by
cases n <;> simp [gcd'_succ]
end Nat
Expected behavior: simp should either succeed, or give a tactic failure
Actual behavior: simp succeeds, but the kernel rejects the proof with
application type mismatch
@Eq.ndrec Nat (succ n✝) (fun n => gcd' n 0 = n) (of_eq_true (eq_self (succ n✝)))
argument has type
succ n✝ = succ n✝
but function has type
(fun n => gcd' n 0 = n) (succ n✝) → ∀ {b : Nat}, succ n✝ = b → (fun n => gcd' n 0 = n) b
Reproduces how often: 100%
Versions
$ ~/.elan/bin/lean --version
Lean (version 4.0.0-nightly-2023-01-08, commit 74b3d101e967, Release)
Additional Information
Any additional information, configuration or data that might be necessary to reproduce the issue.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Run the self-contained reproducer with the listed Lean nightly version, using the Init.WF and Init.WFTactics imports. Start at the WellFounded.fix definition and the simp invocation in gcd'_zero_right; done means simp either reports a tactic failure or produces a proof accepted by the kernel.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100