Difference between pages "Event-B Examples" and "Event-B Indexers"

Revision as of 09:35, 10 March 2009

Purpose

Event-B indexers populate the index repository. Currently, indexers are implemented for the following files :

machine (.bum)
context (.buc)

Event-B Occurrence Kinds

So far, the following occurrence kinds have been defined :

DECLARATION : when a variable, a carrier set, ..., is declared
REFERENCE : when a variable, a carrier set, ..., is referenced (but not modified)
MODIFICATION : when a variable is modified (e.g., occurs in the left-hand side of an event action)
REDECLARATION : when a variable, parameter or event is redeclared (refined).

Please notice the distinction between the index repository notion of declaration (IDeclaration) and the Event-B occurrence kind DECLARATION.

What Is Indexed

Currently, indexed elements are :

carrier sets
constants
variables
events
parameters

Formulas which cannot be parsed are ignored.

In the descriptions below, the following notation will be used to specify locations :

[element] : internal location
[element/attribute] : attribute location
[element/attribute/begin..end] : attribute substring location

Context Indexer

Dependencies

extended contexts

Declarations

carrier sets
constants

Occurrences

DECLARATION of carrier sets [Root]
DECLARATION of constants [Root]
REFERENCE of elements in axioms [Axiom/Predicate/b..e]
REFERENCE of elements in theorems [Theorem/Predicate/b..e]

Example:

 Ctx
 Sets
   S
 Constants
   C
 Axioms
   axm1 : C ∈ S

We will end up with the following occurrences :

 S :
   DECLARATION in [Ctx.Root]
   REFERENCE in [axm1/Predicate/4..5]
 C :
   DECLARATION in [Ctx.Root]
   REFERENCE in [axm1/Predicate/0..1]

Exports

imported and declared carrier sets
imported and declared constants

Machine Indexer

Dependencies

refined machines
seen contexts

Declarations

variables
events
parameters

Occurrences

DECLARATION of (local) variables [Root]
DECLARATION of (local) events [Root]
DECLARATION of (local) parameters [Event]
REDECLARATION of abstract variables in the local variables that redeclare them [Variable/Identifier]
REDECLARATION of abstract events in the local events that refine them [Event/RefinesEvent/Target]
REDECLARATION of abstract parameters in the local parameters that redeclare them [Parameter/Identifier]
REFERENCE of abstract parameters or variables in witnesses [Witness/Label]
REFERENCE of elements in invariants [Invariant/Predicate/b..e]
REFERENCE of elements in theorems [Theorem/Predicate/b..e]
REFERENCE of elements in variants [Variant/Expression/b..e]
REFERENCE of elements in guards [Guard/Predicate/b..e]
REFERENCE of elements in witnesses [Witness/Predicate/b..e]
REFERENCE of non assigned elements in actions [Action/Assignment/b..e]
MODIFICATION of assigned elements in actions [Action/Assignment/b..e]

Example :

 M1
 VARIABLES
   var1
 INVARIANTS
   inv1 : var1 > 0
 EVENTS
   INITIALISATION
     THEN
       act1 : var1 := 1

After indexing M1, we will have the following occurrences:

 M1.var1 :
   DECLARATION in [M1.Root]
   REFERENCE in [M1.inv1/Predicate/0..4]
   MODIFICATION in [M1.act1/Assignment/0..4]
 M1.INITIALISATION :
   DECLARATION in [M1.Root]

Then, if we add another machine

 M2
 REFINES
   M1
 VARIABLES
   var1
 EVENTS
   INITIALISATION
     THEN
       act1 : var1 := 1

we will add the following occurrences :

 M1.var1 :
   REDECLARATION in [M2.var1/Identifier]
 M2.var1 :
   DECLARATION in [M2.Root]
   MODIFICATION in [M2.act1/Assignment/0..4]
 M2.INITIALISATION :
   DECLARATION in [M2.Root]

Exports

imported carrier sets
imported constants
local variables
local events
local parameters

Propagation

Propagators are defined for :

events (EventPropagator) to propagate through refines
parameters (IdentifierPropagator) to propagate through redeclaration
variables (IdentifierPropagator as well) to propagate through redeclaration

In the above example with machines M1 and M2, after both files have been indexed, we can query occurrences of M1.var1.

With no propagator, the result would be :

 M1.var1 :
   DECLARATION in [M1.Root]
   REFERENCE in [M1.inv1/Predicate/0..4]
   MODIFICATION in [M1.act1/Assignment/0..4]
   REDECLARATION in [M2.var1/Identifier]

Using the IdentifierPropagator, the result becomes :

 M1.var1 (propagated) :
   DECLARATION in [M1.Root]
   REFERENCE in [M1.inv1/Predicate/0..4]
   MODIFICATION in [M1.act1/Assignment/0..4]
   REDECLARATION in [M2.var1/Identifier]
   DECLARATION in [M2.Root]
   MODIFICATION in [M2.act1/Assignment/0..4]

