License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2015.6
URN: urn:nbn:de:0030-drops-84761
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8476/
Go to the corresponding LIPIcs Volume Portal

Edi, Juan ; Viso, Andrés ; Bonelli, Eduardo

Efficient Type Checking for Path Polymorphism

pdf-format:
LIPIcs-TYPES-2015-6.pdf (0.7 MB)

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 \dataterm{x}{y} 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.

BibTeX - Entry

@InProceedings{edi_et_al:LIPIcs:2018:8476,
  author =	{Juan Edi and Andr{\'e}s Viso and Eduardo Bonelli},
  title =	{{Efficient Type Checking for Path Polymorphism}},
  booktitle =	{21st International Conference on Types for Proofs and Programs (TYPES 2015)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-030-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{69},
  editor =	{Tarmo Uustalu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8476},
  URN =		{urn:nbn:de:0030-drops-84761},
  doi =		{10.4230/LIPIcs.TYPES.2015.6},
  annote =	{Keywords: lambda-calculus, pattern matching, path polymorphism, type checking}
}

Keywords: lambda-calculus, pattern matching, path polymorphism, type checking
Collection: 21st International Conference on Types for Proofs and Programs (TYPES 2015)
Issue Date: 2018
Date of publication: 15.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI