License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2021.5
URN: urn:nbn:de:0030-drops-167744
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16774/
Di Gianantonio, Pietro ;
Lenisa, Marina
Principal Types as Lambda Nets
Abstract
We show that there are connections between principal type schemata, cut-free λ-nets, and normal forms of the λ-calculus, and hence there are correspondences between the normalisation algorithms of the above structures, i.e. unification of principal types, cut-elimination of λ-nets, and normalisation of λ-terms. Once the above correspondences have been established, properties of the typing system, such as typability, subject reduction, and inhabitation, can be derived from properties of λ-nets, and vice-versa. We illustrate the above pattern on a specific type assignment system, we study principal types for this system, and we show that they correspond to λ-nets with a non-standard notion of cut-elimination. Properties of the type system are then derived from results on λ-nets.
BibTeX - Entry
@InProceedings{digianantonio_et_al:LIPIcs.TYPES.2021.5,
author = {Di Gianantonio, Pietro and Lenisa, Marina},
title = {{Principal Types as Lambda Nets}},
booktitle = {27th International Conference on Types for Proofs and Programs (TYPES 2021)},
pages = {5:1--5:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-254-9},
ISSN = {1868-8969},
year = {2022},
volume = {239},
editor = {Basold, Henning and Cockx, Jesper and Ghilezan, Silvia},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16774},
URN = {urn:nbn:de:0030-drops-167744},
doi = {10.4230/LIPIcs.TYPES.2021.5},
annote = {Keywords: Lambda calculus, Principal types, Linear logic, Lambda nets, Normalization, Cut elimination}
}
Keywords: |
|
Lambda calculus, Principal types, Linear logic, Lambda nets, Normalization, Cut elimination |
Collection: |
|
27th International Conference on Types for Proofs and Programs (TYPES 2021) |
Issue Date: |
|
2022 |
Date of publication: |
|
04.08.2022 |