Ecient type checking for path polymorphism

Juan Edi, Andrés Viso, Eduardo Bonelli

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication21st International Conference on Types for Proofs and Programs, TYPES 2015
EditorsTarmo Uustalu
Pages61-623
Number of pages563
ISBN (Electronic)9783959770309
DOIs
StatePublished - 1 Mar 2018
Event21st International Conference on Types for Proofs and Programs, TYPES 2015 - Tallinn, Estonia
Duration: 18 May 201521 May 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume69
ISSN (Print)1868-8969

Conference

Conference21st International Conference on Types for Proofs and Programs, TYPES 2015
Country/TerritoryEstonia
CityTallinn
Period18/05/1521/05/15

Keywords

  • Path polymorphism
  • Pattern matching
  • Type checking
  • Λ-calculus

Fingerprint

Dive into the research topics of 'Ecient type checking for path polymorphism'. Together they form a unique fingerprint.

Cite this