Difference between pages "Current Developments" and "Membership in Goal"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Andy
 
imported>Billaude
 
Line 1: Line 1:
{{TOCright}}
+
= Objective =
This page sum up the known developments that are being done around or for the [[Rodin Platform]]. ''Please contributes informations about your own development to keep the community informed''
 
  
You may also have a look at [[Past Developments|past developments]].
+
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.<br>
 +
This reasoner discharges sequent whose goal denotes a membership which can be inferred from hypotheses. Here an basic example of what it discharges :<br>
 +
<math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U</math>
  
== Deploy Tasks ==
+
= Analysis =
The following tasks were planned at some stage of the [[Deploy]] project.
 
  
=== Code Generation ===
+
Such sequent are proved by PP and ML. But, these provers have both drawbacks :
For information about the recent release see http://wiki.event-b.org/index.php/Tasking_Event-B_Overview
+
*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).
 +
*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>
 +
<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.
  
[[Code Generation]] wiki page
+
= Design Decision =
  
=== Core Platform ===
+
== Tactic ==
  
====Better event-B Editor====
+
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 :
 +
*<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\}=\cdots</math>
 +
#*<math>\left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=\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>
  
Feedback from users indicates strongly that the current layout used in the default event-B editor (edit tab) is sub-optimal and severely hinders usability of the Rodin platform. Ideas for improving this are collected on page: [[Layout improvements in the event-B editor]].
+
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.
  
==== Mathematical Language ====
+
== Reasoner ==
  
[[Predicate_Variables_Extension|Predicate variables extension]]
+
The way the reasoner must work is still in discussion.
  
[[Mathematical_extensions|Proposals for mathematical extensions]]
+
= Implementation =
  
The current generator for well-definedness lemmas is quite dumb and sometimes produces lemmas containing a lot of redundancy. A new development effort has been started to improve this: [[Improved_WD_Lemma_Generation| Improved WD lemma generation]].
+
This section explain how the tactic has bee implemented.
  
