A case for DOT: Theoretical Foundations for Objects with Pattern Matching and GADT-Style Reasoning

被引:3
作者
Boruch-Gruszecki, Aleksander [1 ]
Wasko, Radoslaw [2 ]
Xu, Yichen [3 ]
Parreaux, Lionel [4 ]
机构
[1] Ecole Polytech Fed Lausanne, Lausanne, Switzerland
[2] Univ Warsaw, Warsaw, Poland
[3] Beijing Univ Posts & Telecommun, Beijing, Peoples R China
[4] HKUST, Hong Kong, Peoples R China
来源
PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL | 2022年 / 6卷 / OOPSLA期
关键词
DOT; pattern matching; GADT; classes; type systems;
D O I
10.1145/3563342
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Many programming languages in the OO tradition now support pattern matching in some form. Historical examples include Scala and Ceylon, with the more recent additions of Java, Kotlin, TypeScript, and Flow. But pattern matching on generic class hierarchies currently results in puzzling type errors in most of these languages. Yet this combination of features occurs naturally in many scenarios, such as when manipulating typed ASTs. To support it properly, compilers needs to implement a form of subtyping reconstruction: the ability to reconstruct subtyping information uncovered at runtime during pattern matching. We introduce cDOT, a new calculus in the family of Dependent Object Types (DOT) intended to serve as a formal foundation for subtyping reconstruction. Being descended from pDOT, itself a formal foundation for Scala, cDOT can be used to encode advanced object-oriented features such as generic inheritance, type constructor variance, F-bounded polymorphism, and first-class recursive modules. We demonstrate that subtyping reconstruction subsumes GADTs by encoding lambda(2,G mu), a classical constraint-based GADT calculus, into cDOT.
引用
收藏
页数:30
相关论文
共 45 条
[1]  
Amin Nada, 2016, A List of Successes that can Change the World. Essays Dedicated to Philip Wadler on the Occasion of his 60th Birthday. LNCS 9600, P249, DOI 10.1007/978-3-319-30936-1_14
[2]  
Amin N, 2014, ACM SIGPLAN NOTICES, V49, P233, DOI [10.1145/2714064.2660216, 10.1145/2660193.2660216]
[3]  
Boruch-Gruszecki A, 2022, Arxiv, DOI [arXiv:2209.07427, 10.48550/arXiv.2209.07427, DOI 10.48550/ARXIV.2209.07427]
[4]  
Boruch-Gruszecki Aleksander, 2022, Zenodo, DOI 10.5281/ZENODO.7079463
[5]  
Boruch-Gruszecki Aleksander, 2017, Master's thesis, P27
[6]  
Boszormenyi Laszlo, 2012, Programming in Modula-3: an introduction in programming with style, P26
[7]   Making the future safe for the past:: Adding genericity to the Java']Java™ programming language [J].
Bracha, G ;
Odersky, M ;
Stoutamire, D ;
Wadler, P .
ACM SIGPLAN NOTICES, 1998, 33 (10) :183-200
[8]  
Canning P.S., 1989, P 4 INT C FUNCT PROG, P273, DOI DOI 10.1145/99370.99392
[9]   ON UNDERSTANDING TYPES, DATA ABSTRACTION, AND POLYMORPHISM. [J].
Cardelli, Luca ;
Wegner, Peter .
Computing surveys, 1985, 17 (04) :471-522
[10]   STITCH: The Sound Type-Indexed Type Checker (Functional Pearl) [J].
Eisenberg, Richard A. .
PROCEEDINGS OF THE 13TH ACM SIGPLAN INTERNATIONAL SYMPOSIUM ON HASKELL, HASKELL 2020, 2020, :39-53