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 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 simulation 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. The part of π-calculus which is needed for the encoding is formulated in a new way, inspired by Berry's and Boudol's Chemical Abstract Machine.
| Original language | English |
|---|---|
| Title of host publication | Automata, Languages and Programming |
| Subtitle of host publication | 17th International Colloquium Warwick University, England, July 16–20, 1990 Proceedings |
| Publisher | Springer |
| Pages | 167-180 |
| Number of pages | 14 |
| ISBN (Electronic) | 978-3-540-47159-2 |
| ISBN (Print) | 978-3-540-52826-5 |
| DOIs | |
| Publication status | Published - 1990 |