runtimeverification / runtimeverification/haskell-backend

Unsatisfiable side conditions in the initial configuration cause the backend to get stuck.

Open
#3,041 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Haskell
Stars
224
Forks
43
PR merge metrics
No merged PRs in 30d

Description

The bug occurs when the initial configuration is not satisfiable because of a side condition.
I'm not sure how to reproduce it with a program without an initial side condition. I expect the entire configuration to simplify to #Bottom.

$ cat test.k
module TEST
    imports BOOL

    configuration <k> true </k>

    syntax KItem ::= myBottom() [function]
    rule myBottom() => #Bottom
endmodule
$ kompile --backend haskell test.k
[Warning] Compiler: Could not find main syntax module with name TEST-SYNTAX in
definition.  Use --syntax-module to specify one. Using TEST as default.
$ kprint test-kompiled/definition.kore unsat-side-confition.kore
Cannot read file: test-kompiled/definition.kore/syntaxDefinition.kore
$ kprint test-kompiled unsat-side-confition.kore
  #Not ( {
    true
  #Equals
    true
  } )
#And
  <k>
    true ~> .
  </k>
$ krun --term --parser cat unsat-side-confition.kore
  #Not ( {
    true
  #Equals
    true
  } )
#And
  <k>
    true ~> .
  </k>

I argue that this behaviour should be supported so that it is consistent
with the following equivalent configurations:

$ kprint test-kompiled simplifies-to-unsat.kore
<k>
  myBottom ( ) ~> .
</k>
$ krun --term --parser cat simplifies-to-unsat.kore
#Bottom
$ kprint test-kompiled simplifies-to-unsat-2.kore
<k>
  {
    true
  #Equals
    false
  } ~> .
</k>
$ krun --term --parser cat simplifies-to-unsat-2.kore
#Bottom

This also happens when the configuration can take a step:

module TEST
    imports BOOL

    configuration <k> foo </k>
    syntax Foo ::= "foo" |  "bar"
    rule foo => bar
endmodule
user@cc9637af03e3:~/boogie/tmp/test-unsat-config$ kprint test-kompiled unsat-side-confition.kore
  #Not ( {
    true
  #Equals
    true
  } )
#And
  <k>
    foo ~> .
  </k>
user@cc9637af03e3:~/boogie/tmp/test-unsat-config$ krun --term --parser cat unsat-side-confition.kore
  #Not ( {
    true
  #Equals
    true
  } )
#And
  <k>
    foo ~> .
  </k>
user@cc9637af03e3:~/boogie/tmp/test-unsat-config$```

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

Reproduce the issue from test.k using kompile --backend haskell, then run krun on unsat-side-confition.kore and the two simplifying examples. Start by comparing how the backend handles the unsatisfiable initial side condition with configurations that simplify to #Bottom. Done means the initial configuration, including one that can step, evaluates consistently to #Bottom.

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
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.