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

Calculus annotations: disallow unsound recursion #63

Open
Philipp15b opened this issue Jan 7, 2025 · 0 comments
Open

Calculus annotations: disallow unsound recursion #63

Philipp15b opened this issue Jan 7, 2025 · 0 comments
Labels
bug Something isn't working enhancement New feature or request

Comments

@Philipp15b
Copy link
Collaborator

We should also add checks that prevent users doing unsound recursive calls.

For example, this example is unsound w.r.t. wp semantics:

@wp
proc unsound() -> (x: Bool)
    pre ?(true)
    post ?(x == false)
{
    x = unsound()
}

The reason is that the call encoding implicitly assumes doing Park induction is valid, but it's not valid w.r.t. the least fixed point semantics and lower bounds (proc).

So we should disallow calls in:

  • procs w.r.t. wp and ert (because of lfp semantics)
  • coprocs w.r.t. wlp (because of gfp semantics)

It might be possible to relax these conditions, for example if we know that the call graph is acyclic. But I'm not sure about that right now.

@Philipp15b Philipp15b added bug Something isn't working enhancement New feature or request labels Jan 7, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant