Vienna Development Method
Encyclopedia
The Vienna Development Method (VDM) is one of the longest-established Formal Methods
for the development of computer-based systems. Originating in work done at IBM's Vienna Laboratory in the 1970s, it has grown to include a group of techniques and tools based on a formal specification language - the VDM Specification Language (VDM-SL). It has an extended form, VDM++, which supports the modeling of object-oriented and concurrent systems. Support for VDM includes commercial and academic tools for analyzing models, including support for testing and proving properties of models and generating program code from validated VDM models. There is a history of industrial usage of VDM and its tools and a growing body of research in the formalism has led to notable contributions to the engineering of critical systems, compilers, concurrent systems and in logic
for computer science
.
Laboratory in Vienna
where the first version of the language was called the Vienna Definition Language (VDL). The VDL was essentially used for giving operational semantics
descriptions in contrast to the VDM - Meta-IV which provided denotational semantics
So Meta-IV, was "used to define major portions of" the PL/I
programming language. Other programming languages described, or partially described, using Meta-IV and VDM-SL include the BASIC programming language, FORTRAN
, the APL programming language
, ALGOL
60, the Ada programming language and the Pascal programming language. Meta-IV evolved into several variants, generally described as the Danish, English and Irish Schools.
The "English School" derived from work by Cliff Jones on the aspects of VDM not specifically related to language definition and compiler design (Jones 1980, 1990). It stresses modelling persistent state through the use of data types constructed from a rich collection of base types. Functionality is typically described through operations which may have side-effects on the state and which are mostly specified implicitly using a precondition and postcondition. The "Danish School" (Bjørner
et al. 1982) has tended to stress a constructive approach with explicit operational specification used to a greater extent. Work in the Danish school led to the first European validated Ada compiler.
An ISO
Standard for the language was released in 1996 (ISO, 1996).
.
A VDM-SL model is a system description given in terms of the functionality performed on data. It consists of a series of definitions of data types and functions or operations performed upon them.
Data types are defined to represent the main data of the modelled system. Each type definition introduces a new type name and gives a representation in terms of the basic types or in terms of types already introduced. For example, a type modelling user identifiers for a log-in management system might be defined as follows:
types
UserId = nat
For manipulating values belonging to data types, operators are defined on the values. Thus, natural number addition, subtraction etc. are provided, as are Boolean operators such as equality and inequality. The language does not fix a maximum or minimum representable number or a precision for real numbers. Such constraints are defined where they are required in each model by means of data type invariants—Boolean expressions denoting conditions that must be respected by all elements of the defined type. For example a requirement that user identifiers must be no greater than 9999 would be expressed as follows (where
UserId = nat
inv uid uid <= 9999
Since invariants can be arbitrarily complex logical expressions, and membership of a defined type is limited to only those values satisfying the invariant, type correctness in VDM-SL is not automatically decidable in all situations.
The other basic types include char for characters. In some cases, the representation of a type is not relevant to the model’s purpose and would only add complexity. In such cases, the members of the type may be represented as structureless tokens. Values of token types can only be compared for equality – no other operators are defined on them. Where specific named values are required, these are introduced as quote types. Each quote type consists of one named value of the same name as the type itself. Values of quote types (known as quote literals) may only be compared for equality.
For example, in modelling a traffic signal controller, it may be convenient to define values to represent the colours of the traffic signal as quote types:
, , ,
The most basic type constructor forms the union of two predefined types. The type
SignalColour = | | |
Enumerated type
s in VDM-SL are defined as shown above as unions on quote types.
Cartesian product types may also be defined in VDM-SL. The type
T :: f1:A1
f2:A2
...
fn:An
is the Cartesian product with fields labelled
Date :: day:nat1
month:nat1
year:nat
inv mk_Date(d,m,y) day <=31 and month<=12
models a simple date type. The value
mk_Date(1,4,2001).month = 4
The set type constructor (written
UGroup = set of UserId
defines a type
The finite sequence type constructor (written
String = seq of char
Defines a type
The order and repetition of items in a sequence is significant, so
A finite mapping is a correspondence between two sets, the domain and range, with the domain indexing elements of the range. It is therefore similar to a finite function. The mapping type constructor in VDM-SL (written
Birthdays = map String to Date
Defines a type
SQRT(x:nat)r:real
post r*r = x
Here the postcondition does not define a method for calculating the result
A more constrained function specification is arrived at by strengthening the postcondition. For example the following definition constrains the function to return the positive root.
SQRT(x:nat)r:real
post r*r = x and r>=0
All function specifications may be restricted by preconditions which are logical predicates over the input variables only and which describe constraints that are assumed to be satisfied when the function is executed. For example, a square root calculating function that works only on positive real numbers might be specified as follows:
SQRTP(x:real)r:real
pre x >=0
post r*r = x and r>=0
The precondition and postcondition together form a contract that to be satisfied by any program claiming to implement the function. The precondition records the assumptions under which the function guarantees to return a result satisfying the postcondition. If a function is called on inputs that do not satisfy its precondition, the outcome is undefined (indeed, termination is not even guaranteed).
VDM-SL also supports the definition of executable functions in the manner of a functional programming language. In an explicit function definition, the result is defined by means of an expression over the inputs. For example, a function that produces a list of the squares of a list of numbers might be defined as follows:
SqList: seq of nat -> seq of nat
SqList(s) if s = [] then [] else [(hd s)**2] ^ SqList(tl s)
This recursive definition consists of a function signature giving the types of the input and result and a function body. An implicit definition of the same function might take the following form:
SqListImp(s:seq of nat)r:seq of nat
post len r = len s and
forall i in set inds s & r(i) = s(i)**2
The explicit definition is in a simple sense an implementation of the implicitly specified function. The correctness of an explicit function definition with respect to an implicit specification may be defined as follows.
Given an implicit specification:
f(p:T_p)r:T_r
pre pre-f(p)
post post-f(p, r)
and an explicit function:
f:T_p -> T_r
we say it satisfies the specification iff
:
forall p in set T_p & pre-f(p) => f(p):T_r and post-f(p, f(p))
So, "
For example, if we have a state consisting of a single variable
state Register of
someStateRegister : nat
end
In VDM++ this would instead be defined as:
instance variables
someStateRegister : nat
An operation to load a value into this variable might be specified as:
LOAD(i:nat)
ext wr someStateRegister:nat
post someStateRegister = i
The externals clause (
Sometimes it is important to refer to the value of a state before it was modified; for example, an operation to add a value to the variable may be specified as:
ADD(i:nat)
ext wr someStateRegister : nat
post someStateRegister = someStateRegister~ + i
Where the
The function returns the element from a set of positive integers:
max(s:set of nat)r:nat
pre card s > 0
post r in set s and
forall r' in set s & r' <= r
The postcondition characterizes the result rather than defining an algorithm for obtaining it. The precondition is needed because no function could return an r in set s when the set is empty.
pre true
post r = i*j
Applying the proof obligation
multp(i,j)
if i=0
then 0
else if is-even(i)
then 2*multp(i/2,j)
else j+multp(i-1,j)
Then the proof obligation becomes:
forall i, j : nat & multp(i,j):nat and multp(i, j) = i*j
This can be shown correct by:
types
Qelt = token;
Queue = seq of Qelt;
state TheQueue of
q : Queue
end
operations
ENQUEUE(e:Qelt)
ext wr q:Queue
post q = q~ ^ [e];
DEQUEUEe:Qelt
ext wr q:Queue
pre q <> []
post q~ = [e]^q;
IS-EMPTYr:bool
ext rd q:Queue
post r <=> (len q = 0)
AccNum = token;
CustNum = token;
Balance = int;
Overdraft = nat;
AccData :: owner : CustNum
balance : Balance
state Bank of
accountMap : map AccNum to AccData
overdraftMap : map CustNum to Overdraft
inv mk_Bank(accountMap,overdraftMap) for all a in set rng accountMap & a.owner in set dom overdraftMap and
a.balance >= -overdraftMap(a.owner)
With operations:
NEWC allocates a new customer number:
operations
NEWC(od : Overdraft)r : CustNum
ext wr overdraftMap : map CustNum to Overdraft
post r not in set dom ~overdraftMap and overdraftMap = ~overdraftMap ++ { r |-> od};
NEWAC allocates a new account number and sets the balance to zero:
NEWAC(cu : CustNum)r : AccNum
ext wr accountMap : map AccNum to AccData
rd overdraftMap map CustNum to Overdraft
pre cu in set dom overdraftMap
post r not in set dom accountMap~ and accountMap = accountMap~ ++ {r|-> mk_AccData(cu,0)}
ACINF returns all the balances of all the accounts of a customer, as a map of account number to balance:
ACINF(cu : CustNum)r : map AccNum to Balance
ext rd accountMap : map AccNum to AccData
post r = {an |-> accountMap(an).balance | an in set dom accountMap & accountMap(an).owner = cu}
Tool Support
A number of different tools support VDM:
Industrial experience
VDM has been applied widely in a variety of application domains. The most well-known of these applications are:
Refinement
Use of VDM starts with a very abstract
model and develops this into an implementation. Each step involves Data Reification, then Operation Decomposition.
Data reification develops the abstract data type
s into more concrete data structure
s, while operation decomposition develops the (abstract) implicit specifications of operations and functions into algorithm
s that can be directly implemented in a computer language of choice.
forall a:ABS_REP & exists r:NEW_REP & a = retr(r)
Since the data representation has changed, it is necessary to update the operations and functions so that they operate on
on the new representation. In order to prove that the new operations and functions model those found in the original specification, it is necessary to discharge two proof obligations:
forall r: NEW_REP & pre-OPA(retr(r)) => pre-OPR(r)
forall ~r,r:NEW_REP & pre-OPA(retr(~r)) and post-OPR(~r,r) => post-OPA(retr(~r,), retr(r))
Operations required:
Formally, this would be:
types
Person = token;
Workers = set of Person;
state AWCCS of
pres: Workers
end
operations
INIT
ext wr pres: Workers
post pres = {};
ENTER(p : Person)
ext wr pres : Workers
pre p not in set pres
post pres = pres~ union {p};
EXIT(p : Person)
ext wr pres : Workers
pre p in set pres
post pres = pres~\{p};
ISPRESENT(p : Person) r : bool
ext rd pres : Workers
post r <=> p in set pres~
As most programming languages have a concept comparable to a set (often in the form of an array), the first step from the specification is to represent the data in terms of a sequence. These sequences must not allow repetition, as we do not want the same worker to appear twice, so we must add an invariant
to the new data type. In this case, ordering is not important, so
The Vienna Development Method is valuable for model-based systems. It is not appropriate if the system is time-based. For such cases, the calculus of communicating systems
(CCS) is more useful.
See also
Further reading
External links
Formal methods
In computer science and software engineering, formal methods are a particular kind of mathematically-based techniques for the specification, development and verification of software and hardware systems...
for the development of computer-based systems. Originating in work done at IBM's Vienna Laboratory in the 1970s, it has grown to include a group of techniques and tools based on a formal specification language - the VDM Specification Language (VDM-SL). It has an extended form, VDM++, which supports the modeling of object-oriented and concurrent systems. Support for VDM includes commercial and academic tools for analyzing models, including support for testing and proving properties of models and generating program code from validated VDM models. There is a history of industrial usage of VDM and its tools and a growing body of research in the formalism has led to notable contributions to the engineering of critical systems, compilers, concurrent systems and in logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
for computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
.
Philosophy
Computing systems may be modeled in VDM-SL at a higher level of abstraction than is achievable using programming languages, allowing the analysis of designs and identification of key features, including defects, at an early stage of system development. Models that have been validated can be transformed into detailed system designs through a refinement process. The language has a formal semantics, enabling proof of the properties of models to a high level of assurance. It also has an executable subset, so that models may be analyzed by testing and can be executed through graphical user interfaces, so that models can be evaluated by experts who are not necessarily familiar with the modeling language itself.History
The origins of VDM-SL lie in the IBMIBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
Laboratory in Vienna
Vienna
Vienna is the capital and largest city of the Republic of Austria and one of the nine states of Austria. Vienna is Austria's primary city, with a population of about 1.723 million , and is by far the largest city in Austria, as well as its cultural, economic, and political centre...
where the first version of the language was called the Vienna Definition Language (VDL). The VDL was essentially used for giving operational semantics
Operational semantics
In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...
descriptions in contrast to the VDM - Meta-IV which provided denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
«Towards the end of 1972 the Vienna group again turned their attention to the problem of systematically developing a compiler from a language definition. The overall approach adopted has been termed the "Vienna Development Method"... The meta-language actually adopted ("Meta-IV") is used to define major portions of PL/1 (as given in ECMA 74 - interestingly a "formal standards document written as an abstract interpreter") in BEKIČ 74.»
So Meta-IV, was "used to define major portions of" the PL/I
PL/I
PL/I is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications...
programming language. Other programming languages described, or partially described, using Meta-IV and VDM-SL include the BASIC programming language, FORTRAN
Fortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
, the APL programming language
APL programming language
APL is an interactive array-oriented language and integrated development environment, which is available from a number of commercial and noncommercial vendors and for most computer platforms. It is based on a mathematical notation developed by Kenneth E...
, ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
60, the Ada programming language and the Pascal programming language. Meta-IV evolved into several variants, generally described as the Danish, English and Irish Schools.
The "English School" derived from work by Cliff Jones on the aspects of VDM not specifically related to language definition and compiler design (Jones 1980, 1990). It stresses modelling persistent state through the use of data types constructed from a rich collection of base types. Functionality is typically described through operations which may have side-effects on the state and which are mostly specified implicitly using a precondition and postcondition. The "Danish School" (Bjørner
Dines Bjørner
Professor Dines Bjørner is a Danish computer scientist.He specializes in research into domain engineering, requirements engineering and formal methods. He worked with Cliff Jones and others on the Vienna Development Method at IBM in Vienna...
et al. 1982) has tended to stress a constructive approach with explicit operational specification used to a greater extent. Work in the Danish school led to the first European validated Ada compiler.
An ISO
International Organization for Standardization
The International Organization for Standardization , widely known as ISO, is an international standard-setting body composed of representatives from various national standards organizations. Founded on February 23, 1947, the organization promulgates worldwide proprietary, industrial and commercial...
Standard for the language was released in 1996 (ISO, 1996).
VDM Features
The VDM-SL and VDM++ syntax and semantics are described at length in the VDMTools language manuals and in the available texts. The ISO Standard contains a formal definition of the language’s semantics. In the remainder of this article, the ISO-defined interchange (ASCII) syntax is used. Some texts prefer a more concise mathematical syntaxMathematical notation
Mathematical notation is a system of symbolic representations of mathematical objects and ideas. Mathematical notations are used in mathematics, the physical sciences, engineering, and economics...
.
A VDM-SL model is a system description given in terms of the functionality performed on data. It consists of a series of definitions of data types and functions or operations performed upon them.
Basic Types: numeric, character, token and quote types
VDM-SL includes basic types modelling numbers and characters as follows:| Basic Types | ||
|---|---|---|
bool |
Boolean datatype Boolean datatype In computer science, the Boolean or logical data type is a data type, having two values , intended to represent the truth values of logic and Boolean algebra... |
false, true |
nat |
natural number Natural number In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively... s (including zero) |
0, 1, 2, 3, ... |
nat1 |
natural numbers (excluding zero) | 1, 2, 3, 4, ... |
int |
integer Integer The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively... s |
..., -3, -2, -1, 0, 1, 2, 3, ... |
rat |
rational number Rational number In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number... s |
a/b, where a and b are integers, b is not 0 |
real |
real number Real number In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π... s |
... |
char |
characters | A, B, C, ... |
token |
structureless tokens | ... |
|
the quote type containing the value |
... |
Data types are defined to represent the main data of the modelled system. Each type definition introduces a new type name and gives a representation in terms of the basic types or in terms of types already introduced. For example, a type modelling user identifiers for a log-in management system might be defined as follows:
types
UserId = nat
For manipulating values belonging to data types, operators are defined on the values. Thus, natural number addition, subtraction etc. are provided, as are Boolean operators such as equality and inequality. The language does not fix a maximum or minimum representable number or a precision for real numbers. Such constraints are defined where they are required in each model by means of data type invariants—Boolean expressions denoting conditions that must be respected by all elements of the defined type. For example a requirement that user identifiers must be no greater than 9999 would be expressed as follows (where
<= is the “less than or equal to” Boolean operator on natural numbers):UserId = nat
inv uid uid <= 9999
Since invariants can be arbitrarily complex logical expressions, and membership of a defined type is limited to only those values satisfying the invariant, type correctness in VDM-SL is not automatically decidable in all situations.
The other basic types include char for characters. In some cases, the representation of a type is not relevant to the model’s purpose and would only add complexity. In such cases, the members of the type may be represented as structureless tokens. Values of token types can only be compared for equality – no other operators are defined on them. Where specific named values are required, these are introduced as quote types. Each quote type consists of one named value of the same name as the type itself. Values of quote types (known as quote literals) may only be compared for equality.
For example, in modelling a traffic signal controller, it may be convenient to define values to represent the colours of the traffic signal as quote types:
Type Constructors: Union, Product and Composite Types
The basic types alone are of limited value. New, more structured data types are built using type constructors.| Basic Type Constructors | |
|---|---|
T1  T2  ...  Tn |
Union of types T1,...,Tn |
T1*T2*...*Tn |
Cartesian product of types T1,...,Tn |
T :: f1:T1 ... fn:Tn |
Composite (Record) type |
The most basic type constructor forms the union of two predefined types. The type
(A|B) contains all elements of the type A and all of the type B. In the traffic signal controller example, the type modelling the colour of a traffic signal could be defined as follows:SignalColour =
Enumerated type
Enumerated type
In computer programming, an enumerated type is a data type consisting of a set of named values called elements, members or enumerators of the type. The enumerator names are usually identifiers that behave as constants in the language...
s in VDM-SL are defined as shown above as unions on quote types.
Cartesian product types may also be defined in VDM-SL. The type
(A1*…*An) is the type composed of all tuples of values, the first element of which is from the type A1 and the second from the type A2 and so on. The composite or record type is a Cartesian product with labels for the fields. The typeT :: f1:A1
f2:A2
...
fn:An
is the Cartesian product with fields labelled
f1,…,fn. An element of type T can be composed from its constituent parts by a constructor, written mk_T. Conversely, given an element of type T, the field names can be used to select the named component. For example, the typeDate :: day:nat1
month:nat1
year:nat
inv mk_Date(d,m,y) day <=31 and month<=12
models a simple date type. The value
mk_Date(1,4,2001) corresponds to 1 April 2001. Given a date d, the expression d.month is a natural number representing the month. Restrictions on days per month and leap years could be incorporated into the invariant if desired. Combining these:mk_Date(1,4,2001).month = 4
Collections: Sets, Mappings and Sequences
Collection types model groups of values. Sets are finite unordered collections in which duplication between values is suppressed. Sequences are finite ordered collections (lists) in which duplication may occur and mappings represent finite correspondences between two sets of values.The set type constructor (written
set of T where T is a predefined type) constructs the type composed of all finite sets of values drawn from the type T. For example, the type definitionUGroup = set of UserId
defines a type
UGroup composed of all finite sets of UserId values. Various operators are defined on sets for constructing their union, intersections, determining proper and non-strict subset relationships etc.| Main Operators on Sets (s, s1, s2 are sets) | |
|---|---|
{a, b, c} |
Set enumeration: the set of elements a, b and c |
x  x:T & P(x) |
Set comprehension: the set of x from type T such that P(x) |
{i, ..., j} |
The set of integers in the range i to j |
e in set s |
e is an element of set s |
e not in set s |
e is not an element of set s |
s1 union s2 |
Union of sets s1 and s2 |
s1 inter s2 |
Intersection of sets s1 and s2 |
s1 \ s2 |
Set difference of sets s1 and s2 |
dunion s |
Distributed union of set of sets s |
s1 psubset s2 |
s1 is a (proper) subset of s2 |
s1 subset s2 |
s1 is a (weak) subset of s2 |
card s |
The cardinality of set s |
The finite sequence type constructor (written
seq of T where T is a predefined type) constructs the type composed of all finite lists of values drawn from the type T. For example, the type definitionString = seq of char
Defines a type
String composed of all finite strings of characters. Various operators are defined on sequences for constructing concatenation, selection of elements and subsequences etc. Many of these operators are partial in the sense that they are not defined for certain applications. For example, selecting the 5th element of a sequence that contains only three elements is undefined.The order and repetition of items in a sequence is significant, so
[a, b] is not equal to [b, a], and [a] is not equal to [a, a].| Main Operators on Sequences (s, s1,s2 are sequences) | |
|---|---|
[a, b, c] |
Sequence enumeration: the sequence of elements a, b and c |
[f(x) x:T & P(x)] |
Sequence comprehension: sequence of expressions f(x) for each x of (numeric) type T such that P(x) holds (x values taken in numeric order) |
hd s |
The head (first element) of s |
tl s |
The tail (remaining sequence after head is removed) of s |
len s |
The length of s |
elems s |
The set of elements of s |
s(i) |
The ith element of s |
inds s |
the set of indices for the sequence s |
s1^s2 |
the sequence formed by concatenating sequences s1 and s2 |
A finite mapping is a correspondence between two sets, the domain and range, with the domain indexing elements of the range. It is therefore similar to a finite function. The mapping type constructor in VDM-SL (written
map T1 to T2) where T1 and T2 are predefined types) constructs the type composed of all finite mappings from sets of T1 values to sets of T2 values. For example, the type definitionBirthdays = map String to Date
Defines a type
Birthdays which maps character strings to Date. Again, operators are defined on mappings for indexing into the mapping, merging mappings, overwriting extracting sub-mappings.| Main Operators on Mappings | |
|---|---|
{a  -> r, b  -> s} |
Mapping enumeration: a maps to r, b maps to s |
{x  -> f(x)  x:T & P(x)} |
Mapping comprehension: x maps to f(x) for all x for type T such that P(x) |
dom m |
The domain of m |
rng m |
The range of m |
m(x) |
m applied to x |
m1 munion m2 |
Union of mappings m1 and m2 (m1, m2 must be consistent where they overlap) |
m1 ++ m2 |
m1 overwritten by m2 |
Structuring
The main difference between the VDM-SL and VDM++ notations are the way in which structuring is dealt with. In VDM-SL there is a conventional modular extension whereas VDM++ has a traditional object-oriented structuring mechanism with classes and inheritance.Structuring in VDM-SL
In the ISO standard for VDM-SL there is an informative annex that contains different structuring principles. These all follow traditional information hiding principles with modules and they can be explained as:- Module naming: Each module is syntactically started with the keyword
modulefollowed by the name of the module. At the end of a module the keywordendis written followed again by the name of the module. - Importing: It is possible to import definitions that has been exported from other modules. This is done in an imports section that is started off with the keyword
importsand followed by a sequence of imports from different modules. Each of these module imports are started with the keywordfromfollowed by the name of the module and a module signature. The module signature can either simply be the keywordallindicating the import of all definitions exported from that module, or it can be a sequence of import signatures. The import signatures are specific for types, values, functions and operations and each of these are started with the corresponding keyword. In addition these import signatures name the constructs that there is a desire to get access to. In addition optional type information can be present and finally it is possible to rename each of the constructs upon import. For types one needs also to use the keywordstructif one wish to get access to the internal structure of a particular type. - Exporting: The definitions from a module that one wish other modules to have access to are exported using the keyword
exportsfollowed by an exports module signature. The exports module signature can either simply consist of the keywordallor as a sequence of export signatures. Such export signatures are specific for types, values, functions and operations and each of these are started with the corresponding keyword. In case one wish to export the internal structure of a type the keywordstructmust be used. - More exotic features: In earlier versions of the VDM-SL tools there was also support for parameterized modules and instantiations of such modules. However, these features was taken out of VDMTools around 2000 because they was hardly ever used in industrial applications and there was a substantial number of tool challenges with these features.
Structuring in VDM++
In VDM++ structuring are done using classes and multiple inheritance. The key concepts are:- Class: Each class is syntactically started with the keyword
classfollowed by the name of the class. At the end of a class the keywordendis written followed again by the name of the class. - Inheritance: In case a class inherits constructs from other classes the class name in the class heading can be followed by the keywords
is subclass offollowed by a comma-separated list of names of superclasses. - Access modifiers: Information hiding in VDM++ is done in the same way as in most object oriented languages using access modifiers. In VDM++ definitions are per default private but in from of all definitions it is possible to use one of the access modifier keywords:
private,publicandprotected.
Functional Modelling
In VDM-SL, functions are defined over the data types defined in a model. Support for abstraction requires that it should be possible to characterize the result that a function should compute without having to say how it should be computed. The main mechanism for doing this is the implicit function definition in which, instead of a formula computing a result, a logical predicate over the input and result variables, termed a postcondition, gives the result's properties. For example, a functionSQRT for calculating a square root of a natural number might be defined as follows:SQRT(x:nat)r:real
post r*r = x
Here the postcondition does not define a method for calculating the result
r but states what properties can be assumed to hold of it. Note that this defines a function that returns a valid square root; there is no requirement that it should be the positive or negative root. The specification above would be satisfied, for example, by a function that returned the negative root of 4 but the positive root of all other valid inputs. Note that functions in VDM-SL are required to be deterministic so that a function satisfying the example specification above must always return the same result for the same input.A more constrained function specification is arrived at by strengthening the postcondition. For example the following definition constrains the function to return the positive root.
SQRT(x:nat)r:real
post r*r = x and r>=0
All function specifications may be restricted by preconditions which are logical predicates over the input variables only and which describe constraints that are assumed to be satisfied when the function is executed. For example, a square root calculating function that works only on positive real numbers might be specified as follows:
SQRTP(x:real)r:real
pre x >=0
post r*r = x and r>=0
The precondition and postcondition together form a contract that to be satisfied by any program claiming to implement the function. The precondition records the assumptions under which the function guarantees to return a result satisfying the postcondition. If a function is called on inputs that do not satisfy its precondition, the outcome is undefined (indeed, termination is not even guaranteed).
VDM-SL also supports the definition of executable functions in the manner of a functional programming language. In an explicit function definition, the result is defined by means of an expression over the inputs. For example, a function that produces a list of the squares of a list of numbers might be defined as follows:
SqList: seq of nat -> seq of nat
SqList(s) if s = [] then [] else [(hd s)**2] ^ SqList(tl s)
This recursive definition consists of a function signature giving the types of the input and result and a function body. An implicit definition of the same function might take the following form:
SqListImp(s:seq of nat)r:seq of nat
post len r = len s and
forall i in set inds s & r(i) = s(i)**2
The explicit definition is in a simple sense an implementation of the implicitly specified function. The correctness of an explicit function definition with respect to an implicit specification may be defined as follows.
Given an implicit specification:
f(p:T_p)r:T_r
pre pre-f(p)
post post-f(p, r)
and an explicit function:
f:T_p -> T_r
we say it satisfies the specification iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
:
forall p in set T_p & pre-f(p) => f(p):T_r and post-f(p, f(p))
So, "
f is a correct implementation" should be interpreted as "f satisfies the specification".State-based Modelling
In VDM-SL, functions do not have side-effects such as changing the state of a persistent global variable. This is a useful ability in many programming languages, so a similar concept exists; instead of functions, operations are used to change state variables (AKA globals).For example, if we have a state consisting of a single variable
someStateRegister : nat, we could define this in VDM-SL as:state Register of
someStateRegister : nat
end
In VDM++ this would instead be defined as:
instance variables
someStateRegister : nat
An operation to load a value into this variable might be specified as:
LOAD(i:nat)
ext wr someStateRegister:nat
post someStateRegister = i
The externals clause (
ext) specifies which parts of the state can be accessed by the operation; rd indicating read-only access and wr being read/write access.Sometimes it is important to refer to the value of a state before it was modified; for example, an operation to add a value to the variable may be specified as:
ADD(i:nat)
ext wr someStateRegister : nat
post someStateRegister = someStateRegister~ + i
Where the
~ symbol on the state variable in the postcondition indicates the value of the state variable before execution of the operation.The max function
This is an example of an implicit function definition.The function returns the element from a set of positive integers:
max(s:set of nat)r:nat
pre card s > 0
post r in set s and
forall r' in set s & r' <= r
The postcondition characterizes the result rather than defining an algorithm for obtaining it. The precondition is needed because no function could return an r in set s when the set is empty.
Natural number multiplication
multp(i,j:nat)r:natpre true
post r = i*j
Applying the proof obligation
forall p:T_p & pre-f(p) => f(p):T_r and post-f(p, f(p)) to an explicit definition of multp:multp(i,j)
if i=0
then 0
else if is-even(i)
then 2*multp(i/2,j)
else j+multp(i-1,j)
Then the proof obligation becomes:
forall i, j : nat & multp(i,j):nat and multp(i, j) = i*j
This can be shown correct by:
- Proving that the recursion ends (this in turn requires proving that the numbers become smaller at each step)
- Mathematical inductionMathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
Queue abstract data type
This is a classical example illustrating the use of implicit operation specification in a state-based model of a well-known data structure. The queue is modelled as a sequence composed of elements of a typeQelt. The representation is Qelt is immaterial and so is defined as a token type.types
Qelt = token;
Queue = seq of Qelt;
state TheQueue of
q : Queue
end
operations
ENQUEUE(e:Qelt)
ext wr q:Queue
post q = q~ ^ [e];
DEQUEUEe:Qelt
ext wr q:Queue
pre q <> []
post q~ = [e]^q;
IS-EMPTYr:bool
ext rd q:Queue
post r <=> (len q = 0)
Bank system example
As a very simple example of a VDM-SL model, consider a system for maintaining details of customer bank account. Customers are modelled by customer numbers (CustNum), accounts are modelled by account numbers (AccNum). The representations of customer numbers are held to be immaterial and so are modelled by a token type. Balances and overdrafts are modelled by numeric types.AccNum = token;
CustNum = token;
Balance = int;
Overdraft = nat;
AccData :: owner : CustNum
balance : Balance
state Bank of
accountMap : map AccNum to AccData
overdraftMap : map CustNum to Overdraft
inv mk_Bank(accountMap,overdraftMap) for all a in set rng accountMap & a.owner in set dom overdraftMap and
a.balance >= -overdraftMap(a.owner)
With operations:
NEWC allocates a new customer number:
operations
NEWC(od : Overdraft)r : CustNum
ext wr overdraftMap : map CustNum to Overdraft
post r not in set dom ~overdraftMap and overdraftMap = ~overdraftMap ++ { r |-> od};
NEWAC allocates a new account number and sets the balance to zero:
NEWAC(cu : CustNum)r : AccNum
ext wr accountMap : map AccNum to AccData
rd overdraftMap map CustNum to Overdraft
pre cu in set dom overdraftMap
post r not in set dom accountMap~ and accountMap = accountMap~ ++ {r|-> mk_AccData(cu,0)}
ACINF returns all the balances of all the accounts of a customer, as a map of account number to balance:
ACINF(cu : CustNum)r : map AccNum to Balance
ext rd accountMap : map AccNum to AccData
post r = {an |-> accountMap(an).balance | an in set dom accountMap & accountMap(an).owner = cu}
Tool Support
A number of different tools support VDM:
- VDMTools are the leading commercial tools for VDM and VDM++, owned, marketed, maintained and developed by CSK Systems, building on earlier versions developed by the Danish Company IFAD. The manuals) and a practical tutorial are available. All licenses are available, free of charge, for the full version of the tool. The full version includes automatic code generation for Java and C++, dynamic link library and CORBA support.
- Overture is a community-based open source initiative aimed at providing freely available tool support for VDM++ on top of the Eclipse platform. Its aim is to develop a framework for interoperable tools that will be useful for industrial application, research and education.
- SpecBox: from Adelard provides syntax checking, some simple semantic checking, and generation of a LaTeX file enabling specifications to be printed in mathematical notation. This tool is freely available but it is not being further maintained.
- LaTeXLaTeXLaTeX is a document markup language and document preparation system for the TeX typesetting program. Within the typesetting system, its name is styled as . The term LaTeX refers only to the language in which documents are written, not to the editor used to write those documents. In order to...
and LaTeX2e macros are available to support the presentation of VDM models in the ISO Standard Language's mathematical syntax. They have been developed and are maintained by the National Physical Laboratory in the UK. [ftp://ftp.npl.co.uk/pub/latex/macros/vdm-sl/README Documentation] and the [ftp://ftp.npl.co.uk/pub/latex/macros/vdm-sl/ macros] are available online.
Industrial experience
VDM has been applied widely in a variety of application domains. The most well-known of these applications are:
- AdaAda (programming language)Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
and CHILLCHILLIn computing, CHILL is a procedural programming language designed for use in telecommunication switches . The language is still used for legacy systems in some telecommunication companies and for signal box programming.The CHILL language is similar in size and complexity to the Ada language...
compilerCompilerA compiler is a computer program that transforms source code written in a programming language into another computer language...
s: The first European validated Ada compiler was developed by DDC-International using VDM. Likewise the semantics of CHILL and Modula-2Modula-2Modula-2 is a computer programming language designed and developed between 1977 and 1980 by Niklaus Wirth at ETH Zurich as a revision of Pascal to serve as the sole programming language for the operating system and application software for the personal workstation Lilith...
were described in their standards using VDM. - ConForm: An experiment at British Aerospace comparing the conventional development of a trusted gateway with a development using VDM.
- Dust-Expert: A project carried out by Adelard in the UK for a safety related application determining that the safety is appropriate in the layout of industrial plants.
- The development of VDMTools: Most components of the VDMTools tool suite are themselves developed using VDM. This development has been made at IFAD in DenmarkDenmarkDenmark is a Scandinavian country in Northern Europe. The countries of Denmark and Greenland, as well as the Faroe Islands, constitute the Kingdom of Denmark . It is the southernmost of the Nordic countries, southwest of Sweden and south of Norway, and bordered to the south by Germany. Denmark...
and CSK in JapanJapanJapan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...
. - TradeOne: Certain key components of the TradeOne back-office system developed by CSK systems for the Japanese stock exchange were developed using VDM. Comparative measurements exist for developer productivity and defect density of the VDM-developed components versus the conventionally developed code.
- FeliCa Networks have reported the development of an operating systemOperating systemAn operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
for an integrated circuitIntegrated circuitAn integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
for cellular telephone applications.
Refinement
Use of VDM starts with a very abstract
Abstraction (computer science)
In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
model and develops this into an implementation. Each step involves Data Reification, then Operation Decomposition.
Data reification develops the abstract data type
Abstract data type
In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
s into more concrete data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s, while operation decomposition develops the (abstract) implicit specifications of operations and functions into algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s that can be directly implemented in a computer language of choice.
| Specification | Implementation | |
|---|---|---|
| Abstract data type | ––– Data reification → | Data structure |
| Operations | ––– Operation decomposition → | Algorithms |
Data reification
Data reification (stepwise refinement) involves finding a more concrete representation of the abstract data types used in a specification. There may be several steps before an implementation is reached. Each reification step for an abstract data representationABS_REP involves proposing a new representation NEW_REP. In order to show that the new representation is accurate, a retrieve function is defined that relates NEW_REP to ABS_REP, i.e. retr : NEW_REP -> ABS_REP. The correctness of a data reification depends on proving adequacy, i.e.forall a:ABS_REP & exists r:NEW_REP & a = retr(r)
Since the data representation has changed, it is necessary to update the operations and functions so that they operate on
NEW_REP. The new operations and functions should be shown to preserve any data type invariantsInvariant (computer science)
In computer science, a predicate is called an invariant to a sequence of operations provided that: if the predicate is true before starting the sequence, then it is true at the end of the sequence.-Use:...
on the new representation. In order to prove that the new operations and functions model those found in the original specification, it is necessary to discharge two proof obligations:
- Domain rule:
forall r: NEW_REP & pre-OPA(retr(r)) => pre-OPR(r)
- Modelling rule:
forall ~r,r:NEW_REP & pre-OPA(retr(~r)) and post-OPR(~r,r) => post-OPA(retr(~r,), retr(r))
Example data reification
In a business security system, workers are given ID cards; these are fed into card readers on entry to and exit from the factory.Operations required:
-
INITinitialises the system, assumes that the factory is empty -
ENTER(p : Person)records that a worker is entering the factory; the workers' details are read from the ID card) -
EXIT(p : Person)records that a worker is exiting the factory -
IS-PRESENT(p : Person) r : boolchecks to see if a specified worker is in the factory or not
Formally, this would be:
types
Person = token;
Workers = set of Person;
state AWCCS of
pres: Workers
end
operations
INIT
ext wr pres: Workers
post pres = {};
ENTER(p : Person)
ext wr pres : Workers
pre p not in set pres
post pres = pres~ union {p};
EXIT(p : Person)
ext wr pres : Workers
pre p in set pres
post pres = pres~\{p};
ISPRESENT(p : Person) r : bool
ext rd pres : Workers
post r <=> p in set pres~
As most programming languages have a concept comparable to a set (often in the form of an array), the first step from the specification is to represent the data in terms of a sequence. These sequences must not allow repetition, as we do not want the same worker to appear twice, so we must add an invariant
Invariant (computer science)
In computer science, a predicate is called an invariant to a sequence of operations provided that: if the predicate is true before starting the sequence, then it is true at the end of the sequence.-Use:...
to the new data type. In this case, ordering is not important, so
[a,b] is the same as [b,a].The Vienna Development Method is valuable for model-based systems. It is not appropriate if the system is time-based. For such cases, the calculus of communicating systems
Calculus of Communicating Systems
The Calculus of Communicating Systems is a process calculus introduced by Robin Milner around 1980 and the title of a book describing the calculus. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing parallel...
(CCS) is more useful.
See also
- Formal methodsFormal methodsIn computer science and software engineering, formal methods are a particular kind of mathematically-based techniques for the specification, development and verification of software and hardware systems...
- Formal specificationFormal specificationIn computer science, a formal specification is a mathematical description of software or hardware that may be used to develop an implementation. It describes what the system should do, not how the system should do it...
- Pidgin code
- Predicate logicPredicate logicIn mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...
- Propositional calculusPropositional calculusIn mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
- Z specification language, the main alternative to VDM-SL (compare)
Further reading
Formal methods
In computer science and software engineering, formal methods are a particular kind of mathematically-based techniques for the specification, development and verification of software and hardware systems...
Formal specification
In computer science, a formal specification is a mathematical description of software or hardware that may be used to develop an implementation. It describes what the system should do, not how the system should do it...
Predicate logic
In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
- Fitzgerald, J.S.John Fitzgerald (computer scientist)John S. Fitzgerald is a British computer scientist and Chair of Formal Methods Europe. He is a Reader in the School of Computing Science at Newcastle University, UK, where he works as a member of the...
and Larsen, P.G., Modelling Systems: Practical Tools and Techniques in Software Engineering. Cambridge University PressCambridge University PressCambridge University Press is the publishing business of the University of Cambridge. Granted letters patent by Henry VIII in 1534, it is the world's oldest publishing house, and the second largest university press in the world...
, 1998 ISBN 0-521-62348-0 (Japanese Edition pub. Iwanami Shoten 2003 ISBN 4-00-005609-3). - Fitzgerald, J.S.John Fitzgerald (computer scientist)John S. Fitzgerald is a British computer scientist and Chair of Formal Methods Europe. He is a Reader in the School of Computing Science at Newcastle University, UK, where he works as a member of the...
, Larsen, P.G., Mukherjee, P., Plat, N. and Verhoef,M., Validated Designs for Object-oriented Systems. Springer Verlag 2005. ISBN 1-85233-881-4. Supporting web site http://www.vdmbook.com includes examples and free tool support. - Jones, C.B., Systematic Software Development using VDM, Prentice HallPrentice HallPrentice Hall is a major educational publisher. It is an imprint of Pearson Education, Inc., based in Upper Saddle River, New Jersey, USA. Prentice Hall publishes print and digital content for the 6-12 and higher-education market. Prentice Hall distributes its technical titles through the Safari...
1990. ISBN 0-13-880733-7. Also available on-line and free of charge: http://www.csr.ncl.ac.uk/vdm/ssdvdm.pdf.zip - Bjørner, D.Dines BjørnerProfessor Dines Bjørner is a Danish computer scientist.He specializes in research into domain engineering, requirements engineering and formal methods. He worked with Cliff Jones and others on the Vienna Development Method at IBM in Vienna...
and Jones, C.B., Formal Specification and Software Development Prentice HallPrentice HallPrentice Hall is a major educational publisher. It is an imprint of Pearson Education, Inc., based in Upper Saddle River, New Jersey, USA. Prentice Hall publishes print and digital content for the 6-12 and higher-education market. Prentice Hall distributes its technical titles through the Safari...
International, 1982. ISBN 0-13-880733-7 - J. Dawes, The VDM-SL Reference Guide, PitmanPitmanPitman may refer to:* Pitman, New Jersey* Pitman, Pennsylvania* Pitman, Saskatchewan* Pitman Shorthand, a system of shorthand* Pitman arm, a vehicle steering component* A connecting rod in an engine* Pitman , a videogame for the Game Boy...
1991. ISBN 0-273-03151-1 - International Organization for StandardizationInternational Organization for StandardizationThe International Organization for Standardization , widely known as ISO, is an international standard-setting body composed of representatives from various national standards organizations. Founded on February 23, 1947, the organization promulgates worldwide proprietary, industrial and commercial...
, Information technology — Programming languages, their environments and system software interfaces — Vienna Development Method — Specification Language — Part 1: Base language International Standard ISO/IEC 13817-1, December 1996. - Jones, C.B., Software Development: A Rigorous Approach, Prentice Hall International, 1980. ISBN 0-13-821884-6
- Jones, C.B. and Shaw, R.C. (eds.), Case Studies in Systematic Software Development, Prentice Hall International, 1990. ISBN 0-13-880733-7
- Bicarregui, J.C., Fitzgerald, J.S.John Fitzgerald (computer scientist)John S. Fitzgerald is a British computer scientist and Chair of Formal Methods Europe. He is a Reader in the School of Computing Science at Newcastle University, UK, where he works as a member of the...
, Lindsay, P.A., Moore, R. and Ritchie, B., Proof in VDM: a Practitioner's Guide. Springer Verlag Formal Approaches to Computing and Information Technology (FACIT), 1994. ISBN 3-540-19813-X .
External links