[OOPSLA23] Mutually Iso-Recursive Subtyping скачать в хорошем качестве

[OOPSLA23] Mutually Iso-Recursive Subtyping

Mutually Iso-Recursive Subtyping (Video, OOPSLA2 2023) Andreas Rossberg (Independent Researcher, Munich, Germany) Abstract: Iso-recursive types are often taken as a type-theoretic model for type recursion as present in many programming languages, e.g., classes in object-oriented languages or algebraic datatypes in functional languages. Their main advantage over an equi-recursive semantics is that they are simpler and algorithmically less expensive, which is an important consideration when the cost of type checking matters, such as for intermediate or low-level code representations, virtual machines, or runtime casts. However, a closer look reveals that iso-recursion cannot, in its standard form, efficiently express essential type system features like mutual recursion or non-uniform recursion. While it has been folklore that mutual recursion and non-uniform type parameterisation can nicely be handled by generalising to higher kinds, this encoding breaks down when combined with subtyping: the classic “Amber” rule for subtyping iso-recursive types is too weak to express mutual recursion without falling back to encodings of quadratic size. We present a foundational core calculus of iso-recursive types with declared subtyping that can express both inter- and intra-recursion subtyping without such blowup, including subtyping between constructors of higher or mixed kind. In a second step, we identify a syntactic fragment of this general calculus that allows for more efficient type checking without “deep” substitutions, by observing that higher-kinded iso-recursive types can be inserted to “guard” against unwanted β-reductions. This fragment closely resembles the structure of typical nominal subtype systems, but without requiring nominal semantics. It has been used as the basis for a proposed extension of WebAssembly with recursive types. Article: https://doi.org/10.1145/3622809 ORCID: https://orcid.org/0000-0003-3137-3160 Video Tags: type systems, recursive types, subtyping, higher-order subtyping, oopslab23main-p150-p, doi:10.1145/3622809, orcid:0000-0003-3137-3160 Presentation at the OOPSLA2 2023 conference, October 22–27, 2023, https://2023.splashcon.org/track/spla... Sponsored by ACM SIGPLAN,