Difference between pages "Strengthening the AST Library for Rodin 3.0" and "Theory Plug-in"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Vinmont
 
(Add to Theory Plug-in category)
 
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.
+
Return to [[Rodin Plug-ins]]
  
−
== Type Environment ==
+
See also [[Theory Release History]]
  
−
Type environments have changed in Rodin 3.0 in order to reinforce their good
+
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.
−
use and their robustness.  
 
  
−
First of all, we have added a new mechanism to add given sets implicitly introduced by types when new elements are added.
+
===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.
  
−
Then, we have added a new interface to represent inferred type environments.
+
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.
−
These environments are the ones that are returned in the result of the
 
−
typecheck methods of Formula and Expression.
 
  
−
Finally we have added mechanism to separate mutable and immutable type
+
The latest Theory plug-in is released for Rodin v2.8.
−
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 ==
+
===Overview===
−
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.
+
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".
  
−
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.
+
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.
  
−
The modification of the type checking step introduces the following modifications:
+
=== Installation & Update ===
−
* 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.
 
−
* 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 ==
+
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.
−
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.
 
−
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]]
+
===User Manual===
−
[[Category:Developer documentation]]
+
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:
 +
 
 +
[[image:SeqTheory.png|center|thumb|1500px|'''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:
 +
[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.
 +
 
 +
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:
 +
* [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]
 +
 
 +
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]
 +
 
 +
The following two papers describe rewriting and well-definedness issues that has to be accounted for:
 +
 
 +
* [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.]
 +
 
 +
 
 +
[[Category:Plugin]]
 +
[[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:

Retrieved from ‘https://wiki.event-b.org/index.php?title=Strengthening_the_AST_Library_for_Rodin_3.0&oldid=14456’