Linearity and the pi-calculus
Authors:
Open Access
- 1 September 1999
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 21 (5) , 914-947
Abstract
The economy and flexibility of the pi-calculus make it an attractive object of theoretical study and a clean basis for concurrent language design and implementation. However, such generality has a cost: encoding higher-level features like functional computation in pi-calculus throws away potentially useful information. We show how a linear type system can be used to recover important static information about a process's behavior. In particular, we can guarantee that two processes communicating over a linear channel cannot interfere with other communicating processes. After developing standard results such as soundness of typing, we focus on equivalences, adapting the standard notion of barbed bisimulation to the linear setting and showing how reductions on linear channels induce a useful “partial confluence” of process behaviors. For an extended example of the theory, we prove the validity of a tail-call optimization for higher-order functions represented as processes.Keywords
This publication has 26 references indexed in Scilit:
- A partially deadlock-free typed process calculusACM Transactions on Programming Languages and Systems, 1998
- Type-based analysis of communication for concurrent programming languages1997
- Syntactic Control of Interference RevisitedElectronic Notes in Theoretical Computer Science, 1995
- Concurrent objects in a process calculus1995
- Lilac: a functional programming language based on linear logicJournal of Functional Programming, 1994
- Computational interpretations of linear logicTheoretical Computer Science, 1993
- A calculus of mobile processes, IInformation and Computation, 1992
- Lively linear LispACM SIGPLAN Notices, 1992
- Linear logicTheoretical Computer Science, 1987
- Viewing control structures as patterns of passing messagesArtificial Intelligence, 1977