On type safety for core Scala: "From F to DOT: Type Soundness Proofs with Definitional Interpreters"
From F to DOT: Type Soundness Proofs with Definitional Interpreters by Tiark Rompf and Nada Amin:
Scala's type system unifies aspects of ML-style module systems, object-oriented, and functional programming paradigms. The DOT (Dependent Object Types) family of calculi has been proposed as a new theoretic foundation for Scala and similar expressive languages. Unfortunately, type soundness has only been established for a very restricted subset of DOT (muDOT), and it has been shown that adding important Scala features such as type refinement or extending subtyping to a lattice breaks at least one key metatheoretic property such as narrowing or subtyping transitivity, which are usually required for a type soundness proof.
The first main contribution of this paper is to demonstrate how, perhaps surprisingly, even though these properties are lost in their full generality, a richer DOT calculus that includes both type refinement and a subtyping lattice with intersection types can still be proved sound. The key insight is that narrowing and subtyping transitivity only need to hold for runtime objects, but not for code that is never executed. Alas, the dominant method of proving type soundness, Wright and Felleisen's syntactic approach, is based on term rewriting, which does not make an adequate distinction between runtime and type assignment time.
The second main contribution of this paper is to demonstrate how type soundness proofs for advanced, polymorphic, type systems can be carried out with an operational semantics based on high-level, definitional interpreters, implemented in Coq. We present the first mechanized soundness proof for System F<: based on a definitional interpreter. We discuss the challenges that arise in this setting, in particular due to abstract types, and we illustrate in detail how DOT-like calculi emerge from straightforward generalizations of the operational aspects of F<:.
Not only they solve a problem that has been open for 12 years, but they also deploy interesting techniques to make the proof possible and simple. As they write themselves, that includes the first type-soundness proof for F<: using definitional interpreters — that is, at least according to some, denotational semantics.
I am looking at the recursion-schemes package (not for the first time), and would like to improve my understanding of some things:
Mu and Nu are supposed to be the least and greatest fixed points, respectively, yet they both have both Foldable and Unfoldable instances. Is it the case that if you wanted to consistently distinguish between data and codata, that you would then only have Foldable (Mu f) and Unfoldable (Nu f), but not vice versa?
How come there are three? Does Fix correspond to Mu or to Nu... or, somehow, to both, or neither? (Is there a fourth hanging out somewhere offstage?)
I notice that if you write data ListF a x = Nil | Cons a x and plug that into Fix, you get a potentially-infinite list: "codata", while if you use data ListF' a x = Nil' | Cons' a !x, you get a strictly-finite list: "data". Does the strictness of the recursive position always determine whether the result is data or codata? What if I do something silly like data WeirdTreeF a x = Leaf | Branch x a !x, where it's heterogenous?
What if I plug those into Mu and Nu? Is data-vs.-codataness determined by the fixed point operator, or by the base functor?
Is there a word (instead of "data-vs.-codataness") to encompass data and codata, in the way that "color" is a word to encompass red and green, or "polarity" is for positive and negative?
[link] [13 comments]