Algebra and models

ABSTRACT

Science makes progress by constructing mathematical models, deducing their observable consequences, and testing them by experiment. Successful theoretical models are later taken as the basis for engineering methods and codes of practice for design of reliable and useful products. Models can play a similar central role in the progress and practical application of Computing Science.A model of a computational paradigm starts with choice of a carrier set of potential direct or indirect observations that can be made of a computational process. A particular process is modelled as the subset of observations to which it can give rise. Process composition is modelled by relating observations of a composite process to those of its components. Indirect observations play an essential role in such compositions. Algebraic properties of the composition operators are derived with the aid of the simple theory of sets and relations. Feasibility is checked by a mapping from a more operational model.A model constructed as a family of sets is easily adapted as a calculus of design for total correctness. A specification is given by an arbitrary set containing all observations permitted in the required product. It should be expressed as clearly as possible with the aid of the full power of mathematics and logic. A product meets a specification if its potential observations form a subset of its permitted observations. This principle requires that all envisaged failure modes of a product are modelled as indirect observations, so that their avoidance can be proved. Specifications of components can be composed mathematically by the same operators as the components themselves. This permits top-down proof of correctness of designs even before their implementation begins. Algebraic properties and reasoning are helpful throughout development. Non-determinism is seen as no problem, but rather as a part of the solution.

REFERENCES

• 1: The Varieties of Programming Language, C.A.R. Hoare, Tapsoft '89, Lecture Notes in Computer Science, 351, Springer- Verlag pp 1-18.
• 2: A Theory of Conduction and Concurrency, C.A.R. Hoare, in Parallel Architectures (cd. Rishe et al) IEEE Computer Society Press 1991, pp 18-27.
• 3: Programs are Predicates, C.A.R. Hoare, Proceedings of FGCS '92,ICOT,pp211-218.
• 4: Mathematics of Programming, C.A.R. Hoare, in Program Verification, (cd. CoIburn et al), Kluwer 1993, pp 135-154.
• 5: C. A. R. Hoare , I. J. Hayes , He Jifeng , C. C. Morgan , A. W. Roscoe , J. W. Sanders , I. H. Sorensen , J. M. Spivey , B. A. Sufrin, Laws of programming, Communications of the ACM, v.30 n.8, p.672-686, Aug. 1987 [doi>10.1145/27651.27653]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

  G. Mathematics of Computing

General Terms:
Design, Theory