Functions as Processes

Robin Milner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication17th International Colloquium Warwick University, England, July 16–20, 1990 Proceedings
PublisherSpringer Press
Pages167-180
Number of pages14
ISBN (Electronic)978-3-540-47159-2
ISBN (Print)978-3-540-52826-5
DOIs
Publication statusPublished - 1990

Cite this