×

zbMATH — the first resource for mathematics

Functions as processes. (English) Zbl 0773.03012
In a recent paper, the author introduced the \(\pi\)-calculus [R. Milner, J. Parrow and D. Walker, Inf. Comput. 100, 1-40, 41- 77 (1992; Zbl 0752.68036 and Zbl 0752.68037)], which is a step toward a canonical treatment of concurrent processes. In order to show the power of that calculus one is led to consider the problem of encoding \(\lambda\)-calculus into the \(\pi\)-calculus, because functions, as considered in \(\lambda\)-calculus, should turn out to be particular cases of concurrent processes.
In this paper, the author shows the encoding for the lazy \(\lambda\)- calculus into \(\pi\)-calculus and a similar encoding for the call-by-value \(\lambda\)-calculus. He also compares the encodings with Abramsky’s precongruence of “applicative bisimulation”.

MSC:
03B40 Combinatory logic and lambda calculus
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1016/0304-3975(75)90017-1 · Zbl 0325.68006 · doi:10.1016/0304-3975(75)90017-1
[2] Walker, Proc Conference Theoretical Aspects of Computer Software, Japan pp 532– (1991) · doi:10.1007/3-540-54415-1_63
[3] Curry, Combinatory Logic 1 (1958)
[4] Boudol, Proc TAPSOFT 351 pp 149– (1989) · doi:10.1007/3-540-50939-9_130
[5] Berry, Modèles Complètement Adéquats et Stables des lambda-calcul typés (1979)
[6] Barendregt, The Lambda Calculus, Its Syntax and Semantics 103 (1981) · Zbl 0467.03010
[7] Abramsky, Research Topics in Functional Programming pp 65–116– (1989)
[8] Abadi, Proceedings of POPL 90 pp 31– (1990)
[9] Nielson, Proc PARLE 89 366 (1989)
[10] Milner, A Calculus of Mobile Processes, Parts I and II (1989)
[11] Milner, Communication and Concurrency (1989)
[12] Milner, Functions as Processes 1154 (1990) · Zbl 0766.68036
[13] DOI: 10.1016/0304-3975(77)90053-6 · Zbl 0386.03006 · doi:10.1016/0304-3975(77)90053-6
[14] Landin, Computer Journal 4 pp 308– (1964) · Zbl 0122.36106 · doi:10.1093/comjnl/6.4.308
[15] DOI: 10.1016/0004-3702(77)90033-9 · doi:10.1016/0004-3702(77)90033-9
[16] Hewitt, Proc IJCAI pp 235– (1973)
[17] DOI: 10.1145/2455.2460 · Zbl 0629.68021 · doi:10.1145/2455.2460
[18] DOI: 10.1016/0304-3975(87)90045-4 · Zbl 0625.03037 · doi:10.1016/0304-3975(87)90045-4
[19] Engberg, A Calculus of Communicating Systems with Label-passing (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.