Eager functions as processes

DOI10.1145/3209108.3209152MaRDI QIDQ5145310zbMATH OpenOpenAlexFDO

Authors Adrien Durier, Daniel Hirschkoff, Davide Sangiorgi

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.02863

zbMATH Keywords

full abstractionlambda-calculuspi-calculuscall-by-value

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40)

Abstract: We study Milner's encoding of the call-by-value $lambda$-calculus into the $pi$-calculus. We show that, by tuning the encoding to two subcalculi of the $pi$-calculus (Internal $pi$ and Asynchronous Local $pi$), the equivalence on $lambda$-terms induced by the encoding coincides with Lassen's eager normal-form bisimilarity, extended to handle $eta$-equality. As behavioural equivalence in the $pi$-calculus we consider contextual equivalence and barbed congruence. We also extend the results to preorders. A crucial technical ingredient in the proofs is the recently-introduced technique of unique solutions of equations, further developed in this paper. In this respect, the paper also intends to be an extended case study on the applicability and expressiveness of the technique.

Recommendations

• Eager functions as processes
• scientific article; zbMATH DE number 177812
• Trees from functions as processes
• Functions as processes
• Trees from functions as processes

Cited in

(8)

• Using -calculus names as locks
• Evaluating functions as processes
• Unique solutions of contractions, CCS, and their HOL formalisation
• Divergence and unique solution of equations
• Eager functions as processes
• An investigation into functions as processes
• scientific article; zbMATH DE number 177812 (Why is no real title available?)
• Functions as processes

This page was built for publication: Eager functions as processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145310)