runtimeverification / runtimeverification/haskell-backend
Compute remainders in booster
Nobody has claimed this yet.
- Dominant language
- Haskell
- Stars
- 224
- Forks
- 43
- PR merge metrics
- No merged PRs in 30d
Description
Various issues with remainders have been identified in kore recently see #3948. These issues should not be addressed in kore due to various reasons, including kore not being actively maintained and the difficulties associated with reasoning/debugging of the kore backend. Instead, we need to implement remainder computation in booster where we can then more efficiently explore various optimisations suggested in the aforementioned issue. This issue should serve as the design document for implementing the remainder computation algorithm.
Currently, the booster aborts in the following scenarios and what i think we should do:
- when the match is indeterminate, e.g. matching
C(...)withf(...)wherefis a function andCis a constructor (only aborts if this happens after a round of configuration simplification)
action: split the current state by- adding
C(...) == f(...)to path constraints and continue with current rule and then try all remaining rules - adding
C(...) =/= f(...)to path constraints and then try all remaining rules
- adding
- rule does not preserve definedness
action:add #Ceil(<term>)to path conditions for the sub<term>which does not preserve definedness and continue - requires clause
Ccould not be determined to be true
action: split the current state by- adding
Cto path constraints and continue with current rule and then try all remaining rules - adding
notBool Cto path constraints and then try all remaining rules
- adding
The changes above should mean we no longer abort and fall back to kore. However, this design is still incomplete/incorrect in the face of applying multiple rules with different priorities: https://github.com/runtimeverification/haskell-backend/blob/master/docs/2019-08-29-Remainders-for-priority-rules.md
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading the remainder design document at docs/2019-08-29-Remainders-for-priority-rules.md and the related issue #3948, then inspect the booster remainder-handling paths. The work is complete when booster handles the listed indeterminate matches, definedness failures, and unresolved requires clauses without aborting or falling back to kore, including the priority-rule behavior still noted as incomplete.
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
- Needs clarification
- Newbie friendliness
- 20/100