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.2017.27
URN: urn:nbn:de:0030-drops-72763
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7276/
Go to the corresponding LIPIcs Volume Portal

Wang, Fei ; Rompf, Tiark

Towards Strong Normalization for Dependent Object Types (DOT)

pdf-format:
LIPIcs-ECOOP-2017-27.pdf (0.7 MB)

Abstract

The Dependent Object Types (DOT) family of calculi has been proposed as a new theoretic foundation for Scala and similar languages, unifying functional programming, object oriented programming and ML-style module systems. Following the recent type soundness proof for
DOT, the present paper aims to establish stronger meta-theoretic properties. The main result is a fully mechanized proof of strong normalization for D_<:, a variant of DOT that excludes recursive functions and recursive types. We further discuss techniques and challenges for adding recursive types while maintaining strong normalization, and demonstrate that certain variants of recursive self types can be integrated successfully.

BibTeX - Entry

@InProceedings{wang_et_al:LIPIcs:2017:7276,
  author =	{Fei Wang and Tiark Rompf},
  title =	{{Towards Strong Normalization for Dependent Object Types (DOT)}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{27:1--27:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{Peter M{\"u}ller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7276},
  URN =		{urn:nbn:de:0030-drops-72763},
  doi =		{10.4230/LIPIcs.ECOOP.2017.27},
  annote =	{Keywords: Scala, DOT, strong normalization, logical relations, recursive types}
}

Keywords: Scala, DOT, strong normalization, logical relations, recursive types
Collection: 31st European Conference on Object-Oriented Programming (ECOOP 2017)
Issue Date: 2017
Date of publication: 16.06.2017

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