Difference between pages "Code Generation Tutorial" and "Event-B Qualitative Probability User Guide"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Andy
 
imported>Son
 
Line 1: Line 1:
−
'''This Page is Under Construction!!!!'''
+
[[User:Son]] is in charge of the plug-in.
 +
{{TOCright}}
  
−
=== Tutorial Overview ===
+
== Introduction ==
 +
Event-B Qualitative Probability plug-in provides supports for reasoning about termination with probability 1 (almost-certain termination).
 +
For more details about the principles on XEvent-B, see the [[Qualitative Probability | Qualitative Probability page]].
  
−
The aim of the tutorial is to allow users to explore the approach with a relatively simple example. The example uses a shared buffer with reader and writer processes. The tutorial is presented in three stages, making use of the example projects from the download site. There are two translations performed, one is to a common language model (IL1). The second is to an Event-B project which includes a model of the implementation. There is a PrettyPrinter for Ada source code, which uses the common language model. An overview of Tasking Event-B can be found at http://wiki.event-b.org/index.php/Tasking_Event-B_Overview.
+
== Installing and Updating ==
 +
The plug-in is available through the main Rodin Update Site under '''Modelling Extension''' category.
  
−
A typical Event-B development may be refined to the point where it is ready for implementation, but the Event-B language is not expressive enough to fully describe the implementation. Tasking Event-B facilitates this final step to implementation, by extending Event-B with the necessary constructs. Event-B machines that are to be implemented (and their seen Contexts) are selected and added to a ''Tasking Development''; the Tasking Development files have the file extension ''.tasking''. The machines in the Tasking Development are then extended with implementation details.
+
== News ==
 +
* 23.11.2011: Version 0.2.1 released for Rodin 2.3.*
 +
* 10.04.2012: Version 0.2.1 is compatible with Rodin 2.4.*
 +
* 14.05.2012: Version 0.2.1 is compatible with Rodin 2.5.*
 +
* 09.03.2015: Version 0.2.2 is released with Rodin 3.x.x
 +
* 09.10.2015: Version 0.2.3 is released
 +
* 23.07.2017: Version 0.2.4 is released
  
−
The example/tutorial projects are,
+
== Technical References ==
 +
* Thai Son Hoang. '''Reasoning about almost-certain convergence properties using Event-B'''. Science of Computer Programming, 81:108–121, February 2014 © Elsevier. [https://doi.org/10.1016/j.scico.2013.08.006 SCP website] (''Please use this article as the reference for the plug-in).
 +
** Extended version of the EASST paper (below).
 +
** Probablistic convergence event with refinement
 +
** Constraints on how (not-) to refine probabilistic events.
 +
** Example: Duelling cowboys
 +
** Example: Rabin's choice coordination.
 +
** Example: Herman's probabilistic self-stabilization.
 +
* 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.
 +
* 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).
  
−
{| border="1"
+
== Usage ==
−
|SharedBuffer20100819Demo
+
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.
−
|An example project with a completed Tasking Development and IL1 model (post IL1 translation, but before Event-B translation).
 
−
|-
 
−
|Sharedbuffer20100819Tasking
 
−
|Same as the example project above, but with Event-B model translations. The difference being that this development includes a model of the implementation. These are refinements that include a program counter to describe flow of execution in each task.
 
−
|-
 
−
|SharedBuffer20100819Tutorial
 
−
|A bare project for step 1 of the tutorial.
 
−
|-
 
−
|Sharedbuffer20100819Tutorial2
 
−
|A partially completed tasking development for steps 2 and 3 of the tutorial.
 
−
|}
 
  
−
== Preliminaries ==
+
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.
−
Before further discussion of the modelling aspects, we take a look at the PrettyPrint viewers. The PrettyPrinters make the viewing of IL1 and tasking models easier; it also provides a route to generate source code. The source code can easily be pasted from the IL1 Pretty Printer window into an the Ada source file .  
 
−
==== The PrettyPrint View of a Tasking Development ====
 
−
To open the Tasking PrettyPrint viewer,
 
−
* from the top-menu select ''Window/Show View/Other/Tasking Pretty Printer''.
 
  
−
Note that the Tasking PrettyPrinter may have to be closed when editing the Tasking Development, since it can give rise to exceptions. The PrettyPrinter would need further work to make it robust, however it is intended only as a short-term solution.
+
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.
  
