feat: proper let_fun support in simp#6220
Merged
leodemoura merged 7 commits intomasterfrom Nov 26, 2024
Merged
Conversation
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Nov 26, 2024
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Nov 26, 2024
|
Mathlib CI status (docs):
|
kim-em
added a commit
to leanprover-community/mathlib4
that referenced
this pull request
Nov 26, 2024
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Nov 26, 2024
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Nov 26, 2024
ghost
pushed a commit
to leanprover-community/batteries
that referenced
this pull request
Nov 26, 2024
ghost
pushed a commit
to leanprover-community/mathlib4
that referenced
this pull request
Nov 26, 2024
kmill
reviewed
Nov 26, 2024
| -/ | ||
| def isNonDepLetFun (e : Expr) : Bool := | ||
| let_expr letFun _ beta _ body := e | false | ||
| beta.isLambda && !beta.bindingBody!.hasLooseBVars && body.isLambda |
Collaborator
There was a problem hiding this comment.
I thought I'd mention that Lean.Expr.letFun? is an existing recognizer for letfuns, though it doesn't give anything in this case (it's able to deal with letfuns that have a non-lambda body, but that is a dependent letfun). There's also Lean.Expr.letFunAppArgs? to handle the case where the letfun is applied as a function (like (let_fun f := id; f) 2), which is used elsewhere to handle reducing letfuns.
JovanGerb
pushed a commit
to JovanGerb/lean4
that referenced
this pull request
Jan 21, 2025
This PR adds proper support for `let_fun` in `simp`.
kmill
added a commit
to kmill/lean4
that referenced
this pull request
Jun 24, 2025
This PR adds the following features to `simp`: - A routine for simplifying `let` telescopes, like what leanprover#6220 did for `letFun` telescopes. Furthermore, simp converts `letFun`s into `have`s (nondependent lets), and we remove the leanprover#6220 routine. - A `+letToHave` configuration option (enabled by default) that converts lets into haves when possible, when `-zeta` is set. Previosuly Lean would need to do a full typecheck the bodies of `let`s, but the `letToHave` procedure can be faster, and it modifies the `let`s in an entire expression at once. - A `+zetaHave` configuration option, to turn off zeta reduction of `have`s specifically. The motivation is that dependent `let`s can only be dsimped by let, so zeta reducing just nondependent lets is a reasonable way to make progress.
kmill
added a commit
to kmill/lean4
that referenced
this pull request
Jun 24, 2025
This PR adds the following features to `simp`: - A routine for simplifying `let` telescopes, like what leanprover#6220 did for `letFun` telescopes. Furthermore, simp converts `letFun`s into `have`s (nondependent lets), and we remove the leanprover#6220 routine. - A `+letToHave` configuration option (enabled by default) that converts lets into haves when possible, when `-zeta` is set. Previosuly Lean would need to do a full typecheck the bodies of `let`s, but the `letToHave` procedure can be faster, and it modifies the `let`s in an entire expression at once. - A `+zetaHave` configuration option, to turn off zeta reduction of `have`s specifically. The motivation is that dependent `let`s can only be dsimped by let, so zeta reducing just nondependent lets is a reasonable way to make progress.
kmill
added a commit
to kmill/lean4
that referenced
this pull request
Jun 26, 2025
This PR adds the following features to `simp`: - A routine for simplifying `let` telescopes, like what leanprover#6220 did for `letFun` telescopes. Furthermore, simp converts `letFun`s into `have`s (nondependent lets), and we remove the leanprover#6220 routine. - A `+letToHave` configuration option (enabled by default) that converts lets into haves when possible, when `-zeta` is set. Previosuly Lean would need to do a full typecheck the bodies of `let`s, but the `letToHave` procedure can be faster, and it modifies the `let`s in an entire expression at once. - A `+zetaHave` configuration option, to turn off zeta reduction of `have`s specifically. The motivation is that dependent `let`s can only be dsimped by let, so zeta reducing just nondependent lets is a reasonable way to make progress.
github-merge-queue bot
pushed a commit
that referenced
this pull request
Jun 27, 2025
This PR adds the following features to `simp`: - A routine for simplifying `have` telescopes in a way that avoids quadratic complexity arising from locally nameless expression representations, like what #6220 did for `letFun` telescopes. Furthermore, simp converts `letFun`s into `have`s (nondependent lets), and we remove the #6220 routine since we are moving away from `letFun` encodings of nondependent lets. - A `+letToHave` configuration option (enabled by default) that converts lets into haves when possible, when `-zeta` is set. Previously Lean would need to do a full typecheck of the bodies of `let`s, but the `letToHave` procedure can skip checking some subexpressions, and it modifies the `let`s in an entire expression at once rather than one at a time. - A `+zetaHave` configuration option, to turn off zeta reduction of `have`s specifically. The motivation is that dependent `let`s can only be dsimped by let, so zeta reducing just the dependent lets is a reasonable way to make progress. The `+zetaHave` option is also added to the meta configuration. - When `simp` is zeta reducing, it now uses an algorithm that avoids complexity quadratic in the depth of the let telescope. - Additionally, the zeta reduction routines in `simp`, `whnf`, and `isDefEq` now all are consistent with how they apply the `zeta`, `zetaHave`, and `zetaUnused` configurations. The `letToFun` option is addressing a TODO in `getSimpLetCase` ("handle a block of nested let decls in a single pass if this becomes a performance problem"). Performance should be compared to before #8804, which temporarily disabled the #6220 optimizations for `letFun` telescopes. Good kernel performance depends on carefully handling the `have` encoding. Due to the way the kernel instantiates bvars (it does *not* beta reduce when instantiating), we cannot use congruence theorems of the form `(have x := v; f x) = (have x ;= v'; f' x)`, since the bodies of the `have`s will not be syntactically equal, which triggers zeta reduction in the kernel in `is_def_eq`. Instead, we work with `f v = f' v'`, where `f` and `f'` are lambda expressions. There is still zeta reduction, but only when converting between these two forms at the outset of the generated proof.
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 adds proper support for
let_funinsimp.