The Laws of Programming with Concurrency

Regular algebra provides a full set of simple laws for the programming of abstract state machines by regular expressions. They apply equally to sequential programs run on real computers. When extended by similar laws for interleaving of regular expressions, they apply also to programs for modern concurrent and distributed systems.

Evidence for this claim is given by deriving from the algebra a concurrent extension of Hoare Logic (O’Hearn’s separation logic), and also an operational semantics for Milner’s process calculus (CCS).

Speaker Details

Tony Hoare’s computing interests were stimulated by his first (and only) degree in the humanities (1956): he studied Latin and ancient Greek, followed by philosophy, with particular interest in mathematical philosophy and logic. He learnt Russian during National Service in the Royal Navy. He spent a postgraduate year studying statistics at Oxford and another at Moscow State University, where he discovered the sorting algorithm Quicksort. In 1960, he joined the British Computer industry as a programmer, eventually rising to the rank of Chief Engineer.

His Academic career started in 1968 with appointment as professor at the Queen’s University, Belfast. He chose his long-term research area as proof of the correctness of programs. In the thick of the troubles, he built up a strong computing department, and moved in 1978 to do the same at Oxford. Following the example of Theoretical Physics, his interests broadened to the pursuit of Unifying Theories of Programming.

On reaching retiring age, he accepted an offer of employment at Microsoft Research in Cambridge, where he has seen a strong surge of interest in automation of computer proofs of program correctness. He continues to pursue this interest, while exhorting academic researchers in long-term pursuit of even more idealistic scientific goals.

Date:
Speakers:
Tony Hoare