Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-23T18:36:42.479Z Has data issue: false hasContentIssue false
  • English
  • Français

Typing and subtyping for mobile processes

Published online by Cambridge University Press:  19 April 2018

Benjamin Pierce  and
Davide Sangiorgi
Benjamin Pierce
Affiliation:
Computer Laboratory, University of Cambridge, New Museums Site, Pembroke Street, Cambridge CB2 3QG, U.K. Email [email protected]
Davide Sangiorgi
Affiliation:
INRIA-Sophia Antipolis, 2004 Rue des Lucioles, B.P. 93, 06902 Sophia Antipolis, France. Email [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The π-calculus is a process algebra that supports mobility by focusing on the communication of channels. Milner's presentation of the π-calculus includes a type system assigning arities to channels and enforcing a corresponding discipline in their use. We extend Milner's language of types by distinguishing between the ability to read from a channel, the ability to write to a channel, and the ability both to read and to write. This refinement gives rise to a natural subtype relation similar to those studied in typed λ-calculi. The greater precision of our type discipline yields stronger versions of standard theorems on the π-calculus. These can be used, for example, to obtain the validity of β-reduction for the more efficient of Milner's encodings of the call-by-value λ-calculus, which fails in the ordinary π-calculus. We define the syntax, typing, subtyping, and operational semantics of our calculus, prove that the typing rules are sound, apply the system to Milner's λ-calculus encodings, and sketch extensions to higher-order process calculi and polymorphic typing.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 6 , Issue 5 , October 1996 , pp. 409 - 453
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Appendix. References

Abramsky, S. (1989) The Lazy Lambda Calculus. In: Turner, D. (ed.) Research Topics in Functional Programming, Addison-Wesley 65–116.Google Scholar
Amadio, R. M., and Cardelli, L. (1993) Subtyping Recursive Types. ACM Transactions on Programming Languages and Systems 15 (4) 575–631. (A preliminary version appeared in POPL ’91 (104-118), and as DEC Systems Research Center Research Report 62 August 1990.)CrossRefGoogle Scholar
Cardelli, L. (1986) Amber. In: Cousineau, G., Curien, P.-L., and Robinet, B. (eds.) Combinators and Functional Programming Languages. Springer-Verlag Lecture Notes in Computer Science 242 21–47.CrossRefGoogle Scholar
Cardelli, L. and Wegner, P. (1985) On Understanding Types, Data Abstraction, and Polymorphism. Computing Surveys 17 (4).CrossRefGoogle Scholar
Courcelle, B. (1983) Fundamental Properties of Infinite Trees. Theoretical Computer Science 25 95–169.CrossRefGoogle Scholar
de Bruijn, N. G. (1972) Lambda-Calculus Notation with Nameless Dummies: a Tool for Automatic Formula Manipulation with Application to the Church-Rosser Theorem. Indag. Math. 34 (5) 381–392.CrossRefGoogle Scholar
Engberg, U. and Nielsen, M. (1986) A Calculus of Communicating Systems with Label-Passing. Report DAIMI PB-208, Computer Science Department, University of Aarhus, Denmark.CrossRefGoogle Scholar
Gay, S. J. (1993) A Sort Inference Algorithm for the Polyadic π-Calculus. In: Proceedings of the Twentieth ACM Symposium on Principles of Programming Languages. CrossRefGoogle Scholar
Girard, J.-Y. (1972) Interpretation fonctionelle et elimination des coupures de l'arithmetique d'ordre supérieur, Ph.D. thesis, Université Paris VII.Google Scholar
Glavan, P. and Rosenzweig, D. (1993) Communicating Evolving Algebras. In: Borger, E., Martini, S., Jager, G., Kleine Biining, H. and Richter, M. (eds.) Computer Science Logic, Selected Papers from CSL'92. Springer-Verlag Lecture Notes in Computer Science 702 186–215.Google Scholar
Kobayashi, N., Pierce, B. C. and Turner, D. N. (1996) Linearity and the Pi-Calculus. Principles of Programming Languages. CrossRefGoogle Scholar
Milner, R. (1989) Communication and Concurrency, Prentice Hall.Google Scholar
Milner, R. (1990) Functions as Processes. Research Report 1154, INRIA, Sophia Antipolis. (Final version in Journal of Mathem. Structures in Computer Science (1992) 2 (2) 119-141.)CrossRefGoogle Scholar
Milner, R. (1991) The polyadic π-calculus: a tutorial. Tech. rept. ECS–LFCS–91–180. LFCS, Dept. of Comp. Sci., Edinburgh Univ. (Also in Bauer, F. L., Brauer, W. and Schwichtenberg, H. (eds.) (1993) Logic and Algebra of Specification, Springer-Verlag.)Google Scholar
Milner, R., and Sangiorgi, D. (1992) Barbed Bisimulation. In: Kuich, W. (ed) Proceedings 19th ICALP. Springer-Verlag Lecture Notes in Computer Science 623 685–695.Google Scholar
Milner, R., Parrow, J. and Walker, D. (1992) A Calculus of Mobile Processes, (Parts I and II). Information and Computation 100 1–77.CrossRefGoogle Scholar
Milner, R. (1978) A Theory of Type Polymorphism in Programming. Journal of Computer and System Sciences 17 348–375.CrossRefGoogle Scholar
Nielson, H. R. and Nielson, F. (1994) Higher-Order Concurrent Programs with Finite Communication Topology. In: Proceedings of POPL ’94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, Oregon 84–97.CrossRefGoogle Scholar
Odersky, M. (1995) Polarized Name Passing. In: Proceedings of Foundations of Software Technology and Theoretical Computer Science. Springer-Verlag Lecture Notes in Computer Science. CrossRefGoogle Scholar
Parrow, J. and Sangiorgi, D. (1993) Algebraic Theories for Name-Passing Calculi. Tech. rept. ECS-LFCS-93-262, LFCS, Dept. of Comp. Sci., Edinburgh Univ. (To appear in Information and Compuation. Short version in Proc. REX Summer School/Symposium 1993, Springer-Verlag Lecture Notes in Computer Science 803.)Google Scholar
Pierce, B. C. and Turner, D. N. (1995a) Concurrent Objects in a Process Calculus. In: Ito, T., and Yonezawa, A. (eds.) Theory and Practice of Parallel Programming (TPPP), Sendai, Japan (Nov. 1994). Springer-Verlag Lecture Notes in Computer Science 907 187–215.CrossRefGoogle Scholar
Pierce, B. C. and Turner, D. N. (1995b) Pict: A Programming Language Based on the Pi-Calculus (to appear).Google Scholar
Pierce, B. C., Remy, D. and Turner, D. N. (1993) A Typed Higher-Order Programming Language Based on the Pi-Calculus. In: Workshop on Type Theory and its Application to Computer Systems, Kyoto University.Google Scholar
Plotkin, G. (1975) Call by Name, Call by Value and the λ-calculus. Theoretical Computer Science 1 125–159.CrossRefGoogle Scholar
Reynolds, J. (1974) Towards a Theory of Type Structure. In: Proc. Colloque sur la Programmation. Springer-Verlag Lecture Notes in Computer Science 19 408–425.Google Scholar
Reynolds, J. 1985. Three Approaches to Type Structure. In: Mathematical Foundations of Software Development. Springer-Verlag Lecture Notes in Computer Science 185.Google Scholar
Reynolds, J. C. (1988) Preliminary Design of the Programming Language Forsythe. Tech. rept. CMU-CS-88-159, Carnegie Mellon University.Google Scholar
Sangiorgi, D. (1992) Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms, Ph.D. thesis CST-99-93, Department of Computer Science, University of Edinburgh.Google Scholar
Sangiorgi, D. (1993) A Theory of Bisimulation for the π-calculus. Tech. rept. ECS–LFCS–93–270. LFCS, Dept. of Comp. Sci., Edinburgh Univ. (Extended Abstract in Proc. CONCUR ’93, Springer-Verlag Lecture Notes in Computer Science 715.)CrossRefGoogle Scholar
Takeuchi, K., Honda, K. and Kubo, M. (1994) An Interaction-based Language and its Typing System. Proceedings of PARLE'94. Springer-Verlag Lecture Notes in Computer Science 817 398–113.CrossRefGoogle Scholar
Turner, D. N. (1996). The Polymorphic Pi-calculus: Theory and Implementation, Ph.D. thesis, LFCS, University of Edinburgh.Google Scholar
Vasconcelos, V. T. and Honda, K. (1993) Principal Typing Schemes in a Polyadic Pi-Calculus. In: Proceedings of CONCUR ’93. Also available as Keio University Report CS-92-004.Google Scholar
Walker, D. (1995) Objects in the π-calculus. Information and Computation 116 253–271.CrossRefGoogle Scholar