H ? « ‹ ← → › »

Language peer sets for Pi Calculus:
United Kingdom↑
United Kingdom/1991↑
Designed 1991 ↑
1990s languages ↑
Fifth generation↑
Post-Cold War↑

Pi Calculus(ID:6813/)

alternate simple view

Country: United Kingdom
Designed 1991

Milners calculus with mobility

People:

Robin Milner

Related languages

value-passing CCS	→	Pi Calculus	Evolution of
Pi Calculus	→	PICT	Based on
Pi Calculus	→	PiLib	Implementation

References:

Milner, Robin (1991) Milner, Robin "The polyadic pi-calculus: a tutorial" October 1991.

Turner, David N, (1995) Turner, David N, "The Polymorphic Pi-Calculus: Theory and Implications" PhD Thesis Edinburgh 1995 Abstract

Walker, David (1995) Walker, David "Objects and the pi-calculus" Information and Computation, 1995.

Pierce, Benjamin C. and Turner, David N. (1996) Pierce, Benjamin C. and Turner, David N. "Pict Language Definition", Version 3.9d, 1996

Gengler, Marc; Martel, Matthieu (1997) Gengler, Marc; Martel, Matthieu "Self-applicable partial evaluation for the pi-calculus" pp36-46 Abstract DOI
in [SIGPLAN] (1997) [ACM SIGPLAN] SIGPLAN Notices 32(12)

Pierce, Benjamin C. (1997) Pierce, Benjamin C. and Turner, David N. Pict: A programming language based on the pi-calculus. Technical report, Computer Science Department, Indiana University, 1997. To appear in Milner festschrift, MIT Press.
in [SIGPLAN] (1997) [ACM SIGPLAN] SIGPLAN Notices 32(12)
Resources

Interview with Robin Milner Can you describe the development from CCS to Pi in its historic timeline? What was your first concurrency formalism and how did you change it? What didn't work? How was it perceived?

I think it's an interesting story. I was working with what I called Behaviour Algebra in 1978. The set of primitives included parallel composition, prefixing and those things. I wanted to make this small set of primitives do everything or do as much as possible, and to understand them semantically, preferably in Domain Theory; but that didn't work. The idea of labelled transition systems became very important because it was a replacement for what didn't work, which was encoding things into Domain Theory. Because encoding things into Domain Theory, the equivalences became either too rich or too poor, I mean too big or too small. They didn't hit what I regarded as correct notion of behavioural equivalence. There seemed to be something inescapably missing in Domain Theory in respect to this. So labelled transition systems -- following on from Gordon Plotkin's work on operational semantics and bringing the idea of labels in -- became central.

But automata already had labels!

Yes, that's true, they did, and Keller had labelled transition systems. The idea of a label being, as it were, a vehicle of interaction became totally important. So it's hard to know where it came from: Keller with his labelled transition systems, or automata theory? Making it a shared action was already present in Petri to some extent. But doing it algebraically and compositionally, that was an important thing. When I gave lectures in Aarhus in '79, that was essentially how the book on CCS evolved. What you are asking about is how it developed. What people perhaps don't know is that I was talking to Mogens Nielsen there and we were really trying to make the Pi-calculus work at that time. I remember vividly discussions in his office in Aarhus, and we couldn't make it work. So CCS became the Pi-calculus without communication of channels.

You were aware that CCS had shortcomings? You didn't think you had hit on the right formalism and later changed your mind.

Absolutely not. But it seemed to me -- and later all the more -- that it was good not to go the whole way, because there was a certain nice, manageable modesty about concurrency in CCS -- same thing with CSP, really. You have two levels: you have data and then you have that data being moved around, but you don't have the one feeding on the other. You like to move the values around, but not to move the means of movement. It was very important, I think, to see concurrent calculi without movement. Because then you could see how much could be done without movement. And the answer is: a tremendous amount could be done. The CSP people have shown that. A tremendous number of systems can be handled. And then you could begin see just where the barrier lay, what things you couldn't model. Anyway, whatever justification you could have for inventing something without mobility, Mogens Nielsen and I tried to get it to work for the label passing, but we didn't succeed. So then CCS became what it was.

Search in: Google Google scholar World Cat Yahoo Overture DBLP Monash bib NZ IEEE ACM portal CiteSeer CSB ncstrl jstor Bookfinder