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

Don't fold lets if the let-bound variable occurs under a lambda-abstraction #3002

Closed
lukaszcz opened this issue Sep 6, 2024 · 0 comments · Fixed by #3029
Closed

Don't fold lets if the let-bound variable occurs under a lambda-abstraction #3002

lukaszcz opened this issue Sep 6, 2024 · 0 comments · Fixed by #3029
Assignees
Milestone

Comments

@lukaszcz
Copy link
Collaborator

lukaszcz commented Sep 6, 2024

Currently, a let is always folded if the bound variable occurs at most once. But this is incorrect if the variable occurs under a lambda-abstraction, because the lambda may (and typically will) be passed to another function and called multiple times. This can duplicate the computation of the let-bound value, potentially even changing the asymptotic complexity.

Example:

f (lst1 lst2 : List Nat) : Bool :=
  let s := sum lst2
  in
  all (x in lst1)
    x > s;

The let-folding folds the s resulting in:

f (lst1 lst2 : List Nat) : Bool :=
  all (x in lst1)
    x > sum lst2;

The computation of sum lst2 was moved inside the loop.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant