Dependent Object Types (DOT) is intended to be a core calculus for modelling Scala. Its distinguishing feature is abstract type members, fields in objects that hold types rather than values. Proving soundness of DOT has been surprisingly challenging, and existing proofs are complicated, and reason about multiple concepts at the same time (e.g. types, values, evaluation). To serve as a core calculus for Scala, DOT should be easy to experiment with and extend, and therefore its soundness proof needs to be easy to modify. This paper presents a simple and modular proof strategy for reasoning in DOT. The strategy separates reasoning about types from other concerns. It is centred around a theorem that connects the full DOT type system to a restricted variant in which the challenges and paradoxes caused by abstract type members are eliminated. Almost all reasoning in the proof is done in the intuitive world of this restricted type system. Once we have the necessary results about types, we observe that the other aspects of DOT are mostly standard and can be incorporated into a soundness proof using familiar techniques known from other calculi. Our paper comes with a machine-verified version of the proof in Coq. admits typings that seem just plain wrong, and give no hope for soundness, so it seems necessary to have lemmas that reason simultaneously about the intricate properties of values, types, and the environments that they inhabit. A core calculus needs to be easy to extend. Some extensions of DOT are necessary even just to model essential Scala features. As a prominent example, types in Scala may depend on paths x .a 1 .···.a n .A (where x is a variable, a i are fields, and A is a type member), but types in the existing DOT calculi can depend only directly on variables (x .A). Path-dependent types are needed to model essential features such as classes and traits (as members nested in objects and packages) and the famous cake pattern [Odersky and Zenger 2005] . Another important Scala feature to be studied in DOT are implicit parameters. Moreover, language modifications and extensions are the raison d'être of a core calculus. DOT enables designers to experiment with exciting new features that can be added to Scala, to tweak them and reason about their properties before attempting to integrate them in the compiler with the complexity of the full Scala language. The complexity of the proof is a hindrance to such extension and experimentation. Over the past ten years, DOT has been designed and re-designed to be just right, so that the brilliant lemmas that ensure its soundness hold and can be proven. When the DOT calculus is disrupted by a modification, it is difficult to predict which parts of the proof will be affected. Experimenting with modifications to DOT is difficult because each tweak requires many lemmas to be re-proven. Our goal in this paper is a soundness proof that is simpler, more modular, and more intuitive. We aim to separate the concepts of types, values, and operational semantics, and to reason about one concept at a time. Then, if a language extension modifies only one concept, such as typing, the necessary changes are localized to the parts of the proof that deal with types. We also aim to isolate most of the reasoning in a simpler system that is immune to the paradox of bad bounds, the key challenge that plagued the long search for a soundness proof. In this system, our reasoning can rely on intuitive notions from familiar object calculi without dependent object types [Abadi and Cardelli 1996; Pierce 2002] . The results of this reasoning are lifted to the full DOT type system by a single, simple theorem. The main focus of our proof is on types. Dependent object types are the one feature that distinguishes DOT, so we aim to decouple that one feature, which mainly affects the static type system, from other concerns. We focus on proving the properties that one expects of types, and deliberately keep the proof independent of other aspects, such as operational semantics and runtime values, which are similar in DOT as in other object calculi. Of course, a soundness proof must eventually speak about execution and values, but once we have the necessary theory to reason about types, these other concerns can be handled separately, at the end of the proof, using standard proof techniques. Our final soundness theorem is stated for the small-step operational semantics given by , but that is only the final conclusion; the theory that we develop about dependent object types would be equally applicable in a proof for a big-step operational semantics. In a sense, this paper moves in the opposite direction compared to other recent work related to DOT: this paper aims for a simpler proof of one specific calculus, while other work generalizes DOT with features from other calculi. The most significant addition in is subtyping between recursive types, which requires sophisticated proof techniques and induction schemes, but is not needed to model Scala. Amin and Rompf [2017] focuses on a family of calculi with some features similar to those in DOT, and on general proof techniques applicable to the whole family. While it is useful to generalize and compare DOT to other calculi, that is not the topic of this paper. This paper focuses inwards, on DOT itself, on only those features of DOT that are necessary for modelling Scala, with an aim to make the soundness proof of those specific features as simple and modular as possible.
So far, work on the DOT calculi mainly focused on soundness proofs REF .
A simple soundness proof for dependent object types
PACMPL
Computer Science