Difference between pages "Event-B Qualitative Probability User Guide" and "The Use of Theories in Code Generation"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Son
 
imported>Andy
 
Line 1: Line 1:
[[User:Son]] at '''ETH Zurich''' is in charge of the plug-in.
+
== The Theory Plug-in ==
{{TOCright}}
+
The theory plug-in is used to add mathematical extensions to Rodin. The theories are created, and deployed, and can then be used in any models in the workspace. When dealing with implementation level models, such as in Tasking Event-B, we need to consider how to translate newly added types and operators into code. We have augmented the theory interface with a Translation Rules section. This enables a user to define translation rules that map Event-B formulas to code.
 +
=== Translation Rules===
 +
Figure 1 shows the interface, and some translations rules of the mapping to Ada.
  
== Introduction ==
+
<div id="fig:Translation Rules">
Event-B Qualitative Probability plug-in provides supports for reasoning about termination with probability 1 (almost-certain termination).
+
<br/>
 +
[[Image:TheoryCGRules.png|center||caption text]]
 +
<center>'''Figure 1''': Translation Rules</center>
 +
<br/>
 +
</div>
  
 
+
The translation rules are templates used for pattern matching. The meta-variables are defined and typed, and used in the rules. Event-B expressions and predicates are defined on the left hand side of the rule, and the code to be output (as text) appears on the right hand side of the matching rule.
== Installing and Updating ==
 
The plug-in is available through the main Rodin Update Site under '''Modelling Extension''' category.
 
 
 
== News ==
 
* 23.11.2011: Version 0.2.1 released for Rodin 2.3.*
 
 
 
== Technical References ==
 
* S. Hallerstede, T.S. Hoang. '''Qualitative Probabilistic Modelling in Event-B'''. In ''IFM 2007: Integrated Formal Methods, 6th International Conference Proceedings'', Oxford, UK, July 2-5, 2007, volume 4591 of LNCS © Springer-Verlag. [http://dx.doi.org/10.1007/978-3-540-73210-5_16 Springer website]
 
** Initial idea about probabilistic convergence event.
 
** New modelling elements: Variant bound
 
** New proof obligations: '''PRV''', '''BND''', '''FINACT'''.
 
** Example: Resolve contention in IEEE 1395 (Firewire protocol).
 
 
 
* E. Yilmaz, T.S. Hoang. '''Development of Rabin’s Choice Coordination Algorithm in Event-B'''.  In ''Automated Verification of Critical Systems 2010'', volume 35 of ''Electronic Communications of the EASST'' © EASST. [http://journal.ub.tu-berlin.de/eceasst/article/view/548 EASST website]
 
** Probablistic convergence event with refinement
 
** Constraints on how (not-) to refine probabilistic events.
 
** Example: Rabin's Choice Coordination Algorithm.
 
 
 
== Usage ==
 
We illustrate the usage of the plug-in using the example of contention resolving (part of IEEE 1394 Firewire protocol). The description of the problem is as follows.
 
 
 
Two processes in contention use a probabilistic protocol to resolve the problem. In each step, each process probabilisitcally choose to communicate in either short or long delay.  The contention is resolved when the processes choose different delays.
 
 
 
We start with a non-deterministic model of the system
 
* Boolean variables <math>x</math> and <math>y</math> represent the choice for each process: <math>TRUE</math> for short delay <math>FALSE</math> for long delay.
 
 
 
* Resolving contention is model as an event of the model with guard <math>x = y</math> (i.e. keep trying when the choices are identical).
 
[[Image:contention-nondet.jpg]]
 
 
 
 
 
=== Probabilistic Modelling ===
 
* To set event '''resolve''' is probabilistic convergence:
 
# Go to the '''Edit''' page of the standard ''Rodin Editor''.
 
# Open the '''EVENTS''' section
 
# Set convergence attribute of '''resolve''' from ''ordinary'' to ''convergent''.
 
# Set probabilistic attribute of '''resolve''' from ''standard'' to ''probabilistic''.
 
[[Image:contention-prob.jpg]]
 
 
 
* Set <math>\Bool \setminus \{x, y\}</math> as the variant of the model
 
[[Image:contention-variant.jpg]]
 
 
 
* Set <math>\Bool</math> as the bound of the model
 
[[Image:contention-bound.jpg]]
 
 
 
* Save the model
 
 
 
=== Proof Obligations ===
 
* The model should have 3 proof obligations including '''resolve/PRV'''.
 
[[Image:contention-po.jpg]]
 
 
 
* The goal of proof obligation '''resolve/PRV''' is <math>\exists x^\prime, y^\prime \qdot \Bool \setminus \{x^\prime, y^\prime\} \subset \Bool \setminus \{x, y\}</math>.  With hypothesis <math>x = y</math> (from the guard of the event), the proof obligation can be discharged by instantiating different values for <math>x^\prime</math> and <math>y^\prime</math> (e.g. <math>\True</math> for <math>x^\prime</math> and <math>\False</math> for <math>y^\prime</math>). Alternatively, the obligation can be interactively discharge using '''p1''' (AterlierB Predicate Prover on lasso'd hypotheses) directly as shown below
 
[[Image:resolve-prv.jpg]]
 
 
 
== Explanations for some warning and error messages ==
 
 
 
* '''Missing variant''' warning
 
** Problem: [[Image:contention-novariant.jpg]]
 
** Explanation: User needs to provide a variant for probabilistic convergence events.
 
** Solution: Add a variant to the model
 
 
 
 
 
* '''Missing bound''' error
 
** Problem: [[Image:contention-nobound.jpg]]
 
** Explanation: The variant for probabilistic events need to be bounded above.
 
** Solution: Add a bound to the model (using Edit page of the standard Rodin editor).
 
 
 
== Additional features to be investigated/implemented ==
 
* ''Proof hints'': Select event guards when creating proof obligations, such as PRV and BND
 
 
 
* ''Finer-grain for probabilisitc attribute''. The probabilistic attribute might/should be attached to individual assignment and/or parameter of the event.
 

Revision as of 08:38, 15 May 2012

The Theory Plug-in

The theory plug-in is used to add mathematical extensions to Rodin. The theories are created, and deployed, and can then be used in any models in the workspace. When dealing with implementation level models, such as in Tasking Event-B, we need to consider how to translate newly added types and operators into code. We have augmented the theory interface with a Translation Rules section. This enables a user to define translation rules that map Event-B formulas to code.

Translation Rules

Figure 1 shows the interface, and some translations rules of the mapping to Ada.


caption text
Figure 1: Translation Rules


The translation rules are templates used for pattern matching. The meta-variables are defined and typed, and used in the rules. Event-B expressions and predicates are defined on the left hand side of the rule, and the code to be output (as text) appears on the right hand side of the matching rule.