The calculus of Dependent Object Types (DOT) has enabled a more principled and robust implementation of Scala, but its support for type-level computation has proven insufficient. As a remedy, we propose F ·· ω , a rigorous theoretical foundation for Scala’s higher-kinded types. F ·· ω extends F <: ω with interval kinds , which afford a unified treatment of important type- and kind-level abstraction mechanisms found in Scala, such as bounded quantification, bounded operator abstractions, translucent type definitions and first-class subtyping constraints. The result is a flexible and general theory of higher-order subtyping. We prove type and kind safety of F ·· ω , as well as weak normalization of types and undecidability of subtyping. All our proofs are mechanized in Agda using a fully syntactic approach based on hereditary substitution.

@article{paperbot1133,
  title = {A theory of higher-order subtyping with type intervals},
  author = {Sandro Stucki and Paolo G. Giarrusso},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {5},
  number = {ICFP},
  year = {2021},
  doi = {10.1145/3473574}
}