Unifying Theories of Programming

Unifying Theories of Programming
AuthorC. A. R. Hoare
He Jifeng
LanguageEnglish
SeriesSeries in Computer Science
GenreScientific non-fiction
PublisherPrentice Hall
Publication date1998
Publication placeUnited Kingdom
Pagesxix+298
ISBN0-13-458761-8
Dewey Decimal005.1/01
LC ClassQA76.6. .H5735 1998
Websiteunifyingtheories.org

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.

The book of this title by C.A.R. Hoare and He Jifeng was published in the Prentice Hall International Series in Computer Science in 1998 and has been made freely available on the web.

A UTP Symposium series was started in 2006.

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 parts:

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

P1⊑P2if and only if[P2⇒P1]

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:

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

𝐬𝐤𝐢𝐩≡v′=v

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

P1;P2≡∃v0∙P1[v0/v′]∧P2[v0/v]

P1⊓P2≡P1∨P2

P1◃C▹P2≡(C∧P1)∨(¬C∧P2)

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