leanprover / leanprover/lean4

disable rejection of `perm` simp lemmas, or override `perm` field for a simp lemma

Open
#1,743 4 comments 0 reactions 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

The simplifier identifies some simp lemmas as permutation lemmas (if the lhs and rhs differ only by a permutation of variables), and then rejects some rewrites by these lemmas.

This has undesirable effects, in particular when using simp lemmas with side conditions that independently prevent looping. It would be helpful to either be able to disable the check that rejects rewrites by perm lemmas, or on a per-lemma basis to override the perm field.

(This is a feature request, not a bug report.)

Steps to Reproduce
class AddCommMonoid (α : Type _) extends Add α where
  add_assoc : ∀ a b c : α, a + b + c = a + (b + c) 
  add_comm : ∀ a b : α, a + b = b + a

open AddCommMonoid

variable [AddCommMonoid α]

theorem comm (f : Nat → Nat → α) (_h : i < j) : f a j + f b i = f b i + f a j :=
  add_comm _ _

theorem comm_assoc (f : Nat → Nat → α) (h : i < j) : 
    f a j + (f b i + x) = f b i + (f a j + x) := by
  rw [← add_assoc, comm _ h, add_assoc]
  
set_option trace.Meta.Tactic.simp.rewrite true

example (f : Nat → Nat → α) : f a 5 + f b 3 + f c 0 = f c 0 + f b 3 + f a 5 := by
  simp only [comm, comm_assoc, add_assoc] -- succeeds

example (f : Nat → Nat → α) : f a 5 + f b 3 + f 37 0 = f 37 0 + f b 3 + f a 5 := by
  simp only [comm, comm_assoc, add_assoc] -- fails

Note here the two examples are identical, except that I have replaced c with 37 in the second example.
The intention here is that simp only [comm, comm_assoc, add_assoc] should sort a sum of f a i terms according to the value of i.

Expected behavior:

Both examples to succeed. I'd be happy if I needed to add some annotation that tells simp that comm should not be considered a perm lemma (because of the side condition), or to specify a configuration object for simp that disables the perm check.

Actual behavior:

The first example succeeds, tracing:

[Meta.Tactic.simp.rewrite] @comm:1000:perm, f a 5 + f b 3 ==> f b 3 + f a 5 
[Meta.Tactic.simp.rewrite] @AddCommMonoid.add_assoc:1000, f b 3 + f a 5 + f c 0 ==> f b 3 + (f a 5 + f c 0) 
[Meta.Tactic.simp.rewrite] @comm:1000:perm, f a 5 + f c 0 ==> f c 0 + f a 5 
[Meta.Tactic.simp.rewrite] @comm_assoc:1000:perm, f b 3 + (f c 0 + f a 5) ==> f c 0 + (f b 3 + f a 5) 
[Meta.Tactic.simp.rewrite] @AddCommMonoid.add_assoc:1000, f c 0 + f b 3 + f a 5 ==> f c 0 + (f b 3 + f a 5) 
[Meta.Tactic.simp.rewrite] @eq_self:1000, f c 0 + (f b 3 + f a 5) = f c 0 + (f b 3 + f a 5) ==> True 

The second example fails with unsolved goals, tracing:

[Meta.Tactic.simp.rewrite] @comm:1000:perm, f a 5 + f b 3 ==> f b 3 + f a 5 
[Meta.Tactic.simp.rewrite] @AddCommMonoid.add_assoc:1000, f b 3 + f a 5 + f 37 0 ==> f b 3 + (f a 5 + f 37 0) 
[Meta.Tactic.simp.rewrite] @comm:1000:perm, perm rejected f a 5 + f 37 0 ==> f 37 0 + f a 5 
[Meta.Tactic.simp.rewrite] @AddCommMonoid.add_assoc:1000, f 37 0 + f b 3 + f a 5 ==> f 37 0 + (f b 3 + f a 5) 
Versions

Lean (version 4.0.0-nightly-2022-10-12, commit aa845dee98e3, Release)

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 with src/Lean/Meta/Tactic/Simp/SimpTheorems.lean, where simp lemmas are identified as permutation lemmas, and src/Lean/Meta/Tactic/Simp/Rewrite.lean, where some rewrites are rejected. Reproduce the two examples from the issue and investigate a configuration or per-lemma override that allows the side-conditioned rewrite; done means both examples succeed without unintended looping.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
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.