Recursive types, generics, and subtyping are all essential features for modern programming languages, such as Go, Rust, TypeScript and Java. However, their combination is difficult to manage. The LASIGE researcher Andreia Mordido is part of the international team that studied the interaction of these features. The work will be presented at the 51st ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2024), a top-tier conference on programming languages. The paper, titled “Parametric Subtyping for Structural Parametric Polymorphism”, is available here.

In this paper, the authors describe a notion of parametricity for type constructors and define a conceptually simple, decidable, and expressive fragment of structural subtyping, called parametric subtyping. The paper also presents an effective decision procedure for parametric subtyping that is proved to be correct.