<nowiki>{a |-> r, b |-> s}</nowiki> || Mapping enumeration: a maps to r, b maps to s|-| <nowiki>{x |-> f(x) | x:T & P(x)}</nowiki> || 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
module followed by the name of the module. At the end of a module the keyword end is 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
imports and followed by a sequence of imports from different modules. Each of these module imports are started with the keyword from followed by the name of the module and a module signature. The module signature can either simply be the keyword all indicating 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 keyword struct if 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
exports followed by an exports module signature. The exports module signature can either simply consist of the keyword all or 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 keyword struct must 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 were taken out of VDMTools around 2000 because they were 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
class followed by the name of the class. At the end of a class the keyword end is 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 of followed 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 front of all definitions it is possible to use one of the access modifier keywords:
private, public and protected.
Modelling functionality
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 function SQRT for calculating a square root of a natural number might be defined as follows:SQRT(x:nat)r:realpost r*r = xHere 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:realpost r*r = x and r>=0All 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:realpre x >=0post r*r = x and r>=0The 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 natSqList(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 natpost len r = len s and forall i in set inds s & r(i) = s(i)**2The 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_rpre pre-f(p)post post-f(p, r)and an explicit function:f:T_p -> T_rwe 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, "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 (also known as 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 endIn VDM++ this would instead be defined as: instance variables someStateRegister : natAn operation to load a value into this variable might be specified as: LOAD(i:nat) ext wr someStateRegister:nat post someStateRegister = iThe 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~ + iWhere the ~ symbol on the state variable in the postcondition indicates the value of the state variable before execution of the operation.
Examples
The max function
This is an example of an implicit function definition. The function returns the largest 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' <= rThe 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:nat pre true post r = i*jApplying 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*jThis can be shown correct by:
- Proving that the recursion ends (this in turn requires proving that the numbers become smaller at each step)
- Mathematical induction
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 type Qelt. 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 ++ ;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~ ++ 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 =
Tool support
A number of different tools support VDM:
- VDMTools was 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 all VDM dialects (VDM-SL, VDM++ and VDM-RT) originally on top of the Eclipse platform but subsequently on top of the Visual Studio Code platform. Its aim is to develop a framework for interoperable tools that will be useful for industrial application, research and education.
- vdm-mode is a collection of Emacs packages for writing VDM specifications using VDM-SL, VDM++ and VDM-RT. It supports syntax highlighting and editing, on-the-fly syntax checking, template completion and interpreter support.
- 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.
- LaTeX 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. Documentation and the 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:
- Ada and CHILL compilers: The first European validated Ada compiler was developed by Dansk Datamatik Center using VDM.[8] Likewise the semantics of CHILL and Modula-2 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 Denmark and CSK in Japan.[9]
- 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 system for an integrated circuit for cellular telephone applications.
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 types into more concrete data structures, while operation decomposition develops the (abstract) implicit specifications of operations and functions into algorithms that can be directly implemented in a computer language of choice.
\begin{array}{|rcl|}
bf{Specification}
&&
bf{Implementation}
\\
\hline
Abstractdatatype&
\xrightarrowDatareification&
Datastructure
\\
Operations&
\xrightarrow[Operationdecomposition]{}&
Algorithms
\end{array}
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 representation ABS_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 invariants 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))
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:
INIT initialises the system, assumes that the factory is emptyENTER(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 factoryIS-PRESENT(p : Person) r : bool checks 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 ;
EXIT(p : Person) ext wr pres : Workers pre p in set pres post pres = pres~\;
IS-PRESENT(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 [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 (CCS) is more useful.
See also
Further reading
- Book: Bjørner, Dines . Cliff B. Jones . The Vienna Development Method: The Meta-Language, Lecture Notes in Computer Science 61 . Springer . 1978 . Berlin, Heidelberg, New York . 978-0-387-08766-5 .
- Book: O'Regan, Gerard . Mathematical Approaches to Software Quality . Springer . 2006 . London . 978-1-84628-242-3 .
- Book: Cliff B. Jones . Programming Languages and Their Definition — H. Bekič (1936-1982). . 177 . Springer-Verlag . 1984 . Berlin, Heidelberg, New York, Tokyo . 978-3-540-13378-0 . 10.1007/BFb0048933. 7488558.
- Fitzgerald, J.S. and Larsen, P.G., Modelling Systems: Practical Tools and Techniques in Software Engineering. Cambridge University Press, 1998 (Japanese Edition pub. Iwanami Shoten 2003).[10]
- Fitzgerald, J.S., Larsen, P.G., Mukherjee, P., Plat, N. and Verhoef, M., Validated Designs for Object-oriented Systems. Springer Verlag 2005. . Supporting web site http://www.vdmbook.com includes examples and free tool support.[11]
- Jones, C.B., Systematic Software Development using VDM, Prentice Hall 1990. . Also available on-line and free of charge: http://www.csr.ncl.ac.uk/vdm/ssdvdm.pdf.zip
- Bjørner, D. and Jones, C.B., Formal Specification and Software Development Prentice Hall International, 1982.
- J. Dawes, The VDM-SL Reference Guide, Pitman 1991.
- International Organization for Standardization, 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.
- Jones, C.B. and Shaw, R.C. (eds.), Case Studies in Systematic Software Development, Prentice Hall International, 1990.
- Bicarregui, J.C., Fitzgerald, J.S., 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. .
External links
|