==== Text Editor ====
+
=== Positions ===
The efforts in [[Düsseldorf]] ([[User:Fabian|Fabian]]) and [[Newcastle]] ([[User:Alexei|Alexei]]) have been joined to create a single text editor which will be part of the [[#EMF framework for Event-B|EMF framework for Event-B]] (see that [[#EMF framework for Event-B|section]] for details).
+
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>
 +
* '''''leftDProd''''' : it corresponds to the left member of a direct product.
 +
**<math>\left[f\otimes g\right]_{pos\;=\;leftDProd} = f</math>
 +
**<math>\left[A\cprod \left(B\cprod C\right)\right]_{pos\;=\;leftDProd} = A\cprod B</math>
 +
* '''''rightDProd''''' : it corresponds to the right member of a direct product
 +
**<math>\left[f\otimes g\right]_{pos\;=\;rightDProd} = g</math>
 +
**<math>\left[A\cprod\left(B\cprod C\right)\right]_{pos\;=\;rightDProd} = A\cprod C</math>
 +
* '''''leftPProd''''' : it corresponds to the left member of a parallel product
 +
**<math>\left[f\parallel g\right]_{pos\;=\;leftPProd} = f</math>
 +
**<math>\left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;leftPProd} = A\cprod C</math>
 +
* '''''rightPProd''''' : it corresponds to the right member of a parallel product
 +
**<math>\left[f\parallel g\right]_{pos\;=\;rightPProd} = g</math>
 +
**<math>\left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;rightPProd} = B\cprod D</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[f\otimes\left(\left(A\cprod dom(g)\right)\parallel g\right)\right]_{pos\;=\;\left[rightDProd,\;leftPProd,\;kran\right]} = \left[\left(A\cprod dom(g)\right)\parallel g\right]_{pos\;=\;\left[leftPProd,\;kran\right]} = \left[A\cprod dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[dom(g)\right]_{pos\;=\;\left[~\right]} = \left[g\right]_{pos\;=\;\left[kdom\right]}</math>
  
The first version of the TextEditor will be released in a few weeks (following the Rodin 1.0 release). Until then we are going to release a few testing releases (beta) for interested users. Find detailed information on the page [[Text Editor|TextEditor]].
+
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>
  
==== EMF framework for Event-B ====
+
=== Goal ===
Newcastle, Southampton and Düsseldorf have begun to develop an EMF framework to support Rodin modelling tools based on EMF. The framework includes an EMF representation of Event-B, a synchronising persistence interface for loading and saving models via the Rodin API and facilities to support text editing and parsing. Examples of tools that will be based on the EMF framework for Rodin are, a Text editor, a compare/merge editor (which can be used for team based development), pattern/composition tools, Diagram Editors. 
 
  
More details can be found here: [[EMF framework for Event-B]]
+
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\;[0]</math>
 +
*<math>ran(g)\;\mapsto\;[1,~0]</math>
 +
*<math>g\;\mapsto\;[1,~1,~0]</math>
 +
Only ''range'', ''domain'' and ''converse'' can be taken into account to get all the possibles goals.
  
==== Preferences for the automatic tactics ====
+
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''.
[[Systerel]] is in charge of this task.
 
{{details|Preferences for the automatic tactics|Preferences for the automatic tactics}}
 
  
The purpose is to give more detailed preferences to the user to build his own automated tactics.
+
=== Hypotheses ===
  
==== New Tactic Providers ====
+
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>.
[[Systerel]] is in charge of this task.
 
{{details|New Tactic Providers|New Tactic Providers}}
 
  
The purpose is to give more flexibility to tactic providers by allowing them to provide as many tactic applications as they will for a given proof node, even they apply to the same predicate and at the same position.
+
=== Find a path ===
  
==== Generated Model Elements ====
+
Let's considered the sequent with the following goal : <math>x\in V</math>.
[[Systerel]] is in charge of this task.
+
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.
It aims to tag elements of a model that have been generated by a tool, in order to prevent from directly editing these elements.
 
{{details|Generated Model Elements|Generated Model Elements}}
 
  
=== Plug-ins ===
+
To be continued.
  
==== Modularisation Plug-in ====
+
= Untreated cases =
  
The [[Modularisation Plug-in]] provides facilities for structuring Event-B developments into logical units of modelling, called modules. The module concept is very close to the notion Event-B development (a refinement tree of Event-B machines). However, unlike a conventional development, a module comes with an interface. An interface defines the conditions on how a module may be incorporated into another development (that is, another module). The plug-in follows an approach where an interface is characterised by a list of operations specifying the services provided by the module. An integration of a module into a main development is accomplished by referring operations from Event-B machine actions using an intuitive procedure call notation.
+
Some cases are not treated. Further enhancement may be provided for some.
 +
*<math>x\in A\cup B,\quad A\cup B\cup C\subseteq D\quad\vdash\quad x\in D</math>
 +
*<math>x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B</math>
 +
*<math>f\ovl \left\{x\mapsto y\right\}\subseteq A\cprod B\quad\vdash\quad x\in A</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 \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>
  
==== UML-B Improvements ====
+
[[Category:Design proposal]]
[[Southampton]] is in charge of [[UML-B]] plug-in.
 
 
 
A new version of UML-B is being developed that will have improved integration with Event-B. The new version will be built as an extension to the EMF framework for Event-B. While this new version is being developed improvements are also being made to the existing version of UML-B. Both topics are covered in more detail on the following page:
 
[[UML-B Integration and Improvements]]
 
 
 
==== ProB Plug-in ====
 
[[Düsseldorf]] is in charge of [[ProB]].
 
<!-- {{details|ProB current developments|ProB current developments}} -->
 
 
 
===== Work already performed =====
 
 
 
We have now ported ProB to work directly on the Rodin AST. Animation is working and the user can now set a limited number of preferences.
 
The model checking feature is now also accessible.
 
It is also possible to create CSP and classical B specification files. These files can be edited with BE4 and animated/model checked with ProB.
 
On the classical B side we have moved to a new, more robust parser (which is now capable of parsing some of the more complicated AtelierB
 
specifications from Siemens).
 
 
 
On the developer side, we have moved to a continuous integration infrastructure using CruiseControl. Rodin is also building from CVS in that infrastructure.
 
 
 
Developers can build tools on top of ProB using the [[ProB API]].
 
 
 
===== Ongoing and future developments=====
 
 
 
We are currently developing a new, better user interface.
 
We also plan to support multi-level animation with checking of the gluing invariant.
 
 
 
We have prototypes for several extensions working, but they need to be fully tested and integrated into the plugin:
 
* an inspector that allows the user to inspect complex predicates (such as invariants or guards) as well as expressions in a tree-like manner
 
* a graphical animator based on SWT that allows the user to design his/her own animations easily within the tool
 
* a 2D viewer to inspect the state space of the specification
 
 
 
==== B2Latex Plug-in ====
 
[[Southampton]] is in charge of [[B2Latex]].
 
 
 
Kriangsak Damchoom will update the plug-in to add [[Event Extension|extensions of events]].
 
 
 
==== Event Model Decomposition (A-style) ====
 
[[Systerel]] ([[User:Carine|Carine]]) is in charge of this task.
 
{{details|Event Model Decomposition|Event Model Decomposition}}
 
 
 
The purpose of (A-style) event model decomposition is to cut a heavy event system into smaller pieces which can be handled more comfortably than the whole. More precisely, each piece can then be refined independently of the others.
 
 
 
==== Parallel Composition Plug-in ====
 
[[Southampton]] is in charge of the [[Parallel Composition using Event-B]] .
 
 
 
The purpose of the plug-in is to allow the parallel composition of several Event-B machines into a composite machine. The machine composition uses a shared event composition, where separate machines operate on disjoint variables and
 
machines interact by synchronising on events that may share parameters.
 
 
 
This plug-in allows:
 
* Selection of machines that will be part of the composition (''Includes'' Section)
 
* Possible selection of an abstract machine (''Refines'' Section)
 
* Possible inclusion of invariants that relate the included machines (''Invariant'' Section and use of the monotonicity )
 
* Invariants of included machines are conjoined.
 
* Selection of events that will be merged. The event(s) must come from different machines. At the moment, events with parameters with same name are merged. If it is a refinement composition, it is possible to choose the abstract event that is being refined.
 
* Initialisation event is the parallel composition of all the included machines' initialisations.
 
* For a composed event, the guards are conjoined and the all the actions are composed in parallel.
 
 
 
Currently, after the conclusion of the composition machine, a new machine can be generated, resulting from the properties defined on the composition file. This allows proofs to be generated as well as a visualisation of the composition machine file. In the future, the intention is to make the validation directly on the composition machine file directly where proofs would be generated ( and discharged) - the new machine generation would be optional. An event-b model for the validation/generation of proofs in currently being developed. Another functionality which should be quite useful for the composition (but not restricted to that) is '''renaming''':
 
 
 
* while composing, two machines may have variables with the same name for instance (which is not allowed for this type of composition). In order to solve this problem, one would have to rename one of the variables in order to avoid the clash, which would mean change the original machine. A possible solution for that would be to rename the variable but just on composition machine file, keeping the original machine intact. A renaming framework designed and developed by Stefan Hallerstede and Sonja Holl exists currently although still on a testing phase. The framework was developed to be used in a general fashion (not constrained to event-b syntax). The idea is to extend the development of this framework and apply to Event-B syntax (current development).
 
 
 
There is a prototype for the composition plug-in available that works for Rodin 0.9.2.1 available from the Rodin Main Update Site soon, under 'Shared Event Composition'.
 
 
 
==== Refactoring Framework Plug-in ====
 
[[Southampton]] is in charge of the [[Refactoring Framework]].
 
 
 
The intention of the plug-in is to allow the renaming/refactoring of elements on a file (and possible related files). Although created to be used in a general way, the idea is to embed this framework on the Rodin platform, using Event-B syntax. This plug-in was initially designed and developed by Stefan Hallerstede and Sonja Holl.
 
 
 
This plug-in allows:
 
* Defining extensions that can be used to select related files.
 
* Defining extesions that can be used to rename elements based on the type of file.
 
* Renaming of elements on a file and possible occurrences on related files.
 
* Generating of a report of possible problems (clashes) that can occur while renaming.
 
 
 
==== Measurement Plug-In ====
 
 
 
The [[Measurement Plug-In]] to the RODIN platform will provide information both about the model itself and about the process of building the model.
 
It has a double purpose:
 
 
 
* provide feedback to the user about the quality of the Event-B model he is building and about potential problems in it or in the way he is building it.
 
* automate the data collection process for the measurement and assessment WP. This data collected will be analyzed to identify global transfer (increase in model quality, size, complexity,...), tool shortcomings (usability, prover), modelling issues (to be addressed by training, language, tool evolution,...), etc.
 
 
 
==== Generic Instantiation ====
 
 
 
The context of a machine can be viewed as defining the parameters of that machine
 
(carrier sets, constants, axioms).  These parameters make a machine generic.
 
We propose an  approach for  instantiating Event-B  machines by replacing generic sets and constants
 
with more specific sets and constants.  The axioms of a context represent assumptions on the
 
sets and constants that need to be satisfied whenever the machine is instantiated.
 
The instantiation leads to proof obligations
 
to ensure that the generic axioms are satisfied by the instantiation.  For more details see [[Generic Instantiation | Generic Instantiation page]].
 
 
 
==== Rule-based Extensible Prover ====
 
[[Southampton]] is in charge of devising an extensible rule-based prover.
 
 
 
In order to extend the prover with new rewrite and inference rules, it is necessary to write Java code
 
adding to the appropriate extension points. That way, it becomes very difficult to verify the soundness of the
 
implemented rules. We propose a mechanism by which the prover can be extended with new rewrite rules
 
and inference rules without compromising its soundness. Our proposal follows a similar
 
approach employed by Event-B: generating proof obligations. We, initially, focus on adding the facility to specify
 
rewrite rules. We envisage the mechanism to evolve to cover inference rules as well as the many mathematical extensions
 
proposed in [[Mathematical_extensions]]. For more details, we refer to the [[Rule-based_Prover_Plug-in]] page.
 
and [[Image:Rule-based_Prover_Proposal.pdf | Proposal for a rule-based extensible prover]].
 
 
 
==== SMT Plug-in ====
 
 
 
[Systerel] ([[User:YGU|YGU]]) is in charge of this task.
 
{{details|SMT Plug-in|SMT Plug-in}}
 
{{details|Event-B to SMT-LIB|Event-B to SMT-LIB}}
 
 
 
The purpose of the plug-in is to integrate SMT solvers into Rodin.
 
 
 
==== New Proof Rules ====
 
 
 
[[New Proof Rules|This document]] describes the set of newly added reasoners for improving the usability of the prover within Rodin Platform.
 
 
 
== Exploratory Tasks ==
 
=== Template Base Exporter ===
 
Some prototyping work is done in python, to explore how to use template engines to export rodin models to text, Latex, docbook, mediawiki,...
 
The [http://www.mercurial.org mercurial] repository is available [https://bitbucket.org/matclab/rodin_exporter/ here]. You can cloned it by installing mercurial on your computer and doing <code>hg clone https://bitbucket.org/matclab/rodin_exporter/</code>.
 
 
 
Be warn that, for now, it bypass the rodin database API and does parse the .bum and .buc files directly. It is also highly experimental, so do not rely to much on the produced output.
 
 
 
(This work is done by [[User:Mathieu|Mathieu]] on its spare time...)
 
 
 
== Others ==
 
 
 
=== AnimB ===
 
[[User:Christophe|Christophe]] devotes some of its spare time for this plug-in.
 
{{details|AnimB Current Developments|AnimB Current Developments}}
 
The current developments around the [[AnimB]] plug-in encompass the following topics:
 
;Live animation update
 
:where the modification of the animated event-B model is instantaneously taken into account by the animator, without the need to restart the animation.
 
;Collecting history
 
:The history of the animation will be collected.
 
 
 
=== Team-Based Development ===
 
 
 
; Usage Scenarios
 
: In order to understand the problem properly, [http://www.stups.uni-duesseldorf.de/ Düsseldorf] created a number of usage [[Scenarios for Team-based Development]].
 
: A page has also been opened for [[Scenarios for Merging Proofs|merging proofs scenarios]].
 
 
 
 
 
;Team working based on EMF Compare
 
:The EMF Compare project provides a comparison/merging style editor (similar to the Java merging editor used for synchronising changes with code repositories). This could be used to synchronise model changes into a repository such as SVN. The use of the EMF Compare editor relies on the  [[EMF framework for Event-B|EMF representation of Event-B]] that has already been developed and is available. A prototype plug-in is available which enables the use of the EMF compare editor for Rodin Machines and Contexts. It is intended that deploy partners will try out this plug-in in order to gather requirements for the Teamwork plug-in.
 
:More details are here: [[Team-based development]]
 
 
 
=== Wishlist ===
 
A [[Plug-in Wishlist | wish list]] of tool plug-ins that cannot be resourced by [[Deploy]] is maintained.
 
 
 
[[Category:Work in progress]]
 

Revision as of 13:28, 9 August 2011

Objective

This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.
This reasoner discharges sequent whose goal denotes a membership which can be inferred from hypotheses. Here an basic example of what it discharges :
H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U

Analysis

Such sequent are proved by PP and ML. But, these provers have both drawbacks :

  • 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).
  • If there are too many hypotheses, or if the expression of the x 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 : 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

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

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 :

  • \cdots~\in~\cdots

For examples :

  • f(x)\in g\otimes h
  • x\in A\cprod\left(B\cup C\right)
  • x\mapsto y\in A\cprod B

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 :

  1. the ones related to the left member of the goal \left( x\in S\right) (this is the start point):
    • x\in \cdots
    • \cdots\mapsto x\mapsto\cdots\in\cdots
    • \left\{\cdots, x,\cdots\right\}=\cdots
    • \left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=\cdots
  2. the ones denoting inclusion (all but the ones matching the description of the first point) :
    • \cdots\subset\cdots
    • \cdots\subseteq\cdots
    • \cdots=\cdots

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. f always represent an expression (may be a domain, a range, etc.).

  1. The following sequent is provable because f\subseteq \varphi (f).
    • x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g
    • \varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f
  2. The following sequent is provable because \psi (f)\subseteq f.
    • x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g
    • \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
  3. 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.
    • x\in \psi (f),\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g
  4. For some relations, positions are needed to be known to continue to find hypotheses, but it is not always necessary.
    • x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A
    • x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A
    • x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B

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 \left(A\subseteq B,\quad B\subseteq A\right). 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.
    • \left[A\cprod B\right]_{pos\;=\;kdom} = A
    • \left[x\mapsto y\right]_{pos\;=\;kdom} = x
    • \left[g\right]_{pos\;=\;kdom} = dom(g)
  • kran : it corresponds to the domain.
    • \left[A\cprod B\right]_{pos\;=\;kran} = B
    • \left[x\mapsto y\right]_{pos\;=\;kran} = y
    • \left[g\right]_{pos\;=\;kran} = ran(g)
  • leftDProd : it corresponds to the left member of a direct product.
    • \left[f\otimes g\right]_{pos\;=\;leftDProd} = f
    • \left[A\cprod \left(B\cprod C\right)\right]_{pos\;=\;leftDProd} = A\cprod B
  • rightDProd : it corresponds to the right member of a direct product
    • \left[f\otimes g\right]_{pos\;=\;rightDProd} = g
    • \left[A\cprod\left(B\cprod C\right)\right]_{pos\;=\;rightDProd} = A\cprod C
  • leftPProd : it corresponds to the left member of a parallel product
    • \left[f\parallel g\right]_{pos\;=\;leftPProd} = f
    • \left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;leftPProd} = A\cprod C
  • rightPProd : it corresponds to the right member of a parallel product
    • \left[f\parallel g\right]_{pos\;=\;rightPProd} = g
    • \left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;rightPProd} = B\cprod D
  • converse : it corresponds to the child of an inverse
    • \left[f^{-1}\right]_{pos\;=\;converse}=f
    • \left[A\cprod B\right]_{pos\;=\;converse} = B\cprod A

