leanprover / leanprover/lean4

Failed to generate equality theorems

Open
#2,237 3 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

P-low
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

Pasted from Zulip:

inductive Ty where
| star: Ty
notation " ✶ " => Ty.star

abbrev Context : Type := List Ty

inductive Lookup : Context → Ty → Type where
| z : Lookup (t :: Γ) t

inductive Term : Context → Ty → Type where
| var : Lookup Γ a → Term Γ a
| lam : Term (✶ :: Γ) ✶ → Term Γ ✶
| ap : Term Γ ✶ → Term Γ ✶ → Term Γ ✶

abbrev plus : Term Γ a → Term Γ a
| .var i => .var i
| .lam n => .lam (plus n)
| .ap (.lam _) m => plus m -- This case takes precedence over the next one.
| .ap l m => (plus l).ap (plus m)

-- I wish to be able to prove the following "by definition":
example : plus (.ap l m) = (plus l).ap (plus m) := by
  unfold plus
--^^ failed to generate equality theorems for `match` expression `plus.match_1`

Expected behavior: The plus definition gets unfolded. IIRC since it's recursive, it should be unfolded only once.

Actual behavior: The last line generates the following error message:

failed to generate equality theorems for `match` expression `plus.match_1`
Γ : Context
a : Ty
motive : Term Γ a → Sort u_1
n : Term ( ✶ :: Γ) ✶
h_1 : (i : Lookup Γ a) → motive (Term.var i)
h_2 : (n : Term ( ✶ :: Γ) ✶ ) → motive (Term.lam n)
h_3 : (a : Term ( ✶ :: Γ) ✶ ) → (m : Term Γ ✶ ) → motive (Term.ap (Term.lam a) m)
h_4 : (l m : Term Γ ✶ ) → motive (Term.ap l m)
⊢ Eq.rec (fun x motive h_1 h_2 h_3 h_4 h => (_ : Term.lam n = x) ▸ h_2 n) (_ : ✶ = a) (Term.lam n) motive h_1 h_2 h_3 h_4
      (_ : HEq (Term.lam n) (Term.lam n)) =
    h_2 n

Reproduces how often: 100%

Versions

lean-toolchain: leanprover/lean4:nightly-2023-05-16
OS: macOS Ventura 13.4 22F66 arm64

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the self-contained plus example with the stated Lean nightly version and inspect the failed equality-theorem generation for plus.match_1. Done means unfold plus succeeds for the example and the recursive definition unfolds once as expected, without the reported error.

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
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.