Unifying Theories of Programming - Alchetron, the free social encyclopedia

Originally published 1998		Author Tony Hoare
Computer program books A Discipline of Progra, Refinement calculus, Theories of Programming and Form, The B‑book, A Practical Theory of Programming

Unifying Theories of Programming (UTP) in computer science deals with program semantics. It shows how denotational semantics, operational semantics and algebraic semantics can be combined in a unified framework for the formal specification, design and implementation of programs and computer systems.

Theories

The semantic foundation of the UTP is the first-order predicate calculus, augmented with fixed point constructs from second-order logic. Following the tradition of Eric Hehner, programs are predicates in the UTP, and there is no distinction between programs and specifications at the semantic level. In the words of Hoare:

A computer program is identified with the strongest predicate describing every relevant observation that can be made of the behaviour of a computer executing that program.

In UTP parlance, a theory is a model of a particular programming paradigm. A UTP theory is composed of three ingredients:

an alphabet, which is a set of variable names denoting the attributes of the paradigm that can be observed by an external entity;

a signature, which is the set of programming language constructs intrinsic to the paradigm; and

a collection of healthiness conditions, which define the space of programs that fit within the paradigm. These healthiness conditions are typically expressed as monotonic idempotent predicate transformers.

Program refinement is an important concept in the UTP. A program P 1 is refined by P 2 if and only if every observation that can be made of P 2 is also an observation of P 1 . The definition of refinement is common across UTP theories:

P 1 ⊑ P 2 if and only if [ P 2 ⇒ P 1 ]

where [ X ] denotes the universal closure of all variables in the alphabet.

Relations

The most basic UTP theory is the alphabetised predicate calculus, which has no alphabet restrictions or healthiness conditions. The theory of relations is slightly more specialised, since a relation's alphabet may consist of only:

undecorated variables ( v ), modelling an observation of the program at the start of its execution; and

primed variables ( v ′ ), modelling an observation of the program at a later stage of its execution.

Some common language constructs can be defined in the theory of relations as follows:

The skip statement, which does not alter the program state in any way, is modelled as the relational identity:

s k i p ≡ v ′ = v

The assignment of value E to a variable a is modelled as setting a ′ to E and keeping all other variables (denoted by u ) constant:

a := E ≡ a ′ = E ∧ u ′ = u

The sequential composition of two programs is just relational composition of intermediate state:

P 1 ; P 2 ≡ ∃ v 0 ∙ P 1 [ v 0 / v ′ ] ∧ P 2 [ v 0 / v ]

Non-deterministic choice between programs is their greatest lower bound:

P 1 ⊓ P 2 ≡ P 1 ∨ P 2

Conditional choice between programs is written using infix notation:

P 1 ◃ C ▹ P 2 ≡ ( C ∧ P 1 ) ∨ ( ¬ C ∧ P 2 )

A semantics for recursion is given by the least fixed point μ F of a monotonic predicate transformer F :

μ X ∙ F ( X ) ≡ ⊓ { X ∣ F ( X ) ⊑ X }

References

Unifying Theories of Programming Wikipedia

(Text) CC BY-SA

Contents

Theories

Relations

References