HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Functions as processes

Robin Milner 1
1 MEIJE - Concurrency, Synchronization and Real-time Programming
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This paper exhibits accurate encodings of the l-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 l-calculus reduction strategies are simulated very closely ; each reduction in l-calculus is mimicked by a short sequence of reductions in ¹-calulus. Abramsky's precongruence of applicative simulation over l-calculus is compared with that induced by the encoding of the lazy l-calculus into ¹-calculus ; a similar comparison is made for call-by-value l-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. The new formulation is shown to be consistent with the original.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 6:09:13 PM
Last modification on : Friday, February 4, 2022 - 3:16:34 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 6:51:06 PM


  • HAL Id : inria-00075405, version 1



Robin Milner. Functions as processes. [Research Report] RR-1154, INRIA. 1990. ⟨inria-00075405⟩



Record views


Files downloads