feat: identify more fixed parameters #7166
Merged
Conversation
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Feb 20, 2025
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Feb 20, 2025
|
Mathlib CI status (docs):
|
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Feb 24, 2025
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Feb 24, 2025
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Feb 24, 2025
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Feb 24, 2025
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Feb 25, 2025
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Feb 25, 2025
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Feb 25, 2025
github-merge-queue bot
pushed a commit
that referenced
this pull request
Mar 3, 2025
This PR extends the notion of “fixed parameter” of a recursive function
also to parameters that come after varying function. The main benefit is
that we get nicer induction principles.
Before the definition
```lean
def app (as : List α) (bs : List α) : List α :=
match as with
| [] => bs
| a::as => a :: app as bs
```
produced
```lean
app.induct.{u_1} {α : Type u_1} (motive : List α → List α → Prop) (case1 : ∀ (bs : List α), motive [] bs)
(case2 : ∀ (bs : List α) (a : α) (as : List α), motive as bs → motive (a :: as) bs) (as bs : List α) : motive as bs
```
and now you get
```lean
app.induct.{u_1} {α : Type u_1} (motive : List α → Prop) (case1 : motive [])
(case2 : ∀ (a : α) (as : List α), motive as → motive (a :: as)) (as : List α) : motive as
```
because `bs` is fixed throughout the recursion (and can completely be
dropped from the principle).
This is a breaking change when such an induction principle is used
explicitly. Using `fun_induction` makes proof tactics robust against
this change.
The rules for when a parameter is fixed are now:
1. A parameter is fixed if it is reducibly defq to the the corresponding
argument in each recursive call, so we have to look at each such call.
2. With mutual recursion, it is not clear a-priori which arguments of
another function correspond to the parameter. This requires an analysis
with some graph algorithms to determine.
3. A parameter can only be fixed if all parameters occurring in its type
are fixed as well.
This dependency graph on parameters can be different for the different
functions in a recursive group, even leading to cycles.
4. For structural recursion, we kinda want to know the fixed parameters
before investigating which argument to actually recurs on. But once we
have that we may find that we fixed an index of the recursive
parameter’s type, and these cannot be fixed. So we have to un-fix them
5. … and all other fixed parameters that have dependencies on them.
Lean tries to identify the largest set of parameters that satisfies
these criteria.
Note that in a definition like
```lean
def app : List α → List α → List α
| [], bs => bs
| a::as, bs => a :: app as bs
```
the `bs` is not considered fixes, as it goes through the matcher
machinery.
Fixes #7027
Fixes #2113
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Mar 3, 2025
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Mar 3, 2025
auto-merge was automatically disabled
March 3, 2025 17:09
Pull Request is not mergeable
This was referenced Mar 4, 2025
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Mar 4, 2025
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Mar 4, 2025
…chim/fixed-params
5937465 to
6864392
Compare
This was referenced Apr 25, 2025
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This PR extends the notion of “fixed parameter” of a recursive function also to parameters that come after varying function. The main benefit is that we get nicer induction principles.
Before the definition
produced
app.induct.{u_1} {α : Type u_1} (motive : List α → List α → Prop) (case1 : ∀ (bs : List α), motive [] bs) (case2 : ∀ (bs : List α) (a : α) (as : List α), motive as bs → motive (a :: as) bs) (as bs : List α) : motive as bsand now you get
app.induct.{u_1} {α : Type u_1} (motive : List α → Prop) (case1 : motive []) (case2 : ∀ (a : α) (as : List α), motive as → motive (a :: as)) (as : List α) : motive asbecause
bsis fixed throughout the recursion (and can completely be dropped from the principle).This is a breaking change when such an induction principle is used explicitly. Using
fun_inductionmakes proof tactics robust against this change.The rules for when a parameter is fixed are now:
This dependency graph on parameters can be different for the different functions in a recursive group, even leading to cycles.
Lean tries to identify the largest set of parameters that satisfies these criteria.
Note that in a definition like
the
bsis not considered fixes, as it goes through the matcher machinery.Fixes #7027
Fixes #2113