DROPS

Document

Towards Strong Normalization for Dependent Object Types (DOT) (Artifact)

Authors: Fei Wang and Tiark Rompf

Published in: DARTS, Volume 3, Issue 2, Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract

This artifact provides the fully mechanized proof of strong normalization for D_{<:} , a variant of (Dependent Object Types) DOT (Rompf & Amin, 2016) that excludes recursive functions and recursive types. The intersection type and recursive self type are further integrated, moving towards DOT. The key proof idea follows the method of Girard (Girard, 1972) and Tait (Tait, 1967).

Cite as

Fei Wang and Tiark Rompf. Towards Strong Normalization for Dependent Object Types (DOT) (Artifact). In Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017). Dagstuhl Artifacts Series (DARTS), Volume 3, Issue 2, pp. 5:1-5:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{wang_et_al:DARTS.3.2.5,
  author =	{Wang, Fei and Rompf, Tiark},
  title =	{{Towards Strong Normalization for Dependent Object Types (DOT) (Artifact)}},
  pages =	{5:1--5:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2017},
  volume =	{3},
  number =	{2},
  editor =	{Wang, Fei and Rompf, Tiark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.3.2.5},
  URN =		{urn:nbn:de:0030-drops-72869},
  doi =		{10.4230/DARTS.3.2.5},
  annote =	{Keywords: Scala, DOT, strong normalization, logical relations, recursive types}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2017.27

Towards Strong Normalization for Dependent Object Types (DOT)

Authors: Fei Wang and Tiark Rompf

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)

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.

Cite as

Fei Wang and Tiark Rompf. Towards Strong Normalization for Dependent Object Types (DOT). In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 27:1-27:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ECOOP.2017.27,
  author =	{Wang, Fei and Rompf, Tiark},
  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 =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.27},
  URN =		{urn:nbn:de:0030-drops-72763},
  doi =		{10.4230/LIPIcs.ECOOP.2017.27},
  annote =	{Keywords: Scala, DOT, strong normalization, logical relations, recursive types}
}

Search Results

Documents authored by Wang, Fei

Towards Strong Normalization for Dependent Object Types (DOT) (Artifact)

Abstract

Cite as

Towards Strong Normalization for Dependent Object Types (DOT)

Abstract

Cite as

Thanks for your feedback!

Could not send message