Session Chair: M.Y. Vardi.

Speaker: Robin Milner, Cambridge University.

Title: Calculi for Interaction

Abstract: Modern Computer Science is increasingly concerned with distributed systems, mobile connectivity and interaction. Systems with these properties are becoming bewilderingly complex. If we care about understanding their structure, then they need a structural semantic theory just as programming languages do. Intriguingly, the abstract concepts in programming semantics do not clearly extend to play the role.

With this in mind, several years ago with Joachim Parrow and David Walker (extending work by Uffe Engberg and Mogens Nielsen) I designed a calculus of mobile processes, the pi calculus. The strategy behind this move was that, to find the right abstract concepts for mobile interactive systems, one should first distill a bare descriptive notation from the various and intractable ways in which their designers had previously to describe them.

This process of distilling a calculus is not complete. The pi calculus is useful but not canonical. Recently I have introduced a family of calculi, known as action calculi; this contains the pi calculus, Petri nets, the lambda calculus and others, and is therefore a space in which we can hope to distinguish what is adhoc from what is essential in calculi for interaction. Colleagues have also begun to look at a uniform space of interpretations of these calculi.

In my talk I shall illustrate action calculi with simple examples, discuss some of their theory, and indicate how one may attempt to classify them. I shall emphasize their graphical nature, which can be regarded as generalising the interaction nets of Lafont.

Biographical Sketch: Arthur John Robin Gorell Milner was educated at Eton College and Cambridge. He worked for a few years in Ferranti Ltd, then re-entered academic life. He joined the University of Edinburgh in 1973, becoming Professor of Computation Theory in 1984. In 1986, with colleagues, he founded the Laboratory for Foundations of Computer Science at Edinburgh. He was elected Fellow of the Royal Society in 1988, and in 1991 won the A.M. Turing Award.

Milner has worked on computer-assisted reasoning; his system LCF (Logic for Computable Functions) was a model for several later systems. He led a team which designed and defined Standard ML, a widely used programming language. His main contribution has been to the theory of concurrent computation. Some of this work is widely accessible through his book Communication and Concurrency (1989); also, around that time he devised (with two colleagues) the pi calculus, a basic model for mobile communicating systems.

In January 1995, Milner was appointed Professor in the Computer Laboratory at Cambridge, which he now heads.