For example, the following expressions at the given positions are equivalent.

\left[f\otimes\left(\left(A\cprod dom(g)\right)\parallel g\right)\right]_{pos\;=\;\left[rightDProd,\;leftPProd,\;kran\right]} = \left[\left(A\cprod dom(g)\right)\parallel g\right]_{pos\;=\;\left[leftPProd,\;kran\right]} = \left[A\cprod dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[dom(g)\right]_{pos\;=\;\left[~\right]} = \left[g\right]_{pos\;=\;\left[kdom\right]}

Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :

  • ran(f^{-1}) = dom(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kran\right]} = \left[f\right]_{pos\;=\;\left[kdom\right]}
  • dom(f^{-1}) = ran(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kdom\right]} = \left[f\right]_{pos\;=\;\left[kran\right]}
  • \left(f^{-1}\right)^{-1} = f\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~converse\right]} = \left[f\right]_{pos\;=\;\left[~\right]}

Goal

As explained in the design decision part, goal is checked. If it matches the description here above \left(x\in S\right) 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 dom(ran(ran(g))), the map will be computed :

  • dom(ran(ran(g)))\;\mapsto\;[\;]
  • ran(ran(g))\;\mapsto\;[0]
  • ran(g)\;\mapsto\;[1,~0]
  • g\;\mapsto\;[1,~1,~0]

