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

Huang, Xuejing ; Oliveira, Bruno C. d. S.

A Type-Directed Operational Semantics For a Calculus with a Merge Operator

pdf-format:
LIPIcs-ECOOP-2020-26.pdf (0.7 MB)

Abstract

Calculi with disjoint intersection types and a merge operator provide general mechanisms that can subsume various other features. Such calculi can also encode highly dynamic forms of object composition, which capture common programming patterns in dynamically typed languages (such as JavaScript) in a fully statically typed manner. Unfortunately, unlike many other foundational calculi (such as System F, System F_{< :} or Featherweight Java), recent calculi with the merge operator lack a (direct) operational semantics with standard and expected properties such as determinism and subject-reduction. Furthermore the metatheory for such calculi can only account for terminating programs, which is a significant restriction in practice.
This paper proposes a type-directed operational semantics (TDOS) for λ_i^{:}: a calculus with intersection types and a merge operator. The calculus is inspired by two closely related calculi by Dunfield (2014) and Oliveira et al. (2016). Although Dunfield proposes a direct small-step semantics for her calculus, her semantics lacks both determinism and subject-reduction. Using our TDOS we obtain a direct semantics for λ_i^{:} that has both properties. To fully obtain determinism, the λ_i^{:} calculus employs a disjointness restriction proposed in Oliveira et al.’s λ_i calculus. As an added benefit the TDOS approach deals with recursion in a straightforward way, unlike λ_i and subsequent calculi where recursion is problematic. To further relate λ_i^{:} to the calculi by Dunfield and Oliveira et al. we show two results. Firstly, the semantics of λ_i^{:} is sound with respect to Dunfield’s small-step semantics. Secondly, we show that the type system of λ_i^{:} is complete with respect to the λ_i type system. All results have been fully formalized in the Coq theorem prover.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2020:13183,
  author =	{Xuejing Huang and Bruno C. d. S. Oliveira},
  title =	{{A Type-Directed Operational Semantics For a Calculus with a Merge Operator}},
  booktitle =	{34th European Conference on Object-Oriented Programming (ECOOP 2020)},
  pages =	{26:1--26:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-154-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{166},
  editor =	{Robert Hirschfeld and Tobias Pape},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13183},
  URN =		{urn:nbn:de:0030-drops-131832},
  doi =		{10.4230/LIPIcs.ECOOP.2020.26},
  annote =	{Keywords: operational semantics, type systems, intersection types}
}

Keywords: operational semantics, type systems, intersection types
Collection: 34th European Conference on Object-Oriented Programming (ECOOP 2020)
Issue Date: 2020
Date of publication: 06.11.2020
Supplementary Material: ECOOP 2020 Artifact Evaluation approved artifact available at https://doi.org/10.4230/DARTS.6.2.9. https://github.com/XSnow/ECOOP2020

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