runtimeverification / runtimeverification/haskell-backend

User-defined Set simplification rule not applied

Open
#2,700 9 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

On K master commit (72d33ae0e0), the following very simple spec does not work. This affects some KEVM proofs which are being ported.

requires "domains.md"

module TEST
    imports INT
    imports SET

    configuration <k> $PGM:Step </k>

    syntax Step ::= run ( Set ) | done ( Set )

    rule <k> run(S) => done(S) ... </k>

    syntax Bool ::= pred ( Int ) [function, no-evaluators]

    rule .Set -Set _ => .Set [simplification]
    rule (SetItem(X) REST) -Set SetItem(Y) => SetItem(X) (REST -Set SetItem(Y)) requires pred(X) andBool notBool pred(Y) [simplification]

    rule pred(X) => false requires 1 <=Int X andBool X <=Int 9 [simplification]
endmodule

module TEST-SPEC
    imports TEST

    claim <k> run(SetItem(1) -Set SetItem(X)) => done(SetItem(1)) ... </k> requires pred(X)

endmodule

To reproduce the failure:

kompile --backend haskell test.k --main-module TEST --syntax-module TEST
kprove test.k --def-module TEST --spec-module TEST-SPEC

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 by reproducing the failure with kompile --backend haskell test.k --main-module TEST --syntax-module TEST and kprove test.k --def-module TEST --spec-module TEST-SPEC. Inspect how the simplification rules in the TEST module interact with the claim in TEST-SPEC. Done means the provided proof succeeds for the user-defined Set rules.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
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.