−
* Open the ''SharedBuffer20100819Demo'' Project and switch to the Resource Perspective.
+
* 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).
−
* Open the ''.tasking'' model and inspect it. Clicking on the Main, Machine or Event nodes updates the pretty print window.
+
[[Image:contention-nondet.jpg|480px|alt=Alt|Nondeterminsitc modelling of Contention problem]]
  
−
==== Viewing Source Code ====
 
−
aka. The PrettyPrint View of an IL1 Model.
 
  
−
To view Ada source code,
+
=== Probabilistic Modelling ===
−
* from the top-menu select ''Window/Show View/Other/IL1 Pretty Printer''.
+
* Set event '''resolve''' to be probabilistic convergence by setting its convergence attribute to be ''convergent'' and the probabilistic attribute of '''resolve''' from ''standard'' to ''probabilistic''.
−
* Open the ''SharedBuffer20100819Demo'' Project and switch to the Resource Perspective.
+
[[Image:contention-prob.jpg|400px|alt=Alt|Probabilistic modelling of contention]]
−
* Open the ''.il1'' model and inspect it. Clicking on the Protected, Main Entry, or Task nodes updates the pretty print window.
 
  
−
==== Cleaning the Tasking Development ====
+
* Set <math>\Bool \setminus \{x, y\}</math> as the variant of the model
−
If the ''.tasking'' file has errors, then it may need cleaning. To do this right-click on the ''Main'' node, select ''Epsilon Translation/CleanUp''. If a model has errors it can still be viewed by clicking on the ''Selection'' tab at the bottom of the tasking editor window.
+
[[Image:contention-variant.jpg|150px|alt=Alt|Variant for the probabilistic convergent event]]
  
