Abstract

The Amber rules are well-known and widely used for subtyping iso-recursive types. They were first briefly and informally introduced in 1985 by Cardelli in a manuscript describing the Amber language. Despite their use over many years, important aspects of the metatheory of the iso-recursive style Amber rules have not been studied in depth or turn out to be quite challenging to formalize.

This paper aims to revisit the problem of subtyping iso-recursive types. We start by introducing a novel declarative specification for Amber-style iso-recursive subtyping. Informally, the specification states that two recursive types are subtypesif all their finite unfoldings are subtypes. The Amber rules are shown to be sound and complete with respect to this declarative specification. We then show another sound,complete and decidable algorithmic formulation of subtyping that employs a novel double unfolding rule. Compared to the Amber rules, the double unfolding rule has the advantage of: 1) being modular; 2) not requiring reflexivity tobe built in; and 3) leading to an easy proof of transitivity of subtyping.

This work sheds new insights on the theory of subtyping iso-recursive types, and the new double unfolding rule has important advantages over the original Amber rules for both implementations and metatheoretical studies involving recursive types. All results are mechanically formalized in the Coq theorem prover.

This is an expanded version of the OOPSLA’20 paper