This report summarises the background and recent progress in the research of its coauthors. It is aimed at the construction of links between algebraic presentations of the principles of programming and the exploitatio...
详细信息
This report summarises the background and recent progress in the research of its coauthors. It is aimed at the construction of links between algebraic presentations of the principles of programming and the exploitation of concurrency in modern programming practice. The signature and laws of a Concurrent Kleene Algebra (CKA) largely overlap with those of a Regular Algebra, with the addition of concurrent composition and a few simple laws for it. They are re-interpreted here in application to computer programs. The inclusion relation for regular expressions is re-interpreted as a refinement ordering, which supports a stepwise contractual approach to software system design and to program debugging. The laws are supported by a hierarchy of models, applicable and adaptable to a range of different purposes and to a range of different programming languages. The algebra is presented in three tiers. The bottom tier defines traces of program execution, represented as sets of events that have occurred in a particular run of a program;the middle tier defines a program as the set of traces of all its possible behaviours. The top tier introduces additional incomputable operators, which are useful for describing the desired or undesired properties of computer program behaviour. The final sections outline directions in which further research is needed. (C) 2015 Elsevier Inc. All rights reserved.
Data refinement is the transformation in a computer program of one data type to another. Usually, we call the original data type ‘abstract’ and the final data type ‘concrete’. The concrete data type is said to rep...
详细信息
Data refinement is the transformation in a computer program of one data type to another. Usually, we call the original data type ‘abstract’ and the final data type ‘concrete’. The concrete data type is said to represent the abstract. In spite of recent advances, there remain obvious data refinements that are difficult to prove. We give such a refinement and present a new technique that avoids the difficulty. Our innovation is the use of program fragments that do not satisfy Dijkstra's Law of the excluded miracle . These of course can never be implemented, so they must be eliminated before the final program is reached. But, in the intermediate stages of development, they simplify the calculations.
A trace of the execution of a concurrent object-oriented program can be displayed in two-dimensions as a diagram of a non-metric finite geometry. The actions of a programs are represented by points, its objects and th...
详细信息
ISBN:
(数字)9783319522289
ISBN:
(纸本)9783319522289;9783319522272
A trace of the execution of a concurrent object-oriented program can be displayed in two-dimensions as a diagram of a non-metric finite geometry. The actions of a programs are represented by points, its objects and threads by vertical lines, its transactions by horizontal lines, its communications and resource sharing by sloping arrows, and its partial traces by rectangular figures. We prove informally that the geometry satisfies the laws of Concurrent Kleene Algebra (CKA);these describe and justify the interleaved implementation of multithreaded programs on computer systems with a lesser number of concurrent processors. More familiar forms of semantics (e.g., verification-oriented and operational) can be derived from CKA. Programs are represented as sets of all their possible traces of execution, and non-determinism is introduced as union of these sets. The geometry is extended to multiple levels of abstraction and granularity;a method call at a higher level can be modelled by a specification of the method body, which is implemented at a lower level. The final section describes how the axioms and definitions of the geometry have been encoded in the interactive proof tool Isabelle, and reports on progress towards automatic checking of the proofs in the paper.
Despite the rich depository of empirical knowledge on programming and software engineering, the theoretical model of programs is still unknown. This paper presents an embedded relational model (ERM) for describing the...
详细信息
ISBN:
(纸本)9781424400379
Despite the rich depository of empirical knowledge on programming and software engineering, the theoretical model of programs is still unknown. This paper presents an embedded relational model (ERM) for describing the nature of programs. ERM provides a unified mathematical treatment of programs, which reveals that a program is a large and finite set of embedded binary relations between a given current statement and all previous ones that formed the semantic context or environment of computing. According to the ERM model, a program is a composed listing and a logical combination of multiple statements according to certain composing rules. A set of 17 meta statements and a set of 17 compositional relations in computing are elicited in real-time process algebra (RTPA). Based on the ERM model, a set of mathematical laws of programming is formally established.
暂无评论