Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T17:07:15.075Z Has data issue: false hasContentIssue false
  • English
  • Français

Functions as processes

Published online by Cambridge University Press:  04 March 2009

Robin Milner
Robin Milner
Affiliation:
University of Edinburgh
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper exhibits accurate encodings of the λ-calculus in the π-calculus. The former is canonical for calculation with functions, while the latter is a recent step (Milner et al. 1989) towards a canonical treatment of concurrent processes. With quite simple encodings, two λ-calculus reduction strategies are simulated very closely; each reduction in λ-calculus is mimicked by a short sequence of reductions in π-calculus. Abramsky's precongruence of applicative bisimulation (Abramsky 1989) over λ-calculus is compared with that induced by the encoding of the lazy λ-calculus into π-calculus; a similar comparison is made for call-by-value λ-calculus.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 2 , Issue 2 , June 1992 , pp. 119 - 141
Copyright
Copyright © Cambridge University Press 1992

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

Abadi, M., Cardelli, L., Curien, P–L. and Lévy, J–J. (1990), Explicit Substitutions, Proceedings of POPL 90, pp. 31–46.Google Scholar
Abramsky, S. (1989), The Lazy Lambda Calculus, in: Research Topics in Functional Programming, ed. Turner, D., Addison Wesley, pp. 65–116.Google Scholar
Barendregt, H.P. (1981), The Lambda Calculus, Its Syntax and Semantics, Studies in Logic and Fondations of Mathematics, Vol 103, North Holland.Google Scholar
Berry, G. (1979), Modèles Complètement Adéquats et Stables des lambda-calcul typés, Thèse de Doctorat d'Etat, Université Paris VII.Google Scholar
Berry, G. and Boudol, G. (1990), The Chemical Abstract Machine, Proc 17th Annual Symposium on Principles of Programming Languages.CrossRefGoogle Scholar
Boudol, G. (1989), Towards a Lambda-Calculus for Concurrent and Communicating Systems, Proc TAPSOFT 1989, Lecture Notes in Computer Science 351, Springer-Verlag, pp. 149–161.CrossRefGoogle Scholar
Curry, H.B. and Feys, R. (1958), Combinatory Logic, Vol 1, North Holland.Google Scholar
Clinger, W.D. (1981), Foundations of Actor Semantics, Ph.D. thesis, Massachusetts Institute of Technology, Artificial Intelligence Lab Technical Report £633, May 1981. Reprinted in: Towards Open Information Systems Science, Hewitt C.E., Manning C.R., Inman J.T. and Agha G. (eds.), Cambridge, MA: MIT Press, Spring 1991.Google 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.CrossRefGoogle Scholar
Girard, J. Y. (1987), Linear Logic, Journal of Theoretical Computer Science, Vol 50, pp. 111–102.CrossRefGoogle Scholar
Hennessy, M. and Milner, R. (1985), Algebraic Laws for Non-determinism and Concurrency, Journal of ACM, Vol 32, pp. 137–161.CrossRefGoogle Scholar
Hewitt, C., Bishop, P. and Steiger, R. (1973), A universal Modular Actor Formalism for Artificial Intelligence Proc IJCAI '73, Stanford, California, pp. 235–245.Google Scholar
Hewitt, C. (1977), Viewing Control Structures as Patterns of Passing Messages, Journal of Artificial Intelligence, Vol 8, No 3, pp. 323–364, 06 1977.CrossRefGoogle Scholar
Landin, P.J. (1964), The Mechanical Evaluation of Expressions, Computer Journal, Vol 4, pp. 308–320.CrossRefGoogle Scholar
Milner, R. (1977), Fully Abstract Models of Typed Lambda-calculi, Journal of Theoretical Computer science, Vol 5, pp. 1–23.CrossRefGoogle Scholar
Milner, R. (1990), Functions as Processes, Research Report No. 1154, INRIA, Sophia Antipolis, 02 1990.Google Scholar
Milner, R. (1989), Communication and Concurrency, Prentice Hall.Google Scholar
Milner, R., Parrow, J.G. and Walker, D.J. (1989), A Calculus of Mobile Processes, Parts I and II, Report ECS-LFCS-89–85 and 86, Laboratory for Foundations of Computer Science, Computer Science Department, Edinburgh University.Google Scholar
Nielson, F. (1989), The Typed λ-calculus with First-class Processes, Proc PARLE 89, Lecture Notes in Computer Science 366, Springer-Verlag.Google Scholar
Ong, C-H.L. (1988), Fully Abstract Models of the Lazy Lambda Calculus, Proc 29th Symposium on Foundations of Computer Science, pp. 368–376.Google Scholar
Ong, C-H.L. (1990), Operational extensionality of Plotkin's pure untyped call-by-value calculus λν, Unpublished memorandum.Google Scholar
Plotkin, G.D. (1975), Call-by-name and Call-by-value and the λ-calculus, Journal of Theoretical Computer Science, Vol 1, pp. 125–159.CrossRefGoogle Scholar
Sangiorgi, D. (1992), Forthcoming PhD thesis, University of Edinburgh.Google Scholar
Stoughton, A. (1989), Private communication.Google Scholar
Thomsen, B. (1989), A Calculus of Higher-order Communicating Systems, Proc 16th Annual Symposium on Principles of Programming Languages, pp. 143–154.Google Scholar
Thomsen, B. (1990) A Calculi for Higher-order Communicating Systems, PhD Thesis, Department of Computing, Imperial College, London.Google Scholar
Walker, D.J. (1991), π-Calculus Semantics of Object-oriented Programming Languages, Proc Conference Theoretical Aspects of Computer Software, Japan, Lecture Notes in Computer Science 526, Springer-Verlag, pp. 532–547.CrossRefGoogle Scholar