Skip to content

feat: proper let_fun support in simp#6220

Merged
leodemoura merged 7 commits intomasterfrom
letFunSimp
Nov 26, 2024
Merged

feat: proper let_fun support in simp#6220
leodemoura merged 7 commits intomasterfrom
letFunSimp

Conversation

@leodemoura
Copy link
Copy Markdown
Member

@leodemoura leodemoura commented Nov 26, 2024

This PR adds proper support for let_fun in simp.

@leodemoura leodemoura changed the title feat: feat: proper let_fun support in simp Nov 26, 2024
@leodemoura leodemoura marked this pull request as draft November 26, 2024 02:24
@leodemoura leodemoura added the changelog-language Language features and metaprograms label Nov 26, 2024
@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 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 ghost added the breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan label Nov 26, 2024
@ghost
Copy link
Copy Markdown

ghost commented 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 ghost added builds-mathlib CI has verified that Mathlib builds against this PR and removed breaks-mathlib This is not necessarily a blocker for merging: but there needs to be a plan labels Nov 26, 2024
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc November 26, 2024 19:00 Inactive
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
@leodemoura leodemoura marked this pull request as ready for review November 26, 2024 20:13
@github-actions github-actions bot temporarily deployed to lean-lang.org/lean4/doc November 26, 2024 20:20 Inactive
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
@leodemoura leodemoura added this pull request to the merge queue Nov 26, 2024
Merged via the queue into master with commit 54c4836 Nov 26, 2024
-/
def isNonDepLetFun (e : Expr) : Bool :=
let_expr letFun _ beta _ body := e | false
beta.isLambda && !beta.bindingBody!.hasLooseBVars && body.isLambda
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

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

2 participants