runtimeverification / runtimeverification/haskell-backend

Internal representation of `if _ then _ else _`

Open
#945 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

design feature ml-research
Dominant language
Haskell
Stars
224
Forks
43
PR merge metrics
No merged PRs in 30d

Description

It often happens (particularly during function evaluation) that we have if _ then _ else _ patterns, which are encoded in Kore as

(P ∧ A) ∨ (¬P ∧ B)  // if P then A else B

which evaluates the predicate P twice. We would prefer to have something like an alias,

// cond-itional, in homage to Lisp
alias \cond(P, A, B) := (P ∧ A) ∨ (¬P ∧ B)

with some recognition that the predicate P need only be evaluated once.
Further, in a chain of conditions,

\cond(P, A, \cond(P', B, C))

if P = ⊤, then we never need to consider P'.

I would like to introduce an internal TermLike node,

-- represents a nested sequence of conditionals as above
newtype Cond variable = Cond { getCond :: Seq (Predicate variable, TermLike variable) }

data TermLikeF variable
    = ...
    | CondF (Cond variable)

(Presently, using a Predicate in this place would introduce a circular dependency, but it is not complicated to refactor that dependency away.)

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 tracing the TermLikeF definition and the Predicate dependency mentioned in the issue, then inspect how the existing conjunction/disjunction encoding evaluates conditionals. The change is complete when nested conditionals can be represented by Cond without a circular dependency and can avoid reevaluating predicates or later branches when an earlier predicate is true.

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
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.