Difference between pages "Strengthening the AST Library for Rodin 3.0" and "Tasking Event-B Overview"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Vinmont
 
imported>Andy
 
Line 1: Line 1:
−
A part of the Rodin 3.0 development aims to strengthen the AST library. This page explains the choices we have done during this step.
+
=== Tasking Event-B ===
 +
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.
  
−
== Type Environment ==
+
<center>
 +
{| border="1"
 +
|Construct
 +
|Options
 +
|-
 +
|Machine Type
 +
|DeclaredTask, AutoTask, SharedMachine, Environ
 +
|-
 +
|Control
 +
|Sequence, Loop, Branch, EventSynch
 +
|-
 +
|Task Type
 +
|Periodic(n), Triggered, Repeating, OneShot
 +
|-
 +
|Priority
 +
| -
 +
|-
 +
|Event Type
 +
|Branch, Loop, ProcedureDef, ProcedureSynch, Actuating, Sensing
 +
|-
 +
|Parameter Type
 +
|ActualIn, ActualOut, FormalIn, FormalOut
 +
|
 +
|-
 +
|Addressed Variable
 +
|Address, Base
 +
}
 +
</center>
  
−
Type environments have changed in Rodin 3.0 in order to reinforce their good
+
=== Tasking Developments ===
−
use and their robustness.  
+
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.
  
−
First of all, we have added a new mechanism to add given sets implicitly introduced by types when new elements are added.
+
==== Tasking Machines ====
 +
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.
  
−
Then, we have added a new interface to represent inferred type environments.
+
* Tasking Machines may be characterised by the following types:
−
These environments are the ones that are returned in the result of the
+
** AutoTasks - Singleton Tasks.
−
typecheck methods of Formula and Expression.
+
** 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.
  
−
Finally we have added mechanism to separate mutable and immutable type
+
''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.
−
environments by creating two children interfaces of the type environment
 
−
interface, {{class|ITypeEnvironmentBuilder}} and
 
−
{{class|ISealedTypeEnvironment}}. This mechanism provides a strong guarantee
 
−
that a type environment will not be modified if necessary and allows at the
 
−
same time to be flexible when needed (see [[Rodin 3.0 Plug-in Migration
 
−
Guide]] for more information).
 
  
−
== Type Checking ==
+
==== Shared Machines ====
−
The type checking step has been strengthened to avoid that the type checker accepts given types implicitly introducing given sets incompatibles with the type environment and thus free identifiers. It also allowed to detect and correct a new occurrence of the bug #635 (old name #3574565) that was leading to an incoherent result of the formula type checking since the formula was not correctly type checked but the result was indicating a success.
+
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.
  
−
Regarding the legibility for identifiers no modification has been done, that is to say that if the same name is used for a free and bound identifier then the bound identifier will be renamed since it is identified by its de Bruijn number.
+
* Applied to the Shared Machine we have:
 +
** A SharedMachine ''keyword'' that identifies a machine as a Shared Machine.
  
−
The modification of the type checking step introduces the following modifications:
+
==== The Environ Machine ====
−
* In the ''typecheck()'' procedure of nodes, we now analyse the type of the nodes that could introduce new given sets and add those given sets to the resulting inferred type environment. It guarantees that incompatible free identifiers names or given sets are not introduced.
+
An Environ machine is a model of the environment. It can be used to generate code for use in a simulation, or discarded in the case that it is not required.
−
* In the ''synthesize()'' procedure, that is executed a first time at node creation and a second time during solving types step, we now add the given sets introduced by given types as free identifiers on concerned nodes. As a consequence if a given set and a free identifier have a name conflict it will also be detected during this step. Particularly it will provide a way to detect and raise an {{class|IllegalArgumentException}} when an invalid type is provided at node creation.
 
−
* If the whole type checking procedure succeeds then all free identifiers are checked and added to the inferred environment if necessary.
 
  
−
== AST nodes construction ==
+
* Applied to the Environ Machine we have:
−
AST nodes construction is possible using {{class|FormulaFactory}} methods (direct access to constructors is now explicitly forbidden) and has been strengthened by verifying that arguments provided are valid regarding constructed node. Those verifications are documented with the exceptions raised when conditions on arguments are not respected. It allows to avoid exceptions raised later for which source is more complicated to locate.
+
** An Environ Machine ''keyword'' that identifies a machine as an Environ Machine.
−
Moreover AST nodes and types are now keeping a reference on the factory that was used to build them and AST library enforces that they have been built by the same formula factory. Then we now avoid incoherent nodes and types by construction regarding their formula factory that could have lead, e.g., to use reserved words in a part of a formula as a free identifier name in another part.
 
  
−
[[Category:Design]]
+
=== Implementation Specifics ===
−
[[Category:Developer documentation]]
+
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.
 +
==== 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:
 +
** 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.
 +
** Event Synchronisation - synchronization between two events.
 +
 
 +
Synchronization corresponds to:
 +
* a subroutine call from task to shared machine, or,
 +
* 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.
 +
 
 +
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.
 +
 
 +
Event wrappers:
 +
* 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.
 +
 
 +
==== 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.
 +
** 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.
 +
 
 +
In an implementation, 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
 +
** 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.
 +
 
 +
== References ==
 +
 
 +
<references/>
 +
 
 +
 
 +
[[Category:User documentation]]

Revision as of 15:57, 3 May 2011

Tasking Event-B

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.

Construct Options
Machine Type DeclaredTask, AutoTask, SharedMachine, Environ
Control Sequence, Loop, Branch, EventSynch
Task Type Periodic(n), Triggered, Repeating, OneShot
Priority -
Event Type Branch, Loop, ProcedureDef, ProcedureSynch, Actuating, Sensing
Parameter Type ActualIn, ActualOut, FormalIn, FormalOut
Addressed Variable Address, Base

}

Tasking Developments

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 [1], 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

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.

  • Tasking Machines may be characterised by the following types:
    • 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.

Shared Machines

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.

  • Applied to the Shared Machine we have:
    • A SharedMachine keyword that identifies a machine as a Shared Machine.

The Environ Machine

An Environ machine is a model of the environment. It can be used to generate code for use in a simulation, or discarded in the case that it is not required.

  • Applied to the Environ Machine we have:
    • An Environ Machine keyword that identifies a machine as an Environ Machine.

Implementation Specifics

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.

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:
    • 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.
    • Event Synchronisation - synchronization between two events.

Synchronization corresponds to:

  • a subroutine call from task to shared machine, or,
  • 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.

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.

Event wrappers:

  • 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.

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.
    • 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.

In an implementation, 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
    • 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.

References

  1. ↑ EMF framework for Event-B
Retrieved from ‘https://wiki.event-b.org/index.php?title=Strengthening_the_AST_Library_for_Rodin_3.0&oldid=9633’