kframework / matching-logic-prover

15 stars 4 forks source link

Deterministic choice operators #63

Open nishantjr opened 4 years ago

nishantjr commented 4 years ago

When strategies such as kt generate multiple subgoals to prove a claim,
we currently use the | operator to handle each branch.
This is a bit mucky, since the strategies intended for the initial goals
are also discharged against the later goals complicating debugging.

e.g. If we have:

claim     a /\ b                                                                
strategy  and-split . ( strat-for-a | strat-for-b )                             

strat-for-a is used to prove a. Then, the prover first tries strat-for-a
to prove b, and fails. It then tries the second branch of the choice.


We propose two new strategies: one for introducing branches in to a proof-tree
and another for resolving them.

syntax IntroduceBranchStrategy  ::= List{Strategy, "&>"}                        
syntax ResolveBranchStrategy    ::= List{Strategy, "<|"}                        
rule (I1 &> Is) . (O1 <& Os) => (I1 . O1 &  Is . Os)                            
rule (I1 &> Is) . S => (I1 . S &>  Is . S)                                      
  requires notBool isResolveBranchStrategy(S)                                   

When the &> is followed by a strategy that is not <| it behaves
identically to &.
However, when followed by the <| strategy, each sub-strategy in the &>
is paired with the corresponding strategy in <|.

nishantjr commented 4 years ago

This will also a step needed towards generating proof objects.