imported>Billaude |
imported>Laurent |
| Line 1: |
Line 1: |
| − | = Objective =
| + | {{TOCright}} |
| | | | |
| − | This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.<br>
| + | == Release Policy == |
| − | This reasoner discharges sequent whose goal denotes a membership which can be inferred from hypotheses. Here an basic example of what it discharges :<br>
| + | * The Rodin platform is released every 3 months. |
| − | <math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U</math><br>
| + | * The code is frozen during the 2 weeks preceding each release. |
| − | The other purpose of the reasoner is to have a condense proof tree (one step contain several inference rule). | + | * Each release is announced on the [[Mailing_lists | Devel]] mailing list. Two days later, the information is broadcast on the [[Mailing_lists | Announce]] and [[Mailing_lists | User]] mailing lists. |
| | + | * The [http://wiki.eclipse.org/index.php/Version_Numbering Eclipse versioning policy] is enforced. |
| | + | * The optional plug-ins shall strive to meet the release date: the release will not be held back. |
| | + | * The news related to the optional plug-ins are spread on the [[Mailing_lists | Announce]] and [[Mailing_lists | User]] mailing lists. |
| | + | * A wiki page is dedicated to each release. Select a version from the lists below to see the corresponding release notes. |
| | + | * The maintainers of the optional plug-ins shall update the ''External Plug-ins'' section of the release notes (plug-in version, link to the plug-in documentation) once they have ensured the compatibility of their plug-ins with the Rodin platform. |
| | | | |
| − | = Analysis = | + | == Upcoming Releases == |
| | | | |
| − | Such sequent are proved by PP and ML. But, these provers have both drawbacks :
| + | {{SimpleHeader}} |
| − | *All the visible are added as needed hypotheses, which is most of the time not the case.
| + | |- |
| − | *They take quite consequent time to prove it (even with the basic example given here above, the difference in time execution is noticeable).
| + | ! scope=col | Version || Scheduled Release Date |
| − | *If there are too many hypotheses, or if the expression of the <math>x</math> is too complicated, they may not prove it.
| + | |- |
| − | This is particularly true when in the list of inclusion expressions of each side of the relation are not equal. For example : <math>H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq U\quad\vdash a\in U</math>
| + | |[[Rodin Platform 2.1 Release Notes|2.1]] || 2011/01/28 |
| − | <p>
| + | |} |
| − | Such a reasoner contributes to prove more Proof Obligations automatically, faster and with fewer needed hypotheses which makes proof rule more legible and proof replay less sensitive to modifications.
| |
| | | | |
| − | = Design Decision = | + | == Previous Releases == |
| | | | |
| − | == Tactic == | + | {{SimpleHeader}} |
| | + | |- |
| | + | ! scope=col | Version || Release Date |
| | + | |- |
| | + | |[[Rodin Platform 2.0 Release Notes|2.0]] || 2010/10/08 |
| | + | |- |
| | + | |[[Rodin Platform 1.3.1 Release Notes|1.3.1]] || 2010/06/15 |
| | + | |- |
| | + | |[[Rodin Platform 1.3 Release Notes|1.3]] || 2010/05/05 |
| | + | |- |
| | + | |[[Rodin Platform 1.2 Release Notes|1.2]] || 2010/02/05 |
| | + | |- |
| | + | |[[Rodin Platform 1.1 Release Notes|1.1]] || 2009/10/15 |
| | + | |- |
| | + | |[https://sourceforge.net/projects/rodin-b-sharp/files/Core_%20Rodin%20Platform/1.0/ 1.0] || 2009/07/01 |
| | + | |} |
| | | | |
| − | This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
| + | [[Category:Rodin Platform Release Notes]] |
| − | === Goal ===
| + | [[Category:Rodin Platform]] |
| − | The tactic (as the reasoner) should works only on goals such as :
| + | [[Category:Release Notes]] |
| − | *<math>\cdots~\in~\cdots</math>
| |
| − | For examples :
| |
| − | *<math>f(x)\in g\otimes h</math>
| |
| − | *<math>x\in A\cprod\left(B\cup C\right)</math>
| |
| − | *<math>x\mapsto y\in A\cprod B</math>
| |
| − | In the latter case, the reasoner won't try to prove that ''x'' belongs to ''A'' and ''y'' belongs to ''B'', but that the mapplet belong 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 <math>\left( x\in S\right)</math> (this is the start point):
| |
| − | #*<math>x\in \cdots</math>
| |
| − | #*<math>\cdots\mapsto x\mapsto\cdots\in\cdots</math>
| |
| − | #*<math>\left\{\cdots, x,\cdots\right\}=/\subset/\subseteq\cdots</math>
| |
| − | #*<math>\left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=/\subset/\subseteq\cdots</math>
| |
| − | #*<math>f\ovl\left\{\cdots, x, \cdots\right\}=/\subset/\subseteq\cdots</math>
| |
| − | #the ones denoting inclusion (all but the ones matching the description of the first point) :
| |
| − | #*<math>\cdots\subset\cdots</math>
| |
| − | #*<math>\cdots\subseteq\cdots</math>
| |
| − | #*<math>\cdots=\cdots</math>
| |
| − | 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. <math>f</math> always represent an expression (may be a domain, a range, etc.).
| |
| − | #The following sequent is provable because <math>f\subseteq \varphi (f)</math>.
| |
| − | #*<math>x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
| |
| − | #*<math>\varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f</math>
| |
| − | #The following sequent is provable because <math>\psi (f)\subseteq f</math>.
| |
| − | #*<math>x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g</math>
| |
| − | #*<math>\psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f</math>
| |
| − | #We can generalized the first two points. This is the Russian dolls system. We can easily prove a sequent with multiple inclusions by going from hypothesis to hypothesis.
| |
| − | #*<math>x\in \psi (f),\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
| |
| − | #For some relations, [[#positions|positions]] are needed to be known to continue to find hypotheses, but it is not always necessary.
| |
| − | #*<math>x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
| |
| − | #*<math>x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
| |
| − | #*<math>x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B</math>
| |
| − | | |
| − | By using these inclusion and rewrites, it tries to find a path among the recovered hypotheses. Every one of those should only be used once, avoiding possible infinite loop <math>\left(A\subseteq B,\quad B\subseteq A\right)</math>. Among all paths that lead to discharge the sequent, the tactic give the first it finds. Moreover, so that the reasoner does not do the same work as the tactic of writing new hypothesis, it gives all needed hypotheses and added hypotheses in the input.
| |
| − | | |
| − | == Reasoner ==
| |
| − | | |
| − | The way the reasoner must work is still in discussion.
| |
| − | | |
| − | = Implementation =
| |
| − | | |
| − | This section explain how the tactic has bee implemented.
| |
| − | | |
| − | === Positions ===
| |
| − | As it was said, we may sometimes need the position. It is represented by an array of integer. Here are the possible values the array contains (atomic positions) :
| |
| − | * '''''kdom''''' : it corresponds to the domain.
| |
| − | **<math>\left[A\cprod B\right]_{pos\;=\;kdom} = A</math>
| |
| − | **<math>\left[x\mapsto y\right]_{pos\;=\;kdom} = x</math>
| |
| − | **<math>\left[g\right]_{pos\;=\;kdom} = dom(g)</math>
| |
| − | * '''''kran''''' : it corresponds to the domain.
| |
| − | **<math>\left[A\cprod B\right]_{pos\;=\;kran} = B</math>
| |
| − | **<math>\left[x\mapsto y\right]_{pos\;=\;kran} = y</math>
| |
| − | **<math>\left[g\right]_{pos\;=\;kran} = ran(g)</math>
| |
| − | * '''''converse''''' : it corresponds to the child of an inverse
| |
| − | **<math>\left[f^{-1}\right]_{pos\;=\;converse}=f</math>
| |
| − | **<math>\left[A\cprod B\right]_{pos\;=\;converse} = B\cprod A</math>
| |
| − | For example, the following expressions at the given positions are equivalent.
| |
| − | :<math>\left[ran(dom(g))\right]_{pos\;=\;\left[\right]} = \left[dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[g\right]_{pos\;=\;\left[kdom,\; kran\right]}</math>
| |
| − | | |
| − | Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :
| |
| − | *<math>ran(f^{-1}) = dom(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kran\right]} = \left[f\right]_{pos\;=\;\left[kdom\right]}</math>
| |
| − | *<math>dom(f^{-1}) = ran(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kdom\right]} = \left[f\right]_{pos\;=\;\left[kran\right]}</math>
| |
| − | *<math>\left(f^{-1}\right)^{-1} = f\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~converse\right]} = \left[f\right]_{pos\;=\;\left[~\right]}</math>
| |
| − | | |
| − | === Goal ===
| |
| − | | |
| − | As explained in the design decision part, goal is checked. If it matches the description here above <math>\left(x\in S\right)</math> then ''x'' is stored in an attribute. Moreover, from the set ''S'', we compute every pair ''expression'' & ''position'' equivalent to it. For example, from the set <math>dom(ran(ran(g)))</math>, the map will be computed :
| |
| − | *<math>dom(ran(ran(g)))\;\mapsto\;[\;]</math>
| |
| − | *<math>ran(ran(g))\;\mapsto\;[kdom]</math>
| |
| − | *<math>ran(g)\;\mapsto\;[kran,~kdom]</math>
| |
| − | *<math>g\;\mapsto\;[kran,~kran,~kdom]</math>
| |
| − | | |
| − | A pair (expression ; position) is said equal to the goal if and only if there exists a pair equivalent to the goal (GoalExp ; GoalPos) and a pair equivalent to the given pair (Exp ; Pos) such as ''Pos = GoalPos'' and ''Exp'' is contained in ''GoalExp''.
| |
| − | | |
| − | === Hypotheses ===
| |
| − | | |
| − | As explained in the design decision part, there are two kinds of hypotheses which are recovered. But when hypotheses related to the left member of the goal <math>\left(x\in S\right)</math> are stored, the position of ''x'' is also record. Then, if there is an hypothesis such as <math>\left\{\cdots\;,\;y\mapsto x\mapsto z\;,\;m\mapsto x\;,\;\cdots\right\} = A</math>, then this hypothesis is mapped to the positions <math>\left\{\left[0,~1\right],~\left[1\right]\right\}</math>.
| |
| − | | |
| − | === Find a path ===
| |
| − | | |
| − | Let's considered the sequent with the following goal : <math>x\in V</math>.
| |
| − | We start with the hypotheses which have a connection with the goal's member. Such a hypothesis gives two informations : the position <math>pos</math> and the set <math>S</math> as explained in [[#Hypotheses|hypotheses]]. Then, for each equivalent pair to these one <math>\left(S', pos'\right)</math>, we compute set containing <math>S'</math> ([[#Design Decision#Tactic#Find a path| Find a path 2.]]). For every new pair, we test if it is contained in the goal.
| |
| − | | |
| − | To be continued.
| |
| − | | |
| − | = Untreated cases =
| |
| − | | |
| − | Some cases are not treated. Further enhancement may be provided for some.
| |
| − | *<math>x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B</math>
| |
| − | *<math>x\in f\otimes g,\quad f\subseteq A\cprod B,\quad g\subseteq C\cprod D\quad\vdash\quad x\in (A\cprod C)\cprod(B\cprod D)</math>
| |
| − | *<math>x\in f\otimes g,\quad f\subseteq h\quad\vdash\quad x\in h\otimes g</math>
| |
| − | *<math>x\in \left\{a,~b,~c\right\},\quad\left\{a,~b,~c,~d,~e,~f\right\}\subseteq D\quad\vdash\quad x\in D</math>
| |
| − | *<math>x\in A\cprod B,\quad A\subseteq C\quad\vdash\quad x\in C\cprod B</math>
| |
| − | *<math>x\in dom(f)\cap A\quad\vdash\quad x\in dom(A\domres f)</math>
| |
| − | *<math>x\in ran(f)\cap A\quad\vdash\quad x\in ran(f\ranres A)</math>
| |
| − | *<math>x\in dom(A\domres f)\quad\vdash\quad x\in dom(f)\cap A</math>
| |
| − | *<math>x\in ran(f\ranres A)\quad\vdash\quad x\in ran(f)\cap A</math>
| |
| − | *<math>x\in \quad\vdash\quad</math>
| |
| − | *<math>\quad\vdash\quad</math>
| |
| − | *<math>\quad\vdash\quad</math>
| |
| − | *<math>\quad\vdash\quad</math>
| |
| − | *:<math>\bigl(</math> where <math>op_1</math> and <math>op_2</math> are ones of :<math>\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)</math>
| |
| − | | |
| − | [[Category:Design proposal]] | |