@@ Line 1: / Line 1: @@
-{{TOCright}}
+==Purpose==
-This page is for listing available example Event-B/Rodin projects.
+Event-B indexers populate the index repository. Currently, indexers are implemented for the following files :
+* machine (.bum)
+* context (.buc)
-== Year 2010 ==
-===[http://deploy-eprints.ecs.soton.ac.uk/227/ Modularisation Training]===
+==Event-B Occurrence Kinds==
-By Alexei Iliasov.
-This is teaching material for those wishing to learn about the Modularisation plugin. It includes a development and detailed explanatory slides.
+So far, the following occurrence kinds have been defined :
+* DECLARATION : when a variable, a carrier set, ..., is declared
+* REFERENCE : when a variable, a carrier set, ..., is referenced (but not modified)
+* MODIFICATION : when a variable is modified (e.g., occurs in the left-hand side of an event action)
+* REDECLARATION : when a variable, parameter or event is redeclared (refined).
+Please notice the distinction between the index repository notion of declaration ({{class|IDeclaration}}) and the Event-B occurrence kind DECLARATION.
+==What Is Indexed==
-== Year 2009 ==
+Currently, indexed elements are :
+* carrier sets
+* constants
+* variables
+* events
+* parameters
-===[http://deploy-eprints.ecs.soton.ac.uk/150/ Code Generation - Shared Buffer Example]===
+Formulas which cannot be parsed are ignored.
-By Andrew Edmunds and Michael Butler
-The document describes an example Event-B development of a shared buffer and reading/writing processes. An implementation is then specified using the OCB notation; and a description of the implementation refinement and Java source is shown. An archive file contains the abstract Event-B development, however the implementation refinement proof is ongoing.
+In the descriptions below, the following notation will be used to specify locations :
+* [element] : internal location
+* [element/attribute] : attribute location
+* [element/attribute/begin..end] : attribute substring location
-=== [http://deploy-eprints.ecs.soton.ac.uk/138/ Well-ordering theorem]===
+===Context Indexer===
-By Jean-Raymond Abrial.
-The slides outline the use of Rodin in the proof of Well-ordering theorem.  The archive contains the
+====Dependencies====
-Rodin development.
+* extended contexts
+====Declarations====
+* carrier sets
+* constants
-=== [Development of a flash-based filestore]===
+====Occurrences====
-By Kriangsak Damchom and Michael Butler.
-The paper outlines the use of Event-B in the development of a flash-based filestore.  The archive contains the
+* DECLARATION of carrier sets [Root]
-Event-B development.
+* DECLARATION of constants [Root]
+* REFERENCE of elements in axioms [Axiom/Predicate/b..e]
+* REFERENCE of elements in theorems [Theorem/Predicate/b..e]
-=== [http://deploy-eprints.ecs.soton.ac.uk/107/ Real-time controller for a water tank]===
+Example:
-By Michael Butler.
-The draft paper outlines an approach to treating continuous behaviour in Event-B by a discrete approximation.
+  Ctx
-An example of a water tank system is used to illustrate the proposed approach.  The archive contains the
+  Sets
-Event-B development for the water tank system.
+    S
+  Constants
+    C
+  Axioms
+    axm1 : C ∈ S
-=== [http://deploy-eprints.ecs.soton.ac.uk/95/ UML-B Development of an ATM]===
+We will end up with the following occurrences :
-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
+  S :
-with an Automated Teller Machine (ATM) example.  The ATM development is contained in a Rodin
+    DECLARATION in [Ctx.Root]
-archive.  It consists of an abstract model focusing on bank account updates.  The ATM, pin cards and
+    REFERENCE in [axm1/Predicate/4..5]
-messaging between ATMs and a bank server are introduced in successive refinements.
+  C :
+    DECLARATION in [Ctx.Root]
+    REFERENCE in [axm1/Predicate/0..1]
-=== [http://deploy-eprints.ecs.soton.ac.uk/84/ MIDAS: A Formally Constructed Virtual Machine]===
-By [[User:Steve|Steve]].
-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.
+====Exports====
+* imported and declared carrier sets
+* imported and declared constants
-The archive supplied at [http://deploy-eprints.ecs.soton.ac.uk/84/ 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.
+===Machine Indexer===
-MIDAS is described in detail in [http://deploy-eprints.ecs.soton.ac.uk/163/ Formal Construction of Instruction Set Architectures (PhD Thesis)].
+====Dependencies====
+* refined machines
+* seen contexts
-=== [http://deploy-eprints.ecs.soton.ac.uk/82/ Development of a Network Topology Discovery Algorithm]===
+====Declarations====
-By ''Hoang, Thai Son and Basin, David and Kuruma, Hironobu and Abrial, Jean-Raymond''.
+* variables
+* events
+* parameters
-This paper and this Rodin development is another version of the [[#Link State Routing Development|Link State Routing Development]] presented in 2008.
+====Occurrences====
+* DECLARATION of (local) variables [Root]
+* DECLARATION of (local) events [Root]
+* DECLARATION of (local) parameters [Event]
+* REDECLARATION of abstract variables in the local variables that redeclare them [Variable/Identifier]
+* REDECLARATION of abstract events in the local events that refine them [Event/RefinesEvent/Target]
+* REDECLARATION of abstract parameters in the local parameters that redeclare them [Parameter/Identifier]
+* REFERENCE of abstract parameters or variables in witnesses [Witness/Label]
+* REFERENCE of elements in invariants [Invariant/Predicate/b..e]
+* REFERENCE of elements in theorems [Theorem/Predicate/b..e]
+* REFERENCE of elements in variants [Variant/Expression/b..e]
+* REFERENCE of elements in guards [Guard/Predicate/b..e]
+* REFERENCE of elements in witnesses [Witness/Predicate/b..e]
+* REFERENCE of non assigned elements in actions [Action/Assignment/b..e]
+* MODIFICATION of assigned elements in actions [Action/Assignment/b..e]
-== Year 2008 ==
+Example :
-=== [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.
+  M1
+  VARIABLES
+    var1
+  INVARIANTS
+    inv1 : var1 > 0
+  EVENTS
+    INITIALISATION
+      THEN
+        act1 : var1 := 1
-=== [http://deploy-eprints.ecs.soton.ac.uk/22/ Modelling and proof of a Tree-structured File System] ===
+After indexing M1, we will have the following occurrences:
-By ''Damchoom, Kriangsak and Butler, Michael and Abrial, Jean-Raymond''.
-We present a verified model of a tree-structured ﬁle system which was carried out using Event-B and the Rodin platform. The model is focused on basic functionalities aﬀecting 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 ﬁle system, we begin with an abstract model of a ﬁle system and subsequently reﬁne it by adding more details through reﬁnement 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.
+  M1.var1 :
+    DECLARATION in [M1.Root]
+    REFERENCE in [M1.inv1/Predicate/0..4]
+    MODIFICATION in [M1.act1/Assignment/0..4]
+  M1.INITIALISATION :
+    DECLARATION in [M1.Root]
-=== [http://deploy-eprints.ecs.soton.ac.uk/56/ Deliverable D8 D10.1 "Teaching Materials"] ===
+Then, if we add another machine
-By ''Abrial, Jean-Raymond and Hoang, Thai Son and Schmalz, Matthias''.
-==Year 2007==
+  M2
-=== [http://deploy-eprints.ecs.soton.ac.uk/9/ Redevelopment of an Industrial Case Study Using Event-B and Rodin]===
+  REFINES
-From ''Rezazadeh, Abdolbaghi and Butler, Michael and Evans, Neil''.
+    M1
+  VARIABLES
+    var1
+  EVENTS
+    INITIALISATION
+      THEN
+        act1 : var1 := 1
-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.
+we will add the following occurrences :
-[[Category:Examples]]
+  M1.var1 :
+    REDECLARATION in [M2.var1/Identifier]
+  M2.var1 :
+    DECLARATION in [M2.Root]
+    MODIFICATION in [M2.act1/Assignment/0..4]
+  M2.INITIALISATION :
+    DECLARATION in [M2.Root]
+====Exports====
+* imported carrier sets
+* imported constants
+* local variables
+* local events
+* local parameters
+==Propagation==
+Propagators are defined for :
+* events ({{class|EventPropagator}}) to propagate through refines
+* parameters ({{class|IdentifierPropagator}}) to propagate through redeclaration
+* variables ({{class|IdentifierPropagator}} as well) to propagate through redeclaration
+In the above example with machines M1 and M2, after both files have been indexed, we can query occurrences of M1.var1.
+With no propagator, the result would be :
+  M1.var1 :
+    DECLARATION in [M1.Root]
+    REFERENCE in [M1.inv1/Predicate/0..4]
+    MODIFICATION in [M1.act1/Assignment/0..4]
+    REDECLARATION in [M2.var1/Identifier]
+Using the {{class|IdentifierPropagator}}, the result becomes :
+  M1.var1 (propagated) :
+    DECLARATION in [M1.Root]
+    REFERENCE in [M1.inv1/Predicate/0..4]
+    MODIFICATION in [M1.act1/Assignment/0..4]
+    REDECLARATION in [M2.var1/Identifier]
+    DECLARATION in [M2.Root]
+    MODIFICATION in [M2.act1/Assignment/0..4]
+[[Category:Developer documentation]]

Difference between pages "Event-B Examples" and "Event-B Indexers"

Revision as of 09:35, 10 March 2009

Contents

Purpose

Event-B Occurrence Kinds

What Is Indexed

Context Indexer

Dependencies

Declarations

Occurrences

Exports

Machine Indexer

Dependencies

Declarations

Occurrences

Exports

Propagation

Navigation menu

Page actions

Page actions

Personal tools

Navigation

contribute

Search

Tools