runtimeverification / runtimeverification/haskell-backend

Failure to prune branch with a boolean function involving `==K`

Open
#3,560 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug
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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.