In data refinement, a concrete data type replaces an abstract data type used in the design of an algorithm or system (Gries and Prins, 1985; Hoare, 1972; Jones, 1980). We present two methods for calculating the weakes...
详细信息
In data refinement, a concrete data type replaces an abstract data type used in the design of an algorithm or system (Gries and Prins, 1985; Hoare, 1972; Jones, 1980). We present two methods for calculating the weakest specification of each operation on a concrete data type from the specification of the corresponding abstract operation, together with a single simulation relation (Milner, 1980; Park, 1981), which specifies the correspondence between the two types. The methods are proved sound and (jointly) complete for a nondeterministic procedural programming language slightly more powerful than Dijkstra's (1976). Operations (in general, nondeterministic) are represented by relations, and significant use is made of prespecification and postspecification (Hoare and He, Jifeng, 1987).
A mathematical model of reconfigurability. We restrict is presented. The study is restricted to reconfigurations that can be implemented by connecting and disconnecting the wires that link nodes;these wires could be p...
详细信息
A mathematical model of reconfigurability. We restrict is presented. The study is restricted to reconfigurations that can be implemented by connecting and disconnecting the wires that link nodes;these wires could be physical or logical.
Dijkstra's (1975) weakest precondition is generalized in 4 ways, including: 1. The parameter Q may be a program, or it may be just the specification of a program that is not yet written. 2. The programming lang...
详细信息
Dijkstra's (1975) weakest precondition is generalized in 4 ways, including: 1. The parameter Q may be a program, or it may be just the specification of a program that is not yet written. 2. The programming language is extended to include general recursion. The increase in generality is obtained at the expense of some increase in complexity, and it can be justified only when it is needed. It is suggested that, in the design and development of correct programs, a calculus should be adopted in which: 1. programs and specifications are freely mixed, and 2. P is a program or design that correctly implements a design or specification Q, represented by the relational inclusion of P as a subset of Q. These suggestions generate some paradoxes, but they can be solved by recognizing that the set of programs is a proper subset of the set of specifications. Specifically, they are confined to relations that can be described using the primitives and operators of some programming language only.
Two collaborative projects, the European ESPRIT BRA ProCoS project and the UK IED safemos project, are currently investigating methods to prove software and hardware systems correct at a number of different levels of ...
详细信息
Two collaborative projects, the European ESPRIT BRA ProCoS project and the UK IED safemos project, are currently investigating methods to prove software and hardware systems correct at a number of different levels of abstraction. Both projects intend to concentrate on subsets of Occam, and the transputer instruction set. The projects will aim to use the same machine language so that results obtained on both projects will be compatible. The initial selection of the projects (a simple subset of the transputer) is presented using the specification language Z. The role of the specification in the two projects is explained and the benefits and drawbacks of such a specification are discussed.
We describe the rudiments of algorithm refinement: the business of taking a specification and producing code that correctly implements it. The paper starts with a general discussion of the concepts, and then turns to ...
详细信息
We describe the rudiments of algorithm refinement: the business of taking a specification and producing code that correctly implements it. The paper starts with a general discussion of the concepts, and then turns to a particular calculus for algorithm refinement.
Program transformation is used to develop the alpha-beta pruning algorithm from a specification of minimaxing. The pruning algorithm is nontrivial, and yet the transformation turns out to be relatively straightforward...
详细信息
Program transformation is used to develop the alpha-beta pruning algorithm from a specification of minimaxing. The pruning algorithm is nontrivial, and yet the transformation turns out to be relatively straightforward. The exercise is regarded as providing yet more evidence of the importance of transformational techniques, both for producing efficient programs and explaining them.
In ordinary mathematics, an equation can be written down which is syntactically correct, but for which no solution exists. For example, consider the equation x = x + 1 defined over the real numbers; there is no value ...
详细信息
ISBN:
(数字)9781447132035
ISBN:
(纸本)9783540197805
In ordinary mathematics, an equation can be written down which is syntactically correct, but for which no solution exists. For example, consider the equation x = x + 1 defined over the real numbers; there is no value of x which satisfies it. Similarly it is possible to specify objects using the formal specification language Z [3,4], which can not possibly exist. Such specifications are called inconsistent and can arise in a number of ways. Example 1 The following Z specification of a functionf, from integers to integers "f x : ~ 1 x ~ O· fx = x + 1 (i) "f x : ~ 1 x ~ O· fx = x + 2 (ii) is inconsistent, because axiom (i) gives f 0 = 1, while axiom (ii) gives f 0 = 2. This contradicts the fact that f was declared as a function, that is, f must have a unique result when applied to an argument. Hence no suchfexists. Furthermore, iff 0 = 1 andfO = 2 then 1 = 2 can be deduced! From 1 = 2 anything can be deduced, thus showing the danger of an inconsistent specification. Note that all examples and proofs start with the word Example or Proof and end with the symbol.1.
作者：
Raskovsky, Martin R.Essex University
Department Of Computing Science Oxford University Computing Laboratory Programming Research Group United Kingdom
We describe the automatic generation - from the formal denotational semantic specification - of an efficient compiler's code generation phase, producing efficient code for real machines. The method has been succes...
详细信息
The Z notation has been developed at the programmingresearchgroup at the Oxford University computinglaboratory and elsewhere for over a decade. It is now used by industry as part of the software (and hardware) deve...
详细信息
ISBN:
(数字)9781447135562
ISBN:
(纸本)9783540198185
The Z notation has been developed at the programmingresearchgroup at the Oxford University computinglaboratory and elsewhere for over a decade. It is now used by industry as part of the software (and hardware) development process in both Europe and the USA. It is currently undergoing BSI standardisation in the UK, and has been proposed for ISO standardisation internationally. In recent years researchers have begun to focus increasingly on the development of techniques and tools to encourage the wider application of Z and other formal methods and notations. This volume contains papers from the Seventh Annual Z User Meeting, held in London in December 1992. In contrast to previous years the meeting concentrated specifically on industrial applications of Z, and a high proportion of the participants came from an industrial background. The theme is well represented by the four invited papers. Three of these discuss ways in which formal methods are being introduced, and the fourth presents an international survey of industrial applications. It also provides a reminder of the improvements which are needed to make these methods an accepted part of software development. In addition the volume contains several submitted papers on the industrial use of Z, two of which discuss the key area of safety-critical applications. There are also a number of papers related to the recently-completed ZIP project. The papers cover all the main areas of the project including methods, tools, and the development of a Z Standard, the first publicly-available version of which was made available at the meeting. Finally the volume contains a select Z bibliography, and section on how to access information on Z through ***.z, the international, computer-based USENET newsgroup.;provides an important overview of current research into industrial applications of Z, and will provide invaluable reading for researchers, postgraduate students andalso potential industrial users of Z.
暂无评论