runtimeverification / runtimeverification/haskell-backend
Failure to prune branch with a boolean function involving `==K`
Nobody has claimed this yet.
- Dominant language
- Haskell
- Stars
- 224
- Forks
- 43
- PR merge metrics
- No merged PRs in 30d
Description
The backend fails to simplify a boolean function involving ==K when the function occurs inside a requires clause.
This is a minimal example which reproduces the bug:
verification.k
module VERIFICATION
imports BOOL
imports K-EQUAL
syntax Bar ::= "AA" | "BB" | Bar2
syntax Bar2 ::= "CC" Bar3
syntax Bar3 ::= "DD" | "EE"
syntax KItem ::= Bar
syntax Bool ::= #isAorB ( Bar ) [function, total]
rule #isAorB(OP) => OP ==K AA orBool OP ==K BB
syntax KItem ::= runLemma ( Bool )
| runLemma2 ( Bool )
| doneLemma( Bool )
// --------------------------------------
rule <k> runLemma( T ) => doneLemma( T ) ... </k>
rule <k> ( runLemma2( T ) => doneLemma ( false ) ) ... </k> requires notBool T
rule <k> ( runLemma2( T ) => doneLemma ( true ) ) ... </k> requires T
endmodule
spec.k
requires "verification.k"
module SPEC
imports VERIFICATION
imports BOOL
claim <k> runLemma ( #isAorB ( CC _ ) ) => doneLemma ( false ) ... </k>
claim <k> runLemma2 ( #isAorB ( CC _ ) ) => doneLemma ( false ) ... </k>
endmodule
Note that runLemma simply forces the evaluation of #isAorB ( CC _ ) into false, however runLemma2 makes two branches, one for evaluating to doneLemma ( false ) and another to doneLemma ( true ) based on a requires notBool #isAorB ( CC _ ) and requires #isAorB ( CC _ ) respectively.
The backend fails to prune the second branch, as it fails to rewrite true #Equals #isAorB ( CC _ ) to #Bottom even tho it was able to rewrite #isAorB ( CC _ ) into false on the other branch (this can be checked by disabling rule <k> ( runLemma2( T ) => doneLemma ( true ) ) ... </k> requires T ):
➜ kompile verification.k --backend haskell --no-haskell-binary
➜ kprove spec.k
kore-exec: [213254] Warning (WarnStuckClaimState):
The configuration's term doesn't unify with the destination's term and the configuration cannot be rewritten further. Location: /Users/sam/git/evm-semantics/spec.k:10:7-10:73
Context:
(InfoReachability) while checking the implication
<k>
doneLemma ( true ) ~> _DotVar1 ~> .
</k>
#And
{
true
#Equals
( CC _Gen0 ~> . ) ==K ( AA ~> . ) orBool ( CC _Gen0 ~> . ) ==K ( BB ~> . )
}
[Error] Prover: backend terminated because the configuration cannot be
rewritten further. See output for more details.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the minimal reproducer in verification.k and spec.k, then run kompile verification.k --backend haskell --no-haskell-binary followed by kprove spec.k. Trace why the requires branch does not rewrite true #Equals #isAorB (CC _) to #Bottom, while the other branch simplifies the function to false. Done means the impossible doneLemma(true) branch is pruned and the claim completes without the stuck-state error.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100