Functions as processes
- 1 June 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 2 (2) , 119-141
- https://doi.org/10.1017/s0960129500001407
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.Keywords
This publication has 13 references indexed in Scilit:
- Functions as processesMathematical Structures in Computer Science, 1992
- π-Calculus semantics of object-oriented programming languagesPublished by Springer Nature ,1991
- Towards a lambda-calculus for concurrent and communicating systemsPublished by Springer Nature ,1989
- Linear logicTheoretical Computer Science, 1987
- A Calculus of Communicating Systems with Label PassingDAIMI Report Series, 1986
- Algebraic laws for nondeterminism and concurrencyJournal of the ACM, 1985
- Viewing control structures as patterns of passing messagesArtificial Intelligence, 1977
- Fully abstract models of typed λ-calculiTheoretical Computer Science, 1977
- Call-by-name, call-by-value and the λ-calculusTheoretical Computer Science, 1975
- The Mechanical Evaluation of ExpressionsThe Computer Journal, 1964