Elements of interaction

Robin Milner

In 1997 we celebrated the 60th anniversary of Alan Turing's work in the entscheidungs problem, in which he put forward his universal 'paper machine', the paradigm for the digital computers that followed. Computing-as-calculation began in mathematical logic.

What about computing-as-interaction? It didn't begin in logic; the fundamental study of it seems to have arisen in various ways, including automata to model the brain (McCulloch and Pitts), interest in causality among events (Petri) and in computer networks (passim).

The Web, and the platforms and applications built upon it, offer both opportunity and challenge to foundational models of interaction. Think of these systems as forming three levels of a `science of the artificial' (H.A.Simon), loosely analogous to three levels of natural science: physics, chemistry, biology.

At the highest level there are `organisms', complete individual systems like software for the Child Support Agency, or any complete application mounted on the Web, or the Web itself. At the medium level are non-trivial structures, like protocols or data structures or workflow patterns, that are used to build the organisms.

At the lowest level are atomic things, which we can call the 'elements' of interaction. They can be really simple, like synchronised action (handshake) or naming. To anyone who has studied calculi of concurrent processes for any length of time it is delightful to see exactly these elements cropping up on the Web as clicks and URLs.

So the opportunity the Web offers such people is to try out their foundational theories of interaction to see if they adequately model the Web and what happens on it. They won't, completely; so the challenge it offers is to improve the theories so that they model it better. Once this is done, the chemistry of the Web, like protocols and semi-structured data, can be based firmly on the theories and derived their properties from it.

This experimental activity can be, and is being, carried out in particular for Web choreography: the expression and analysis of Web platforms for transactional processes (for business, or for anything). There is surprising convergence of ideas in `elementary' calculi, like the pi calculus, and a language such as CDL -- the emerging Choreography Description Language of the web (part of its chemistry).

If we can achieve this rigorous understanding for Web engineering, then we shall set a paradigm for a harder job: the creation of a rigorous underpinning for the ubiquitous computing that will pervade the 21st century.