runtimeverification / runtimeverification/haskell-backend

Add a lightweight check for `requires` of equations when matching is indeterminate

Open
#4,053 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

When matching of a function equation is indeterminate, Booster will abort the application of this function. However, sometimes the requires clause of the same equation can fully instantiated with the determinate part of the matching substitution. If the instantiated requires clause is false, we are safe to conclude that the equation does not apply, and we can proceed to attempting other equations of this function.

@PetarMax suggests to tweak the algorithm of applying equations:

  • when matching is indeterminate, extract the determinate part of the substitution
  • if that is non-empty, apply it to the requires clause and simplify with LLVM
  • if any of the conjuncts is false --- we are safe to conclude the equation does not apply

Notes:

  • the result of the equation application can only become negative or remain indeterminate. There's no way we can apply the equation if matching is indeterminate
  • it is critical to not call the SMT solver on this requires clause, as it may introduce a massive performance regression. That's why we restrict ourselves to a concrete LLVM simplification and simplify the requires clause recursively with other equations.

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

Locate the algorithm that applies function equations and handles indeterminate matching. Trace how determinate substitutions reach requires clauses, ensuring only LLVM simplification and recursive equation simplification are used, not the SMT solver. Done means a false instantiated requires clause rejects the equation and other equations are attempted, while indeterminate matching otherwise remains non-applicable.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
backend
Issue type
Feature
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.