Ecient type checking for path polymorphism

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 applicativ...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2018
Materias:	Path polymorphism Pattern matching Type checking Λ-calculus Calculations Differentiation (calculus) Polynomial approximation Trees (mathematics) Exponential time complexity Polynomial-time Recursive types Tree structures Type equivalence Type systems Typechecking Typical patterns Computer programming languages
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18688969_v69_n_p61_Edi http://hdl.handle.net/20.500.12110/paper_18688969_v69_n_p61_Edi
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_18688969_v69_n_p61_Edi
record_format	dspace
spelling	paper:paper_18688969_v69_n_p61_Edi2023-06-08T16:29:53Z Ecient type checking for path polymorphism Path polymorphism Pattern matching Type checking Λ-calculus Calculations Differentiation (calculus) Pattern matching Polynomial approximation Trees (mathematics) Exponential time complexity Polynomial-time Recursive types Tree structures Type equivalence Type systems Typechecking Typical patterns Computer programming languages 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. © 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). 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18688969_v69_n_p61_Edi http://hdl.handle.net/20.500.12110/paper_18688969_v69_n_p61_Edi
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Path polymorphism Pattern matching Type checking Λ-calculus Calculations Differentiation (calculus) Pattern matching Polynomial approximation Trees (mathematics) Exponential time complexity Polynomial-time Recursive types Tree structures Type equivalence Type systems Typechecking Typical patterns Computer programming languages
spellingShingle	Path polymorphism Pattern matching Type checking Λ-calculus Calculations Differentiation (calculus) Pattern matching Polynomial approximation Trees (mathematics) Exponential time complexity Polynomial-time Recursive types Tree structures Type equivalence Type systems Typechecking Typical patterns Computer programming languages Ecient type checking for path polymorphism
topic_facet	Path polymorphism Pattern matching Type checking Λ-calculus Calculations Differentiation (calculus) Pattern matching Polynomial approximation Trees (mathematics) Exponential time complexity Polynomial-time Recursive types Tree structures Type equivalence Type systems Typechecking Typical patterns Computer programming languages
description	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. © 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).
title	Ecient type checking for path polymorphism
title_short	Ecient type checking for path polymorphism
title_full	Ecient type checking for path polymorphism
title_fullStr	Ecient type checking for path polymorphism
title_full_unstemmed	Ecient type checking for path polymorphism
title_sort	ecient type checking for path polymorphism
publishDate	2018
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_18688969_v69_n_p61_Edi http://hdl.handle.net/20.500.12110/paper_18688969_v69_n_p61_Edi
_version_	1768545025285685248

Ecient type checking for path polymorphism

Ejemplares similares