runtimeverification / runtimeverification/haskell-backend

Feature: custom unification rules

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

Nobody has claimed this yet.

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

Description

I've attempted to add the following rule to a KEVM proof:

    rule [fast-unification-failure]: { <kevm> <k> K_CELL </k> ... </kevm> #Equals <kevm> <k> K_CELL' </k> ... </kevm> } => #Bottom requires K_CELL =/=K K_CELL' [simplification(20)]

I can see in definition.kore (bug report attached storagevar00-spec.tar.gz), that the rule makes it into the backend. I've also marked several other rules with labels. I'm calling the backend with export KORE_EXEC_OPTS="--debug-equation VERIFICATION.fast-unification-failure --debug-equation VERIFICATION.test1 --debug-equation VERIFICATION.test2 --debug-equation VERIFICATION.test3 --bug-report tests/specs/benchmarks/storagevar00-spec --log tests/specs/benchmarks/storagevar00-spec.debug-log --log-format oneline --log-entries DebugTransition,DebugAttemptedRewriteRules", so that we can see attempts of these equations.

In the debug log (attached storagevar00-spec.debug-log.txt), I can see that equation test1 in exercised, but simplification rule fast-unification-failure never is. I use command grep 'DebugAttemptEquation' tests/specs/benchmarks/storagevar00-spec.debug-log | cut -d ':' -f3-4 | sort -u to see this.

Can the Haskell backend try user-supplied unification rules before trying the default unification algorithm when applying semantic rules? Maybe if they are simplification(N) for N < 50 rules, or N < 25?

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 attached definition.kore and storagevar00-spec.debug-log.txt, then reproduce the command using tests/specs/benchmarks/storagevar00-spec and inspect the DebugAttemptEquation entries for test1 and fast-unification-failure. Determine how user-supplied unification rules should be prioritized relative to the default algorithm, including the simplification threshold. Done means the backend attempts the requested custom rule when applying semantic rules.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
backend
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.