# 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)