|
Vienna Development MethodThe Vienna Development Method (VDM) is one of the longest-established formal methods for the development of computer-based systems. Originating in work done at the IBM Laboratory Vienna[1] 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++,[2] 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. PhilosophyComputing 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. HistoryThe origins of VDM-SL lie in the IBM Laboratory in Vienna where the first version of the language was called the Vienna Definition Language (VDL).[3] The VDL was essentially used for giving operational semantics descriptions in contrast to the VDM – Meta-IV which provided denotational semantics[4]
There is no connection between Meta-IV,[6] and Schorre's META II language, or its successor Tree Meta; these were compiler-compiler systems rather than being suitable for formal problem descriptions. So Meta-IV was "used to define major portions of" the PL/I programming language. Other programming languages retrospectively 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[7] 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). VDM featuresThe 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 syntax. 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 typesVDM-SL includes basic types modelling numbers and characters as follows:
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: <Red>, <Amber>, <FlashingAmber>, <Green>
Type constructors: union, product and composite typesThe basic types alone are of limited value. New, more structured data types are built using type constructors.
The most basic type constructor forms the union of two predefined types. The type SignalColour = <Red> | <Amber> | <FlashingAmber> | <Green>
Enumerated types 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) == d<=31 and m<=12
models a simple date type. The value mk_Date(1,4,2001).month = 4
CollectionsCollection 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. SetsThe set type constructor (written UGroup = set of UserId
defines a type
SequencesThe finite sequence type constructor (written String = seq of char
Defines a type The order and repetition of items in a sequence is significant, so
MapsA 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
StructuringThe 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-SLIn 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:
Structuring in VDM++In VDM++ structuring are done using classes and multiple inheritance. The key concepts are:
Modelling functionalityFunctional modellingIn 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(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, " State-based modellingIn 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 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 ExamplesThe max functionThis 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' <= 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:nat
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:
Queue abstract data typeThis 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 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];
DEQUEUE()e:Qelt
ext wr q:Queue
pre q <> []
post q~ = [e]^q;
IS-EMPTY()r:bool
ext rd q:Queue
post r <=> (len q = 0)
Bank system exampleAs 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 supportA number of different tools support VDM:
Industrial experienceVDM has been applied widely in a variety of application domains. The most well-known of these applications are:
RefinementUse 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. Data reificationData 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 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
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 reificationIn 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:
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};
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 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
References
External links
|
![{\displaystyle {\begin{array}{|rcl|}{\textbf {Specification}}&&{\textbf {Implementation}}\\\hline {\text{Abstract data type}}&\xrightarrow {\text{Data reification}} &{\text{Data structure}}\\{\text{Operations}}&{\xrightarrow[{\text{Operation decomposition}}]{}}&{\text{Algorithms}}\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7cfd927beebe328e3bd51537dffb7316579b2b7)
Portal di Ensiklopedia Dunia
