Asynchronous π -calculus at Work: The Call-by-Need Strategy

In a well-known and influential paper [17] Palamidessi has shown that the expressive power of the Asynchronous π -calculus is strictly less than that of the full (synchronous) π -calculus. This gap in expressiveness has a correspondence, however, in sharper semantic properties for the former calculus, notably concerning algebraic laws. This paper substantiates this, taking, as a case study, the encoding of call-by-need λ -calculus into the π -calculus. We actually adopt the Local Asynchronous π -calculus, that has even sharper semantic properties. We exploit such properties to prove some instances of validity of β -reduction (meaning that the source and target terms of a β -reduction are mapped onto behaviourally equivalent processes). Nearly all results would fail in the ordinary synchronous π -calculus. We show that however the full β -reduction is not valid. We also consider a refined encoding in which some further instances of β -validity hold. We conclude with a few questions for future work.