Functions as processes
Robin Milner · Mathematical Structures in Computer Science · 1992
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.
Cited by 528 works. doi:10.1017/s0960129500001407
Authors
References
- Communication and Concurrency
- The Mechanical Evaluation of Expressions
- Linear logic
- Communication and concurrency
- The Lambda Calculus - Its Syntax and Semantics
- Viewing control structures as patterns of passing messages
- Algebraic laws for nondeterminism and concurrency
- Call-by-name, call-by-value and the λ-calculus
- Fully abstract models of typed λ-calculi
- A calculus of higher order communicating systems