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

feat: refined variable behavior in proofs #4814

Merged
merged 3 commits into from
Aug 9, 2024
Merged

Conversation

Kha
Copy link
Member

@Kha Kha commented Jul 23, 2024

Resolves #2452. For theorems, section variables are now conditionally included when elaborating the theorem body and sending the result to the kernel based on their use in the header; elaboration of the header is unchanged. Definitions as well are unchanged for now because the cost/benefit ratio is much less clear for them.

Specifically, section variables are included if they

  • are directly referenced by the theorem header,
  • are included via the new include command in the current section,
  • are directly referenced by any variable included by these rules, OR
  • are instance-implicit variables that reference only variables included by these rules.

For porting, a new option deprecated.oldSectionVars is included to locally switch back to the old behavior.

breaking change

@Kha Kha changed the base branch from master to nightly-with-mathlib July 23, 2024 17:04
@github-actions github-actions bot added the toolchain-available A toolchain is available for this PR, at leanprover/lean4-pr-releases:pr-release-NNNN label Jul 23, 2024
leanprover-community-mathlib4-bot added a commit to leanprover-community/batteries that referenced this pull request Jul 23, 2024
leanprover-community-mathlib4-bot added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 23, 2024
@semorrison semorrison added the release-ci Enable all CI checks for a PR, like is done for releases label Jul 24, 2024
@fpvandoorn
Copy link
Contributor

fpvandoorn commented Jul 25, 2024

are instance-implicit variables that reference any variable included by these rules.

Should this be "are instance-implicit variables and all referenced variables are included by these rules."?
For example, if I have

variable {R : Type*} [CommRing R] {M : Type*} [AddCommGroup M] [Module R M]

If only one of R/M is referenced, Module R M should not be included.

(I would also love it if include supports binder updates)

@Kha
Copy link
Member Author

Kha commented Jul 26, 2024

are instance-implicit variables that reference any variable included by these rules.

Should this be "are instance-implicit variables and all referenced variables are included by these rules."? For example, if I have

Makes sense to me, updated.

(I would also love it if include supports binder updates)

Would include {v} be equivalent to variable {v} include v? I'm not sure yet what to think about such overloading of semantics

leanprover-community-mathlib4-bot added a commit to leanprover-community/batteries that referenced this pull request Jul 26, 2024
leanprover-community-mathlib4-bot added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 26, 2024
@fpvandoorn
Copy link
Contributor

Yes, those would be equivalent.

In Mathlib we are striving towards using variable {v} and include v only using in (i.e. variable {v} or include v is banned, you should solely use variable {v} in and include v in).
If we follow that rule, then the ability to write include {v} means that we don't need variable {v} anymore in Mathlib, since all its uses can be replaced by include.

@semorrison
Copy link
Collaborator

Yes, those would be equivalent.

In Mathlib we are striving towards using variable {v} and include v only using in (i.e. variable {v} or include v is banned, you should solely use variable {v} in and include v in). If we follow that rule, then the ability to write include {v} means that we don't need variable {v} anymore in Mathlib, since all its uses can be replaced by include.

@fpvandoorn, I've finally started looking at Mathlib under this PR (the lean-pr-testing-4814 branch). (It is going to be epic! :-)

I've already encountered a few places where is seems rather inconvenient for only using include ... in, rather than bounded by a section. Please see leanprover-community/mathlib4@c3ec6be for the first two examples I encountered.

@leanprover-community-mathlib4-bot leanprover-community-mathlib4-bot added the breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan label Jul 29, 2024
@leanprover-community-mathlib4-bot
Copy link
Collaborator

leanprover-community-mathlib4-bot commented Jul 29, 2024

Mathlib CI status (docs):

@semorrison
Copy link
Collaborator

semorrison commented Jul 29, 2024

Re: looking at Mathlib on this PR. So far there are two classes of problems: typeclasses hypothesis being included which should not be (for which the new linter is really helpful), and variables with need an include.

Fixing the first class of problems requires either adding sections to bound variable [...] scopes, using variable ... in, or reordering results.

I propose that for anyone working on the Mathlib branch for this PR, we try to backport all the changes of the first form.

