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.2022.18
URN: urn:nbn:de:0030-drops-162463
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16246/
Fan, Andong ;
Huang, Xuejing ;
Xu, Han ;
Sun, Yaozhu ;
Oliveira, Bruno C. d. S.
Direct Foundations for Compositional Programming
Abstract
The recently proposed CP language adopts Compositional Programming: a new modular programming style that solves challenging problems such as the Expression Problem. CP is implemented on top of a polymorphic core language with disjoint intersection types called ?_{i}^{+}. The semantics of ?_{i}^{+} employs an elaboration to a target language and relies on a sophisticated proof technique to prove the coherence of the elaboration. Unfortunately, the proof technique is technically challenging and hard to scale to many common features, including recursion or impredicative polymorphism. Thus, the original formulation of ?_{i}^{+} does not support the two later features, which creates a gap between theory and practice, since CP fundamentally relies on them.
This paper presents a new formulation of ?_{i}^{+} based on a type-directed operational semantics (TDOS). The TDOS approach was recently proposed to model the semantics of languages with disjoint intersection types (but without polymorphism). Our work shows that the TDOS approach can be extended to languages with disjoint polymorphism and model the full ?_{i}^{+} calculus. Unlike the elaboration semantics, which gives the semantics to ?_{i}^{+} indirectly via a target language, the TDOS approach gives a semantics to ?_{i}^{+} directly. With a TDOS, there is no need for a coherence proof. Instead, we can simply prove that the semantics is deterministic. The proof of determinism only uses simple reasoning techniques, such as straightforward induction, and is able to handle problematic features such as recursion and impredicative polymorphism. This removes the gap between theory and practice and validates the original proofs of correctness for CP. We formalized the TDOS variant of the ?_{i}^{+} calculus and all its proofs in the Coq proof assistant.
BibTeX - Entry
@InProceedings{fan_et_al:LIPIcs.ECOOP.2022.18,
author = {Fan, Andong and Huang, Xuejing and Xu, Han and Sun, Yaozhu and Oliveira, Bruno C. d. S.},
title = {{Direct Foundations for Compositional Programming}},
booktitle = {36th European Conference on Object-Oriented Programming (ECOOP 2022)},
pages = {18:1--18:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-225-9},
ISSN = {1868-8969},
year = {2022},
volume = {222},
editor = {Ali, Karim and Vitek, Jan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16246},
URN = {urn:nbn:de:0030-drops-162463},
doi = {10.4230/LIPIcs.ECOOP.2022.18},
annote = {Keywords: Intersection types, disjoint polymorphism, operational semantics}
}
