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

Lambda support #16

Merged
merged 40 commits into from
Dec 2, 2024
Merged

Lambda support #16

merged 40 commits into from
Dec 2, 2024

Conversation

utkn
Copy link
Contributor

@utkn utkn commented Nov 15, 2024

This PR aims to add lambda support. To that end, the following changes have been made:

  • A new typeclass LawfulHeap has been added. This denotes the types that can be argued with separation logic predicates. Implementors must define the operations (union and disjoint) and prove some fundamental theorems about them. SLP now works over all types that implement LawfulHeap. State _ has been replaced with two types that implement LawfulHeap: ValHeap and State where ValHeap is the old state and State is a wrapper around ValHeap that adds a set of lambdas. We can construct lambda singletons with the [r ↣ l] which means r refers to the lambda l. This is a big change, and required many changes across the codebase.
  • AST: A new structure Lambda is introduced. A lambda expression Expr.lam is introduced. Moreover, FunctionIdent is extended to support references to lambda functions in the environment. Accordingly, lambda calls can be represented with Expr.calls.
  • Syntax: New syntax for creating and calling lambdas have been introduced. Lambdas can be constructed as
    let add = |a, b| : u8, u8 -> u8 { ... }, and they can be called with ^add(4 : u8, 7 : u8)
  • Semantics: Two new Omni rules (one for creating a lambda and one for calling lambdas) were added. A new theorem nested_triple is added that can be used by the steps tactic to deconstruct the goals of form P {e} Q with introduction rules of form {P1} e1 {Q} -> {P1 * H} e2 {Q * H}, like callLambda_intro. Corresponding introduction rules were added and integrated into the steps tactic.

Closes #6

@utkn utkn added the enhancement New feature or request label Nov 15, 2024
@utkn utkn self-assigned this Nov 15, 2024
@utkn utkn marked this pull request as ready for review November 27, 2024 08:27
@utkn utkn requested a review from kustosz November 27, 2024 08:27
Copy link
Contributor

@kustosz kustosz left a comment

Choose a reason for hiding this comment

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

Some changes needed, but this awesome! I'm glad this works and turned out so nice

Lampe/Lampe.lean Outdated Show resolved Hide resolved
Lampe/Lampe.lean Outdated Show resolved Hide resolved
Lampe/Lampe/Ast.lean Outdated Show resolved Hide resolved
Lampe/Lampe/Ast.lean Outdated Show resolved Hide resolved
Lampe/Lampe/Hoare/SepTotal.lean Show resolved Hide resolved
Lampe/Lampe/Semantics.lean Outdated Show resolved Hide resolved
Lampe/Lampe/Semantics.lean Show resolved Hide resolved
Lampe/Lampe/SeparationLogic/LawfulHeap.lean Outdated Show resolved Hide resolved
Lampe/Lampe/SeparationLogic/State.lean Outdated Show resolved Hide resolved
Lampe/Lampe/SeparationLogic/ValHeap.lean Outdated Show resolved Hide resolved
@utkn utkn requested a review from kustosz November 30, 2024 08:11
…field. Accordingly, ugly hacks to acommodate this were fixed
Lampe/Lampe.lean Outdated Show resolved Hide resolved
@utkn utkn merged commit 327a194 into main Dec 2, 2024
6 checks passed
@utkn utkn deleted the us/lambdas branch December 2, 2024 12:38
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Lambdas
2 participants