×

zbMATH — the first resource for mathematics

Functions as processes. (English) Zbl 0766.68036
Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 167-180 (1990).
Summary: [For the entire collection see Zbl 0758.00017.]
This paper exhibits accurate encodings of the \(\lambda\)-calculus in the \(\pi\)-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 \(\lambda\)-calculus reduction strategies are simulated very closely; each reduction in \(\lambda\)-calculus is mimicked by a short sequence of reductions in \(\pi\)-calculus. Abramsky’s precongruence of applicative simulation [S. Abramsky, The lazy lambda calculus, to appear in Declarative Programming, ed. D. Turner, Addison Wesley (1988)] over \(\lambda\)- calculus is compared with that induced by the encoding of the lazy \(\lambda\)-calculus into \(\pi\)-calculus; a similar comparison is made for call-by-value \(\lambda\)-calculus.
The part of \(\pi\)-calculus which is needed for the encoding is formulated in a new way, inspired by Berry’s and Boudol’s chemical abstract machine [G. Berry and G. Boudol, Theor. Comput. Sci. 96, No. 1, 217- 248 (1992; Zbl 0747.68013)].

MSC:
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
03B40 Combinatory logic and lambda calculus
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite