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 :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00075405
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 6:09:13 PM
Last modification on : Saturday, January 27, 2018 - 1:31:05 AM
Long-term archiving on : Tuesday, April 12, 2011 - 6:51:06 PM

Identifiers

  • HAL Id : inria-00075405, version 1

Collections

Citation

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

Share

Metrics

Record views

564

Files downloads

1305