Difference between pages "Event-B Examples" and "The Use of Theories in Code Generation"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>WikiSysop
 
imported>Andy
 
Line 1: Line 1:
{{TOCright}}
+
= Defining Translations Using The Theory Plug-in =
This page is for listing available example Event-B/Rodin projects.
+
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==
 +
<div id="fig:Translation Rules">
 +
<br/>
 +
[[Image:TheoryCGRules.png|center||caption text]]
 +
<center>'''Figure 1''': Translation Rules</center>
 +
<br/>
 +
</div>
  
 +
Figure 1 shows the interface, and some translations rules of the mapping to Ada.
  
== Year 2009 ==
+
The theory is given a name, and may import some other theories. Type parameters can be added, and we use them here to type the meta-variables. The meta-variable ''a'' is restricted to be an integer type, but meta-variable ''c'' can be any type. Meta-variables are used in the translator rules for pattern matching.
  
=== [http://deploy-eprints.ecs.soton.ac.uk/107/ Real-time controller for a water tank]===
+
Translator rules are templates, which are used in pattern matching. Event-B formulas 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. During translation an abstract syntax tree (AST) representation of the formula is used. The theory plug-in attempts to match the formulas in the rules with each syntactic element of the AST. As it does so it builds the textual output as a string, until the whole AST has been successfully matched. When a complete tree is matched, the target code is returned. If the AST is not matched, a warning is issued, and a string representation of the original formula is returned.
By Michael Butler.
 
  
The draft paper outlines an approach to treating continuous behaviour in Event-B by a discrete approximation.
+
== Type Rules for Code Generation ==
An example of a water tank system is used to illustrate the proposed approach.  The archive containts the
 
Event-B development for the water tank system.
 
  
=== [http://deploy-eprints.ecs.soton.ac.uk/95/ UML-B Development of an ATM]===
+
The type rules section, shown in Figure 1, is where the relationship is defined, between Event-B types and the type system of the implementation.
By Mar Yah Said,  Michael Butler and Colin Snook.
 
  
This paper outlines support for refinement of classes and statemachines in UML-B and issustrates these
+
= Adding New (implementation-level) Types =
with an Automated Teller Machine (ATM) example.  The ATM development is contained in a Rodin
+
When we are working at abstraction levels close to the implementation level, we may make an implementation decision which requires the introduction of a new type to the development. We give an example of our approach, where we add a new array type, shown in Figure 2, and then define its translation to code.
archive. It consists of an abstract model focusing on bank account updates.  The ATM, pin cards and
 
messaging between ATMs and a bank server are introduced in successive refinements.
 
  
=== [http://deploy-eprints.ecs.soton.ac.uk/84/ MIDAS: A Formally Constructed Virtual Machine]===
+
== An Array Type Definition ==
By [[Steve]].
+
<div id="fig:Extension with an Array Type">
 +
<br/>
 +
[[Image:ArrayDef.png|center||caption text]]
 +
<center>'''Figure 2''': Array Definition</center>
 +
<br/>
 +
</div>
  
MIDAS (Microprocessor Instruction and Data Abstraction System) is a specification of an Instruction Set Architecture (ISA). It is refined to a usable Virtual Machine (VM) capable of executing binary images compiled from the C language. It was developed to demonstrate a methodology for formal construction of various ISAs in Event-B via a generic model. There are two variants: a stack-based machine and a randomly accessible register array machine. The two variants employ the same instruction codes, the differences being limited to register file behavior.
+
The array operator notation is defined in the expression array(s: P(T)); and the semantics is defined in the direct definition. arrayN constrains the arrays to be of fixed length. Array lookup, update, and constructor operators are subsequently defined. In the next step we need to define any translations required to implement the array in code.
  
The archive supplied at the Deploy repository contains: C-coded prototypes of the MIDAS VMs, an Event-B model refinement constructing the same VMs, the B2C Event-B to C auto-generation tool, C compiler/assembler/linkers for the VMs, an example C test suite, and execution environments for running compiled C on the machines.
+
== Translation Rules ==
  
=== [http://deploy-eprints.ecs.soton.ac.uk/82/ Development of a Network Topology Discovery Algorithm]===
+
<div id="Translation Rules for the Array Type">
By ''Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond''.
+
<br/>
 +
[[Image:ArrayTrans.png|center||caption text]]
 +
<center>'''Figure 3''': Translation Rules for the Array Type</center>
 +
<br/>
 +
</div>
  
This paper and this Rodin development is another version of the [[#Link State Routing Development|Link State Routing Development]] presented in 2008.
+
Figure 3 shows the Ada translation; beginning with the meta-variable definitions that are used for pattern matching in the translation rules. Each of the operators; ''newArray'', and ''update'', and an expression using the ''lookup'' operator, are mapped to their implementations on the right hand side of the rule. The ''Type Rules'' section describes the implementation's description of the ''arrayN'' type.
 
 
== Year 2008 ==
 
=== [http://deploy-eprints.ecs.soton.ac.uk/31/ Link State Routing Development]===
 
By ''Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond''.
 
 
 
We present a formal development in Event-B of a distributed topology discovery algorithm. Distributed topology discovery is at the core several routing algorithms and is the problem of each node in a network discovering and maintaining information on the network topology. One of the key challenges in developing this algorithm is specifying the problem itself.We provide a specification that includes both safety properties, formalizing invariants that should hold in all system states, and liveness properties that characterize when the system reaches stable states. We specify these by appropriately combining invariants, event refinement, and proofs of event convergence and deadlock freedom. The combination of these features is novel and should be useful for formalizing and developing other kinds of semi-reactive systems, which are systems that react to, but do not modify, their environment.
 
 
 
=== [http://deploy-eprints.ecs.soton.ac.uk/22/ Modelling and proof of a Tree-structured File System] ===
 
By ''Damchoom, Kriangsak and Butler, Michael and Abrial, Jean-Raymond''.
 
 
 
We present a verified model of a tree-structured file system which was carried out using Event-B and the Rodin platform. The model is focused on basic functionalities affecting the tree structure including create, copy, delete and move. This work is aimed at constructing a clear and accurate model with all proof obligations discharged. While constructing the model of a file system, we begin with an abstract model of a file system and subsequently refine it by adding more details through refinement steps.  We have found that careful formulation of invariants and useful theorems that can be reused for discharging similar proof obligations make models simpler and easier to prove.
 
 
 
=== [http://deploy-eprints.ecs.soton.ac.uk/56/ Deliverable D8 D10.1 "Teaching Materials"] ===
 
By ''Abrial, Jean-Raymond and Hoang, Thai Son and Schmalz, Matthias''.
 
 
 
==Year 2007==
 
=== [http://deploy-eprints.ecs.soton.ac.uk/9/ Redevelopment of an Industrial Case Study Using Event-B and Rodin]===
 
From ''Rezazadeh, Abdolbaghi and Butler, Michael and Evans, Neil''.
 
 
 
CDIS is a commercial air traffic information system that was developed using formal methods 15 years ago by Praxis, and it is still in operation today. This system is an example of an industrial scale system that has been developed using formal methods. In particular, the functional requirements of the system were specified using VVSL -- a variant of VDM. A subset of the original specification has been chosen to be reconstructed on the Rodin platform based on the new Event-B formalism. The goal of our reconstruction was to overcome three key difficulties of the original formalisation, namely the difficulty of comprehending the original specification, the lack of any mechanical proof of the consistency of the specification and the difficulty of dealing with distribution and atomicity refinement. In this paper we elucidate how a new formal notation and tool can help to overcome these difficulties.
 
 
 
[[Category:Examples]]
 

Revision as of 15:51, 15 May 2012

Defining Translations Using 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


caption text
Figure 1: Translation Rules


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

The theory is given a name, and may import some other theories. Type parameters can be added, and we use them here to type the meta-variables. The meta-variable a is restricted to be an integer type, but meta-variable c can be any type. Meta-variables are used in the translator rules for pattern matching.

Translator rules are templates, which are used in pattern matching. Event-B formulas 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. During translation an abstract syntax tree (AST) representation of the formula is used. The theory plug-in attempts to match the formulas in the rules with each syntactic element of the AST. As it does so it builds the textual output as a string, until the whole AST has been successfully matched. When a complete tree is matched, the target code is returned. If the AST is not matched, a warning is issued, and a string representation of the original formula is returned.

Type Rules for Code Generation

The type rules section, shown in Figure 1, is where the relationship is defined, between Event-B types and the type system of the implementation.

Adding New (implementation-level) Types

When we are working at abstraction levels close to the implementation level, we may make an implementation decision which requires the introduction of a new type to the development. We give an example of our approach, where we add a new array type, shown in Figure 2, and then define its translation to code.

An Array Type Definition


caption text
Figure 2: Array Definition


The array operator notation is defined in the expression array(s: P(T)); and the semantics is defined in the direct definition. arrayN constrains the arrays to be of fixed length. Array lookup, update, and constructor operators are subsequently defined. In the next step we need to define any translations required to implement the array in code.

Translation Rules


caption text
Figure 3: Translation Rules for the Array Type


Figure 3 shows the Ada translation; beginning with the meta-variable definitions that are used for pattern matching in the translation rules. Each of the operators; newArray, and update, and an expression using the lookup operator, are mapped to their implementations on the right hand side of the rule. The Type Rules section describes the implementation's description of the arrayN type.