Difference between pages "Tasking Event-B Overview" and "Theory Plug-in"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Andy
 
(Add to Theory Plug-in category)
 
Line 1: Line 1:
=== Tasking Event-B ===
+
Return to [[Rodin Plug-ins]]
Tasking Event-B can be viewed as an extension of the existing Event-B language. We use the existing approaches of refinement and decomposition to structure a project that is suitable for a Tasking Development. During the modelling phase parameters are introduced to facilitate decomposition. As a result of the decomposition process, parameters become part of the interface that enables event synchronization. We make use of this interface and add information (see [[#Implementing Events]]) to facilitate code generation. The tasking extension consists of the constructs in the following table.
 
  
<center>
+
See also [[Theory Release History]]
{| border="1"
 
!Construct
 
!Options
 
|-
 
|Machine Type
 
|DeclaredTask, [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Tasking_Machines AutoTask], [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Shared_Machines SharedMachine], [http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#The_Environ_Machine Environ]
 
|-
 
|[http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Control_Constructs Control]
 
|Sequence, Loop, Branch, EventSynch, Output
 
|-
 
|[http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Tasking_Machines Task Type]
 
|Periodic(n), Triggered, Repeating, OneShot
 
|-
 
|Priority
 
| -
 
|-
 
|[http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Implementing_Events Event Role]
 
|Branch, Loop, ProcedureDef, ProcedureSynch, Actuating, Sensing
 
|-
 
|http://wiki.event-b.org/index.php/Tasking_Event-B_Overview#Implementing_Events Parameter Type]
 
|ActualIn, ActualOut, FormalIn, FormalOut
 
|-
 
|Addressed Variable
 
|Address, Base
 
|}
 
</center>
 
  
=== Tasking Developments ===
+
The Theory plug-in provides capabilities to extend the Event-B language and the proving infrastructure in a familiar fashion to Rodin users. This page provides useful information about the plug-in and its capabilities.
A Tasking Development is modelling component that is generated programmatically, at the direction of the user. The Tasking Development consists of a number of machines (and perhaps associated contexts). We make use of the Event-B EMF extension mechanism <ref name = "EBEMF">[[EMF framework for Event-B]]</ref>, which allows addition of new constructs to a model. The machines in the Tasking Development are extended with the constructs shown in the table, and may be viewed as keywords in a textual representation of the language. With extensions added, a Tasking Development can be translated to a common language model for mapping to implementation source code. There is also a translator that constructs new machines/contexts modelling the implementation, and these should refine/extend the existing elements of the Event-B project.
 
  
==== Tasking Machines ====
+
===Motivation===
The following constructs relate only to Tasking Machines, and provide implementation details. Timing of periodic tasks is not modelled formally. Tasking Machines are related to the concept of an Ada task. These can be implemented in Ada using tasks, in C using the pthread library C, or in Java using threads.
+
Up to Rodin v2.0, the mathematical language used in Event-B has been fixed. As such, it was not possible to define reusable polymorphic operators. A workaround was to define any required operators as set constructs in contexts. Originally, contexts were supposed to provide a parametrization of machines. The aforementioned limitations of the Event-B language lead to users to use contexts for purposes for which they were not intentionally devised. Examples of operators that can be useful to users include the sequence operator (which was present in classical B mathematical language) and the bag operator.
  
* Tasking Machines may be characterised by the following types:
+
In Rodin v2.0, support for customised syntactic symbols was introduced. The Theory plug-in, as a result, evolved from being just a component to define rewrite rules to a versatile platform to define and validate proof and language extensions.
** AutoTasks - Singleton Tasks.
 
** Declared tasks - (Not currently used) A task template relating to an Ada ''tasktype'' declaration.  
 
** TaskType - Defines the scheduling, cycle and lifetime of a task. i.e. one-shot periodic or triggered. The period of a task is specified in milliseconds.
 
** Priority - An integer value is supplied, the task with the highest value priority takes precedence when being scheduled. For the demonstrator tool the default priority is 5.
 
  
''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.
+
The latest Theory plug-in is released for Rodin v2.8.
  
==== Shared Machines ====
+
===Overview===
A Shared Machine corresponds to the concept of a protected resource, such as a monitor. They may be implemented in Ada as a Protected Object, in C using mutex locking, or in Java as a monitor.
+
The Theory plug-in is a Rodin extension that provides the facility to define '''''mathematical extensions''''' as well as '''''prover extensions'''''.
 +
Mathematical extensions are new operator definitions and new datatype definitions and axiomatic definitions. Operator definitions can be expression operators (e.g., ''card'') and predicate operators (e.g., ''finite''). Datatypes extensions can be used to define enumerated datatypes (e.g., ''DIRECTION'') as well as inductive datatypes (e.g., ''Tree''). Axiomatic definitions can be used to define new data types like "REAL".
  
* Applied to the Shared Machine we have:
+
The placeholder for mathematical and prover extensions is a Theory construct which looks similar to contexts and machines. A theory can include datatypes definitions, operator definitions, axiomatic definitions, inference and rewrite rules as well as polymorphic theorems. The [http://wiki.event-b.org/images/Theory_Plugin.pdf user manual] provides a guide to developing and using theories.
** A SharedMachine ''keyword'' that identifies a machine as a Shared Machine.
 
  
==== The Environ Machine ====
+
=== Installation & Update ===
An Environ machine is a model of the environment. It can be used to generate code for use in a simulation, or discarded (from the IL1 model) in the case that a simulated environment is not required.
 
  
* Applied to the Environ Machine we have:
+
The installation or update for the Theory plug-in is available under the main Rodin Update site (http://rodin-b-sharp.sourceforge.net/updates) under the category "Modelling Extensions". Like always, after the installation, restarting Rodin is recommended.
** An Environ Machine ''keyword'' that identifies a machine as an Environ Machine.
 
  
=== Implementation Specifics ===
+
===User Manual===
At the stage where we are considering how to implement the Event-B development we need to think about controlling the flow of execution, and how events should be implemented. The following section describes the constructs that we have introduced to facilitate this.
+
The user manual is available here: [http://wiki.event-b.org/images/Theory_Plugin.pdf Theory User Manual]. Below is the presentation of the sequence theory which its description can be found in the user manual:
==== Control Constructs ====
 
Each Tasking Machine has a ''task body'' which contains the flow control (algorithmic constructs).
 
  
* We have the following constructs available in the Tasking Machine body:
+
[[image:SeqTheory.png|center|thumb|1500px|'''Theory of Sequence''']]
** Sequence - for imposing an order on events.
 
** Branch - choice between a number of mutually exclusive events.
 
** Loop - event repetition while it's guard remains true.
 
** EventWrapper - a wrapper for the Event-B element (soon to be redundant). 
 
** Synch Events - synchronizes two events.
 
** Text Output - writes textual output to the screen.
 
  
Synchronization corresponds to:
+
===Standard Library===
* a subroutine call from task to shared machine, or,
+
In this section, you find a set of standard theories and some models using some of these theories.  
* sensing or actuating of environment variables.
 
  
In the case of a subroutine call the subroutine is an atomic (with respect to an external viewer) update to state. The updates in the protected resource are implemented by a procedure call to a protected object, and tasks do no share state. The synchronization construct also provides the means to specify parameter passing, both in and out of the task.
+
The standard library of the theories is available to download:
 +
[https://sourceforge.net/projects/rodin-b-sharp/files/Theory_StdLib/StandardTheory0.1.zip/download here] for Rodin2.8 and
 +
[https://sourceforge.net/projects/rodin-b-sharp/files/Theory_StdLib/StandardTheory0.2.zip/download here] for Rodin3.1.  
 +
This library includes:
 +
* BasicTheory project: including theories of BinaryTree, BoolOps, List, PEANO, SUMandPRODUCT and Seq.
 +
* RelationOrderTheory project: including theories of Connectivity, FixPoint, Relation, Well_Fondation, closure, complement and galois.
 +
* RealTheory project: including theory of Real.
  
In the case of a sensing or actuating event, the updates of the action correspond to reads of monitored variables, and writes to controlled variables of the environment.
+
Also it includes three simple Event-B models that use some of the theories:
 +
* Data project: using SUMandPRODUCT theory
 +
* Queue project: using Seq theory
 +
* SimpleNetwork project: using closure theory
  
Event wrappers:
+
In order to keep the POs discharged, you need to install "Atelier B provers" as well.
* The event synchronization construct is contained in an event wrapper. The wrapper may also contain a single event (we re-use the synchronization construct, but do not use it for synchronizing). The event may belong to the Tasking Machine, a Shared Machine that is visible to the task, or the Environ machine. Single events in a wrapper correspond to a subroutine call in an implementation.
 
  
When Editing the EMF model the constructs have the following names:
+
===Capabilities===
 +
The Theory plug-in has the following capabilities:
  
<center>
+
* Theory Definition:
{| border="1"
+
** Definition of datatypes: datatypes are defined by supplying the types on which they are polymorphic, a set of constructors one of which has to be a base constructor. Each constructor may or may not have destructors.
!Construct
+
** Definition of operators: operators can be defined as predicate or expression operators. An expression operator is an operator that "returns" an expression, an example existing operator is ''card''. A predicate operator is one that "returns" a predicate, an example existing predicate operator is ''finite''.
!EMF name
+
** Definition of axiomatic definitions: axiomatic definitions are defined by supplying the types, a set of operators, and a set of axioms.
|-
+
** Definition of rewrite rules: rewrite rules are one-directional equalities that can be applied from left to right. The Theory plug-in can be used to define rewrite rules.
|Sequence
+
** Definition of inference rules: inference rules can be used to infer new hypotheses, split a goal into sub-goals or discharge sequents.
|Seq
+
** Definition of polymorphic theorems: theorems can be defined and validated once, and can then be imported into sequents of proof obligations if a suitable type instantiation is available.
|-
+
** Validation of extensions: where appropriate, proof obligations are generated to ensure soundness of extensions. This includes, proof obligations for validity of inference and rewrite rules, as well as proof obligations to validate operator properties such as associativity and commutativity.
|Branch
+
*Theory Deployment: this step signifies that a theory is ready for use. Theories can be deployed after they have been optionally validated by the user. It is strongly advisable to discharge all proof obligations before deployment.
|Branch
+
Once a theory has been deployed to its designated project, all its extensions (mathematical and prover extensions) can be used in models.
|-
 
|Loop
 
|Do
 
|-
 
|Text Output
 
|Output
 
|-
 
|EventWrapper
 
|EventWrapper
 
|-
 
|SynchEvents
 
|SynchEvents
 
|-
 
|}
 
</center>
 
  
== The Abstract Syntax ==
+
===Insider Look===
 +
The Theory plug-in partially satisfies the requirements outlined in the following document:
 +
* [http://deploy-eprints.ecs.soton.ac.uk/80/ Abrial, Jean-Raymond and Butler, Michael and Schmalz, Matthias and Hallerstede, Stefan and Voisin, Laurent. Mathematical Extensions Proposal]
  
The following BNF syntax relates to the EMF model that developers will use in the tutorial. The task body is used to specify the ordering of events.  The use of the EMF editor should be seen as a short term solution, in the longer term a suitable form-based or text-based editor is envisaged. Text, Variable and Event nodes are terminals in the syntax, they relate to Event-B elements.
+
A more accurate description of the implemented functionalities of the plug-in can be found in the following document:
 +
* [http://deploy-eprints.ecs.soton.ac.uk/251/ Michael Butler, Issam Maamria. Mathematical Extensions Summary]
  
<pre>
+
The following two papers describe rewriting and well-definedness issues that has to be accounted for:
    TaskBody ::= Seq | Branch | Do | EventWrapper | Output
 
  
    Seq  ::=  TaskBody TaskBody
+
* [http://eprints.ecs.soton.ac.uk/18269/ Issam Maamria, Michael Butler, Andrew Edmunds, and Abdolbaghi Rezazadeh. On an Extensible Rule-based Prover for Event-B, ABZ'2010.]
 
+
* [http://eprints.ecs.soton.ac.uk/21221/ Issam Maamria, Michael Butler. Rewriting and Well-Definedness within a Proof System.]
    Branch ::=  Body [SubBranch] Else
 
 
 
    SubBranch ::=  Body [SubBranch]
 
 
 
    Else ::=  EventWrapper
 
 
 
    Body ::=  EventWrapper
 
 
 
    Do ::=  Body [Finally]
 
 
 
    Finally ::=  EventWrapper
 
 
 
    Output ::=  Text Variable
 
 
 
    EventWrapper ::=  SynchEvents
 
 
 
    SynchEvents ::=  Local Remote
 
 
 
    Local ::=  Event
 
 
 
    Remote ::=  Event
 
</pre>
 
 
 
==== Implementing Events ====
 
An event's role in the implementation is identified using the following extensions which are added to the event. Events used in task bodies are 'references' that make use of existing event definitions from the abstract development. The events are extended. to assist with translation, with a keyword indicating their role in the implementation.
 
 
 
* Event implementation role.
 
** Branch - In essence a task's event is split in the implementation; guards are mapped to branch conditions and actions are mapped to the branch body. If the branch refers to a Shared Machine event (procedureDef) then this is mapped to a simple procedure call.
 
** Loop - The task's event guard maps to the loop condition and actions to to loop body. If the loop refers to a Shared Machine event then it is mapped to a simple procedure call.
 
** ProcedureSynch - This usually indicates to the translator that the event maps to a subroutine, but an event in a task may not require a subroutine implementation if its role is simply to provide parameters for a procedure call.
 
** ProcedureDef - Identifies an event that maps to a (potentially blocking) subroutine definition. Event guards are implemented as a conditional wait; in Ada this is an entry barrier, and in C may use a pthread condition variable .
 
** Sensing - Identifies an event that maps to a read from the environment. If the environment is simulated without address variables then the sensing event is similar to a ProcedureSynch event, in that it has an update action that models assignment of a return value from a subroutine call. The event parameters act like the ''actualIn'' parameters of a ProcedureSynch event. On the other hand, if the event has addressed variables associated with its event parameters, then they map to direct reads from memory mapped variables in the generated code.
 
** Actuating - Identifies an event that maps to a write to the environment. If the environment is simulated without address variables then the actuating event has no update action, the parameters act like ''actualOut'' parameters of a ProcedureSynch event. If a sensing event has addressed variables associated with its parameters then they map to direct writes to memory mapped variables in the generated code.  
 
 
 
Sensing (and actuating) can be viewed as a kind of synchronisation. Synchronisation between tasks and shared objects are represented as subroutine calls. The sensing/actuating synchronisations only occur between tasks and the environment. In implementable code, when an subroutine is defined, its formal parameters are replaced by actual parameter values at run-time. To assist the code generator we extend the Event-B parameters. We identify formal and actual parameters in the implementation, and add the following keywords to the event parameters, as follows:
 
 
 
* Event parameter types - Note: formal parameters are place-holders in a subroutine; they are replaced by the actual parameters at call time.
 
** FormalIn or FormalOut - event parameters are extended with the ParameterType construct. Extension with formal parameters indicates a mapping to formal parameters in the implementation.
 
** ActualIn or ActualOut - Extension with an actual parameter indicates a mapping to an actual parameter in the implementation.
 
 
 
===== Addressed Variables =====
 
When sensing monitored variables, or actuating controlled variables in the environment, we may wish to use explicit memory addresses for use in the final implementation, or perhaps in the environment simulation too. We can link a task's event parameters, and an Environ machines variables, with specific addresses and use these in the generated code.
 
 
 
== References ==
 
 
 
<references/>
 
  
  
 +
[[Category:Plugin]]
 
[[Category:User documentation]]
 
[[Category:User documentation]]
 +
[[Category:Proof]]
 +
[[Category:Theory Plug-in]]

Latest revision as of 14:53, 14 June 2021

Return to Rodin Plug-ins

See also Theory Release History

The Theory plug-in provides capabilities to extend the Event-B language and the proving infrastructure in a familiar fashion to Rodin users. This page provides useful information about the plug-in and its capabilities.

Motivation

Up to Rodin v2.0, the mathematical language used in Event-B has been fixed. As such, it was not possible to define reusable polymorphic operators. A workaround was to define any required operators as set constructs in contexts. Originally, contexts were supposed to provide a parametrization of machines. The aforementioned limitations of the Event-B language lead to users to use contexts for purposes for which they were not intentionally devised. Examples of operators that can be useful to users include the sequence operator (which was present in classical B mathematical language) and the bag operator.

In Rodin v2.0, support for customised syntactic symbols was introduced. The Theory plug-in, as a result, evolved from being just a component to define rewrite rules to a versatile platform to define and validate proof and language extensions.

The latest Theory plug-in is released for Rodin v2.8.

Overview

The Theory plug-in is a Rodin extension that provides the facility to define mathematical extensions as well as prover extensions. Mathematical extensions are new operator definitions and new datatype definitions and axiomatic definitions. Operator definitions can be expression operators (e.g., card) and predicate operators (e.g., finite). Datatypes extensions can be used to define enumerated datatypes (e.g., DIRECTION) as well as inductive datatypes (e.g., Tree). Axiomatic definitions can be used to define new data types like "REAL".

The placeholder for mathematical and prover extensions is a Theory construct which looks similar to contexts and machines. A theory can include datatypes definitions, operator definitions, axiomatic definitions, inference and rewrite rules as well as polymorphic theorems. The user manual provides a guide to developing and using theories.

Installation & Update

The installation or update for the Theory plug-in is available under the main Rodin Update site (http://rodin-b-sharp.sourceforge.net/updates) under the category "Modelling Extensions". Like always, after the installation, restarting Rodin is recommended.

User Manual

The user manual is available here: Theory User Manual. Below is the presentation of the sequence theory which its description can be found in the user manual:

Theory of Sequence

Standard Library

In this section, you find a set of standard theories and some models using some of these theories.

The standard library of the theories is available to download:

here for Rodin2.8 and
here for Rodin3.1. 

This library includes:

  • BasicTheory project: including theories of BinaryTree, BoolOps, List, PEANO, SUMandPRODUCT and Seq.
  • RelationOrderTheory project: including theories of Connectivity, FixPoint, Relation, Well_Fondation, closure, complement and galois.
  • RealTheory project: including theory of Real.

Also it includes three simple Event-B models that use some of the theories:

  • Data project: using SUMandPRODUCT theory
  • Queue project: using Seq theory
  • SimpleNetwork project: using closure theory

In order to keep the POs discharged, you need to install "Atelier B provers" as well.

Capabilities

The Theory plug-in has the following capabilities:

  • Theory Definition:
    • Definition of datatypes: datatypes are defined by supplying the types on which they are polymorphic, a set of constructors one of which has to be a base constructor. Each constructor may or may not have destructors.
    • Definition of operators: operators can be defined as predicate or expression operators. An expression operator is an operator that "returns" an expression, an example existing operator is card. A predicate operator is one that "returns" a predicate, an example existing predicate operator is finite.
    • Definition of axiomatic definitions: axiomatic definitions are defined by supplying the types, a set of operators, and a set of axioms.
    • Definition of rewrite rules: rewrite rules are one-directional equalities that can be applied from left to right. The Theory plug-in can be used to define rewrite rules.
    • Definition of inference rules: inference rules can be used to infer new hypotheses, split a goal into sub-goals or discharge sequents.
    • Definition of polymorphic theorems: theorems can be defined and validated once, and can then be imported into sequents of proof obligations if a suitable type instantiation is available.
    • Validation of extensions: where appropriate, proof obligations are generated to ensure soundness of extensions. This includes, proof obligations for validity of inference and rewrite rules, as well as proof obligations to validate operator properties such as associativity and commutativity.
  • Theory Deployment: this step signifies that a theory is ready for use. Theories can be deployed after they have been optionally validated by the user. It is strongly advisable to discharge all proof obligations before deployment.

Once a theory has been deployed to its designated project, all its extensions (mathematical and prover extensions) can be used in models.

Insider Look

The Theory plug-in partially satisfies the requirements outlined in the following document:

A more accurate description of the implemented functionalities of the plug-in can be found in the following document:

The following two papers describe rewriting and well-definedness issues that has to be accounted for: