Difference between revisions of "Membership in Goal"
imported>Laurent 
imported>Josselin (Update implementation part (SAT solver)) 

Line 102:  Line 102:  
= Implementation =  = Implementation =  
−  This section explain how the  +  This section explain how the reasoner has been implemented. 
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
=== Find a path ===  === Find a path ===  
−  Let's consider the following sequent : <math>x\in B,\quad  +  Let's consider the following sequent : <math> x \in B,\quad f \ovl \{ x \mapsto y \} \in A \rel B,\quad dom(A \cprod B) \subseteq C,\quad A \binter B\binter C \subseteq D \quad\vdash\quad x\in D </math> 
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
+  From the hypothesis "<math> f \ovl \{ x \mapsto y \} \in A \rel B </math>" the reasoner deduct the following predicates: <math> \{ x \in A , \quad x \in dom(A \cprod B) \} </math>  
−  +  The reasoner encodes the new hypotheses derived from the hypotheses and the negation of the goal, to SAT clauses by representing each inclusion of the form <math> A \subseteq B </math> into the clause <math>\{\lnot x\in A,\; x\in B\}</math> and then by encoding it in CNF format <math> \{1, 2\}</math>. In order to obtain a minimal solution, the clauses are inserted one by one into the SAT problem until the solver reports the problem as unsatisfiable.  
{ class="wikitable" style="textalign:center; width:80%;"  { class="wikitable" style="textalign:center; width:80%;"  
−  +  +  + SAT problem encoding 
−  
−  
−  
−  
−  
    
−    +  ! scope=col  Hypothesis 
−    +  ! scope=col  Clause 
−    +  ! scope=col  Dimacs format 
−  
    
−  <math>  +  <math>x \in B</math> 
−  +  <math>x \in B</math>  
−  <math>x\in  +  <math>2</math> 
−  <math>  
    
−  <math>  +  <math>x \in A</math> 
−  +  <math>x \in A</math>  
−  <math>x\in  +  <math>3</math> 
−  <math>  
    
−  <math>  +  <math>x \in dom(A \cprod B)</math> 
−  +  <math>x \in dom(A \cprod B)</math>  
−  <math>x\in  +  <math>4</math> 
−  <math>  
    
−  <math>  +  <math>dom(A \cprod B) \subseteq C</math> 
−  <math>\  +  <math> \lnot x \in dom(A \cprod B),\quad x \in C </math> 
−  +  <math>4 \quad 5 </math>  
−  <math>\  
    
−  <math>  +  <math>A \binter B \binter C \subseteq D</math> 
−  <math>\  +  <math>\lnot x \in A, \quad \lnot x \in B, \quad \lnot x \in C, \quad x \in D </math> 
−  +  <math>3 \quad 2 \quad 5 \quad 1</math>  
−  <math>\  
    
−  <math>  +  <math> \vdash\quad x \in D </math> 
−  +  <math>\lnot x \in D</math>  
−  +  <math>1</math>  
−  <math>\  
−  
−  
−  
−  <math>  
−  
}  }  
−  +  Afterwards, the clauses in the sat core sorted by their insertion order, are then reordered by using topological sorting. The reasonner traces each clause back to the corresponding hypotheses.  
+  
+  For each hypothesis into the list, a rationale is built and saved into an array at the index of the list. If the hypothesis denotes a membership, the rationale is directly saved into the array else it retrevies all needed rationales (already seen) and contained it into the array.  
+  
+  Finally, the reasoner checks that the generated rule is equal to the goal. If so, the sequent is discharged. Else, a failure is returned  
+  
+  
+  We see that the tactic may not find the most simple path to discharge the sequent. Moreover, there are some cases where the tactic is able to find a path but the reasoner is unable to prove it due to a weakness in the rules (see [[#Untreatedall the untreated cases]]). Example :  
+  :<math>x\in dom(f\bunion g)\binter A,~A\subseteq B,~dom(f)\bunion dom(g)\subseteq B~\vdash~x\in B</math>  
+  Depending on whether the tactic returns <math>\left\{x\in dom(f\bunion g)\binter A,~dom(f)\bunion dom(g)\subseteq B\right\}</math> or <math>\left\{x\in dom(f\bunion g)\binter A,~A\subseteq B\right\}</math>, the reasoner will fail or succeed. To prevent such hazardous behavior, rewriting should be proceeded.  
+  
= Unimplemented cases =  = Unimplemented cases = 
Revision as of 17:13, 20 November 2013
Contents
Objective
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.
This reasoner discharges sequents whose goal denotes a membership which can be inferred from hypotheses, such as the following:
Analysis
Usually, such sequents are proved by the external provers PP or ML. But, these provers have several drawbacks :
 They do not report needed hypotheses, so that a conservative choice is made to depend on all hypotheses.
 They take substantial time to prove them (even with the basic example given above, the difference in time execution is noticeable).
 If there are too many hypotheses, or if the expression of the or the intermediate sets is too complicated, they may get lost into details and not discharge.
This is particularly true when in the set expressions of each side of relations are not equal, such as in:
Such a reasoner thus increases the rate of automated proof, faster and with fewer needed hypotheses which makes proof rules more legible and proof replay less sensitive to modifications of the models.
Design Decision
Tactic
This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
Goal
The tactic (as the reasoner) should works only on goals such as :
For examples :
In the last example, the reasoner will not try to prove that belongs to and belongs to , but that the maplet belongs to the Cartesian product .
Hypotheses
Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic recovers two kinds of hypotheses :
 the ones related to the left member of the goal (this is the start point):
 the ones denoting inclusion (all but the ones matching the description of the first point) :
Then, it will search a link between those hypotheses so that the sequent can be discharged.
Find a path
Now that we recovered all the hypotheses that could be useful for the reasoner, it remains to find a path among the hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. always represent an expression (may be a domain, a range, etc.).
 The following sequent is provable because .
 The following sequent is provable because .
 By keeping the notation we also deduce that :
 For some relations, positions are needed to be known to continue to find hypotheses, but it is not always necessary.
By using these inclusions the tactic tries to find a path among the recovered hypotheses. Every one of them should only be used once, avoiding possible infinite loop .
Since Rodin 3.0, the path search is delegated to the Sat4j solver. The problem encoding to SAT is done by representing each inclusion of the form into the clause and feeding the solver with all clauses that derive from the hypotheses and the negation of the goal. As soon as the solver reports the problem as unsatisfiable, the tactic obtains an unsat core and traces it back to the corresponding hypotheses.
Reasoner
This part describe how the reasoner MembershipGoal works.
Goal
First, it checks that the goal matches the description made in the part tactic : . Thus, we record the member x as well as the set S
Input
Then, it checks that the input is a hypothesesReasonerInput (an input with an array of predicates). Every given predicates must be a hypothesis of the sequent. Only one must be a membership with the same member as the goal so that there are no ambiguity. All the other ones must denote set inclusion or equality.
Find a path
With the same reasoning as for the tactic, we try to find a path leading to discharge the goal.
Trusted Base
At that point, the reasoner performs the same jobs as the tactic which is quite complicated. That poses one problem : it is hard to prove the reasoner to be sound (only doing what it was meant to, not discharging sequents that cannot be proved). Because the reasoner is in the trusted base, we should be absolutely sure of what it performs. How to validate the found path ?
As we know, the reasoner condense several inferences rules in only one proof rule. To validate the found path, we have to validate every single inference rule. To achieve it, we create, internally to the reasoner, a small proof tree built from internal proof rules (implemented in class Rules). Each rule contains one predicate and an array of rules (its antecedents). When the path is searched, the corresponding rule is created. When the path is found, we check that the predicate of the root rule is the same as the goal. If not, it means the found path was incorrect, so the reasoner fails, else the sequent is discharged.
Example of rules :
Implementation
This section explain how the reasoner has been implemented.
Find a path
Let's consider the following sequent :
From the hypothesis "" the reasoner deduct the following predicates:
The reasoner encodes the new hypotheses derived from the hypotheses and the negation of the goal, to SAT clauses by representing each inclusion of the form into the clause and then by encoding it in CNF format . In order to obtain a minimal solution, the clauses are inserted one by one into the SAT problem until the solver reports the problem as unsatisfiable.
Hypothesis  Clause  Dimacs format 

Afterwards, the clauses in the sat core sorted by their insertion order, are then reordered by using topological sorting. The reasonner traces each clause back to the corresponding hypotheses.
For each hypothesis into the list, a rationale is built and saved into an array at the index of the list. If the hypothesis denotes a membership, the rationale is directly saved into the array else it retrevies all needed rationales (already seen) and contained it into the array.
Finally, the reasoner checks that the generated rule is equal to the goal. If so, the sequent is discharged. Else, a failure is returned
We see that the tactic may not find the most simple path to discharge the sequent. Moreover, there are some cases where the tactic is able to find a path but the reasoner is unable to prove it due to a weakness in the rules (see all the untreated cases). Example :
Depending on whether the tactic returns or , the reasoner will fail or succeed. To prevent such hazardous behavior, rewriting should be proceeded.
Unimplemented cases
Some cases are not yet implemented. Further enhancements may be provided for some.
 as well as all the possibles rewriting.

 the last 12 examples fails because the Rules have some weakness. This show that some rewriting should be performed.

 the reason for the failure of the two last examples is that when union or intersection are compared, we should take all the expression containing each member, but we don't.

 it fails because when we get equivalent expression of the Cartesian product, we don't go further enough.
 where and are ones of :