Skip to content

feat: identify more fixed parameters #7166

Merged
nomeata merged 51 commits intomasterfrom
joachim/fixed-params
Mar 4, 2025
Merged

feat: identify more fixed parameters #7166
nomeata merged 51 commits intomasterfrom
joachim/fixed-params

Conversation

@nomeata
Copy link
Copy Markdown
Collaborator

@nomeata nomeata commented Feb 20, 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

def app (as : List α) (bs : List α) : List α :=
  match as with
  | [] => bs
  | a::as => a :: app as bs

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 bs

and 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 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

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

@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc February 20, 2025 15:27 Inactive
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc February 20, 2025 16:09 Inactive
@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 Feb 20, 2025
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
@ghost ghost added the builds-mathlib CI has verified that Mathlib builds against this PR label Feb 20, 2025
@ghost
Copy link
Copy Markdown

ghost commented Feb 20, 2025

Mathlib CI status (docs):

  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-02-20 17:14:54) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-02-24 10:43:21) View Log
  • 💥 Mathlib branch lean-pr-testing-7166 build failed against this PR. (2025-02-24 11:58:05) View Log
  • 💥 Mathlib branch lean-pr-testing-7166 build failed against this PR. (2025-02-25 09:57:58) View Log
  • 🟡 Mathlib branch lean-pr-testing-7166 build against this PR was cancelled. (2025-02-25 10:58:04) View Log
  • 🟡 Mathlib branch lean-pr-testing-7166 build against this PR was cancelled. (2025-02-25 11:28:23) View Log
  • 💥 Mathlib branch lean-pr-testing-7166 build failed against this PR. (2025-02-25 12:04:41) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-02-25 12:27:38) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-02-25 13:41:34) View Log
  • ❗ Mathlib CI can not be attempted yet, as the nightly-testing-2025-02-26 tag does not exist there yet. We will retry when you push more commits. If you rebase your branch onto nightly-with-mathlib, Mathlib CI should run now. (2025-02-26 09:44:23)
  • 💥 Mathlib branch lean-pr-testing-7166 build failed against this PR. (2025-02-27 10:20:08) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-02-27 11:51:09) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-03-02 16:57:15) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-03-03 12:38:46) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-03-03 17:51:06) View Log
  • ✅ Mathlib branch lean-pr-testing-7166 has successfully built against this PR. (2025-03-04 12:01:36) View Log
  • ❗ Batteries/Mathlib CI will not be attempted unless your PR branches off the nightly-with-mathlib branch. Try git rebase 23b5baa5ecb48489326e9765f15934360953dde8 --onto e3c6909ad593e5a966a449df5e92abb1f0dbc317. (2025-03-04 18:56:48)
  • ❗ Batteries/Mathlib CI will not be attempted unless your PR branches off the nightly-with-mathlib branch. Try git rebase e2ee629022f21a74b48765d19bcaf06879923b57 --onto e3c6909ad593e5a966a449df5e92abb1f0dbc317. (2025-03-04 22:28:52)

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 ghost added breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan and removed builds-mathlib CI has verified that Mathlib builds against this PR labels 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
@nomeata nomeata enabled auto-merge March 3, 2025 16:35
@nomeata nomeata added the changelog-language Language features and metaprograms label Mar 3, 2025
@nomeata nomeata added this pull request to the merge queue Mar 3, 2025
@nomeata nomeata removed this pull request from the merge queue due to a manual request Mar 3, 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
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc March 3, 2025 16:43 Inactive
@nomeata nomeata enabled auto-merge March 3, 2025 16:53
@nomeata nomeata added this pull request to the merge queue Mar 3, 2025
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

@github-merge-queue github-merge-queue bot removed this pull request from the merge queue due to failed status checks Mar 3, 2025
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc March 4, 2025 10:51 Inactive
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
github-merge-queue bot pushed a commit that referenced this pull request Mar 4, 2025
…#7324)

This PR changes the internal construction of well-founded recursion, to
not change the type of `fix`’s induction hypothesis in non-defeq ways.

Fixes #7322 and hopefully unblocks #7166.
@nomeata nomeata force-pushed the joachim/fixed-params branch from 5937465 to 6864392 Compare March 4, 2025 18:23
@nomeata nomeata enabled auto-merge March 4, 2025 18:23
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc March 4, 2025 18:40 Inactive
@nomeata nomeata added this pull request to the merge queue Mar 4, 2025
@github-merge-queue github-merge-queue bot removed this pull request from the merge queue due to a conflict with the base branch Mar 4, 2025
@nomeata nomeata enabled auto-merge March 4, 2025 21:46
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

builds-mathlib CI has verified that Mathlib builds against this PR changelog-language Language features and metaprograms 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: late fixed parameters in functional induction structural recursion cannot be used when index depends on non index

1 participant