−
== The Tutorial ==
+
* Create a new bound element (right-click on the machine name and choose ''Add Child''/Event-B Bound Element).
−
The steps needed to generate code from an Event-B model, in this tutorial, are as follows,
+
[[Image:contention-bound-create.jpg|500px|alt=Alt|Create the bound element]]
−
* Step 1 - [http://wiki.event-b.org/index.php/Code_Generation_Tutorial#Creating_The_Tasking_Development Create the tasking development].
 
−
* Step 2 - [http://wiki.event-b.org/index.php/Code_Generation_Tutorial#Providing_the_Annotations_for_Implementations Add annotations]
 
−
* Step 3 - [http://wiki.event-b.org/index.php/Code_Generation_Tutorial#Invoking_the_Translation Invoke translators].
 
  
−
==== Creating The Tasking Development ====
+
* Set <math>\Bool</math> as the bound of the model
−
* Change to the Event-B Perspective.
+
[[Image:contention-bound.jpg|100px|alt=Alt|Bound for the probabilistic convergent event]]
−
* Open the ''SharedBuffer20100819Tutorial'' Project.
 
−
* Select the following Machines: Reader, Writer and Shared.
 
−
* Right-click and select ''Make Tasking Development/Generate Tasking Development''.
 
  
−
The new Tasking Development will not be visible in the Event-B perspective, change to the resource perspective, open and inspect the new ''.tasking'' file. The Tasking Development contains (the EMF representation of) the machines that we wish to provide implementations for. In order to introduce the new concepts we have prepared a partially complete development.
+
* Save the model
  
−
Change to the Project ''SharedBuffer20100819Tutorial2'' to begin the next step.
+
=== Proof Obligations ===
 +
* The model should have 3 proof obligations including '''resolve/PRV'''.
 +
[[Image:contention-po.jpg]]
  
−
==== Providing the Annotations for Implementations ====
+
* 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
−
* Close any Tasking Pretty Print Viewers that remain open. The incomplete model will give rise to exceptions.
+
[[Image:resolve-prv.jpg]]
−
* Go to the to the Resource Perspective.
 
−
* Open and inspect the ''.tasking'' machine.
 
  
−
The ''WriterTsk'' and ''SharedObj'' machines are incomplete. We will take the steps to necessary to provide implementation details.
+
== Explanations for some warning and error messages ==
  
−
===== The WriterTsk Machine =====
+
* '''Missing variant''' warning
−
In the partially complete tutorial project we already identified the ''WriterTsk'' as an ''Auto Task'' Tasking Machine, by adding the ''Auto Task'' extension. ''Auto Tasks'' are tasks that will be declared and defined in the ''Main'' procedure of the implementation. The effect of this is that the ''Auto Tasks'' are created when the program first loads, and then activated (made ready to run) before the ''Main'' procedure body runs. We have added the ''Periodic Task'' extension to the ''Auto Task'', and set a period of 250 milliseconds. We will now complete the sequence that has been partially defined in the task body.
+
** Problem: [[Image:contention-novariant.jpg|500px|alt=Alt|Missing variant]]
 +
** Explanation: User needs to provide a variant for probabilistic convergence events.
 +
** Solution: Add a variant to the model
  
−
*'''Add Synchronisation between TWrite and SWrite'''.
 
−
** Expand the ''Auto Task Machine'' node.
 
−
** Expand the ''Seq'' sub-tree.
 
−
** Right-click on the ''Seq'' node and select ''New Child/Left Branch EventWrapper''.
 
−
** Provide the event label ''w1'' using the properties view.
 
−
** Right-click on Event Wrapper and select ''New Child/ Synch Events''.
 
−
** Select ''Synch Events'' and go to the drop-down menu of the ''Local Event'' property.
 
−
** At this point the drop-down box displays a number of event names, select the ''TWrite'' event.
 
−
** Go to the drop-down menu of the ''Remote Event'' property.
 
−
** From the list of events select the ''SWrite'' event.
 
  
−
The Synch Events construct is used to implement [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Control_Constructs Event Synchronisation]. The next step wraps an event in an Event Wrapper in order to update the local state; there is no synchronisation as such but we will re-use the constructs that already exist.
+
* '''Missing bound''' error
 +
** Problem: [[Image:contention-nobound.jpg|400px|alt=Alt|Missing bound]]
 +
** 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).
  
−
*'''Add the Wrapped Event TcalcWVal'''.
+
== Additional features to be investigated/implemented ==
−
** Expand the sub-tree of the second ''Seq'' node.
+
* ''Proof hints'': Select event guards when creating proof obligations, such as PRV and BND
−
** Right-click on the ''Seq'' node and select ''New Child/Left Branch EventWrapper''.
 
−
** Provide the event label ''w2'' using the properties view.
 
−
** Right-click on Event Wrapper and select ''New Child/ Synch Events''.
 
−
** Select ''Synch Events'' and go to the drop-down menu of the ''Local Event'' property.
 
−
** From the list of events select the ''TcalcWVal'' event.
 
  
−
We have now completed the task body, and it just remains to complete provide details for the ''TWrite'' event. The ''TWrite'' event in ''WriterTsk'' is to be synchronized with the ''SWrite'' event in the ''SharedObj''.
+
* ''Finer-grain for probabilisitc attribute''. The probabilistic attribute might/should be attached to individual assignment and/or parameter of the event.
−
*'''Add Event Extensions'''.
 
−
** Right-click on the ''TWrite'' Event node.
 
−
** Select ''New Child/Extension''.
 
−
** Right-click on the ''Extension'' node and select ''New Child/Implementation'' from the menu.
 
−
** Go to the Implementation properties view and set the ''Implementation Type'' property to ''ProcedureSynch''.
 
−
 
 
−
*'''Identify Incoming and Outgoing parameters'''.
 
−
** Right-click on the ''outAP'' node and add an ''Extension''.
 
−
** Right-click on the ''Extension'' and select''New Child/Parameter Type''.
 
−
** Go to the ''Parameter Type'' properties view and set the ''Parameter Type'' property to ''actualOut''.
 
−
** Right-click on the ''inAP'' node and add an ''Extension''.
 
−
** Right-click on the ''Extension'' and select''New Child/Parameter Type''.
 
−
** Go to the ''Parameter Type'' properties view and set the ''Parameter Type'' property to ''actualIn''.
 
−
 
 
−
===== The Shared Machine =====
 
−
 
 
−
The next step is to identify the ''SharedObj'' machine as a ''Shared Machine''. The ''SharedObj'' Machine will be extended using the Event-B EMF extension mechanism.
 
−
* Right-click on the ''SharedObj'' Machine node in the ''.tasking'' file.
 
−
* Select ''New Child/Extension''.
 
−
* Right-click on the ''Extension'' node and select ''New Child/Shared Machine'' from the menu.
 
−
 
 
−
We now show how to extend the ''SWrite'' event of the Shared Machine with details about its implementation. The ''SWrite'' event in ''SharedObj'' is to be synchronized with the ''TWrite'' event in the ''WriterTsk''.
 
−
* '''Identify SWrite as a Syncronisation'''.
 
−
** Right-click on the ''SWrite'' Event node.
 
−
** Select ''New Child/Extension''.
 
−
** Right-click on the ''Extension'' node and select ''New Child/Implementation'' from the menu.
 
−
** Go to the Implementation properties view and set the ''Implementation Type'' property to ''ProcedureSynch''.
 
−
 
 
−
* '''Identify incoming and outgoing parameters'''.
 
−
** Right-click on the ''inFP'' node and add an ''Extension''.
 
−
** Right-click on the ''Extension'' and select''New Child/Parameter Type''.
 
−
** Go to the ''Parameter Type'' properties view and set the ''Parameter Type'' property to ''formalIn''.
 
−
** Right-click on the ''outFP'' node and add an ''Extension''.
 
−
** Right-click on the ''Extension'' and select''New Child/Parameter Type''.
 
−
** Go to the ''Parameter Type'' properties view and set the ''Parameter Type'' property to ''formalOut''.
 
−
 
 
−
===== A summary of steps taken =====
 
−
 
 
−
For a Tasking Machine definition:
 
−
# Add the Tasking Machine type (Auto etc).
 
−
# Add the task type (Periodic etc.).
 
−
# Define the task priority.
 
−
# Define the task body.
 
−
# For each event, add the Event Type.
 
−
# For each event parameter, add the Parameter Type.
 
−
 
 
−
 
 
−
For a Shared Machine definition:
 
−
# Add the ''SharedMachine'' Machine type.
 
−
# For each event, define the Event Type.
 
−
# For each event parameter, define the Parameter Type.
 
−
 
 
−
==== Invoking the Translation ====
 

Revision as of 20:51, 25 July 2017

User:Son is in charge of the plug-in.

Introduction

Event-B Qualitative Probability plug-in provides supports for reasoning about termination with probability 1 (almost-certain termination). For more details about the principles on XEvent-B, see the Qualitative Probability page.

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.*
  • 10.04.2012: Version 0.2.1 is compatible with Rodin 2.4.*
  • 14.05.2012: Version 0.2.1 is compatible with Rodin 2.5.*
  • 09.03.2015: Version 0.2.2 is released with Rodin 3.x.x
  • 09.10.2015: Version 0.2.3 is released
  • 23.07.2017: Version 0.2.4 is released

Technical References

  • Thai Son Hoang. Reasoning about almost-certain convergence properties using Event-B. Science of Computer Programming, 81:108–121, February 2014 © Elsevier. SCP website (Please use this article as the reference for the plug-in).
    • Extended version of the EASST paper (below).
    • Probablistic convergence event with refinement
    • Constraints on how (not-) to refine probabilistic events.
    • Example: Duelling cowboys
    • Example: Rabin's choice coordination.
    • Example: Herman's probabilistic self-stabilization.
  • 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. EASST website
    • Probablistic convergence event with refinement
    • Constraints on how (not-) to refine probabilistic events.
    • Example: Rabin's Choice Coordination.
  • 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. 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).

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 x and y represent the choice for each process: TRUE for short delay FALSE for long delay.
  • Resolving contention is model as an event of the model with guard x = y (i.e. keep trying when the choices are identical).

Alt


Probabilistic Modelling

  • Set event resolve to be probabilistic convergence by setting its convergence attribute to be convergent and the probabilistic attribute of resolve from standard to probabilistic.

Alt

  • Set \Bool \setminus \{x, y\} as the variant of the model

Alt

  • Create a new bound element (right-click on the machine name and choose Add Child/Event-B Bound Element).

Alt

  • Set \Bool as the bound of the model

Alt

  • Save the model

Proof Obligations

  • The model should have 3 proof obligations including resolve/PRV.

Contention-po.jpg

  • The goal of proof obligation resolve/PRV is \exists x^\prime, y^\prime \qdot \Bool \setminus \{x^\prime, y^\prime\} \subset \Bool \setminus \{x, y\}. With hypothesis x = y (from the guard of the event), the proof obligation can be discharged by instantiating different values for x^\prime and y^\prime (e.g. \True for x^\prime and \False for y^\prime). Alternatively, the obligation can be interactively discharge using p1 (AterlierB Predicate Prover on lasso'd hypotheses) directly as shown below

Resolve-prv.jpg

Explanations for some warning and error messages

  • Missing variant warning
    • Problem: Alt
    • Explanation: User needs to provide a variant for probabilistic convergence events.
    • Solution: Add a variant to the model


  • Missing bound error
    • Problem: Alt
    • 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.
Retrieved from ‘https://wiki.event-b.org/index.php?title=Code_Generation_Tutorial&oldid=4245’