A reasonable workflow seems to be:

  • As you make changes on lean-pr-testing-4814, any changes that use include (i.e. which will not work on master), you immediately stage.
  • But any changes for excluding typeclasses hypotheses you leave unstage.
  • At suitable intervals, make a commit of the stages changes on lean-pr-testing-4814
  • Then stash the remaining changes, make a new branch off master, make a PR from it, and then merge that branch cherry-pick that commit back to lean-pr-testing-4814. (See first example of such a PR at [Merged by Bors] - chore: backports for leanprover/lean4#4814 (part 1) leanprover-community/mathlib4#15245.)

(We have have following a similar workflow for the byAsSorry branch, c.f. zulip discusssion.)

This is going to be a massive adaptation exercise to get this working, and I will need help to get it done.

semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
semorrison added a commit to leanprover-community/batteries that referenced this pull request Jul 29, 2024
semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
@semorrison
Copy link
Collaborator

are instance-implicit variables that reference any variable included by these rules.

Should this be "are instance-implicit variables and all referenced variables are included by these rules."? For example, if I have

Makes sense to me, updated.

@Kha, I think this change may have not worked as intended. In Mathlib on lean-pr-testing-4814 I am seeing:

section Trans

variable [IsTrans N r] (m n : M) {a b c d : N}

--  Lemmas with 3 elements.
theorem act_rel_of_rel_of_act_rel (ab : r a b) (rl : r (μ m b) c) : r (μ m a) c :=
  _root_.trans (act_rel_act_of_rel m ab) rl

theorem rel_act_of_rel_of_rel_act (ab : r a b) (rr : r c (μ m a)) : r c (μ m b) :=
  _root_.trans rr (act_rel_act_of_rel _ ab)

end Trans

failing with failed to synthesize IsTrans N r, despite both the arguments of IsTrans being mentioned in the theorem statement.

(I have no idea why in Mathlib the first argument of IsTrans is explicit rather than implicit -- I'll investigate that too...)

Let me know if you'd like a minimization of this.

@semorrison
Copy link
Collaborator

semorrison commented Jul 29, 2024

@Kha, another bug, where typeclass arguments that are included transitively can be included with multiplicity, apparently!

Again on lean-pr-testing-4814, in Mathlib.Order.Monotone, we see:

variable (α) [Preorder α] [Nonempty α] [NoMinOrder α] [NoMaxOrder α]

/-- If `α` is a nonempty preorder with no minimal or maximal elements, then there exists a strictly
monotone function `f : ℤ → α`. -/
theorem exists_strictMono : ∃ f : ℤ → α, StrictMono f := by
  inhabit α
  rcases Nat.exists_strictMono' (default : α) with ⟨f, hf, hf₀⟩
  rcases Nat.exists_strictAnti' (default : α) with ⟨g, hg, hg₀⟩
  refine ⟨fun n ↦ Int.casesOn n f fun n ↦ g (n + 1), strictMono_int_of_lt_succ ?_⟩
  rintro (n | _ | n)
  · exact hf n.lt_succ_self
  · show g 1 < f 0
    rw [hf₀, ← hg₀]
    exact hg Nat.zero_lt_one
  · exact hg (Nat.lt_succ_self _)

resulting in the signature

Int.exists_strictMono.{u} (α : Type u) [Preorder α] [Preorder α] [Nonempty α] [NoMinOrder α] [NoMaxOrder α] :
  ∃ f, StrictMono f

where apparently [Preorder α] has been added twice, once because [NoMinOrder α] needs it and again because [NoMaxOrder α] needs it.

Again, please let me know if you'd like an minimisation.

@semorrison
Copy link
Collaborator

And another problem, @Kha! We have places in Mathlib where people have add implicit arguments that could otherwise be automatically included instance arguments, on the principle that it is faster/better to find these by unification from later arguments that to redo typeclass search.

Here's an example from Mathlib in Mathlib.Algebra.GroupWithZero:

@[simp]
lemma coe_copy {_ : MulZeroOneClass α} {_ : MulZeroOneClass β} (f : α →*₀ β) (f' : α → β) (h) :
    (f.copy f' h) = f' := rfl

lemma copy_eq {_ : MulZeroOneClass α} {_ : MulZeroOneClass β} (f : α →*₀ β) (f' : α → β) (h) :
    f.copy f' h = f := DFunLike.ext' h

It's perfectly okay on master to just omit these, and instead we get corresponding instance arguments included.

However on lean-pr-testing-4814, we get warning, because the signature becomes:

MonoidWithZeroHom.coe_copy.{u_2, u_3} {α : Type u_2} {β : Type u_3} [MulZeroOneClass α] [MulZeroOneClass β] :
  ∀ {x : MulZeroOneClass α} {x_1 : MulZeroOneClass β} (f : α →*₀ β) (f' : α → β) (h : f' = ⇑f), ⇑(f.copy f' h) = f'

I'm uncertain the best way to proceed here. Probably we ought to make the variable inclusion mechanism robust to this, and decline to include instance arguments if there are already there as implicit arguments. In this particular case it's fine to just remove them, but I don't think that is always going to be true.

Again, let me know if you want a minimization.

@semorrison
Copy link
Collaborator

And more. :-)

We may need to pull in typeclass arguments because they mention the type of an included argument, not just the argument itself.

For example in Mathlib we have in Mathlib.Algebra.Ring.Divisibility.Basic:

variable [Semigroup α] [Semigroup β] {F : Type*} [EquivLike F α β] [MulEquivClass F α β] (f : F)

theorem map_dvd_iff {a b} : f a ∣ f b ↔ a ∣ b :=
  let f := MulEquivClass.toMulEquiv f
  ⟨fun h ↦ by rw [← f.left_inv a, ← f.left_inv b]; exact map_dvd f.symm h, map_dvd f⟩

theorem MulEquiv.decompositionMonoid [DecompositionMonoid β] : DecompositionMonoid α where
  primal a b c h := by
    rw [← map_dvd_iff f, map_mul] at h
    obtain ⟨a₁, a₂, h⟩ := DecompositionMonoid.primal _ h
    refine ⟨symm f a₁, symm f a₂, ?_⟩
    simp_rw [← map_dvd_iff f, ← map_mul, eq_symm_apply]
    iterate 2 erw [(f : α ≃* β).apply_symm_apply]
    exact h

Here include f on MulEquiv.decompositionMonoid (or just writing it as an explicit argument) doesn't suffice to pull in [MulEquivClass F α β].

Making matters worse, if we just change the theorem statement to

theorem MulEquiv.decompositionMonoid 
    [MulEquivClass F α β] (f : F) [DecompositionMonoid β] : DecompositionMonoid α where

then we get the incorrect warning:

included section variable '[MulEquivClass F α β]' is not used in 'MulEquiv.decompositionMonoid', consider excluding it

I can work around this by just not making it a section variable at all and instead including it directly in both theorems here.

(As above with minimization. :-)

semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Jul 29, 2024
@fpvandoorn
Copy link
Contributor

Yes, those would be equivalent.
In Mathlib we are striving towards using variable {v} and include v only using in (i.e. variable {v} or include v is banned, you should solely use variable {v} in and include v in). If we follow that rule, then the ability to write include {v} means that we don't need variable {v} anymore in Mathlib, since all its uses can be replaced by include.

@fpvandoorn, I've finally started looking at Mathlib under this PR (the lean-pr-testing-4814 branch). (It is going to be epic! :-)

I've already encountered a few places where is seems rather inconvenient for only using include ... in, rather than bounded by a section. Please see leanprover-community/mathlib4@c3ec6be for the first two examples I encountered.

We should probably not strive to do this immediately. Another thing we can consider is to have (in the long-term) no explicit variables, instead repeating those in each theorem statement. That should also reduce the number of includes.
But given your example we maybe want to allow having a global include directly after the corresponding variable statement. Then whenever that variable is visible it will have the include statement.

semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Aug 8, 2024
Parcly-Taxel added a commit to leanprover-community/mathlib4 that referenced this pull request Aug 8, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 8, 2024
j-loreaux added a commit to leanprover-community/mathlib4 that referenced this pull request Aug 8, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 8, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 9, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 9, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 9, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 9, 2024
semorrison added a commit to leanprover-community/mathlib4 that referenced this pull request Aug 9, 2024
@Kha Kha marked this pull request as ready for review August 9, 2024 09:14
@Kha Kha requested a review from TwoFX as a code owner August 9, 2024 09:14
@Kha Kha requested a review from semorrison as a code owner August 9, 2024 09:15
@Kha Kha changed the title feat: new variable command feat: refined variable behavior in proofs Aug 9, 2024
@Kha Kha changed the base branch from nightly-with-mathlib to master August 9, 2024 09:50
@Kha Kha merged commit 5da9038 into leanprover:master Aug 9, 2024
21 checks passed
@Kha Kha deleted the new-variable branch August 9, 2024 09:50

Variable declarations have the same flexibility as regular function paramaters. In particular they
can be [explicit, implicit][binder docs], or [instance implicit][tpil classes] (in which case they
can be anonymous). This can be changed, for instance one can turn explicit variable `x` into an
implicit one with `variable {x}`. Note that currently, you should avoid changing how variables are
bound and declare new variables at the same time; see [issue 2789] for more on this topic.

In *theorem bodies* (i.e. proofs), variables are not included based on usage in order to ensure that
Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@david-christiansen I merged this version for now to avoid a stale update-stage0, but please feel free to refine!

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think the text is perfectly fine as-is. I'll do a refinement pass when I get to that chapter of the manual.

mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 9, 2024
mathlib-bors bot pushed a commit to leanprover-community/mathlib4 that referenced this pull request Aug 13, 2024
This one is a bit awkward / done badly. I reordered theorems in order to avoid pulling in `SmoothManifoldWithCorners` unnecessarily, but I didn't preserve the section headings properly. :-(
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
backport releases/v4.11.0 breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan release-ci Enable all CI checks for a PR, like is done for releases toolchain-available A toolchain is available for this PR, at leanprover/lean4-pr-releases:pr-release-NNNN
Projects
None yet
Development

Successfully merging this pull request may close these issues.

RFC: change variable inclusion mechanism
5 participants