Only range, domain and converse can be taken into account to get all the possibles goals.

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 \left(x\in S\right) are stored, the position of x is also record. Then, if there is an hypothesis such as \left\{\cdots\;,\;y\mapsto x\mapsto z\;,\;m\mapsto x\;,\;\cdots\right\} = A, then this hypothesis is mapped to the positions \left\{\left[0,~1\right],~\left[1\right]\right\}.

Find a path

Let's considered the sequent with the following goal : x\in V. We start with the hypotheses which have a connection with the goal's member. Such a hypothesis gives two informations : the position pos and the set S as explained in hypotheses. Then, for each equivalent pair to these one \left(S', pos'\right), we compute set containing S' ( 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.

  • x\in A\cup B,\quad A\cup B\cup C\subseteq D\quad\vdash\quad x\in D
  • x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B
  • f\ovl \left\{x\mapsto y\right\}\subseteq A\cprod B\quad\vdash\quad x\in A
  • 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)
  • x\in f\otimes g,\quad f\subseteq h\quad\vdash\quad x\in h\otimes g
  • x\in \left\{a,~b,~c\right\},\quad\left\{a,~b,~c,~d,~e,~f\right\}\subseteq D\quad\vdash\quad x\in D
  • x\in A\cprod B,\quad A\subseteq C\quad\vdash\quad x\in C\cprod B
  • x\in dom(f)\cap A\quad\vdash\quad x\in dom(A\domres f)
  • x\in ran(f)\cap A\quad\vdash\quad x\in ran(f\ranres A)
  • x\in \quad\vdash\quad
  • \quad\vdash\quad
  • \quad\vdash\quad
  • \quad\vdash\quad
    \bigl( where op_1 and op_2 are ones of :\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)