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)].

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