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.ECOOP.2023.17
URN: urn:nbn:de:0030-drops-182109
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18210/
Go to the corresponding LIPIcs Volume Portal

Madsen, Magnus ; Starup, Jonathan Lindegaard ; Lutze, Matthew

Restrictable Variants: A Simple and Practical Alternative to Extensible Variants

pdf-format:
LIPIcs-ECOOP-2023-17.pdf (1 MB)

Abstract

We propose restrictable variants as a simple and practical alternative to extensible variants. Restrictable variants combine nominal and structural typing: a restrictable variant is an algebraic data type indexed by a type-level set formula that captures its set of active labels. We introduce new pattern-matching constructs that allows programmers to write functions that only match on a subset of variants, i.e., pattern-matches may be non-exhaustive. We then present a type system for restrictable variants which ensures that such non-exhaustive matches cannot get stuck at runtime.
An essential feature of restrictable variants is that the type system can capture structure-preserving transformations: specifically the introduction and elimination of variants. This property is important for writing reusable functions, yet many row-based extensible variant systems lack it.
In this paper, we present a calculus with restrictable variants, two partial pattern-matching constructs, and a type system that ensures progress and preservation. The type system extends Hindley-Milner with restrictable variants and supports type inference with an extension of Algorithm W with Boolean unification. We implement restrictable variants as an extension of the Flix programming language and conduct a few case studies to illustrate their practical usefulness.

BibTeX - Entry

@InProceedings{madsen_et_al:LIPIcs.ECOOP.2023.17,
  author =	{Madsen, Magnus and Starup, Jonathan Lindegaard and Lutze, Matthew},
  title =	{{Restrictable Variants: A Simple and Practical Alternative to Extensible Variants}},
  booktitle =	{37th European Conference on Object-Oriented Programming (ECOOP 2023)},
  pages =	{17:1--17:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-281-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{263},
  editor =	{Ali, Karim and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18210},
  URN =		{urn:nbn:de:0030-drops-182109},
  doi =		{10.4230/LIPIcs.ECOOP.2023.17},
  annote =	{Keywords: restrictable variants, extensible variants, refinement types, Boolean unification}
}

Keywords: restrictable variants, extensible variants, refinement types, Boolean unification
Collection: 37th European Conference on Object-Oriented Programming (ECOOP 2023)
Issue Date: 2023
Date of publication: 11.07.2023
Supplementary Material: Software (ECOOP 2023 Artifact Evaluation approved artifact): https://doi.org/10.4230/DARTS.9.2.12

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