runtimeverification / runtimeverification/haskell-backend

Cannot apply rule for symbolic list with multiple elements

Open
#2,391 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

Symbolic list unification fails with multiple elements

To reproduce:

tmp.k:

module TMP
  imports INT
  imports LIST

  syntax KItem ::= "push" | "pop"
  syntax KItem ::= Int

  rule  <k> push => .K ... </k>
        <stack> (.List => ListItem(1)) ... </stack>

  rule  <k> pop => .K ... </k>
        <stack> (ListItem(_:KItem) => .List) ... </stack>
    [label(xyzzy)]

  configuration
    <T>
      <k color="green"> .K </k>
      <stack> .List </stack>
    </T>

endmodule

tmp-proof.k:

module TMP-PROOF
  imports TMP

  claim 
      <T>
        <k> push ~> push ~> pop ~> pop ~> K:K </k>
        <stack> Stack:List </stack>
      </T>
      =>
      <T>
        <k> K </k>
        <stack> Stack </stack>
      </T>
endmodule

to run:

kompile tmp.k --backend haskell && kprove tmp-proof.k

The repl provides no reason explaining why the xyzzy rule is not applied:

Kore (0)> step 2
Kore (2)> try xyzzy
No explanation given
Kore (2)> 

Note that the claim above works with a single push/pop, i.e. <k> push ~> pop ~> K:K </k>

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 tmp.k symbolic list rules and tmp-proof.k claim, then reproduce the failure with kompile tmp.k --backend haskell && kprove tmp-proof.k. Inspect the REPL behavior for try xyzzy after the two pushes; done means the multiple-element case is handled and the REPL no longer reports no explanation for the failed application.

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.