Fully Abstract Encodings of λ-Calculus in HOcore through Abstract Machines

05/13/2022
by   Małgorzata Biernacka, et al.
0

We present fully abstract encodings of the call-by-name and call-by-value λ-calculus into HOcore, a minimal higher-order process calculus with no name restriction. We consider several equivalences on the λ-calculus side – normal-form bisimilarity, applicative bisimilarity, and contextual equivalence – that we internalize into abstract machines in order to prove full abstraction of the encodings. We also demonstrate that this technique scales to the λμ-calculus, i.e., a standard extension of the λ-calculus with control operators.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset