Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2205.06665 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909280042483712 |
|---|---|
| author | Biernacka, Małgorzata Biernacki, Dariusz Lenglet, Sergueï Polesiuk, Piotr Pous, Damien Schmitt, Alan |
| author_facet | Biernacka, Małgorzata Biernacki, Dariusz Lenglet, Sergueï Polesiuk, Piotr Pous, Damien Schmitt, Alan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_06665 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fully Abstract Encodings of $λ$-Calculus in HOcore through Abstract Machines Biernacka, Małgorzata Biernacki, Dariusz Lenglet, Sergueï Polesiuk, Piotr Pous, Damien Schmitt, Alan Logic in Computer Science 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. |
| title | Fully Abstract Encodings of $λ$-Calculus in HOcore through Abstract Machines |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2205.06665 |