leanprover / leanprover/lean4

unfortunate interaction of `isDefEq`, `simp` and proof irrelevance

Open
#11,798 0 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

bug
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites
Description

On Zulip a user proposed the following MWE:

structure Struct (n : Nat) : Prop where

def Struct.data {n} (s : Struct n) : Nat := n

variable (m : Nat)

structure Extend m extends Struct m

@[simp]
theorem fact (h : Extend m) : h.data = m := rfl

set_option pp.all true in
set_option trace.Meta.Tactic.simp true in
example (h : Extend m) : h.data = m := by simp only [fact]
/-
[Meta.Tactic.simp.discharge] fact discharge ❌️
      Extend m
[Meta.Tactic.simp.unify] eq_self.{u_1}:1000, failed to unify
      @Eq.{?u.151} ?α ?a ?a
    with
      @Eq.{1} Nat (@Struct.data m (@Extend.toStruct m h)) m
-/

The surprising behavior here is that h is left as an obligation for the simp discharger to solve instead of being solved through unification. The main reason for this seems to be that in the unification problem:

 @Struct.data ?m (@Extend.toStruct ?m ?h) =?= @Struct.data m (@Extend.toStruct m h)

only ?m but not ?h gets assigned. This is presumably the case because the subterm (@Extend.toStruct m h) is a proof so we directly skip it and never see the opportunity to assign ?h. This is not a deal breaker of course because the user can manually supply h to simp but still an unfortunate situation.

Context

#lean4 > Bizarre `simp` error

Steps to Reproduce
  1. Run above example

Expected behavior: Should work without errors or alternatively simp should inform the user this is not a good pattern.

Actual behavior: Only works when h is provided explicitly to simp

Versions

Lean 4.28.0-nightly-2025-12-25
Target: x86_64-unknown-linux-gnu

Additional Information

[Additional information, configuration or data that might be necessary to reproduce the issue]

Impact

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

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 running the minimal self-contained Lean example from the issue against the reported nightly version and inspect the included simp trace. Investigate the isDefEq and simp interaction around proof irrelevance and the unification problem shown. Done means the example works without explicitly supplying h, or simp clearly reports that the pattern is unsupported, with regression coverage for the behavior.

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
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.