TY - GEN
T1 - Ecient type checking for path polymorphism
AU - Edi, Juan
AU - Viso, Andrés
AU - Bonelli, Eduardo
N1 - Publisher Copyright:
© Juan Edi, Andrés Viso, and Eduardo Bonelli; licensed under Creative Commons License CC-BY 21st International Conference on Types for Proofs and Programs (TYPES 2015).
PY - 2018/3/1
Y1 - 2018/3/1
N2 - A type system combining type application, constants as types, union types (associative, commutative and idempotent) and recursive types has recently been proposed for statically typing path polymorphism, the ability to define functions that can operate uniformly over recursively specified applicative data structures. A typical pattern such functions resort to is xy which decomposes a compound, in other words any applicative tree structure, into its parts. We study type-checking for this type system in two stages. First we propose algorithms for checking type equivalence and subtyping based on coinductive characterizations of those relations. We then formulate a syntax-directed presentation and prove its equivalence with the original one. This yields a type-checking algorithm which unfortunately has exponential time complexity in the worst case. A second algorithm is then proposed, based on automata techniques, which yields a polynomial-time type-checking algorithm.
AB - A type system combining type application, constants as types, union types (associative, commutative and idempotent) and recursive types has recently been proposed for statically typing path polymorphism, the ability to define functions that can operate uniformly over recursively specified applicative data structures. A typical pattern such functions resort to is xy which decomposes a compound, in other words any applicative tree structure, into its parts. We study type-checking for this type system in two stages. First we propose algorithms for checking type equivalence and subtyping based on coinductive characterizations of those relations. We then formulate a syntax-directed presentation and prove its equivalence with the original one. This yields a type-checking algorithm which unfortunately has exponential time complexity in the worst case. A second algorithm is then proposed, based on automata techniques, which yields a polynomial-time type-checking algorithm.
KW - Path polymorphism
KW - Pattern matching
KW - Type checking
KW - Λ-calculus
UR - http://www.scopus.com/inward/record.url?scp=85045451200&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045451200&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.TYPES.2015.6
DO - 10.4230/LIPIcs.TYPES.2015.6
M3 - Conference contribution
AN - SCOPUS:85045451200
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 61
EP - 623
BT - 21st International Conference on Types for Proofs and Programs, TYPES 2015
A2 - Uustalu, Tarmo
T2 - 21st International Conference on Types for Proofs and Programs, TYPES 2015
Y2 - 18 May 2015 through 21 May 2015
ER -