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

support strongest-postcondition reasoning #763

Open
3 tasks
lsf37 opened this issue Jun 5, 2024 · 1 comment
Open
3 tasks

support strongest-postcondition reasoning #763

lsf37 opened this issue Jun 5, 2024 · 1 comment
Labels
proof engineering nicer, shorter, more maintainable etc proofs proof tools convenience, automation, productivity tools

Comments

@lsf37
Copy link
Member

lsf37 commented Jun 5, 2024

We currently have _sp rules for a number of the basic monad constructs, and we're using them manually in some situations, e.g. to avoid case blow-up in wp reasoning or when chaining trivial steps in corres proofs.

We should:

  • consistently support at least all of the basic nondet monad constructs with _sp rules -- I think they do have to be manually stated, but their proofs should all follow automatically from the corresponding wp rule
  • have a basic sp tactic, analogous to wp, but not as sophisticated. For a first version, I would propose a simple Eisbach method that repeatedly applies an sp set, and potentially automatically does an sp_pre (analogously to wp_pre).
  • find (most of) the existing manual _sp proofs and replace these to make sure the automation works and is convenient enough to use

I don't think we need a full-blown wp equivalent for sp, because we do not want to switch over to general sp reasoning or use more of it than necessary (to avoid duplicating rules for kernel functions). This issue only proposes to make those instances where it would be beneficial to use more ergonomic to use and easier to read/review.

MCS seems to have a higher use count of sp rules, so we should make sure to test the method there.

@lsf37 lsf37 added proof engineering nicer, shorter, more maintainable etc proofs proof tools convenience, automation, productivity tools labels Jun 5, 2024
@lsf37
Copy link
Member Author

lsf37 commented Jun 5, 2024

There is also a question about which other monads to support (e.g. error and/or reader monad), but so far most of the instances I've seen are on the plain nondet monad, so I'd vote for starting small and doing that one properly first.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
proof engineering nicer, shorter, more maintainable etc proofs proof tools convenience, automation, productivity tools
Projects
None yet
Development

No branches or pull requests

1 participant