Skip to content

Conversation

@samuelchassot
Copy link
Contributor

Description of changes:

update and select on Maps in the Boogie languages are defined by axioms. To add them, this PR adds a mechanism to add axioms for functions in the Boogie functions factory. These axioms are encoded in SMT for each type instantiations when encoding the functions.

By submitting this pull request, I confirm that you can use, modify, copy, and redistribute this contribution, under the terms of your choice.

@samuelchassot samuelchassot marked this pull request as draft July 29, 2025 21:13
@samuelchassot samuelchassot marked this pull request as ready for review July 29, 2025 21:15
atomb
atomb previously approved these changes Jul 29, 2025
@samuelchassot samuelchassot requested a review from shigoel as a code owner July 30, 2025 16:28
@samuelchassot
Copy link
Contributor Author

I wrote some code to extract the axioms from Strata.Boogie code (see Strata/Languages/Boogie/Examples/DDMAxiomExtractionExample.lean).
I cannot just call that in the Factory.lean as this creates a cycle in the imports.
However, we can at least copy/paste them, which is cleaner and less error prone. This could be automated via a script I guess.

For that to work though, the update and select functions must be typed, so I modified the translation to add the types.

@samuelchassot
Copy link
Contributor Author

The axiom generation should probably be elsewhere, any suggestion?

atomb
atomb previously approved these changes Jul 30, 2025
@samuelchassot
Copy link
Contributor Author

The CI fails because the Lambda translation now adds type information to applications of update and select, which change the guard messsages.

atomb
atomb previously approved these changes Aug 1, 2025
Copy link
Contributor

@atomb atomb left a comment

Choose a reason for hiding this comment

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

I'm inclined to merge this as-is because it provides functionality we really want and will serve as a regular reminder to encourage us to implement a way to write the axioms more concisely. :)

@samuelchassot
Copy link
Contributor Author

I'm inclined to merge this as-is because it provides functionality we really want and will serve as a regular reminder to encourage us to implement a way to write the axioms more concisely. :)

I'm just waiting on Shilpi's PR to be merged to un comment the concise version that is working :)

@atomb
Copy link
Contributor

atomb commented Aug 4, 2025

I'm inclined to merge this as-is because it provides functionality we really want and will serve as a regular reminder to encourage us to implement a way to write the axioms more concisely. :)

I'm just waiting on Shilpi's PR to be merged to un comment the concise version that is working :)

Ah, nice! In that case, let's wait for that PR.

@samuelchassot
Copy link
Contributor Author

There you go @atomb :)

Copy link
Contributor

@atomb atomb left a comment

Choose a reason for hiding this comment

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

Very nice! There's one stray TODO comment about something you've already done now.

Copy link
Contributor

@shigoel shigoel left a comment

Choose a reason for hiding this comment

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

LGTM!

@shigoel shigoel merged commit f795094 into main Aug 4, 2025
8 checks passed
@shigoel shigoel deleted the sam/mapAxioms branch August 4, 2025 22:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants