Скачать или смотреть On Satisfiability of Nominal Subtyping with Variance

On Satisfiability of Nominal Subtyping with Variance by Aleksandr Misonizhnik, Dmitry Mordvinov

Nominal type systems with variance, a core of subtype relation in object-oriented programming languages like Java, C# and Scala, have been extensively studied by Kennedy and Pierce; they have shown the undecidability of the subtyping between ground types and proposed the decidable fragments of such type systems. However, precise intraprocedural analysis of object-oriented code may require a reasoning about the relations of open types. In this paper, we formalize and investigate the satisfiability problem for nominal subtyping with variance. We define the problem in the context of first-order logic. We show that, although the non-expansive ground nominal subtyping with variance is decidable, its satisfiability problem is undecidable. Our proof uses a remarkably small fragment of the type system. In fact, we demonstrate that even for the non-expansive class tables with only nullary and unary covariant and invariant type constructors, the satisfiability of quantifier-free conjunctions of positive subtyping atoms is undecidable.

Part of ECOOP 2019 https://2019.ecoop.org/
Video by PL Presents, follow us at   / plpresents