<figure><img src="image_1.png" /></figure>

HAL
open science

# Definitional Factoriality for Dependent (Sub)Types

Théo Laurent, Meven Lennon-Bertrand, Kenji Maillard

► To cite this version:

Théo Laurent, Meven Lennon-Bertrand, Kenji Maillard. Definitional Factoriality for Dependent (Sub)Types. 2023. hal-04160858v3

HAL Id: hal-04160858

https://hal.science/hal-04160858v3

Preprint submitted on 8 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Definitional Functionality for Dependent (Sub)Types – Extended version

THÉO LAURENT, Inria, France

MEVEN LENNON-BERTRAND, University of Cambridge, United Kingdom

KENJI MAILLARD, Gallinette Project Team, Inria, France

Dependently typed proof assistant rely crucially on definitional equality, which relates types and terms that are automatically identified in the underlying type theory. This paper extends type theory with definitional functor laws, equations satisfied propositionally by a large class of container-like type constructors $F$: Type $\rightarrow$ Type, equipped with a map$_F$:($A \rightarrow B) \rightarrow F A \rightarrow F B$, such as lists or trees. Promoting these equations to definitional ones strengthens the theory, enabling slicker proofs and more automation for functorial type constructors. This extension is used to modularly justify a structural form of coercive subtyping, propagating subtyping through type formers in a map-like fashion. We show that the resulting notion of coercive subtyping, thanks to the extra definitional equations, is equivalent to a natural and implicit form of subsumptive subtyping. The key result of decidability of type-checking in a dependent type system with functor laws for lists has been entirely mechanized in Coq.

This is the extended version of [34].

Additional Key Words and Phrases: Subtyping, Dependent types, Bidirectional typing, Logical relation.

## 1 INTRODUCTION

Dependent type theory is the foundation of many proof assistants: Coq [56], Lean [45], Agda [5], Idris [14], F* [54]. At its heart lies definitional equality, an equational theory that is automatically decided by the implementation of these proof systems. The more expressive definitional equality is, the less work is requested from users to identify objects. However, there is a fundamental tension at play: making the equational theory too rich leads to both practical and theoretical issues, the most prominent one being the undecidability of definitional equality. This default plagues the otherwise appealing Extensional Type Theory (ETT) [41], a type theory which makes every provable equality definitional, thus making ETT rather impractical as a basis for a proof assistant [15]. As a result, to design usable proof assistants we need to carve out a well-behaved equational theory, that strikes the right balance between expressivity and decidability. In this paper, we show that we can maintain this subtle balance while extending intensional type theory with map operations making the functorial character of type formers explicit, and satisfying definitional functor laws. We prove in particular that definitional equality and type-checking remain decidable in this extension, that we dub MLTT$_{map}$.

The map primitives introduced in MLTT$_{map}$ have a computational behaviour reminiscent of structural subtyping, which propagates existing subtyping structurally through type-formers, and should satisfy reflexivity and transitivity laws similar to the functor laws. Guided by the design of MLTT$_{map}$, we devise a second system, MLTT$_{coe}$, with explicit coercions witnessing structural subtyping. To gauge the expressivity of MLTT$_{coe}$, we relate it to a third system, MLTT$_{sub}$, where subtyping is implicit, as users of a type system should expect. A simple translation $|\cdot|$ from MLTT$_{coe}$ to MLTT$_{sub}$ erases coercions. We show that this erasure can be inverted, elaborating coercions back.

Authors' addresses: Théo Laurent, theo.laurent@inria.fr, Inria, Paris, France; Meven Lennon-Bertrand, Meven.Lennon-Bertrand@cl.cam.ac.uk, University of Cambridge, Cambridge, United Kingdom; Kenji Maillard, kenji.maillard@inria.fr, Gallinette Project Team, Inria, Nantes, France.

<figure><img src="image_1.png" /></figure>
# Definitional Functionality for Dependent (Sub)Types – Extended version

THÉO LAURENT, Inria, France

MEVEN LENNON-BERTRAND, University of Cambridge, United Kingdom

KENJI MAILLARD, Gallinette Project Team, Inria, France

Dependently typed proof assistant rely crucially on definitional equality, which relates types and terms that are automatically identified in the underlying type theory. This paper extends type theory with definitional functor laws, equations satisfied propositionally by a large class of container-like type constructors $F$: Type $\rightarrow$ Type, equipped with a map$_F$:($A \rightarrow B) \rightarrow F A \rightarrow F B$, such as lists or trees. Promoting these equations to definitional ones strengthens the theory, enabling slicker proofs and more automation for functorial type constructors. This extension is used to modularly justify a structural form of coercive subtyping, propagating subtyping through type formers in a map-like fashion. We show that the resulting notion of coercive subtyping, thanks to the extra definitional equations, is equivalent to a natural and implicit form of subsumptive subtyping. The key result of decidability of type-checking in a dependent type system with functor laws for lists has been entirely mechanized in Coq.

This is the extended version of [34].

Additional Key Words and Phrases: Subtyping, Dependent types, Bidirectional typing, Logical relation.

## 1 INTRODUCTION

Dependent type theory is the foundation of many proof assistants: Coq [56], Lean [45], Agda [5], Idris [14], F* [54]. At its heart lies definitional equality, an equational theory that is automatically decided by the implementation of these proof systems. The more expressive definitional equality is, the less work is requested from users to identify objects. However, there is a fundamental tension at play: making the equational theory too rich leads to both practical and theoretical issues, the most prominent one being the undecidability of definitional equality. This default plagues the otherwise appealing Extensional Type Theory (ETT) [41], a type theory which makes every provable equality definitional, thus making ETT rather impractical as a basis for a proof assistant [15]. As a result, to design usable proof assistants we need to carve out a well-behaved equational theory, that strikes the right balance between expressivity and decidability. In this paper, we show that we can maintain this subtle balance while extending intensional type theory with map operations making the functorial character of type formers explicit, and satisfying *definitional functor laws*. We prove in particular that definitional equality and type-checking remain decidable in this extension, that we dub MLTT$_{map}$.

The map primitives introduced in MLTT$_{map}$ have a computational behaviour reminiscent of *structural subtyping*, which propagates existing subtyping structurally through type-formers, and should satisfy reflexivity and transitivity laws similar to the functor laws. Guided by the design of MLTT$_{map}$, we devise a second system, MLTT$_{coe}$, with explicit coercions witnessing structural subtyping. To gauge the expressivity of MLTT$_{coe}$, we relate it to a third system, MLTT$_{sub}$, where subtyping is implicit, as users of a type system should expect. A simple translation $|\cdot|$ from MLTT$_{coe}$ to MLTT$_{sub}$ erases coercions. We show that this erasure can be inverted, elaborating coercions back.

Authors’ addresses: Théo Laurent, theo.laurent@inria.fr, Inria, Paris, France; Meven Lennon-Bertrand, Meven.Lennon-Bertrand@cl.cam.ac.uk, University of Cambridge, Cambridge, United Kingdom; Kenji Maillard, kenji.maillard@inria.fr, Gallinette Project Team, Inria, Nantes, France.

<figure><img src="image_3.png" /></figure>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Relation between MLTT, MLTT<sub>map</sub>, MLTT<sub>coe</sub> and MLTT<sub>sub</sub>. Arrows denote type-and-conversion-preserving translations between type theories.¹</figcaption></figure>

For this to be type preserving, it is crucial that MLTT<sub>coe</sub> satisfies our new definitional equalities, which allows us to reflect the equations implicitly satisfied in MLTT<sub>sub</sub> due to coercions being transparent. Fig. 1 synthesizes the three theories that we introduce and their relationships. They all extend Martin-Löf Type Theory (MLTT) [41]. Let us now explore in more detail these three systems.

*Functors and Their Laws.* The notion of functor is pervasive both in mathematics [40] and functional programming [36], capturing the concept of a parametrized construction applying to objects and their transformations. Reformulated in type theory, a type former $F : \text{dom}(F) \to \text{Type}$ is a functor when it is equipped with an operation $\text{map}_F : F A \to F B$ for any morphism $f : \text{hom}_F(A, B)$ between two objects $A, B$ in the domain $\text{dom}(F)$ of $F$. Here, $\text{dom}(F)$ must be endowed with the structure of a category<fnref n="2" />, with specified composition $\circ^F$ and identities $\text{id}^F$, and $\text{map}_F$ must preserve those:

$$ \text{map}_F \text{id}^F = \text{id} \qquad (\text{id-eq}) $$

$$ (\text{map}_F f) \circ (\text{map}_F g) = \text{map}_F (f \circ^F g) \qquad (\text{comp-eq}) $$

These two equations are known as the *functor laws*. For many container-like functors, such as *List A*, lists of elements taken in a type *A*, a map function can be defined in vanilla type theory such that these equations can be shown *propositionally*, e.g. by induction. Such propositional equations need however to be used explicitly, putting an extra burden on users and possibly causing coherence issues typical when working with propositional equalities [57]. This is not acceptable: such simple and natural identifications should hold definitionally!

*Example 1.1 (Representation Change).* Consider a dataset of pairs of a number and a boolean, represented as a list. For compatibility purpose, we may need to embed these pairs into a larger dataset using

$$ \begin{gathered} \text{glue} (r : \{a : \mathbf{N}; b : \mathbf{B}\}) : \{x : \mathbf{B}; y : \mathbf{N}; z : \mathbf{N}\} \stackrel{\text{def}}{=} \\ \{x := r.b; y := r.a; z := \text{if } r.b \text{ then } r.a \text{ else } 42\}. \end{gathered} $$

Going from one dataset to the other amounts to mapping either glue or its left inverse glue_retr, which forgets the extra field:

$$ \begin{aligned} \text{map}_{\text{List}} \text{ glue} & : \text{List} \{a : \mathbf{N}; b : \mathbf{B}\} \to \text{List} \{x : \mathbf{B}; y : \mathbf{N}; z : \mathbf{N}\}, \\ \text{map}_{\text{List}} \text{ glue\_retr} & : \text{List} \{x : \mathbf{B}; y : \mathbf{N}; z : \mathbf{N}\} \to \text{List} \{a : \mathbf{N}; b : \mathbf{B}\}. \end{aligned} $$

<footnote n="2">²Morphisms $\text{hom}_F(A, B)$ in $\text{dom}(F)$ are not constrained to be type theoretic functions. Accordingly, composition need not to be literally the composition of functions and the specified identities can differ from the identity $\lambda x.x$.</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 1. Relation between MLTT, MLTT<sub>map</sub>, MLTT<sub>coe</sub> and MLTT<sub>sub</sub>. Arrows denote type-and-conversion-preserving translations between type theories.¹</figcaption></figure>

For this to be type preserving, it is crucial that MLTT<sub>coe</sub> satisfies our new definitional equalities, which allows us to reflect the equations implicitly satisfied in MLTT<sub>sub</sub> due to coercions being transparent. Fig. 1 synthesizes the three theories that we introduce and their relationships. They all extend Martin-Löf Type Theory (MLTT) [41]. Let us now explore in more detail these three systems.

*Functors and Their Laws.* The notion of functor is pervasive both in mathematics [40] and functional programming [36], capturing the concept of a parametrized construction applying to objects and their transformations. Reformulated in type theory, a type former $F : \text{dom}(F) \to \text{Type}$ is a functor when it is equipped with an operation $\text{map}_F : F A \to F B$ for any morphism $f : \text{hom}_F(A, B)$ between two objects $A, B$ in the domain $\text{dom}(F)$ of $F$. Here, $\text{dom}(F)$ must be endowed with the structure of a category<fnref n="2" />, with specified composition $\circ^F$ and identities $\text{id}^F$, and $\text{map}_F$ must preserve those:

$$ \text{map}_F \text{id}^F = \text{id} \qquad (\text{id-eq}) $$

$$ (\text{map}_F f) \circ (\text{map}_F g) = \text{map}_F (f \circ^F g) \qquad (\text{comp-eq}) $$

These two equations are known as the *functor laws*. For many container-like functors, such as *List A*, lists of elements taken in a type *A*, a map function can be defined in vanilla type theory such that these equations can be shown *propositionally*, e.g. by induction. Such propositional equations need however to be used explicitly, putting an extra burden on users and possibly causing coherence issues typical when working with propositional equalities [57]. This is not acceptable: such simple and natural identifications should hold definitionally!

*Example 1.1 (Representation Change).* Consider a dataset of pairs of a number and a boolean, represented as a list. For compatibility purpose, we may need to embed these pairs into a larger dataset using

$$ \begin{gathered} \text{glue} (r : \{a : \mathbf{N}; b : \mathbf{B}\}) : \{x : \mathbf{B}; y : \mathbf{N}; z : \mathbf{N}\} \stackrel{\text{def}}{=} \\ \{x := r.b; y := r.a; z := \text{if } r.b \text{ then } r.a \text{ else } 42\}. \end{gathered} $$

Going from one dataset to the other amounts to mapping either glue or its left inverse glue_retr, which forgets the extra field:

$$ \begin{aligned} \text{map}_{\text{List}} \text{ glue} & : \text{List} \{a : \mathbf{N}; b : \mathbf{B}\} \to \text{List} \{x : \mathbf{B}; y : \mathbf{N}; z : \mathbf{N}\}, \\ \text{map}_{\text{List}} \text{ glue\_retr} & : \text{List} \{x : \mathbf{B}; y : \mathbf{N}; z : \mathbf{N}\} \to \text{List} \{a : \mathbf{N}; b : \mathbf{B}\}. \end{aligned} $$

<footnote n="2">²Morphisms $\text{hom}_F(A, B)$ in $\text{dom}(F)$ are not constrained to be type theoretic functions. Accordingly, composition need not to be literally the composition of functions and the specified identities can differ from the identity $\lambda x.x$.</footnote>
If the functor laws only hold propositionally, each consecutive simplification of back and forth changes of representation needs to be explicitly lifted to lists, and applied. The uncontrolled accumulation of repetitive proof steps, even as simple as these, can quickly burden proof development. In presence of definitional functor laws, instead, any sequence of representation changes will reduce to a single $map_{List}$: the boilerplate of explicitly manipulating the functor laws is handled automatically by the type theory. Moreover, observe that in this example the retraction $glue_retr \circ glue \cong$ id is definitional thanks to surjective pairing. Combined with definitional functor laws, the following simplification step is discharged automatically by the type-checker:<fnref n="3" />

$$map_{List} glue_retr (map_{List} glue l) \cong map_{List} id l \cong l$$

Note that these equations are valid in any context, in particular under binders, whereas for propositional identifications, rewriting under binders is only possible in presence of the additional axiom of function extensionality.

**Example 1.2 (Coherence of Coercions).** Proof assistants may provide the ability for users to declare automatically-inserted functions acting as glue code (coercions in COQ, instance arguments in AGDA, has_coe typeclass in LEAN). Working with natural (N), integer (Z) and rational (Q) numbers, we want every N to be automatically coerced to an integer, and so declare a natToZ coercion. Similarly, we can also declare a ZToQ coercion. If we write 0 (a N) where a Q is expected, this is accepted, and 0 is silently transformed to ZToQ (natToZ 0).

Now, if we want the same mechanism to apply when we pass the list `[0 :: 1 :: 2]` to a function expecting a **List Q**, we need to provide a way to propagate the coercions on lists. We can expect to solve this problem by declaring $map_{List}$ as a coercion, too: whenever there is a coercion $f: A \to B$, then $map_{List} f$ should be a coercion from **List A** to **List B**. However, by doing so, we would cause more trouble than we solve, as there would be two coercions from **List N** to **List Q**, $map_{List}(ZToQ \circ natToZ)$ and $(map_{List} ZToQ) \circ (map_{List} natToZ)$. In the absence of definitional functor laws for $map_{List}$, these two are not definitionally equal. To add insult to injury, coercions are by default not printed to the user, yielding puzzling error messages like "`l` and `l` are not convertible" (!), because one is secretly $map_{List}(ZToQ \circ natToZ) l$ while the other is $map_{List} ZToQ (map_{List} natToZ l)$. This makes $map_{List}$ virtually unusable with coercions.

**Structural Subtyping.** This last example suggests a connection with **subtyping**. Subtyping equips the collection of types with a **subtyping order** $\leq$ that allows to seamlessly transport terms from a subtype to a supertype, i.e. from A to A' when $A \leq A'$. An important aspect of subtyping is **structural subtyping**, i.e. how subtyping extends structurally through type formers of the type theory. Typically, we want to have **List A** $\leq$ **List A'** whenever $A \leq A'$. In the context of the F\* program verification platform that heavily uses refinement subtyping, the inability to propagate subtyping on inductive datatypes such as lists has been a long-standing issue that never got solved properly [27]. The absence of structural subtyping also has a history of causing difficulties to AGDA [16, 23].

**Definitional Equalities for Subtyping.** From the perspective of users of interactive theorem prover, subtyping should be implicit, transparently providing the expected glue to smoothen the writing of complex statements. From a meta-theoretical perspective, on the other hand, it is useful to explicitly represent all the necessary information of a typing derivation, including where subtyping is used. The first approach is known as **subsumptive subtyping**, on the left, whereas the latter is

<footnote n="3">³We formalize this example, showing that this conversion indeed holds in our system, in file Example_1_1.</footnote>
If the functor laws only hold propositionally, each consecutive simplification of back and forth changes of representation needs to be explicitly lifted to lists, and applied. The uncontrolled accumulation of repetitive proof steps, even as simple as these, can quickly burden proof development. In presence of definitional functor laws, instead, any sequence of representation changes will reduce to a single $map_{List}$: the boilerplate of explicitly manipulating the functor laws is handled automatically by the type theory. Moreover, observe that in this example the retraction $glue_retr \circ glue \cong$ id is definitional thanks to surjective pairing. Combined with definitional functor laws, the following simplification step is discharged automatically by the type-checker:<fnref n="3" />

$$map_{List} glue_retr (map_{List} glue l) \cong map_{List} id l \cong l$$

Note that these equations are valid in any context, in particular under binders, whereas for propositional identifications, rewriting under binders is only possible in presence of the additional axiom of function extensionality.

**Example 1.2 (Coherence of Coercions).** Proof assistants may provide the ability for users to declare automatically-inserted functions acting as glue code (coercions in COQ, instance arguments in AGDA, has_coe typeclass in LEAN). Working with natural (N), integer (Z) and rational (Q) numbers, we want every N to be automatically coerced to an integer, and so declare a natToZ coercion. Similarly, we can also declare a ZToQ coercion. If we write 0 (a N) where a Q is expected, this is accepted, and 0 is silently transformed to ZToQ (natToZ 0).

Now, if we want the same mechanism to apply when we pass the list `[0 :: 1 :: 2]` to a function expecting a **List Q**, we need to provide a way to propagate the coercions on lists. We can expect to solve this problem by declaring $map_{List}$ as a coercion, too: whenever there is a coercion $f: A \to B$, then $map_{List} f$ should be a coercion from **List A** to **List B**. However, by doing so, we would cause more trouble than we solve, as there would be two coercions from **List N** to **List Q**, $map_{List}(ZToQ \circ natToZ)$ and $(map_{List} ZToQ) \circ (map_{List} natToZ)$. In the absence of definitional functor laws for $map_{List}$, these two are not definitionally equal. To add insult to injury, coercions are by default not printed to the user, yielding puzzling error messages like "`l` and `l` are not convertible" (!), because one is secretly $map_{List}(ZToQ \circ natToZ) l$ while the other is $map_{List} ZToQ (map_{List} natToZ l)$. This makes $map_{List}$ virtually unusable with coercions.

**Structural Subtyping.** This last example suggests a connection with **subtyping**. Subtyping equips the collection of types with a **subtyping order** $\leq$ that allows to seamlessly transport terms from a subtype to a supertype, i.e. from A to A' when $A \leq A'$. An important aspect of subtyping is **struc-tural subtyping**, i.e. how subtyping extends structurally through type formers of the type theory. Typically, we want to have **List A** $\leq$ **List A'** whenever $A \leq A'$. In the context of the $F^*$ program verification platform that heavily uses refinement subtyping, the inability to propagate subtyping on inductive datatypes such as lists has been a long-standing issue that never got solved properly [27]. The absence of structural subtyping also has a history of causing difficulties to AGDA [16, 23].

**Definitional Equalities for Subtyping.** From the perspective of users of interactive theorem prover, subtyping should be implicit, transparently providing the expected glue to smoothen the writing of complex statements. From a meta-theoretical perspective, on the other hand, it is useful to explicitly represent all the necessary information of a typing derivation, including where subtyping is used. The first approach is known as **subsumptive subtyping**, on the left, whereas the latter is

<footnote n="3">³We formalize this example, showing that this conversion indeed holds in our system, in file Example_1_1.</footnote>
embodied by coercive subtyping, on the right:

$$ \mathbf{SUB} \frac{\Gamma \vdash_{\mathbf{sub}} t : A \quad \Gamma \vdash_{\mathbf{sub}} A \preceq A'}{\Gamma \vdash_{\mathbf{sub}} t : A'} $$

$$ \mathbf{COE} \frac{\Gamma \vdash_{\mathbf{coe}} t : A \quad \Gamma \vdash_{\mathbf{coe}} A \preceq A' \triangleleft}{\Gamma \vdash_{\mathbf{coe}} \mathrm{coe}_{A,A'} t : A'} $$

We want to present subsumptive subtyping to users, but ground the system on the algebraic, better-behaved coercive subtyping. Informally, an application of `SUB` in the subsumptive type theory `MLTT`$_{sub}$ should correspond to an application of `COE` in the coercive type theory `MLTT`$_{coe}$. However, given a derivation $\mathcal{D}$ of $\Gamma \vdash_{\mathbf{sub}} t : A$ we can apply `SUB` together with a reflexivity proof $\Gamma \vdash_{\mathbf{sub}} A \preceq A$ to yield a new derivation $\mathcal{D}'$ with the same conclusion $\Gamma \vdash_{\mathbf{sub}} t : A$. $\mathcal{D}$ and $\mathcal{D}'$ should respectively correspond to terms $\Gamma \vdash_{\mathbf{coe}} t' : A$ and $\Gamma \vdash_{\mathbf{coe}} \mathrm{coe}_{A,A'} t' : A$ in `MLTT`$_{coe}$. Since $t'$ and $\mathrm{coe}_{A,A'} t'$ both erase to the same `MLTT`$_{sub}$ term $t$, they need to be equated if we want both type theories to be equivalent. Similarly, transitivity of subtyping implies that coercions should compose definitionally, that is $\Gamma \vdash_{\mathbf{coe}} \mathrm{coe}_{B,C}(\mathrm{coe}_{A,B} t') \cong \mathrm{coe}_{A,C} t' \triangleleft C$ should always hold in `MLTT`$_{coe}$.

**Functor Laws Meet Structural Subtyping.** Luo and Adams [38] showed that the functorial composition law `comp-eq` is enough to make structural coercive subtyping compose definitionally, because a structural coercion between lists `coe$_{List A}$`, `List B` behaves just as the function obtained by mapping `coe$_{A,B}$` on every element of the list. We further investigate this bridge between coercive subtyping and functoriality of type formers, in particular the identity functor law `id-eq` needed to handle reflexivity of subtyping, and extend Luo and Adams's limited type system to full-blown Martin-Löf Type Theory (MLTT), with universes and large elimination. This understanding leads to a modular design of subtyping: structural subtyping for a type former relies on a functorial structure, and can be considered orthogonally to other type formers of the theory or to the base subtyping. Moreover, definitional functor laws are sufficient to make structural coercive subtyping for any type former expressive and flexible enough to interpret subsumptive subtyping.

**Contributions.** We make the following contributions:

* we design `MLTT$_{map}$`, an extension of Martin-Löf Type Theory (MLTT) exhibiting the functorial nature of standard type formers (`Π`, `Σ`, `List`, `W`, `Id`, `+`), and satisfying definitional functor laws (Section 3);

* we mechanize the metatheory of a substantial fragment of `MLTT$_{map}$` in `COQ`, extending a formalization of MLTT [3], proving it is normalizing and has decidable type-checking (Section 4);

* we develop bidirectional presentations for `MLTT$_{sub}$` and `MLTT$_{coe}$`, which extend MLTT respectively with subsumptive and coercive subtyping;

* we leverage these presentations and the extra functorial equations satisfied by `coe` in `MLTT$_{coe}$` to give back and forth, type-preserving translations between the two systems (Section 5).

The necessary technical background, notations and definitions for MLTT are introduced in Section 2, while Section 6 details the related and future work.

This is an extended version of [34]. It mainly extends Section 2, adds some figures to the text, the discussion on eliminator fusion in Section 3.3, provides a small instance of base subtyping using records in Section 5.1 and has complete proofs and type systems in appendices. The appendix also contains a detailed description of the formalisation presented in Section 4, which was originally provided as an accompanying note alongside [33] for the artefact evaluation process.
embodied by coercive subtyping, on the right:

$$ \mathbf{SUB} \frac{\Gamma \vdash_{\mathbf{sub}} t : A \quad \Gamma \vdash_{\mathbf{sub}} A \preceq A'}{\Gamma \vdash_{\mathbf{sub}} t : A'} $$

$$ \mathbf{COE} \frac{\Gamma \vdash_{\mathbf{coe}} t : A \quad \Gamma \vdash_{\mathbf{coe}} A \preceq A' \triangleleft}{\Gamma \vdash_{\mathbf{coe}} \mathrm{coe}_{A,A'} t : A'} $$

We want to present subsumptive subtyping to users, but ground the system on the algebraic, better-behaved coercive subtyping. Informally, an application of `SUB` in the subsumptive type theory `MLTT`$_{sub}$ should correspond to an application of `COE` in the coercive type theory `MLTT`$_{coe}$. However, given a derivation $\mathcal{D}$ of $\Gamma \vdash_{\mathbf{sub}} t : A$ we can apply `SUB` together with a reflexivity proof $\Gamma \vdash_{\mathbf{sub}} A \preceq A$ to yield a new derivation $\mathcal{D}'$ with the same conclusion $\Gamma \vdash_{\mathbf{sub}} t : A$. $\mathcal{D}$ and $\mathcal{D}'$ should respectively correspond to terms $\Gamma \vdash_{\mathbf{coe}} t' : A$ and $\Gamma \vdash_{\mathbf{coe}} \mathrm{coe}_{A,A'} t' : A$ in `MLTT`$_{coe}$. Since $t'$ and $\mathrm{coe}_{A,A'} t'$ both erase to the same `MLTT`$_{sub}$ term $t$, they need to be equated if we want both type theories to be equivalent. Similarly, transitivity of subtyping implies that coercions should compose definitionally, that is $\Gamma \vdash_{\mathbf{coe}} \mathrm{coe}_{B,C}(\mathrm{coe}_{A,B} t') \cong \mathrm{coe}_{A,C} t' \triangleleft C$ should always hold in `MLTT`$_{coe}$.

**Functor Laws Meet Structural Subtyping.** Luo and Adams [38] showed that the functorial composition law `comp-eq` is enough to make structural coercive subtyping compose definitionally, because a structural coercion between lists `coe$_{List A}$`, `List B` behaves just as the function obtained by mapping `coe$_{A,B}$` on every element of the list. We further investigate this bridge between coercive subtyping and functoriality of type formers, in particular the identity functor law `id-eq` needed to handle reflexivity of subtyping, and extend Luo and Adams's limited type system to full-blown Martin-Löf Type Theory (MLTT), with universes and large elimination. This understanding leads to a modular design of subtyping: structural subtyping for a type former relies on a functorial structure, and can be considered orthogonally to other type formers of the theory or to the base subtyping. Moreover, definitional functor laws are sufficient to make structural coercive subtyping for any type former expressive and flexible enough to interpret subsumptive subtyping.

**Contributions.** We make the following contributions:

* we design `MLTT$_{map}$`, an extension of Martin-Löf Type Theory (MLTT) exhibiting the functorial nature of standard type formers (`Π`, `Σ`, `List`, `W`, `Id`, `+`), and satisfying definitional functor laws (Section 3);

* we mechanize the metatheory of a substantial fragment of `MLTT$_{map}$` in `COQ`, extending a formalization of MLTT [3], proving it is normalizing and has decidable type-checking (Section 4);

* we develop bidirectional presentations for `MLTT$_{sub}$` and `MLTT$_{coe}$`, which extend MLTT respectively with subsumptive and coercive subtyping;

* we leverage these presentations and the extra functorial equations satisfied by `coe` in `MLTT$_{coe}$` to give back and forth, type-preserving translations between the two systems (Section 5).

The necessary technical background, notations and definitions for MLTT are introduced in Section 2, while Section 6 details the related and future work.

This is an extended version of [34]. It mainly extends Section 2, adds some figures to the text, the discussion on eliminator fusion in Section 3.3, provides a small instance of base subtyping using records in Section 5.1 and has complete proofs and type systems in appendices. The appendix also contains a detailed description of the formalisation presented in Section 4, which was originally provided as an accompanying note alongside [33] for the artefact evaluation process.
$$ \Gamma \vdash T \qquad \text{Type } T \text{ is well-formed under context } \Gamma $$

$$ \Gamma \vdash t:T \qquad \text{Term } t \text{ has type } T \text{ under context } \Gamma $$

$$
\begin{array}{l @{\quad} l @{\quad} l @{\quad} l @{\quad} l}
\text{VAR} & \frac{\Gamma \vdash \Gamma \quad (x : A) \in \Gamma}{\Gamma \vdash x : A} & \text{SORT} & \frac{\Gamma \vdash \Gamma}{\Gamma \vdash \text{Type}_i : \text{Type}_{i+1}} & \text{EL} & \frac{\Gamma \vdash A : \text{Type}_i}{\Gamma \vdash A} \\
\text{FUN} & \frac{\Gamma \vdash A : \text{Type}_i}{\Gamma \vdash x : A \vdash B : \text{Type}_i} & \text{ABS} & \frac{\Gamma \vdash A}{\Gamma \vdash \lambda x : A.t : \Pi x : A.B} & \text{APP} & \frac{\Gamma \vdash t : \Pi x : A.B}{\Gamma \vdash u : A} \\
& & & & & \frac{\Gamma \vdash t : \Pi u : B[u]}{\Gamma \vdash t u : B[u]} \\
\text{LIST} & \frac{\Gamma \vdash A : \text{Type}_i}{\Gamma \vdash \text{List } A : \text{Type}_i} & \text{NIL} & \frac{\Gamma \vdash A}{\Gamma \vdash \varepsilon_A : \text{List } A} & \text{CONS} & \frac{\Gamma \vdash A \quad \Gamma \vdash a : A}{\Gamma \vdash a ::_A l : \text{List } A} \\
& & & & & \\
\text{LISTIND} & \frac{\Gamma \vdash A \quad \Gamma \vdash s : \text{List } A \quad \Gamma, z : \text{List } A \vdash P}{\Gamma \vdash b_\varepsilon : P[\varepsilon_A] \quad \Gamma, x : A, y : \text{List } A, z : P[y] \vdash b_\varepsilon : P[x ::_A y]} & \text{CONV} & \frac{\Gamma \vdash t : A}{\Gamma \vdash A \cong B} \\
& & & & & \frac{\Gamma \vdash t : A}{\Gamma \vdash t : B} \\
\end{array}
$$

<caption>Fig. 2. Declarative typing for MLTT (complete rules: Appendix C.1)</caption>

$$ \Gamma \vdash t \cong u : A \qquad \text{Terms } u \text{ and } v \text{ are convertible at type } A \text{ under context } \Gamma $$

$$ \Gamma \vdash A \cong B \qquad \text{Types } A \text{ and } B \text{ are convertible under context } \Gamma $$

$$
\begin{array}{l @{\quad} l @{\quad} l @{\quad} l @{\quad} l}
\beta\text{FUN} & \frac{\Gamma \vdash A \quad \Gamma, x : A \vdash t : B \quad \Gamma \vdash u : A}{\Gamma \vdash (\lambda x : A.t) u \cong t[u] : B[u]} & \eta\text{FUN} & \frac{\Gamma, x : A \vdash f x \cong g x : B}{\Gamma \vdash f \cong g : \Pi x : A.B} & & \\
\beta\text{NIL} & \frac{\Gamma, z : \text{List } A \vdash P \quad \Gamma \vdash b_\varepsilon : P[\varepsilon_A] \quad \Gamma, x : A, y : \text{List } A, z : P[y] \vdash b_\varepsilon : P[x ::_A y]}{\Gamma \vdash \text{ind}_{\text{List } A}(\varepsilon_A; l.P; b_\varepsilon, x.y.z.b_\varepsilon) \cong b_\varepsilon : P[\varepsilon_A]} & & & & \\
\beta\text{CONS} & \frac{\Gamma, z : \text{List } A \vdash P \quad \Gamma \vdash b_\varepsilon : P[\varepsilon_A] \quad \Gamma, x : A, y : \text{List } A, z : P[y] \vdash b_\varepsilon : P[x ::_A y]}{\Gamma \vdash \text{ind}_{\text{List } A}(a ::_A l; z.P; b_\varepsilon, x.y.z.b_\varepsilon) \cong b_\varepsilon [\text{id}, a, l, \text{ind}_{\text{List } A}(l; z.P; b_\varepsilon, x.y.z.b_\varepsilon)] : P[a ::_A l]} & & & & \\
& & & & & \\
\text{CONVCONV} & \frac{\Gamma \vdash t \cong t' : A \quad \Gamma \vdash A \cong A'}{\Gamma \vdash t \cong t' : A'} & \text{ELCONV} & \frac{\Gamma \vdash A \cong A' : \text{Type}_i}{\Gamma \vdash A \cong A'} & & \\
\text{REFL} & \frac{\Gamma \vdash t : A}{\Gamma \vdash t \cong t : A} & \text{SYM} & \frac{\Gamma \vdash t \cong u : A}{\Gamma \vdash u \cong t : A} & \text{TRANS} & \frac{\Gamma \vdash t \cong u : A \quad \Gamma \vdash u \cong v : A}{\Gamma \vdash t \cong v : A} \\
& & & & & \\
\end{array}
$$

<caption>Fig. 3. Declarative conversion for MLTT (complete rules: Appendix C.1)</caption>
$$ \Gamma \vdash T \qquad \text{Type } T \text{ is well-formed under context } \Gamma $$

$$ \Gamma \vdash t:T \qquad \text{Term } t \text{ has type } T \text{ under context } \Gamma $$

$$
\begin{array}{l @{\quad} l @{\qquad} l @{\quad} l}
\text{VAR} & \frac{\Gamma \vdash \Gamma \quad (x : A) \in \Gamma}{\Gamma \vdash x : A} & \text{SORT} & \frac{\Gamma \vdash \Gamma}{\Gamma \vdash \text{Type}_i : \text{Type}_{i+1}} & \text{EL} \frac{\Gamma \vdash A : \text{Type}_i}{\Gamma \vdash A} \\[1.5em]
\text{FUN} & \frac{\Gamma \vdash A : \text{Type}_i}{\Gamma \vdash \Pi x : A.B : \text{Type}_i} & \text{ABS} & \frac{\Gamma \vdash A \quad \Gamma, x : A \vdash t : B}{\Gamma \vdash \lambda x : A.t : \Pi x : A.B} & \frac{\Gamma \vdash t : \Pi x : A.B}{\Gamma \vdash u : A} \\[1.5em]
& & & & \text{APP} \frac{\Gamma \vdash u : A}{\Gamma \vdash t u : B[u]} \\[1.5em]
\text{LIST} & \frac{\Gamma \vdash A : \text{Type}_i}{\Gamma \vdash \text{List } A : \text{Type}_i} & \text{NIL} & \frac{\Gamma \vdash A}{\Gamma \vdash \varepsilon_A : \text{List } A} & \frac{\Gamma \vdash A \quad \Gamma \vdash a : A}{\Gamma \vdash l : \text{List } A} \\[1.5em]
\text{LISTIND} & \frac{\Gamma \vdash b_\varepsilon : P[\varepsilon_A]}{\Gamma \vdash \text{ind}_{\text{List } A}(s; z.P; b_\varepsilon, x.y.z.b_\varepsilon)} : P[s] & \Gamma, z : \text{List } A \vdash P & & \Gamma \vdash t : A \\[1.5em]
& & & & \text{CONV} \frac{\Gamma \vdash A \cong B}{\Gamma \vdash t : B} \\[1.5em]
\end{array}
$$

<caption>Fig. 2. Declarative typing for MLTT (complete rules: Appendix C.1)</caption>

$$ \Gamma \vdash t \cong u : A \qquad \text{Terms } u \text{ and } v \text{ are convertible at type } A \text{ under context } \Gamma $$

$$ \Gamma \vdash A \cong B \qquad \text{Types } A \text{ and } B \text{ are convertible under context } \Gamma $$

$$
\begin{array}{l @{\quad} l @{\qquad} l @{\quad} l}
\beta\text{FUN} & \frac{\Gamma \vdash A \quad \Gamma, x : A \vdash t : B \quad \Gamma \vdash u : A}{\Gamma \vdash (\lambda x : A.t) u \cong t[u] : B[u]} & \eta\text{FUN} & \frac{\Gamma, x : A \vdash f x \cong g x : B}{\Gamma \vdash f \cong g : \Pi x : A.B} \\[1.5em]
\beta\text{NIL} & \frac{\Gamma, z : \text{List } A \vdash P \quad \Gamma \vdash b_\varepsilon : P[\varepsilon_A] \quad \Gamma, x : A, y : \text{List } A, z : P[y] \vdash b_\varepsilon : P[x ::_A y]}{\Gamma \vdash \text{ind}_{\text{List } A}(\varepsilon_A; l.P; b_\varepsilon, x.y.z.b_\varepsilon) \cong b_\varepsilon : P[\varepsilon_A]} & & \\[1.5em]
\beta\text{CONS} & \frac{\Gamma, z : \text{List } A \vdash P \quad \Gamma \vdash b_\varepsilon : P[\varepsilon_A] \quad \Gamma, x : A, y : \text{List } A, z : P[y] \vdash b_\varepsilon : P[x ::_A y]}{\Gamma \vdash \text{ind}_{\text{List } A}(a ::_A l; z.P; b_\varepsilon, x.y.z.b_\varepsilon) \cong b_\varepsilon [\text{id}, a, l, \text{ind}_{\text{List } A}(l; z.P; b_\varepsilon, x.y.z.b_\varepsilon)] : P[a ::_A l]} & & \\[1.5em]
& & & \\[1.5em]
\text{CONVCONV} & \frac{\Gamma \vdash t \cong t' : A \quad \Gamma \vdash A \cong A'}{\Gamma \vdash t \cong t' : A'} & \text{ELCONV} & \frac{\Gamma \vdash A \cong A' : \text{Type}_i}{\Gamma \vdash A \cong A'} \\[1.5em]
\text{REFL} & \frac{\Gamma \vdash t : A}{\Gamma \vdash t \cong t : A} & \text{SYM} & \frac{\Gamma \vdash t \cong u : A}{\Gamma \vdash u \cong t : A} & \text{TRANS} \frac{\Gamma \vdash t \cong u : A \quad \Gamma \vdash u \cong v : A}{\Gamma \vdash t \cong v : A} \\[1.5em]
\end{array}
$$

<caption>Fig. 3. Declarative conversion for MLTT (complete rules: Appendix C.1)</caption>
## 2 TYPE THEORY AND ITS METATHEORY

We work in the setting of dependent type theories à la Martin-Löf (MLTT) [41], an ideal abstraction of the type theories underlying existing proof assistants such as AGDA, COQ, F* or LEAN. MLTT employs five categories of judgements, characterizing the well-formed contexts (Γ ⊢ T) and terms (Γ ⊢ t : T) (Figure 2), and providing the equational theory on types (Γ ⊢ A ≅ B) and terms (Γ ⊢ t ≅ u : A) (Figure 3). Two terms related by this equational theory are said to be *definitionally equal* or *convertible*, to stress the fact that these terms will be identified by proof assistants implementing this theory, without any need for manual equational reasoning.

*Variables and substitution.* Throughout the paper, we use named variables (x, y...) for readability purposes, but we think of them as de Bruijn indices, which is what we use in the COQ formalization. In particular, we do not consider freshness conditions. A substitution $\sigma$ consists of a list of terms, and we write $t[\sigma]$ for its parallel substitution in the term $t$. The substitution $(\mathrm{id}, u)$ replaces the 0th de Bruijn index by the term $u$, and applies the identity substitution to all other variables, leaving them intact. We will write $t[(\mathrm{id}, u)]$ simply as $t[u]$, which would be written $t[x := u]$ in more verbose notation, if $x$ correspond to the 0th de Bruijn index in $t$. Typing in all systems is extended pointwise to substitutions in a standard fashion, see Appendix C.1.

*Negative Types: Dependent Products and Sums.* Dependent function types, noted $\Pi x : A.B$, are introduced using $\lambda$-abstraction $\lambda x : A.t$ and eliminated with application $t u$. We also include dependent sum types $\Sigma x : A.B$, introduced with pairs $(t, u)_{x.B}$ and eliminated through projections $\pi_1 p$ and $\pi_2 p$. Both come with an $\eta$-law.

*Universes of Types.* Our type theories feature a countable hierarchy of universes $\mathrm{Type}_i$, which are types for types. Any inhabitant of a universe is a well-formed type, and, in order to make the presentation compact, we do not repeat rules applying both for universes and types: all rules given for terms of some universe $\mathrm{Type}_i$ have a counterpart as a type judgement whenever it makes sense.

For instance, in addition to $\mathrm{FUN}$, we have the type-level equivalent

$$ \mathrm{FUNTy} \frac{\Gamma \vdash A \qquad \Gamma, x : A \vdash B}{\Gamma \vdash \Pi x : A.B} $$

*Positive Types: Inductives.* As we study the functorial status of type formers, parametrized inductive types are our main focus. Our running example is the type of lists **List A**, parametrized by a type A, and inhabited by the empty list $\varepsilon_A$ and the consing $hd ::_A tl$ of a head $hd : A$ onto a tail $tl : \mathbf{List} A$. Lists are eliminated using the dependent eliminator $\mathrm{ind}_{\mathbf{List} A}(s; l.P; b_\varepsilon, x.y.z.b_\varepsilon)$, which performs induction on the scrutinee $s$, returning a value in $P[s]$, using the two branches $b_\varepsilon$ and $b_\varepsilon$, corresponding to the two constructors $::$ and $\varepsilon$. $b_\varepsilon$ binds three variables corresponding to the head, tail and induction hypothesis on the tail. More generally, strictly positive recursive datatypes are often presented in MLTT via $\mathbf{W} x : A.B$, the type of well-founded trees with nodes labelled by $a : A$ of arity $B a$. Finally, Martin-Löf's identity type $\mathbf{Id} A x y$ represents equalities between two elements $x, y : A$, and is introduced with the reflexivity proof $\mathrm{refl}_{A,a} : \mathbf{Id} A a a$. A general inductive type scheme is outside the scope of this paper, but the specific types we treat ($\mathbf{List}, \mathbf{W}, \mathbf{Id}$ and $+$) cover all aspects of inductive types: recursion, branching, parameters, and indices. Moreover, they can emulate all indexed inductive types [1, 8, 28], although we will see in Section 3.1 that this encoding interacts poorly with functor laws. As 0 and 1 are not parametrized, their presentation in our setting is entirely standard.

*Rules in the Paper.* Due to space constraints, we focus in the text on the most interesting rules, and on two types: dependent functions and lists. Together, they cover the interesting points of our
## 2 TYPE THEORY AND ITS METATHEORY

We work in the setting of dependent type theories à la Martin-Löf (MLTT) [41], an ideal abstraction of the type theories underlying existing proof assistants such as AGDA, COQ, F* or LEAN. MLTT employs five categories of judgements, characterizing the well-formed contexts (Γ ⊢ T) and terms (Γ ⊢ t : T) (Figure 2), and providing the equational theory on types (Γ ⊢ A ≅ B) and terms (Γ ⊢ t ≅ u : A) (Figure 3). Two terms related by this equational theory are said to be *definitionally equal* or *convertible*, to stress the fact that these terms will be identified by proof assistants implementing this theory, without any need for manual equational reasoning.

*Variables and substitution.* Throughout the paper, we use named variables (x, y...) for readability purposes, but we think of them as de Bruijn indices, which is what we use in the COQ formalization. In particular, we do not consider freshness conditions. A substitution $\sigma$ consists of a list of terms, and we write $t[\sigma]$ for its parallel substitution in the term $t$. The substitution $(\mathrm{id}, u)$ replaces the 0th de Bruijn index by the term $u$, and applies the identity substitution to all other variables, leaving them intact. We will write $t[(\mathrm{id}, u)]$ simply as $t[u]$, which would be written $t[x := u]$ in more verbose notation, if $x$ correspond to the 0th de Bruijn index in $t$. Typing in all systems is extended pointwise to substitutions in a standard fashion, see Appendix C.1.

*Negative Types: Dependent Products and Sums.* Dependent function types, noted $\Pi x : A.B$, are introduced using $\lambda$-abstraction $\lambda x : A.t$ and eliminated with application $t u$. We also include dependent sum types $\Sigma x : A.B$, introduced with pairs $(t, u)_{x.B}$ and eliminated through projections $\pi_1 p$ and $\pi_2 p$. Both come with an $\eta$-law.

*Universes of Types.* Our type theories feature a countable hierarchy of universes $\mathrm{Type}_i$, which are types for types. Any inhabitant of a universe is a well-formed type, and, in order to make the presentation compact, we do not repeat rules applying both for universes and types: all rules given for terms of some universe $\mathrm{Type}_i$ have a counterpart as a type judgement whenever it makes sense.

For instance, in addition to $\mathrm{FUN}$, we have the type-level equivalent

$$ \mathrm{FUNTy} \frac{\Gamma \vdash A \qquad \Gamma, x : A \vdash B}{\Gamma \vdash \Pi x : A.B} $$

*Positive Types: Inductives.* As we study the functorial status of type formers, *parametrized inductive types* are our main focus. Our running example is the type of lists **List A**, parametrized by a type A, and inhabited by the empty list $\varepsilon_A$ and the consing $hd ::_A tl$ of a head $hd : A$ onto a tail $tl : \mathbf{List} A$. Lists are eliminated using the dependent eliminator $\mathrm{ind}_{\mathbf{List} A}(s; l.P; b_\varepsilon, x.y.z.b_\varepsilon)$, which performs induction on the scrutinee $s$, returning a value in $P[s]$, using the two branches $b_\varepsilon$ and $b_\varepsilon$, corresponding to the two constructors $::$ and $\varepsilon$. $b_\varepsilon$ binds three variables corresponding to the head, tail and induction hypothesis on the tail. More generally, strictly positive recursive datatypes are often presented in MLTT via $\mathbf{W} x : A.B$, the type of well-founded trees with nodes labelled by $a : A$ of arity $Ba$. Finally, Martin-Löf's identity type $\mathbf{Id} A x y$ represents equalities between two elements $x, y : A$, and is introduced with the reflexivity proof $\mathrm{refl}_{A,a} : \mathbf{Id} A a a$. A general inductive type scheme is outside the scope of this paper, but the specific types we treat ($\mathbf{List}$, $\mathbf{W}$, $\mathbf{Id}$ and $+$) cover all aspects of inductive types: recursion, branching, parameters, and indices. Moreover, they can emulate all indexed inductive types [1, 8, 28], although we will see in Section 3.1 that this encoding interacts poorly with functor laws. As 0 and 1 are not parametrized, their presentation in our setting is entirely standard.

*Rules in the Paper.* Due to space constraints, we focus in the text on the most interesting rules, and on two types: dependent functions and lists. Together, they cover the interesting points of our
work: dependent product types have a binder and come with an η-law; lists are a parametrized
datatype, for which definitional functor laws are challenging. Complete rules are given in Appen-
dix C.

## 2.1 Metatheoretical Properties

In order to show that the extensions of MLTT from Figure 1 are well-behaved, we establish the
following meta-theoretical properties.

*Consistency and canonicity.* In order to be logically sound, a type theory should have no closed
term of the empty type, i.e. there should be no *t* such that $\vdash t : 0$. This consistency property is an
easy consequence of canonicity, which characterizes the inhabitants of inductive types in the empty
context as those obtained by repeated applications of constructors, up to conversion. Consistency
follows, as 0 has no constructor.

*Decidability of type-checking and conversion.* A proof assistant should also be able to check
whether a proof is valid, i.e. whether a typing judgement is derivable. In a dependent type sys-
tem where terms essentially encode the structure of derivations, the main obstacle to decidability
of typing is that of conversion.

*Normal forms for terms and derivations.* In order to establish both consistency and decidability,
we exhibit a function computing normal forms of terms. Inspecting the possible normal forms
in the empty context entails canonicity. Moreover, conversion of normal forms is easily decided,
and so we can build on normalization to decide conversion. Finally, we can go further, and use
normalization to build canonical representatives of typing and conversion derivations, which we
rely on to relate our different systems.

*Injectivity of type constructors.* A more technical, but equally important property is injectivity
of type constructors, for instance that whenever $\Pi x : A.B \cong \Pi x : A'.B'$, then $A \cong A'$ and
$B \cong B'$. This property fails in extensional type theory, where the equational theory is too rich.
For dependent type theories, injectivity of type constructors is the main stepping stone towards
subject reduction, the fact that reduction is type-preserving, and thus included in conversion.

## 2.2 Neutrals, Normals, and Reduction

Before getting to how we establish these properties, we must introduce a last element: computation.
Indeed, most conversion rules can be seen not just as equalities but be oriented as computations
to be performed. This leads to the definition of weak-head reduction $\rightarrow^*$ in Figure 4, an evalua-
tion strategy for open terms which reduces just as much as needed in order to uncover the head
constructor of a term. This means reducing not just at top level: if our term is an application, we
might need to reduce the function in order to expose a $\lambda$-abstraction and subsequently $\beta$-reduce
the term with the (call-by-name) rule $\beta\mathbf{RED}$. However, we do not allow reduction in the argument
of an application, so that reduction remains deterministic: there is at most one possible reduct for
any term. Weak-head reduction is the only reduction that is used throughout this article.

The normal forms (nf) for weak-head reduction, i.e. the terms that cannot reduce, are inductively
characterized at the bottom of Figure 4, together with the companion notion of neutral forms (ne).
Normal forms can be either a canonical term, starting with a head constructor (for instance, a
$\lambda$-abstraction or $\epsilon$), or a neutral term. Neutrals are stuck computations, blocked by a variable, e.g.
$x u$ is stuck on $x$ and cannot reduce further.

## 2.3 Proof techniques

We can now go through the techniques we use to establish the properties of Section 2.1.
work: dependent product types have a binder and come with an η-law; lists are a parametrized
datatype, for which definitional functor laws are challenging. Complete rules are given in Appen-
dix C.

## 2.1 Metatheoretical Properties

In order to show that the extensions of MLTT from Figure 1 are well-behaved, we establish the
following meta-theoretical properties.

*Consistency and canonicity.* In order to be logically sound, a type theory should have no closed
term of the empty type, i.e. there should be no *t* such that $t : 0$. This *consistency* property is an
easy consequence of *canonicity*, which characterizes the inhabitants of inductive types in the empty
context as those obtained by repeated applications of constructors, up to conversion. Consistency
follows, as *0* has no constructor.

*Decidability of type-checking and conversion.* A proof assistant should also be able to check
whether a proof is valid, i.e. whether a typing judgement is derivable. In a dependent type sys-
tem where terms essentially encode the structure of derivations, the main obstacle to decidability
of typing is that of conversion.

*Normal forms for terms and derivations.* In order to establish both consistency and decidability,
we exhibit a function computing normal forms of terms. Inspecting the possible normal forms
in the empty context entails canonicity. Moreover, conversion of normal forms is easily decided,
and so we can build on normalization to decide conversion. Finally, we can go further, and use
normalization to build canonical representatives of typing and conversion derivations, which we
rely on to relate our different systems.

*Injectivity of type constructors.* A more technical, but equally important property is injectivity
of type constructors, for instance that whenever $Πx : A.B \cong Πx : A'.B'$, then $A \cong A'$ and
$B \cong B'$. This property fails in extensional type theory, where the equational theory is too rich.
For dependent type theories, injectivity of type constructors is the main stepping stone towards
subject reduction, the fact that reduction is type-preserving, and thus included in conversion.

## 2.2 Neutrals, Normals, and Reduction

Before getting to how we establish these properties, we must introduce a last element: computation.
Indeed, most conversion rules can be seen not just as equalities but be oriented as computations
to be performed. This leads to the definition of weak-head reduction $\rightarrow^*$ in Figure 4, an evalua-
tion strategy for open terms which reduces just as much as needed in order to uncover the head
constructor of a term. This means reducing not just at top level: if our term is an application, we
might need to reduce the function in order to expose a $\lambda$-abstraction and subsequently $\beta$-reduce
the term with the (call-by-name) rule $\beta$RED. However, we do not allow reduction in the argument
of an application, so that reduction remains deterministic: there is at most one possible reduct for
any term. Weak-head reduction is the only reduction that is used throughout this article.

The normal forms (nf) for weak-head reduction, i.e. the terms that cannot reduce, are inductively
characterized at the bottom of Figure 4, together with the companion notion of neutral forms (ne).
Normal forms can be either a canonical term, starting with a head constructor (for instance, a
$\lambda$-abstraction or $\epsilon$), or a neutral term. Neutrals are stuck computations, blocked by a variable, e.g.
$x u$ is stuck on $x$ and cannot reduce further.

## 2.3 Proof techniques

We can now go through the techniques we use to establish the properties of Section 2.1.
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 4. Weak-head reduction and normal forms (t stands for an arbitrary term)</figcaption></figure>

**Logical Relations.** Logical relations are our main tool to obtain normalization and canonicity results. At a high-level, we follow the approach of Abel, Öhman, and Vezzosi [2], where the logical relation is based on reducibility, a complex predicate on types and terms, which in particular entails the existence of a weak-head normal form. The key property is the fundamental lemma, stating that every well-typed term is reducible, i.e. that the logical relation is a model of MLTT. The existence of (deep) normal forms is obtained through the inspection of reducibility derivations for a term, since they contain iterated reduction steps to a normal form.

We use the logical relation not only to characterize the normal forms of terms but also the conversion between them, showing that a proof of convertibility between two terms can be transformed to a canonical shape interleaving weak-head reduction sequences and congruence steps between weak-head normal forms. We detail in Section 4 the novel challenges we encountered when adapting the approach of Abel, Öhman, and Vezzosi [2] to parametrized inductive types.

**Bidirectional Typing and Algorithmic Conversion.** Our second tool is a presentation of conversion and typing that, while still inductively defined, is as close as possible to an actual implementation. Typing is bidirectional [32, 46], i.e. decomposed into type inference and type checking, and essentially follows Lennon-Bertrand [32].<fnref n="4" /> We use bidirectional typing for its rigid, canonical derivation structure, rather than for its ability to cut down type annotations on terms. Thus, although we use bidirectional judgements, all our terms infer a type, in contrast to what is common in the bidirectional literature [21, 43], where some terms can only be checked.

Algorithmic conversion, presented in Figure 5 combines ideas from both bidirectional typing and the presentation of Abel, Öhman, and Vezzosi [2]. Crucially, it gets rid entirely of the generic transitivity rule for conversion, and instead uses term-directed reduction, intertwined with comparison of the heads of weak-head normal forms. Algorithmic conversion is mutually defined with a second relation, dedicated to comparing weak-head neutral forms, called when encountering

<footnote n="4">⁴In line with Lennon-Bertrand [32], we pick ▷ as the symbol for inference, and ◁ as the one for checking, to avoid clashes with Coq's => in the formalization.</footnote>
<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 4. Weak-head reduction and normal forms (t stands for an arbitrary term)</figcaption></figure>

**Logical Relations.** Logical relations are our main tool to obtain normalization and canonicity results. At a high-level, we follow the approach of Abel, Öhman, and Vezzosi [2], where the logical relation is based on reducibility, a complex predicate on types and terms, which in particular entails the existence of a weak-head normal form. The key property is the fundamental lemma, stating that every well-typed term is reducible, i.e. that the logical relation is a model of MLTT. The existence of (deep) normal forms is obtained through the inspection of reducibility derivations for a term, since they contain iterated reduction steps to a normal form.

We use the logical relation not only to characterize the normal forms of terms but also the conversion between them, showing that a proof of convertibility between two terms can be transformed to a canonical shape interleaving weak-head reduction sequences and congruence steps between weak-head normal forms. We detail in Section 4 the novel challenges we encountered when adapting the approach of Abel, Öhman, and Vezzosi [2] to parametrized inductive types.

**Bidirectional Typing and Algorithmic Conversion.** Our second tool is a presentation of conversion and typing that, while still inductively defined, is as close as possible to an actual implementation. Typing is bidirectional [32, 46], i.e. decomposed into type inference and type checking, and essentially follows Lennon-Bertrand [32].<fnref n="4" /> We use bidirectional typing for its rigid, canonical derivation structure, rather than for its ability to cut down type annotations on terms. Thus, although we use bidirectional judgements, all our terms infer a type, in contrast to what is common in the bidirectional literature [21, 43], where some terms can only be checked.

Algorithmic conversion, presented in Figure 5 combines ideas from both bidirectional typing and the presentation of Abel, Öhman, and Vezzosi [2]. Crucially, it gets rid entirely of the generic transitivity rule for conversion, and instead uses term-directed reduction, intertwined with comparison of the heads of weak-head normal forms. Algorithmic conversion is mutually defined with a second relation, dedicated to comparing weak-head neutral forms, called when encountering

<footnote n="4">⁴In line with Lennon-Bertrand [32], we pick ▷ as the symbol for inference, and ◁ as the one for checking, to avoid clashes with Coq's => in the formalization.</footnote>
Γ ⊢ n ≈ n' ▷ T Neutrals n and n' are comparable, inferring the type T

$$NVAR \frac{(x : T) \in \Gamma}{\Gamma \vdash x \approx x \triangleright T} \qquad NAPP \frac{\Gamma \vdash n \approx_h n' \triangleright \Pi x : A.B \quad \Gamma \vdash u \cong u' \triangleleft A}{\Gamma \vdash n u \approx n' u' \triangleright B[u]}$$

Γ ⊢ t ≅<sub>h</sub> t' ▷<sub>T</sub> Reduced terms t and t' are convertible at type T

$$CLIST \frac{\Gamma \vdash A \cong A' \triangleleft Type_i}{\Gamma \vdash \mathbf{List} A \cong_h \mathbf{List} A' \triangleleft Type_i} \qquad CPROD \frac{\Gamma, x : A' \vdash B \cong B' \triangleleft Type_i}{\Gamma \vdash \Pi x : A.B \cong_h \Pi x : A'.B' \triangleleft Type_i}$$

$$CFUN \frac{\Gamma, x : A \vdash f x \cong f' x \triangleleft B}{\Gamma \vdash f \cong_h f' \triangleleft \Pi x : A.B} \qquad CCONS \frac{\Gamma \vdash a \cong a' \triangleleft A''}{\Gamma \vdash a \coloneqq_A l \cong_h a' \coloneqq_{A'} l' \triangleleft \mathbf{List} A''}$$

$$NEU LIST \frac{\Gamma \vdash n \cong_h n' \triangleright S}{\Gamma \vdash n \cong_h n' \triangleleft \mathbf{List} A} \qquad NEU NEU \frac{\Gamma \vdash n \approx n' \triangleright N}{\Gamma \vdash n \cong_h n' \triangleleft M}$$

Γ ⊢ t ≅<sub>t'</sub> ▷<sub>T</sub> Terms t and t' are convertible at type T

Γ ⊢ n ≅<sub>h</sub> n' ▷<sub>T</sub> Neutrals n and n' are comparable, inferring reduced type T

$$TMRED \frac{\begin{array}{c} t \rightsquigarrow u \\ T \rightsquigarrow U \end{array} \quad \begin{array}{c} t' \rightsquigarrow u' \\ \Gamma \vdash u \cong_h u' \triangleleft U \end{array}}{\Gamma \vdash t \cong t' \triangleleft T} \qquad NRED \frac{T \rightsquigarrow S \quad nfS}{\Gamma \vdash n \cong_h n' \triangleright S}$$

<table><caption>Fig. 5. Algorithmic conversion (complete rules: Appendix C.2)</caption><thead><tr><th>Judgement</th><th>Input(s)</th><th>Inputs are well-formed</th></tr></thead><tbody><tr><td>Γ ⊢ t ▷ T</td><td>Γ, t</td><td>Γ</td></tr><tr><td>Γ ⊢ t ▷<sub>T</sub> T</td><td>Γ, T, t</td><td>Γ and Γ ⊢ T</td></tr><tr><td>Γ ⊢ T ≅ T' ▷</td><td>Γ, T and T'</td><td>Γ, Γ ⊢ T and Γ ⊢ T'</td></tr><tr><td>Γ ⊢ t ≅ t' ▷<sub>T</sub> T</td><td>Γ, t, t' and T</td><td>Γ, Γ ⊢ T, Γ ⊢ t : T and Γ ⊢ t' : T</td></tr><tr><td>Γ ⊢ t ≈ t' ▷ T</td><td>Γ, t and t'</td><td>Γ, ne t, ne t', and ∃A, A' s.t. Γ ⊢ t : A, Γ ⊢ t' : A'</td></tr></tbody></table>

<caption>Fig. 6. Well-formed inputs (for ≅<sub>h</sub>, ≈<sub>h</sub>, ▷<sub>h</sub>, similar to their non-reduced variants)</caption>

neutrals at positive types. We think of general conversion as “checking”, i.e. taking a type as input, while neutral comparison is “inferring”, i.e. the type is an output. In turn, conversion is used in the following typing rule to compare the inferred type for t with the one it should check against.

$$\mathbf{CHECK} \frac{\Gamma \vdash t \triangleright T' \quad \Gamma \vdash T' \cong T \triangleleft}{\Gamma \vdash t \triangleleft T}$$

Using the consequences of the logical relation, we can show that this algorithmic presentation has many desirable properties. For instance, transitivity is admissible, even though there is no
$\Gamma \vdash n \approx n' \triangleright T$ Neutrals $n$ and $n'$ are comparable, inferring the type $T$

$$NVAR \frac{(x : T) \in \Gamma}{\Gamma \vdash x \approx x \triangleright T} \qquad NAPP \frac{\Gamma \vdash n \approx_h n' \triangleright \Pi x : A.B \qquad \Gamma \vdash u \cong u' \triangleleft A}{\Gamma \vdash n u \approx n' u' \triangleright B[u]}$$

$\Gamma \vdash t \cong_h t' \triangleleft T$ Reduced terms $t$ and $t'$ are convertible at type $T$

$$CLIST \frac{\Gamma \vdash A \cong A' \triangleleft Type_i}{\Gamma \vdash \mathbf{List} A \cong_h \mathbf{List} A' \triangleleft Type_i} \qquad CPROD \frac{\Gamma, x : A' \vdash B \cong B' \triangleleft Type_i}{\Gamma \vdash \Pi x : A.B \cong_h \Pi x : A'.B' \triangleleft Type_i}$$

$$CFUN \frac{\Gamma, x : A \vdash f x \cong f' x \triangleleft B}{\Gamma \vdash f \cong_h f' \triangleleft \Pi x : A.B} \qquad CCONS \frac{\Gamma \vdash a \cong a' \triangleleft A''}{\Gamma \vdash a \coloneqq_A l \cong_h a' \coloneqq_{A'} l' \triangleleft \mathbf{List} A''}$$

$$NEU LIST \frac{\Gamma \vdash n \cong_h n' \triangleright S}{\Gamma \vdash n \cong_h n' \triangleleft \mathbf{List} A} \qquad NEU NEU \frac{\Gamma \vdash n \approx n' \triangleright N}{\Gamma \vdash n \cong_h n' \triangleleft M}$$

$\Gamma \vdash t \cong t' \triangleleft T$ Terms $t$ and $t'$ are convertible at type $T$

$\Gamma \vdash n \cong_h n' \triangleright T$ Neutrals $n$ and $n'$ are comparable, inferring reduced type $T$

$$TMRED \frac{\begin{array}{c} t \rightsquigarrow u \\ T \rightsquigarrow U \end{array} \quad \begin{array}{c} t' \rightsquigarrow u' \\ \Gamma \vdash u \cong_h u' \triangleleft U \end{array}}{\Gamma \vdash t \cong t' \triangleleft T} \qquad NRED \frac{T \rightsquigarrow S \quad nfS}{\Gamma \vdash n \cong_h n' \triangleright S}$$

<table><caption>Fig. 5. Algorithmic conversion (complete rules: Appendix C.2)</caption><thead><tr><th>Judgement</th><th>Input(s)</th><th>Inputs are well-formed</th></tr></thead><tbody><tr><td>Γ ⊢ t ▷ T</td><td>Γ, t</td><td>Γ</td></tr><tr><td>Γ ⊢ t △left T</td><td>Γ, T, t</td><td>Γ and Γ ⊢ T</td></tr><tr><td>Γ ⊢ T ≅ T' △left</td><td>Γ, T and T'</td><td>Γ, Γ ⊢ T and Γ ⊢ T'</td></tr><tr><td>Γ ⊢ t ≅ t' △left T</td><td>Γ, t, t' and T</td><td>Γ, Γ ⊢ T, Γ ⊢ t : T and Γ ⊢ t' : T</td></tr><tr><td>Γ ⊢ t ≈ t' ▷ T</td><td>Γ, t and t'</td><td>Γ, ne t, ne t', and ∃A, A' s.t. Γ ⊢ t : A, Γ ⊢ t' : A'</td></tr></tbody></table>

<caption>Fig. 6. Well-formed inputs (for $\cong_h$, $\approx_h$, $\triangleright_h$, similar to their non-reduced variants)</caption>

neutrals at positive types. We think of general conversion as “checking”, i.e. taking a type as input, while neutral comparison is “inferring”, i.e. the type is an output. In turn, conversion is used in the following typing rule to compare the inferred type for $t$ with the one it should check against.

$$C_{\text{CHECK}} \frac{\Gamma \vdash t \triangleright T' \qquad \Gamma \vdash T' \cong T \triangleleft}{\Gamma \vdash t \triangleleft T}$$

Using the consequences of the logical relation, we can show that this algorithmic presentation has many desirable properties. For instance, transitivity is admissible, even though there is no
dedicated rule. Collecting the properties derived from the logical relation, we can obtain our second main objective: equivalence between the algorithmic and declarative presentations.

**PROPERTY 2.1 (EQUIVALENCE OF THE PRESENTATIONS).** If $Γ ⊢ t : T$, then $Γ ⊢ t < ∗ T$. Conversely, if $Γ ⊢ Γ, Γ ⊢ T$ and $Γ ⊢ t < ∗ T$, then $Γ ⊢ t : T$.

Note that the implication from the bidirectional judgement to the declarative one only holds if the context and type are well-formed. In general, our algorithmic presentations are “garbage-in, garbage-out”: they maintain well-formation of types and contexts, but do not enforce them. Thus, most properties of the algorithmic derivations only hold if their inputs are well-formed, in the sense of Figure 6. Note that in checking and inference modes, while the term is an input, it is of course not assumed to be well-formed in advance, since this is what the judgement itself asserts. This algorithmic, syntax-directed presentation is well suited for implementations and to establish relationships between type systems.

## 3 A FUNCTIONAL TYPE THEORY

We develop an extension MLTT$_{map}$ of MLTT with primitive map$_{F}$ operations for each parametrized type former F of MLTT, that is $Π, Σ, +, List, W$, and $Id$. These map operations internalize the functorial character of the type formers,<fnref n="5" /> and by design *definitely* satisfy the functor laws for each type former F:

$$ \mathrm{map}_F \mathrm{id} \cong \mathrm{id} \qquad (\mathrm{id}-\mathrm{eq}) $$

$$ \mathrm{map}_F f \circ \mathrm{map}_F g \cong \mathrm{map}_F (f \circ g) \qquad (\mathrm{comp}-\mathrm{eq}) $$

Section 3.1 describes the structure needed on type formers to state their functoriality in MLTT$_{map}$. In Section 3.2 we show how *definitely* functorial map$_{F}$ are definable in vanilla MLTT for type formers with an $η$-law. Section 3.3 introduces the main content of this paper, required to enforce the functor laws on inductive type formers: the extension of the equational theory on neutral terms. We explain the technical design choices needed to define and use the logical relations for MLTT$_{map}$ and obtain as a consequence that the theory enjoys consistency, canonicity, and decidable conversion and type-checking. We implement these design choices in Coq for a simplified but representative version of MLTT$_{map}$, with one universe and the $Π, Σ, List$ and $N$ type formers, with their respective map operators. This formalization is detailed in Section 4.

### 3.1 Functionnal Structure on Type Formers

In order to state the functor laws for a type former F, such as $Π, Σ, List, W, Id$, we must specify the categorical structures involved. A type former F is parametrized by a telescope of parameters that we collectively refer to as $dom(F)$, and produces a type. We will always equip the codomain Type of a type former F with the category structure of functions between types, with the standard identity and composition. Note that composition is associative and unital up to conversion, thanks to $η$-laws on function types.

The domain $dom(F)$ of a type former must also be equipped with the structure of a category. We introduce the judgement $Δ ⊢_{map} X : dom(F)$ to stand for a substitution in context $Δ$ of the telescope of parameters of F. Then, given two such instances $X_1$ and $X_2$ of parameters for F, morphisms between $X_1$ and $X_2$ are classified by the judgement $Δ ⊢_{map} ϕ : hom_F(X_1, X_2)$. We require $dom(F)$ to be also equipped with identities and a *definitely* associative and unital composition:

<footnote n="5">⁵These equations are all propositionally true in MLTT, proven by induction for datatypes.</footnote>
dedicated rule. Collecting the properties derived from the logical relation, we can obtain our second main objective: equivalence between the algorithmic and declarative presentations.

**PROPERTY 2.1 (EQUIVALENCE OF THE PRESENTATIONS).** If $Γ ⊢ t : T$, then $Γ ⊢ t < ∤T$. Conversely, if $Γ ⊢ Γ, Γ ⊢ T$ and $Γ ⊢ t < ∤T$, then $Γ ⊢ t : T$.

Note that the implication from the bidirectional judgement to the declarative one only holds if the context and type are well-formed. In general, our algorithmic presentations are “garbage-in, garbage-out”: they maintain well-formation of types and contexts, but do not enforce them. Thus, most properties of the algorithmic derivations only hold if their inputs are well-formed, in the sense of Figure 6. Note that in checking and inference modes, while the term is an input, it is of course not assumed to be well-formed in advance, since this is what the judgement itself asserts. This algorithmic, syntax-directed presentation is well suited for implementations and to establish relationships between type systems.

## 3 A FUNCTIONAL TYPE THEORY

We develop an extension MLTT<sub>map</sub> of MLTT with primitive map<sub>F</sub> operations for each parametrized type former F of MLTT, that is Π, Σ<sub>+</sub>, **List**, **W**, and **Id**. These map operations internalize the functorial character of the type formers,<sup>5</sup> and by design *definitely* satisfy the functor laws for each type former F:

$$ \mathrm{map}_F \mathrm{id} \cong \mathrm{id} \qquad (\mathrm{id}-\mathrm{eq}) $$

$$ \mathrm{map}_F f \circ \mathrm{map}_F g \cong \mathrm{map}_F (f \circ g) \qquad (\mathrm{comp}-\mathrm{eq}) $$

Section 3.1 describes the structure needed on type formers to state their functoriality in MLTT<sub>map</sub>. In Section 3.2 we show how *definitely* functorial map<sub>F</sub> are definable in vanilla MLTT for type formers with an η-law. Section 3.3 introduces the main content of this paper, required to enforce the functor laws on inductive type formers: the extension of the equational theory on neutral terms. We explain the technical design choices needed to define and use the logical relations for MLTT<sub>map</sub> and obtain as a consequence that the theory enjoys consistency, canonicity, and decidable conversion and type-checking. We implement these design choices in Coq for a simplified but representative version of MLTT<sub>map</sub>, with one universe and the Π, Σ, **List** and **N** type formers, with their respective map operators. This formalization is detailed in Section 4.

### 3.1 Functionnal Structure on Type Formers

In order to state the functor laws for a type former F, such as Π, Σ, **List**, **W**, **Id**, we must specify the categorical structures involved. A type former F is parametrized by a telescope of parameters that we collectively refer to as dom(F), and produces a type. We will always equip the codomain Type of a type former F with the category structure of functions between types, with the standard identity and composition. Note that composition is associative and unital up to conversion, thanks to η-laws on function types.

The domain dom(F) of a type former must also be equipped with the structure of a category. We introduce the judgement Δ ⊢<map> X : dom(F) to stand for a substitution in context Δ of the telescope of parameters of F. Then, given two such instances X<sub>1</sub> and X<sub>2</sub> of parameters for F, morphisms between X<sub>1</sub> and X<sub>2</sub> are classified by the judgement Δ ⊢<map> ϕ : hom<sub>F</sub>(X<sub>1</sub>, X<sub>2</sub>). We require dom(F) to be also equipped with identities and a *definitely* associative and unital composition:

<footnote n="5">⁵These equations are all propositionally true in MLTT, proven by induction for datatypes.</footnote>
<table><caption>Fig. 7. Domain and categorical structure on type formers</caption><thead><tr><th>Type former <i>F</i></th><th>Domain &Delta; <sup>&vdash;</sup><sub>map</sub> <i>X</i> : dom(<i>F</i>)</th><th>Morphisms &Delta; <sup>&vdash;</sup><sub>map</sub> &phi; : hom<sub><i>F</i></sub>(<i>&middot;</i><sub>1</sub>, <i>&middot;</i><sub>2</sub>)</th></tr></thead><tbody><tr><td><b>List</b></td><td><i>X</i> = (A) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> A</td><td>&phi; = (f) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td rowspan="2"><i>&Pi;</i></td><td><i>X</i> = (A, B) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> A</td><td>&phi; = (f, g) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f : A<sub>2</sub> &rarr; A<sub>1</sub></td></tr><tr><td>&wedge; &Delta;, a : A <sup>&vdash;</sup><sub>map</sub> B</td><td>&wedge; &Delta;, a : A<sub>2</sub> <sup>&vdash;</sup><sub>map</sub> g : B<sub>1</sub>[f a] &rarr; B<sub>2</sub></td></tr><tr><td rowspan="2"><i>&Sigma;</i></td><td rowspan="2">idem</td><td>&phi; = (f, g) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>&wedge; &Delta;, a : A<sub>1</sub> <sup>&vdash;</sup><sub>map</sub> g : B<sub>1</sub> &rarr; B<sub>2</sub>[f a]</td></tr><tr><td rowspan="2"><b>W</b></td><td rowspan="2">idem</td><td>&phi; = (f, g) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>&wedge; &Delta;, a : A<sub>1</sub> <sup>&vdash;</sup><sub>map</sub> g : B<sub>2</sub>[f a] &rarr; B<sub>1</sub></td></tr><tr><td rowspan="3"><b>Id</b></td><td><i>X</i> = (A, x, y) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> A</td><td>&phi; = (f) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>&wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> x : A</td><td>&wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f x<sub>1</sub> &cong; x<sub>2</sub> : A<sub>2</sub></td></tr><tr><td>&wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> y : A</td><td>&wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f y<sub>1</sub> &cong; y<sub>2</sub> : A<sub>2</sub></td></tr><tr><td rowspan="2">+</td><td><i>X</i> = (A, B) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> A</td><td>&phi; = (f, g) &wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> f : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>&wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> B</td><td>&wedge; &Delta; <sup>&vdash;</sup><sub>map</sub> g : B<sub>1</sub> &rarr; B<sub>2</sub></td></tr></tbody></table>

$$ \frac{\Delta \vdash_{\text{map}} X : \text{dom}(F)}{\Delta \vdash_{\text{map}} \text{id}_X^F : \text{hom}_F(X, X)} \qquad \frac{\Delta \vdash_{\text{map}} \varphi : \text{hom}_F(X, Y)}{\Delta \vdash_{\text{map}} \psi \circ^F \varphi : \text{hom}_F(X, Z)} $$

For instance, for dependent products, dom(Π) and hom<sub>Π</sub> are given by

$$ \begin{array}{lclcl} \Delta \vdash_{\text{map}} (A, B) : \text{dom}(\Pi) & \iff & \Delta \vdash_{\text{map}} A \wedge \Delta, a : A \vdash_{\text{map}} B \\ \Delta \vdash_{\text{map}} (f, g) : \text{hom}_{\Pi}((A_1, B_1), (A_2, B_2)) & \iff & \Delta \vdash_{\text{map}} f : A_2 \to A_1 \wedge \\ & & \Delta, a : A_2 \vdash_{\text{map}} g : B_1[f a] \to B_2 \end{array} $$

with identity $id_{(A,B)}^{\Pi} \stackrel{\text{def}}{=} (id_A, id_B)$ and composition $(f,g) \circ^{\Pi} (f',g') \stackrel{\text{def}}{=} (f' \circ f, g \circ g')$.

The domain and morphism for each type former are described in Figure 7. Identities and compositions are given by the categorical structure on Type for **List** and **Id**, and are defined componentwise, for Σ, **W** and +, similarly to Π. Figure 8 presents the conversion rules of MLTT<sub>map</sub>, extending those of MLTT with general functoriality rules and specific rules for each type former. For each type former *F*, map<sub>*F*</sub> is introduced using MAP and witnesses the functorial nature of *F*, that is *F* maps morphisms φ in its domain between two instances of its parameters *X*, *Y* (left implicit) to functions between types

$$ \Delta \vdash_{\text{map}} \varphi : \text{hom}_{\text{F}}(X, Y) \quad \Rightarrow \quad \Delta \vdash_{\text{map}} \text{map}_{\text{F}} \varphi : F X \to F Y $$

These mapping operations obey the two functor laws, as stated by MAPID and MAPCOMP.

The computational behaviour of maps, as defined by weak-head reduction, depends on the type former. On Π and Σ, map is defined by its observation, namely application for Π and first and second projections for Σ. On inductive types such as **List**, **W**, **Id** and +, map traverses constructors, applying the provided morphism on elements of the parameter type(s), and itself to recursive arguments. This corresponds to the usual notion of map on lists. On **W**-types, the map operation relabels the nodes of the trees using its first component, and reorganizes the subtrees according to its second component. On identity types, the reflexivity proof refl<sub>A<sub>1</sub>,a</sub> at a point *a*: A<sub>1</sub> is mapped to the reflexivity proof at *f*: A<sub>2</sub> for *f*: A<sub>1</sub> → A<sub>2</sub>. On sum types *A* + *B*, either the first or second
<table><caption>Fig. 7. Domain and categorical structure on type formers</caption><thead><tr><th>Type former <i>F</i></th><th>Domain &Delta; &vdash;<sub>map</sub> <i>X</i> : dom(<i>F</i>)</th><th>Morphisms &Delta; &vdash;<sub>map</sub> &phi; : hom<sub><i>F</i></sub>(<i>&#x20D7;</i><sub>1</sub>, <i>&#x20D7;</i><sub>2</sub>)</th></tr></thead><tbody><tr><td><b>List</b></td><td><i>X</i> = (A) &wedge; &Delta; &vdash;<sub>map</sub> A</td><td>&phi; = (<i>f</i>) &wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td rowspan="2"><i>&Pi;</i></td><td><i>X</i> = (A, B) &wedge; &Delta; &vdash;<sub>map</sub> A</td><td>&phi; = (<i>f</i>, <i>g</i>) &wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> : A<sub>2</sub> &rarr; A<sub>1</sub></td></tr><tr><td>&wedge; &Delta;, <i>a</i> : A &vdash;<sub>map</sub> B</td><td>&wedge; &Delta;, <i>a</i> : A<sub>2</sub> &vdash;<sub>map</sub> <i>g</i> : B<sub>1</sub>[<i>f</i> <i>a</i>] &rarr; B<sub>2</sub></td></tr><tr><td rowspan="2"><i>&Sigma;</i></td><td>idem</td><td>&phi; = (<i>f</i>, <i>g</i>) &wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>idem</td><td>&wedge; &Delta;, <i>a</i> : A<sub>1</sub> &vdash;<sub>map</sub> <i>g</i> : B<sub>1</sub> &rarr; B<sub>2</sub>[<i>f</i> <i>a</i>]</td></tr><tr><td rowspan="3"><b>W</b></td><td><i>X</i> = (A, <i>x</i>, <i>y</i>) &wedge; &Delta; &vdash;<sub>map</sub> A</td><td>&phi; = (<i>f</i>) &wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>&wedge; &Delta; &vdash;<sub>map</sub> <i>x</i> : A</td><td>&wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> <i>x</i><sub>1</sub> &cong; <i>x</i><sub>2</sub> : A<sub>2</sub></td></tr><tr><td>&wedge; &Delta; &vdash;<sub>map</sub> <i>y</i> : A</td><td>&wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> <i>y</i><sub>1</sub> &cong; <i>y</i><sub>2</sub> : A<sub>2</sub></td></tr><tr><td rowspan="2">+</td><td><i>X</i> = (A, B) &wedge; &Delta; &vdash;<sub>map</sub> A</td><td>&phi; = (<i>f</i>, <i>g</i>) &wedge; &Delta; &vdash;<sub>map</sub> <i>f</i> : A<sub>1</sub> &rarr; A<sub>2</sub></td></tr><tr><td>&wedge; &Delta; &vdash;<sub>map</sub> B</td><td>&wedge; &Delta; &vdash;<sub>map</sub> <i>g</i> : B<sub>1</sub> &rarr; B<sub>2</sub></td></tr></tbody></table>

$$ \frac{\Delta \vdash_{\text{map}} X : \text{dom}(F)}{\Delta \vdash_{\text{map}} \text{id}_X^F : \text{hom}_F(X, X)} \qquad \frac{\Delta \vdash_{\text{map}} \varphi : \text{hom}_F(X, Y)}{\Delta \vdash_{\text{map}} \psi \circ^F \varphi : \text{hom}_F(X, Z)} $$

For instance, for dependent products, dom(Π) and hom<sub>Π</sub> are given by

$$ \begin{align*} \Delta \vdash_{\text{map}} (A, B) : \text{dom}(\Pi) &\iff \Delta \vdash_{\text{map}} A \wedge \Delta, a : A \vdash_{\text{map}} B \\ \Delta \vdash_{\text{map}} (f, g) : \text{hom}_{\Pi}((A_1, B_1), (A_2, B_2)) &\iff \Delta \vdash_{\text{map}} f : A_2 \to A_1 \wedge \\ & \qquad \Delta, a : A_2 \vdash_{\text{map}} g : B_1[fa] \to B_2 \end{align*} $$

with identity id<sup>Π</sup><sub>(A,B)</sub> ≝<sub>def</sub> (id<sub>A</sub>, id<sub>B</sub>) and composition (<i>f</i>, <i>g</i>) ◦<sup>Π</sup> (<i>f</i>'<sub>1</sub>, <i>g</i>'<sub>1</sub>) ≝<sub>def</sub> (<i>f</i>'<sub>1</sub> ◦ <i>f</i>, <i>g</i> ◦ <i>g</i>'<sub>1</sub>).

The domain and morphism for each type former are described in Figure 7. Identities and compositions are given by the categorical structure on Type for **List** and **Id**, and are defined componentwise, for Σ, **W** and +, similarly to Π. Figure 8 presents the conversion rules of MLTT<sub>map</sub>, extending those of MLTT with general functoriality rules and specific rules for each type former. For each type former *F*, *map*<sub>*F*</sub> is introduced using MAP and witnesses the functorial nature of *F*, that is *F* maps morphisms φ in its domain between two instances of its parameters *X*, *Y* (left implicit) to functions between types

$$ \Delta \vdash_{\text{map}} \varphi : \text{hom}_F(X, Y) \quad \Rightarrow \quad \Delta \vdash_{\text{map}} \text{map}_F \varphi : F X \to F Y $$

These mapping operations obey the two functor laws, as stated by MAPID and MAPCOMP.

The computational behaviour of maps, as defined by weak-head reduction, depends on the type former. On Π and Σ, map is defined by its observation, namely application for Π and first and second projections for Σ. On inductive types such as **List**, **W**, **Id** and +, map traverses constructors, applying the provided morphism on elements of the parameter type(s), and itself to recursive arguments. This corresponds to the usual notion of map on lists. On **W**-types, the map operation relabels the nodes of the trees using its first component, and reorganizes the subtrees according to its second component. On identity types, the reflexivity proof refl<sub>A<sub>1</sub>,a</sub> at a point *a*: A<sub>1</sub> is mapped to the reflexivity proof at *f*<sub>1</sub>: A<sub>2</sub> for *f*: A<sub>1</sub> → A<sub>2</sub>. On sum types *A* + *B*, either the first or second
For each type former $F(\Pi, \Sigma, \mathbf{List}, \mathbf{W}, \mathbf{Id}, +)$

$$ \mathbf{MAP} \quad \frac{\Gamma \vdash_{\mathbf{map}} X, Y : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} f : \mathrm{hom}_F(X, Y)} \quad \mathbf{MAPID} \quad \frac{\Gamma \vdash_{\mathbf{map}} X : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} t : F X} $$

$$ \mathbf{MAPID} \quad \frac{\Gamma \vdash_{\mathbf{map}} X : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} \mathbf{map}_F \mathrm{id}_X^F t \cong t : F X} $$

$$ \mathbf{MAPCOMP} \quad \frac{\Gamma \vdash_{\mathbf{map}} g : \mathrm{hom}_F(X, Y)}{\Gamma \vdash_{\mathbf{map}} f : \mathrm{hom}_F(Y, Z)} \quad \mathbf{MAPCOMP} \quad \frac{\Gamma \vdash_{\mathbf{map}} X, Y, Z : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} t : F X} $$

Specific rules

$$ \mathbf{map}_{\mathbf{List}} f (hd :: tl) \rightsquigarrow^1 f hd :: \mathbf{map}_{\mathbf{List}} f tl \qquad \mathbf{map}_{\mathbf{List}} f \varepsilon \rightsquigarrow^1 \varepsilon $$

$$ \pi_1 (\mathbf{map}_{\Sigma} f p) \rightsquigarrow^1 (\pi_1 f) (\pi_1 p) \qquad \pi_2 (\mathbf{map}_{\Sigma} f p) \rightsquigarrow^1 (\pi_2 f) (\pi_2 p) $$

$$ \mathbf{map}_{\Pi} f h t \rightsquigarrow^1 (\pi_2 f) (h (\pi_1 f t)) \qquad \mathbf{map}_{\mathbf{Id}} f \mathrm{refl}_{A_1, a} \rightsquigarrow^1 \mathrm{refl}_{A_2, f a} $$

$$ \mathbf{map}_{+} (f, g) (\mathrm{inj}^l a) \rightsquigarrow^1 \mathrm{inj}^l (f a) \qquad \mathbf{map}_{+} (f, g) (\mathrm{inj}^r b) \rightsquigarrow^1 \mathrm{inj}^r (g b) $$

$$ \mathbf{map}_{\mathbf{W}} \{T_1\} \{T_2\} f (\sup a k) \rightsquigarrow^1 \sup_{x, \pi_2 T_2} (\pi_1 f a) (\lambda x : (\pi_2 T_2 (\pi_1 f a)). \mathbf{map}_{\mathbf{W}} f (k (\pi_2 g x))) $$

$$ \mathrm{REDMAPCOMP} \quad \frac{\mathrm{ne} \ n \qquad F \in \{\mathbf{List}, \mathbf{Id}, +, \mathbf{W}\}}{\mathbf{map}_F f (\mathbf{map}_F g n) \rightsquigarrow^1 \mathbf{map}_F (f \circ^F g) n} $$

<caption>Fig. 8. MLTT<sub>map</sub> (extends Figures 2 to 5, complete rules: Appendix C.3)</caption>

component of the morphism $(f, g)$ is employed depending on the constructor $\mathrm{inj}^l$ or $\mathrm{inj}^r$. Each reduction rule has a corresponding conversion rule that can be found in Appendix C.3.

*Functorial Maps and Type Former Encodings.* Positive sum types $A+B$ can be simulated in MLTT by the type $\Sigma b : \mathbf{B} \cdot \delta(b, A, B)$, using the branching operation $\delta(b, A, B) \stackrel{\mathrm{def}}{=} \mathrm{ind}_{\mathbf{B}}(b; z, \mathrm{Type}_i; A, B)$. This encoding admits the adequate introduction and elimination rules. It induces a mapping from $\mathrm{dom}(+)$ to $\mathrm{dom}(\Sigma)$, sending a morphism $\Delta \vdash_{\mathbf{map}} (f, g) : \mathrm{hom}_+((A_1, B_1), (A_2, B_2))$ to the morphism $\Delta \vdash_{\mathbf{map}} (\mathrm{id}_{\mathbf{B}}, f \oplus g) : \mathrm{hom}_{\Sigma}((\mathbf{B}, \delta(b, A, B)), (\mathbf{B}, \delta(b, A', B')))$ where $f \oplus g$ is

$$ \Delta, b : \mathbf{B} \vdash_{\mathbf{map}} \mathrm{ind}_{\mathbf{B}}(b; z. \delta(z, A, B) \to \delta(z, A', B'); f, g) : \delta(b, A, B) \to \delta(b, A', B'). $$

We can show by case analysis on $\mathbf{B}$ that this mapping satisfies the propositional functor laws. However, it falls short from satisfying the definitional ones.<fnref n="6" /> It is thus not enough to compose $\mathbf{map}_{\Sigma}$ with this mapping to obtain a functorial action on sum types $A+B$, and explains why we add $+$ primitively.

This obstruction to inductive encodings would motivate a general definition of functorial map for a scheme of indexed inductive types. However, it seems already non-trivial to specify the categorical structure on the domain of an arbitrary inductive type, let alone generate the type and

<footnote n="6">⁶This would amount to an instance of the $\eta$-law for $\mathbf{B}$.</footnote>
For each type former $F(\Pi, \Sigma, \mathbf{List}, \mathbf{W}, \mathbf{Id}, +)$

$$ \mathbf{MAP} \quad \frac{\Gamma \vdash_{\mathbf{map}} X, Y : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} f : \mathrm{hom}_F(X, Y)} \quad \mathbf{MAPID} \quad \frac{\Gamma \vdash_{\mathbf{map}} X : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} t : F X} $$

$$ \mathbf{MAPID} \quad \frac{\Gamma \vdash_{\mathbf{map}} X, Y : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} f : \mathrm{hom}_F(X, Y)} \quad \mathbf{MAPF} \quad \frac{\Gamma \vdash_{\mathbf{map}} id_X^F t \cong t : F X}{\Gamma \vdash_{\mathbf{map}} f : F X} $$

$$ \mathbf{MAPCOMP} \quad \frac{\Gamma \vdash_{\mathbf{map}} g : \mathrm{hom}_F(X, Y)}{\Gamma \vdash_{\mathbf{map}} f : \mathrm{hom}_F(Y, Z)} \quad \mathbf{MAPCOMP} \quad \frac{\Gamma \vdash_{\mathbf{map}} X, Y, Z : \mathrm{dom}(F)}{\Gamma \vdash_{\mathbf{map}} t : F X} \quad \mathbf{MAPCOMP} \quad \frac{\Gamma \vdash_{\mathbf{map}} f : \mathrm{hom}_F(g t) \cong \mathrm{hom}_F(f \circ^F g) t : F Z}{\Gamma \vdash_{\mathbf{map}} f : F X} $$

Specific rules

$$ \mathbf{map_{List}} f (hd :: tl) \rightsquigarrow f hd :: \mathbf{map_{List}} f tl \qquad \mathbf{map_{List}} f \varepsilon \rightsquigarrow \varepsilon $$

$$ \pi_1 (\mathbf{map}_{\Sigma} f p) \rightsquigarrow^1 (\pi_1 f) (\pi_1 p) $$

$$ \pi_2 (\mathbf{map}_{\Sigma} f p) \rightsquigarrow^1 (\pi_2 f) (\pi_2 p) $$

$$ \mathbf{map}_{\Pi} f h t \rightsquigarrow^1 (\pi_2 f) (h (\pi_1 f t)) $$

$$ \mathbf{map_{Id}} f \mathrm{refl}_{A_1, a} \rightsquigarrow^1 \mathrm{refl}_{A_2, f a} $$

$$ \mathbf{map}_{+} (f, g) (\mathrm{inj}^l a) \rightsquigarrow^1 \mathrm{inj}^l (f a) $$

$$ \mathbf{map}_{+} (f, g) (\mathrm{inj}^r b) \rightsquigarrow^1 \mathrm{inj}^r (g b) $$

$$ \mathbf{map_W} \{T_1\} \{T_2\} f (\sup a k) \rightsquigarrow^1 $$

$$ \sup_{x, \pi_2 T_2} (\pi_1 f a) (\lambda x : (\pi_2 T_2 (\pi_1 f a)). \mathbf{map_W} f (k (\pi_2 g x))) $$

$$ \mathbf{REDMAPCOMP} \quad \frac{\text{ne } n \quad F \in \{\mathbf{List}, \mathbf{Id}, +, \mathbf{W}\}}{\mathbf{map}_F f (\mathbf{map}_F g n) \rightsquigarrow^1 \mathbf{map}_F (f \circ^F g) n} $$

<caption>Fig. 8. MLTT<sub>map</sub> (extends Figures 2 to 5, complete rules: Appendix C.3)</caption>

component of the morphism $(f, g)$ is employed depending on the constructor $\mathrm{inj}^l$ or $\mathrm{inj}^r$. Each reduction rule has a corresponding conversion rule that can be found in Appendix C.3.

*Functorial Maps and Type Former Encodings.* Positive sum types $A+B$ can be simulated in MLTT by the type $\Sigma b : \mathbf{B} \cdot \delta(b, A, B)$, using the branching operation $\delta(b, A, B) \stackrel{\mathrm{def}}{=} \mathrm{ind}_{\mathbf{B}}(b; z, \mathrm{Type}_i; A, B)$. This encoding admits the adequate introduction and elimination rules. It induces a mapping from $\mathrm{dom}(+)$ to $\mathrm{dom}(\Sigma)$, sending a morphism $\Delta \vdash_{\mathbf{map}} (f, g) : \mathrm{hom}_+((A_1, B_1), (A_2, B_2))$ to the morphism $\Delta \vdash_{\mathbf{map}} (\mathrm{id}_{\mathbf{B}}, f \oplus g) : \mathrm{hom}_{\Sigma}((\mathbf{B}, \delta(b, A, B)), (\mathbf{B}, \delta(b, A', B')))$ where $f \oplus g$ is

$$ \Delta, b : \mathbf{B} \vdash_{\mathbf{map}} \mathrm{ind}_{\mathbf{B}}(b; z. \delta(z, A, B)) \rightarrow \delta(z, A', B'); f, g : \delta(b, A, B) \rightarrow \delta(b, A', B'). $$

We can show by case analysis on $\mathbf{B}$ that this mapping satisfies the propositional functor laws. However, it falls short from satisfying the definitional ones.<fnref n="6" /> It is thus not enough to compose $\mathbf{map}_{\Sigma}$ with this mapping to obtain a functorial action on sum types $A+B$, and explains why we add $+$ primitively.

This obstruction to inductive encodings would motivate a general definition of functorial map for a scheme of indexed inductive types. However, it seems already non-trivial to specify the categorical structure on the domain of an arbitrary inductive type, let alone generate the type and

<footnote n="6">⁶This would amount to an instance of the η-law for $\mathbf{B}$.</footnote>
equations for the corresponding map operation. Thus, we rather concentrate on understanding the theory on quintessential examples, leaving out a general treatment to future work.

## 3.2 Extensional Types and Map

A type $A$ is extensional when its elements are characterized by their observation, i.e. any element is convertible to its $\eta$-expansion, an elimination followed by an introduction – an equation usually called $\eta$-law. For extensional type formers, it is possible to define a map operation satisfying the functor laws. In MLTT and $MLTT_{map}$, both (strong) dependent sums $\Sigma$ and dependent products $\Pi$ have such extensionality laws, and so their map operations are definable.

$$ \mathrm{map}_{\Pi}((g, f) : \mathrm{hom}_{\Pi}((A, B), (A', B')))(h : \Pi(x : A)B) \stackrel{\mathrm{def}}{=} \lambda x : A' . f(h(g x)) $$

$$ \mathrm{map}_{\Sigma}((g, f) : \mathrm{hom}_{\Sigma}((A, B), (A', B')))(p : \Sigma(x : A)B) \stackrel{\mathrm{def}}{=} (g(\pi_1 p), f(\pi_2 p)) $$

LEMMA 3.1. $\mathrm{map}_{\Pi}$ and $\mathrm{map}_{\Sigma}$ satisfy the definitional functor laws $\mathrm{MAPID}$ and $\mathrm{MAPCOMP}$.

Appendix D.1 gives a direct proof, and the accompanying artifact also shows that the functor laws hold for $\mathrm{CoQ}$'s $\Pi$ and $\Sigma$ types.<fnref n="7" /> The specific rules of Figure 8 hold by $\beta$-reduction.

## 3.3 New Equations for Neutral Terms in Dependent Type Theory

Inductive types in MLTT do not satisfy a definitional $\eta$-law. For identity types, the $\eta$-law is equivalent to the equality reflection principle of extensional MLTT, whose equational theory is undecidable [15, 29]. Extensionality principles for inductive types with recursive occurrences as **List** or **W** are also likely to break the decidability of the equational theory, by adapting an argument for streams [42]. The result of the previous section hence does not apply, and it is instructive to look at the actual obstruction. Consider the case of **List**, and the equation for preservation of identities:

$$ \Gamma \vdash_{\mathrm{map}} \mathrm{map}_{\mathrm{List}} \mathrm{id}_A^{\mathrm{List}} l \cong l : \mathrm{List} A. \quad (*) $$

If we were to define $\mathrm{map}_{\mathrm{List}}$ by induction on lists as is standard, we would get

$$ \mathrm{map}_{\mathrm{List}}(f : A \to B)(l : \mathrm{List} A) \stackrel{\mathrm{def}}{=} \mathrm{ind}_{\mathrm{List}}(\mathrm{List} B; l; \varepsilon_B, hd.tl.ih_{tl}.(f hd) \coloneqq_B ih_{tl}) $$

We can observe that Eq. (*) is validated on closed canonical terms of type **List**:

$$ \begin{align*} \mathrm{map}_{\mathrm{List}} \mathrm{id}_A \varepsilon_A &\cong \varepsilon_A \mathrm{map}_{\mathrm{List}} \mathrm{id}_A (hd \coloneqq_A tl) \\ &\cong (\mathrm{id}_A hd) \coloneqq_A \mathrm{map}_{\mathrm{List}} \mathrm{id}_A tl \stackrel{\mathrm{ind. hyp.}}{\cong} hd \coloneqq_A tl \end{align*} $$

However, on neutral terms, typically variables, we are stuck as long as we stay within the equational theory of MLTT:

$$ A : \mathrm{Type}, x : \mathrm{List} A \not\models \mathrm{map}_{\mathrm{List}} \mathrm{id}_A x \cong x : \mathrm{List} A. $$

In order to validate Eq. (*), $MLTT_{map}$ must thus at the very least extend the equational theory on neutral terms. Allais, McBride, and Boutillier [6] show in the simply-typed case that these equations between neutral terms are actually the only obstruction to functor laws, and in the remainder of this section we discuss how to adapt MLTT to this idea.

<footnote n="7">⁷In file mapPiSigmaFunctorLaws.</footnote>
equations for the corresponding map operation. Thus, we rather concentrate on understanding the theory on quintessential examples, leaving out a general treatment to future work.

## 3.2 Extensional Types and Map

A type $A$ is extensional when its elements are characterized by their observation, i.e. any element is convertible to its $\eta$-expansion, an elimination followed by an introduction – an equation usually called $\eta$-law. For extensional type formers, it is possible to define a map operation satisfying the functor laws. In MLTT and MLTT<sub>map</sub>, both (strong) dependent sums $\Sigma$ and dependent products $\Pi$ have such extensionality laws, and so their map operations are definable.

$$ \mathrm{map}_{\Pi}((g, f) : \mathrm{hom}_{\Pi}((A, B), (A', B')))(h : \Pi(x : A)B) \stackrel{\mathrm{def}}{=} \lambda x : A' . f(h(g x)) $$

$$ \mathrm{map}_{\Sigma}((g, f) : \mathrm{hom}_{\Sigma}((A, B), (A', B')))(p : \Sigma(x : A)B) \stackrel{\mathrm{def}}{=} (g(\pi_1 p), f(\pi_2 p)) $$

LEMMA 3.1. $\mathrm{map}_{\Pi}$ and $\mathrm{map}_{\Sigma}$ satisfy the definitional functor laws MAPID and MAPCOMP.

Appendix D.1 gives a direct proof, and the accompanying artifact also shows that the functor laws hold for Coq's $\Pi$ and $\Sigma$ types.<fnref n="7" /> The specific rules of Figure 8 hold by $\beta$-reduction.

## 3.3 New Equations for Neutral Terms in Dependent Type Theory

Inductive types in MLTT do not satisfy a definitional $\eta$-law. For identity types, the $\eta$-law is equivalent to the equality reflection principle of extensional MLTT, whose equational theory is undecidable [15, 29]. Extensionality principles for inductive types with recursive occurrences as **List** or **W** are also likely to break the decidability of the equational theory, by adapting an argument for streams [42]. The result of the previous section hence does not apply, and it is instructive to look at the actual obstruction. Consider the case of **List**, and the equation for preservation of identities:

$$ \Gamma \vdash_{\mathrm{map}} \mathrm{map}_{\mathrm{List}} \mathrm{id}_A^{\mathrm{List}} l \cong l : \mathrm{List} A. \quad (*) $$

If we were to define $\mathrm{map}_{\mathrm{List}}$ by induction on lists as is standard, we would get

$$ \mathrm{map}_{\mathrm{List}}(f : A \to B)(l : \mathrm{List} A) \stackrel{\mathrm{def}}{=} \mathrm{ind}_{\mathrm{List}}(\mathrm{List} B; l; \varepsilon_B, hd.tl.ih_{tl}.(f hd) \coloneqq_B ih_{tl}) $$

We can observe that Eq. (*) is validated on closed canonical terms of type **List**:

$$ \begin{align*} \mathrm{map}_{\mathrm{List}} \mathrm{id}_A \varepsilon_A &\cong \varepsilon_A \mathrm{map}_{\mathrm{List}} \mathrm{id}_A (hd \coloneqq_A tl) \\ &\cong (\mathrm{id}_A hd) \coloneqq_A \mathrm{map}_{\mathrm{List}} \mathrm{id}_A tl \stackrel{\mathrm{ind. hyp.}}{\cong} hd \coloneqq_A tl \end{align*} $$

However, on neutral terms, typically variables, we are stuck as long as we stay within the equational theory of MLTT:

$$ A : \mathrm{Type}, x : \mathrm{List} A \not\models \mathrm{map}_{\mathrm{List}} \mathrm{id}_A x \cong x : \mathrm{List} A. $$

In order to validate Eq. (*), MLTT<sub>map</sub> must thus at the very least extend the equational theory on neutral terms. Allais, McBride, and Boutillier [6] show in the simply-typed case that these equations between neutral terms are actually the only obstruction to functor laws, and in the remainder of this section we discuss how to adapt MLTT to this idea.

<footnote n="7">⁷In file mapPiSigmaFunctorLaws.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 9. Weak-head normal and neutrals for MLTT<sub>map</sub> (extends Figure 4)</figcaption></figure>

**Map Composition and Compacted Neutrals.** The first step in order to validate the functor laws is to get as close as possible to a canonical representation during reduction. In order to deal with composition of maps, we extend reduction with REDMAPCOMP, merging consecutive stuck maps. In order to preserve the deterministic nature of weak-head reduction, map compaction should only apply when no other rule does. To achieve this, the type former *F* should not be extensional, because map<sub>Π</sub> is already handled through the η-expansion of CFUN, and similarly for map<sub>Σ</sub>. Moreover, the mapped term should be neither a canonical form where map already has a computational behaviour, nor a map itself that could fire the same rule. To control this, we separate neutrals, which cannot contain a map as their head, and *compacted neutrals*, which can start with at most one map, as shown in Figure 9 alongside normal forms. Allais, McBride, and Boutillier [6] also features a similar decomposition of normal forms into three different classes, although their normal forms for lists are more complex than ours as they validate more definitional equations than functor laws.

**Map on Identities.** For identities, using a similar reduction-based approach is difficult: turning the equation Γ ⊢<sub>map</sub> map<sub>List</sub> id<sub>A</sub> l ≅ l : List A into a reduction raises issues similar to those encountered with η-laws. Orienting it as an expansion l ↦→<sup>*</sup> map<sub>List</sub> id<sub>A</sub> l requires knowledge of the type to ensure the expansion only applies to lists, and is potentially non-terminating. Accommodating type-directed reduction would require a deep reworking of our setting.

As a result, just like for η on functions in rule CFUN, we implement this rule as part of conversion, rather than as a reduction. We also incorporate it carefully in the notion of reducible conversion in the logical relation, where we have access to enough properties of the type theories. Since the equation is always validated by canonical forms, we only need to enforce it on compacted neutrals. The logical relation for an inductive type *I* (*List*, *W*, *Id*, +) thus specifies that a neutral *n* is reducibly convertible to a compacted neutral map<sub>*I*</sub> *f* *m*, whenever the neutrals *n* and *m* are convertible and *f* agrees with the identity of dom(*I*) on any neutral term. See MAPNECONVREDL in the next section for the exact rule.

**Eliminators: fusion or no fusion?** When considering the interaction between map and the elimina-
tor ind<sub>List</sub>, a design choice arises: should we also fuse them, i.e. implement the following reduction
rule, which pushes the map from the scrutinee into the branches?

$$
\begin{align*}
\mathrm{ind}_I(\mathrm{map}_{\mathrm{List}} f n; l.P; b_\epsilon, a.l.h.b_\xi) &\rightsquigarrow^1 \\
\mathrm{ind}_I(n; l.P[\mathrm{map}_{\mathrm{List}} f l]; b_\epsilon, a.l.h.b_\xi[\mathrm{id}, f a, \mathrm{map}_{\mathrm{List}} f l, h])
\end{align*}
$$

From the point of view of functorial equations, this is not necessary. Thus, in Figure 9 and the rest
of this paper we take the most conservative approach, and do not add this rule.

However, in the setting of subsumptive bidirectional subtyping, this fusion is necessary if we
wish to infer the parameters of the inductive types from the scrutinee (as in FUS below), rather
than store them in the induction node (as in NoFUS).
<figure><img src="image_7.png" /><figcaption>Fig. 9. Weak-head normal and neutrals for MLTT<sub>map</sub> (extends Figure 4)</figcaption></figure>

*Map Composition and Compacted Neutrals.* The first step in order to validate the functor laws is to get as close as possible to a canonical representation during reduction. In order to deal with composition of maps, we extend reduction with REDMAPCOMP, merging consecutive stuck maps. In order to preserve the deterministic nature of weak-head reduction, map compaction should only apply when no other rule does. To achieve this, the type former *F* should not be extensional, because map<sub>Π</sub> is already handled through the η-expansion of CFUN, and similarly for map<sub>Σ</sub>. Moreover, the mapped term should be neither a canonical form where map already has a computational behaviour, nor a map itself that could fire the same rule. To control this, we separate neutrals, which cannot contain a map as their head, and *compacted neutrals*, which can start with at most one map, as shown in Figure 9 alongside normal forms. Allais, McBride, and Boutillier [6] also features a similar decomposition of normal forms into three different classes, although their normal forms for lists are more complex than ours as they validate more definitional equations than functor laws.

*Map on Identities.* For identities, using a similar reduction-based approach is difficult: turning the equation Γ ⊢<sub>map</sub> map<sub>List</sub> id<sub>A</sub> l ≅ l : List A into a reduction raises issues similar to those encountered with η-laws. Orienting it as an expansion l ↦*<sup>*</sup> map<sub>List</sub> id<sub>A</sub> l requires knowledge of the type to ensure the expansion only applies to lists, and is potentially non-terminating. Accommodating type-directed reduction would require a deep reworking of our setting.

As a result, just like for η on functions in rule CFUN, we implement this rule as part of conversion, rather than as a reduction. We also incorporate it carefully in the notion of reducible conversion in the logical relation, where we have access to enough properties of the type theories. Since the equation is always validated by canonical forms, we only need to enforce it on compacted neutrals. The logical relation for an inductive type *I* (*List*, *W*, *Id*, +) thus specifies that a neutral *n* is reducibly convertible to a compacted neutral map<sub>*I*</sub> *f* *n*, whenever the neutrals *n* and *m* are convertible and *f* agrees with the identity of dom(*I*) on any neutral term. See MAPNECONVREDL in the next section for the exact rule.

*Eliminators: fusion or no fusion?* When considering the interaction between map and the elimina-
tor ind<sub>List</sub>, a design choice arises: should we also fuse them, i.e. implement the following reduction
rule, which pushes the map from the scrutinee into the branches?

$$
\begin{align*}
\mathrm{ind}_I(\mathrm{map}_{\mathrm{List}} f n; l.P; b_\epsilon, a.l.h.b_\ddot{\epsilon}) &\rightsquigarrow^1 \\
\mathrm{ind}_I(n; l.P[\mathrm{map}_{\mathrm{List}} f l]; b_\epsilon, a.l.h.b_\ddot{\epsilon}[\mathrm{id}, f a, \mathrm{map}_{\mathrm{List}} f l, h])
\end{align*}
$$

From the point of view of functorial equations, this is not necessary. Thus, in Figure 9 and the rest
of this paper we take the most conservative approach, and do not add this rule.

However, in the setting of subsumptive bidirectional subtyping, this fusion is necessary if we
wish to infer the parameters of the inductive types from the scrutinee (as in FUS below), rather
than store them in the induction node (as in NoFUS).
$$
\begin{align*}
\text{FUS} &\frac{\Gamma \vdash_{\text{sub}} s \triangleright_h \mathbf{List} A \qquad \Gamma, l : \mathbf{List} A \vdash_{\text{sub}} P \triangleright_h \text{Type} \quad \dots}{\Gamma \vdash_{\text{sub}} \text{ind}_{\mathbf{List}}(s; l.P; \dots) \triangleright P[s]} \\
\text{NoFUS} &\frac{\Gamma \vdash_{\text{sub}} s \triangleleft \mathbf{List} A \qquad \Gamma, l : \mathbf{List} A \vdash_{\text{sub}} P \triangleright_h \text{Type} \quad \dots}{\Gamma \vdash_{\text{sub}} \text{ind}_{\mathbf{List}} A(s; l.P; \dots) \triangleright P[s]}
\end{align*}
$$

Rule FUS is more appealing, as it removes an unnecessary conversion test between the type of s and that stored in the node. Yet, elaborating it to a coercive system requires this target to have the extra fusion law above. Intuitively, this is because rule FUS does not fix the parameter type at which the eliminator is typed, and so this parameter can change, which in a coercive system corresponds to pushing coercions into the branches, as in the fusion equation above.

Experimenting MLTT$_{map}$ through rewrite rules. Even though we have not attempted a justification of the metatheory of MLTT$_{map}$ with a presentation purely based on rewriting, it is still possible to use oriented version of the functor laws to experiment with this theory: AGDA experimentally supports rewrite rules [17] while ongoing implementation work exists for COQ [25]. As an illustration, we implemented Example 1.1 in Agda.<fnref n="8" /> Concretely, we postulate a new constant map$_F$ and add the following rules:

$$
\mathrm{map}_F B' C f (\mathrm{map}_F A B g x) \rightsquigarrow^1 \mathrm{map}_F A C (\lambda z : A. f (g z)) x \quad \text{(comp-rew)}
$$

$$
\mathrm{map}_F A A' (\lambda z : A''.z) x \rightsquigarrow^1 x \qquad \text{(id-rew)}
$$

together with the usual definition of map$_F$ on the constructors of the type former F. We rely on
typing information to enforce that redundant data coincide, for instance that A, A' and A'' are
convertible in id-rew.

4 FORMALIZING NEW EQUATIONS FOR NEUTRAL LISTS

In this section we expose the main components of the accompanying Coq formalization, which covers normalization, equivalence of declarative and algorithmic typing, decidability of type-checking, and canonicity for a subset of MLTT$_{map}$ with 0, N, Π, Σ, List and a single universe. The formalization extends a port to Coq [3] of a previous AGDA formalization [2], which has already been extended multiple times [24, 47, 48]. We focus on the challenges to establish the functor laws on lists, and direct the reader either to the Coq code, or to Abel, Öhman, and Vezzosi and Adjedj et al. for other details. The formalization spans ~26k lines of code, approximately 9k of which are specific to our extension with lists and definitionally functorial maps and are new compared to Adjedj et al. Text in blue refer to files in the companion artifact.

4.1 A Logical Relation withFunctor Laws on List

The Coq development defines both declarative and algorithmic presentations of MLTT<sub>map</sub> and
proves their equivalence through a logical relation parametrized by a generic typing interface<sup>9</sup> in-
stantiated by both presentations. Beyond generic variants of the typing and conversion judgement,
the interface uses two extra judgements: Γ ⊢<sub>map</sub> t ↝* t': A stating that t reduces to t' and that
they are both well typed at type A in context Γ; and Γ ⊢<sub>map</sub> n ≈ n': A stating that n and n' are
convertible neutral terms.

<footnote n="8">⁸See file `map.agda` in the companion artifact.</footnote>

<footnote n="9">⁹Defined in GenericTyping</footnote>
$$
\begin{align*}
\text{FUS} &\frac{\Gamma \vdash_{\text{sub}} s \triangleright_h \mathbf{List} A \qquad \Gamma, l : \mathbf{List} A \vdash_{\text{sub}} P \triangleright_h \text{Type} \quad \dots}{\Gamma \vdash_{\text{sub}} \text{ind}_{\mathbf{List}}(s; l.P; \dots) \triangleright P[s]} \\
\text{NoFUS} &\frac{\Gamma \vdash_{\text{sub}} s \triangleleft \mathbf{List} A \qquad \Gamma, l : \mathbf{List} A \vdash_{\text{sub}} P \triangleright_h \text{Type} \quad \dots}{\Gamma \vdash_{\text{sub}} \text{ind}_{\mathbf{List}} A(s; l.P; \dots) \triangleright P[s]}
\end{align*}
$$

Rule FUS is more appealing, as it removes an unnecessary conversion test between the type of s and that stored in the node. Yet, elaborating it to a coercive system requires this target to have the extra fusion law above. Intuitively, this is because rule FUS does not fix the parameter type at which the eliminator is typed, and so this parameter can change, which in a coercive system corresponds to pushing coercions into the branches, as in the fusion equation above.

Experimenting MLTT$_{map}$ through rewrite rules. Even though we have not attempted a justification of the metatheory of MLTT$_{map}$ with a presentation purely based on rewriting, it is still possible to use oriented version of the functor laws to experiment with this theory: AGDA experimentally supports rewrite rules [17] while ongoing implementation work exists for COQ [25]. As an illustration, we implemented Example 1.1 in Agda.<fnref n="8" /> Concretely, we postulate a new constant map$_F$ and add the following rules:

$$
\mathrm{map}_F B' C f (\mathrm{map}_F A B g x) \rightsquigarrow^1 \mathrm{map}_F A C (\lambda z : A. f (g z)) x \quad \text{(comp-rew)}
$$

$$
\mathrm{map}_F A A' (\lambda z : A''.z) x \rightsquigarrow^1 x \qquad \text{(id-rew)}
$$

together with the usual definition of map$_F$ on the constructors of the type former F. We rely on
typing information to enforce that redundant data coincide, for instance that A, A' and A'' are
convertible in id-rew.

4 FORMALIZING NEW EQUATIONS FOR NEUTRAL LISTS

In this section we expose the main components of the accompanying Coq formalization, which covers normalization, equivalence of declarative and algorithmic typing, decidability of type-checking, and canonicity for a subset of MLTT$_{map}$ with 0, N, Π, Σ, List and a single universe. The formalization extends a port to Coq [3] of a previous AGDA formalization [2], which has already been extended multiple times [24, 47, 48]. We focus on the challenges to establish the functor laws on lists, and direct the reader either to the Coq code, or to Abel, Öhman, and Vezzosi and Adjedj et al. for other details. The formalization spans ~26k lines of code, approximately 9k of which are specific to our extension with lists and definitionally functorial maps and are new compared to Adjedj et al. Text in blue refer to files in the companion artifact.

4.1 A Logical Relation withFunctor Laws on List

The Coq development defines both declarative and algorithmic presentations of MLTT$_{map}$ and
proves their equivalence through a logical relation parametrized by a generic typing interface$^9$ in-
stantiated by both presentations. Beyond generic variants of the typing and conversion judgement,
the interface uses two extra judgements: $\Gamma \vdash_{\text{map}} t \rightsquigarrow^* t'$ : A stating that $t$ reduces to $t'$ and that
they are both well typed at type $A$ in context $\Gamma$; and $\Gamma \vdash_{\text{map}} n \approx n'$ : A stating that $n$ and $n'$ are
convertible neutral terms.

<footnote n="8">⁸See file `map.agda` in the companion artifact.</footnote>

<footnote n="9">⁹Defined in GenericTyping</footnote>
**Definition of the Logical Relation.** In presence of dependent types, the standard strategy of reducibility proofs defining reducibility of terms by induction on their types fails. Rather, reducibility of types and of terms are defined mutually mutually, the latter defined out of a witness of the former, and the former reusing the latter for the universe. Following Abel, Öhman, and Vezzosi [2], we thus first define for each type former *F* what it means to be a type reducible as *F*, and then what it means to be a reducible term and reducibly convertible terms at such a type reducible as *F*. A type is then reducible if it is reducible as *F* for some type former *F*. As we extend the logical relation to handle **List** and map<sub>List</sub>, we focus on a high level description of the reducibility of types as lists and the reducible convertibility of terms of type **List**, the most challenging elements in the definition.<fnref n="10" /> Two points required specific attention with respect to prior work. First, to handle the fact that constructors contain their parameters, we need to impose reducible conversions between these and the parameters coming from the type. Second, in order to validate composition of map on neutrals that may contain a map, we need to equip neutrals with additional reducibility data, rather than pure typing information.

A type *X* is reducible as a list in context Γ, written Γ ⊢<sub>List</sub> *X*, if it weak-head reduces to **List** *A* for some parameter type *A* reducible in any context Δ extending Γ via a weakening ρ : Wk(Δ, Γ). If ℜ : Γ ⊢<sub>List</sub> *X* is a witness that *X* is reducible as a list, then P(以色列) stands for the parameter type *A* of this witness, and P<sub>Γ</sub>(以色列) : Π{ρ : Wk(Δ, Γ)}. Δ ⊢ P(以色列)[ρ] is its witness of reducibility.

Reducible conversion of terms as lists Γ ⊢ t ≅ t' : A | ℜ is defined in Figure 10. Two terms t and t' are reducibly convertible as lists with respect to the witness of reducibility ℜ : Γ ⊢<sub>List</sub> X if they reduce to normal forms v, v' that are reducibly convertible as normal forms of type list Γ ⊢<sub>nf</sub> v ≅ v' : A | ℜ (**ListRED**). Straightforwardly, two canonical forms are convertible if they are both ε (**NILRED**) or both — :: — (**CONSRED**) with reducibly convertible heads and tails.

For compacted neutral forms, we need to consider four cases according to whether each of the
left or the right hand-side term is a map<sub>List</sub>. **NERED** provides the easy case where both terms
are actually neutral, with a single premise requiring that these are convertible as neutrals for the
generic typing interface. **MAPMAPCONVRED** gives the congruence rule for stuck map<sub>List</sub>, relating
map<sub>List</sub> *f* *n* and map<sub>List</sub> *f'* *n'* when the mapped lists *n* and *n'* are convertible as neutrals and
the bodies *f* *x* and *f'* *x* of the functions are reducibly convertible. Note that at this point of the
logical relation, we do not know that the domain of the functions *f* and *f'* is reducible, only that
their codomain is, as provided by P<sub>Γ</sub>(以色列). This constraint motivates both the η-expansion of the
functions on the fly before comparing them, and the necessity of a Kripke-style quantification
on larger contexts for the reducibility of the parameter type P<sub>Γ</sub>(以色列), together ensuring that the
recursive reducible conversion happens at a reducible type, namely an adequate instance of P(以色列).
Finally, the symmetric rules **NEMAPCONVREDR** and **MAPNECONVREDL** deal with the comparison
of a map<sub>List</sub> against a neutral *n*, that can be morally thought as map<sub>List</sub> *id* *n*, and indeed the
premises correspond to what one would obtain with **MAPMAPCONVRED** in that case, up to an
inlined β-reduction step.

*Validity of the Functor Laws.* All the expected properties extend to this new logical relation: reflexivity, symmetry, transitivity, irrelevance with respect to reducible conversion, stability by weakening and anti-reduction. <fnref n="11" /> These properties are essential in order to show that the logical relation validates the functor laws on any reducible term. The proof proceeds through an usual argument for logical relations: on canonical forms, the functor laws hold as observed already in Section 3.3; on compacted neutrals and neutral forms, we need to show that any compositions of map<sub>List</sub> reduce to a single map of a function with a reducible body, which amounts to show that

<footnote n="10">¹⁰Available in file *LogicalRelation*.</footnote>

<footnote n="11">¹¹Available in the directory LogicalRelation.</footnote>
**Definition of the Logical Relation.** In presence of dependent types, the standard strategy of reducibility proofs defining reducibility of terms by induction on their types fails. Rather, reducibility of types and of terms are defined mutually mutually, the latter defined out of a witness of the former, and the former reusing the latter for the universe. Following Abel, Öhman, and Vezzosi [2], we thus first define for each type former *F* what it means to be a type reducible as *F*, and then what it means to be a reducible term and reducibly convertible terms at such a type reducible as *F*. A type is then reducible if it is reducible as *F* for some type former *F*. As we extend the logical relation to handle **List** and map<sub>List</sub>, we focus on a high level description of the reducibility of types as lists and the reducible convertibility of terms of type **List**, the most challenging elements in the definition.<fnref n="10" /> Two points required specific attention with respect to prior work. First, to handle the fact that constructors contain their parameters, we need to impose reducible conversions between these and the parameters coming from the type. Second, in order to validate composition of map on neutrals that may contain a map, we need to equip neutrals with additional reducibility data, rather than pure typing information.

A type *X* is reducible as a list in context Γ, written Γ ⊢<sub>List</sub> *X*, if it weak-head reduces to **List** *A* for some parameter type *A* reducible in any context Δ extending Γ via a weakening ρ : Wk(Δ, Γ). If ℜ : Γ ⊢<sub>List</sub> *X* is a witness that *X* is reducible as a list, then P(以色列) stands for the parameter type *A* of this witness, and P<sub>Γ</sub>(以色列) : Π{ρ : Wk(Δ, Γ)}.Δ ⊢ P(以色列)[ρ] is its witness of reducibility.

Reducible conversion of terms as lists Γ ⊢ t ≅ t' : A | ℜ is defined in Figure 10. Two terms t and t' are reducibly convertible as lists with respect to the witness of reducibility ℜ : Γ ⊢<sub>List</sub> X if they reduce to normal forms v, v' that are reducibly convertible as normal forms of type list Γ ⊢<sub>nf</sub> v ≅ v' : A | ℜ (**ListRED**). Straightforwardly, two canonical forms are convertible if they are both ε (**NILRED**) or both — :: — (**CONSRED**) with reducibly convertible heads and tails.

For compacted neutral forms, we need to consider four cases according to whether each of the
left or the right hand-side term is a map<sub>List</sub>. **NERED** provides the easy case where both terms
are actually neutral, with a single premise requiring that these are convertible as neutrals for the
generic typing interface. **MAPMAPCONVRED** gives the congruence rule for stuck map<sub>List</sub>, relating
map<sub>List</sub> *f* *n* and map<sub>List</sub> *f'* *n'* when the mapped lists *n* and *n'* are convertible as neutrals and
the bodies *f* *x* and *f'* *x* of the functions are reducibly convertible. Note that at this point of the
logical relation, we do not know that the domain of the functions *f* and *f'* is reducible, only that
their codomain is, as provided by P<sub>Γ</sub>(以色列). This constraint motivates both the η-expansion of the
functions on the fly before comparing them, and the necessity of a Kripke-style quantification
on larger contexts for the reducibility of the parameter type P<sub>Γ</sub>(以色列), together ensuring that the
recursive reducible conversion happens at a reducible type, namely an adequate instance of P(以色列).
Finally, the symmetric rules **NEMAPCONVREDR** and **MAPNECONVREDL** deal with the comparison
of a map<sub>List</sub> against a neutral *n*, that can be morally thought as map<sub>List</sub> *id* *n*, and indeed the
premises correspond to what one would obtain with **MAPMAPCONVRED** in that case, up to an
inlined β-reduction step.

*Validity of the Functor Laws.* All the expected properties extend to this new logical relation: reflexivity, symmetry, transitivity, irrelevance with respect to reducible conversion, stability by weakening and anti-reduction.<fnref n="11" /> These properties are essential in order to show that the logical relation validates the functor laws on any reducible term. The proof proceeds through an usual argument for logical relations: on canonical forms, the functor laws hold as observed already in Section 3.3; on compacted neutrals and neutral forms, we need to show that any compositions of map<sub>List</sub> reduce to a single map of a function with a reducible body, which amounts to show that

<footnote n="10">¹⁰Available in file *LogicalRelation*.</footnote>

<footnote n="11">¹¹Available in the directory LogicalRelation.</footnote>
$$ \text{LISTRED} \frac{\Gamma \vdash_{\text{map}} t \rightsquigarrow v : \text{List} \mathbb{P}(\mathfrak{R}) \qquad \Gamma \vdash_{\text{map}} t' \rightsquigarrow v' : \text{List} \mathbb{P}(\mathfrak{R}) \qquad \Gamma \vdash_{\text{nf}} v \cong v' : X \mid \mathfrak{R}}{\Gamma \vdash t \cong t' : X \mid \mathfrak{R}} $$

$$ \text{CONSRED} \frac{\Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \qquad \Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P' \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \\ \Gamma \vdash hd \cong hd' : \mathbb{P}(\mathfrak{R}) \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \qquad \Gamma \vdash tl \cong tl' : X \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} hd \coloneqq_P tl \cong hd' \coloneqq_{P'} tl' : X \mid \mathfrak{R}} $$

$$ \text{NILRED} \frac{\Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \qquad \Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P' \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} \varepsilon_P \cong \varepsilon_{P'} : X \mid \mathfrak{R}} \qquad \text{NERED} \frac{\Gamma \vdash_{\text{map}} n \approx n' : \text{List} \mathbb{P}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} n \cong n' : X \mid \mathfrak{R}} $$

$$ \text{MAPNECONVREDL} \frac{\Gamma \vdash_{\text{map}} n \approx n' : \text{List} \mathbb{P}(\mathfrak{R}) \qquad \Gamma, x : \mathbb{P}(\mathfrak{R}) \vdash f x \cong x : \mathbb{P}(\mathfrak{R}) \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} \text{map}_{\text{List}} f n \cong n' : X \mid \mathfrak{R}} \qquad \text{NEMAPCONVREDR} \dots $$

$$ \text{MAPMAPCONVRED} \frac{\Gamma \vdash_{\text{map}} n \approx n' : \text{List A} \qquad \Gamma, x : A \vdash f x \cong f' x : \mathbb{P}(\mathfrak{R}) \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} \text{map}_{\text{List}} f n \cong \text{map}_{\text{List}} f' n' : X \mid \mathfrak{R}} $$

<caption>Fig. 10. Reducible convertibility of lists (where $\mathfrak{R}$ is a proof of $\Gamma \vdash_{\text{List}} X$)</caption>

composing reducible functions produces reducible outputs on reducible inputs. This last step in the proof reflect our assumption that the categorical structure equipping domains of type formers, here dom(List), should be definitionally associative and unital.

## 4.2 Deciding Conversion and Typechecking for MLTT<sub>map</sub>

Instantiating the generic typing interface of the logical relation with declarative typing provides metatheoretic consequences of the existence of normal forms, among which normalization, injectivity of type constructors and subject reduction. Using those, we can show that algorithmic typing is sound directly by induction, and also that it fits the generic typing interface of the logical relation, which lets us derive that it is complete with respect to declarative typing.

This part of the proof is close to Abel, Öhman, and Vezzosi [2] and Adjedj et al. [3]. The main change is that we adapt algorithmic conversion to reflect the addition of compacted neutrals in our definition of normal forms, by introducing a third mutually defined relation to compare these compacted neutrals. The main idea is summed up in rules `LISTNECONV` and `LISTNEMAP` below: when comparing compacted neutrals, we use the new relation $\approx_{map}$, which simulates the behaviour of the logical relation from Figure 10 on compacted neutrals.

$$ \text{LISTNECONV} \frac{\Gamma \vdash_{\text{map}} c \approx_{\text{map}} c' \triangleleft \text{List A}}{\Gamma \vdash_{\text{map}} c \cong_h c' \triangleleft \text{List A}} $$
$$ \text{LISTNEMAP} \frac{\Gamma \vdash_{\text{map}} n \approx_h n' \triangleright \text{List A} \qquad \Gamma, x : A \vdash f x \cong x \triangleleft B}{\Gamma \vdash_{\text{map}} \text{map}_{\text{List}} f n \approx_{\text{map}} n' \triangleleft \text{List B}} $$

Using this second, algorithmic, instance as a specification, we can show the soundness and completeness of a conversion-checking function extending that of Adjedj et al. [3] with lists and
$$ \text{LISTRED} \frac{\Gamma \vdash_{\text{map}} t \rightsquigarrow v : \mathbf{List} \mathbb{P}(\mathfrak{R}) \qquad \Gamma \vdash_{\text{map}} t' \rightsquigarrow v' : \mathbf{List} \mathbb{P}(\mathfrak{R}) \qquad \Gamma \vdash_{\text{nf}} v \cong v' : X \mid \mathfrak{R}}{\Gamma \vdash t \cong t' : X \mid \mathfrak{R}} $$

$$ \text{CONSRED} \frac{\Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \qquad \Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P' \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \\ \Gamma \vdash hd \cong hd' : \mathbb{P}(\mathfrak{R}) \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \qquad \Gamma \vdash tl \cong tl' : X \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} hd \coloneqq_P tl \cong hd' \coloneqq_{P'} tl' : X \mid \mathfrak{R}} $$

$$ \text{NILRED} \frac{\Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P \mid \mathbb{P}_{\parallel}(\mathfrak{R}) \qquad \Gamma \vdash \mathbb{P}(\mathfrak{R}) \cong P' \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} \varepsilon_P \cong \varepsilon_{P'} : X \mid \mathfrak{R}} \qquad \text{NERED} \frac{\Gamma \vdash_{\text{map}} n \approx n' : \mathbf{List} \mathbb{P}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} n \cong n' : X \mid \mathfrak{R}} $$

$$ \text{MAPNECONVREDL} \frac{\Gamma \vdash_{\text{map}} n \approx n' : \mathbf{List} \mathbb{P}(\mathfrak{R}) \qquad \Gamma, x : \mathbb{P}(\mathfrak{R}) \vdash f x \cong x : \mathbb{P}(\mathfrak{R}) \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} \text{map}_{\mathbf{List}} f n \cong n' : X \mid \mathfrak{R}} \qquad \text{NEMAPCONVREDR} \dots $$

$$ \text{MAPMAPCONVRED} \frac{\Gamma \vdash_{\text{map}} n \approx n' : \mathbf{List} A \qquad \Gamma, x : A \vdash f x \cong f' x : \mathbb{P}(\mathfrak{R}) \mid \mathbb{P}_{\parallel}(\mathfrak{R})}{\Gamma \vdash_{\text{nf}} \text{map}_{\mathbf{List}} f n \cong \text{map}_{\mathbf{List}} f' n' : X \mid \mathfrak{R}} $$

<caption>Fig. 10. Reducible convertibility of lists (where $\mathfrak{R}$ is a proof of $\Gamma \vdash_{\mathbf{List}} X$)</caption>

composing reducible functions produces reducible outputs on reducible inputs. This last step in the proof reflect our assumption that the categorical structure equipping domains of type formers, here dom(*List*), should be definitionally associative and unital.

## 4.2 Deciding Conversion and Typechecking for MLTT<sub>map</sub>

Instantiating the generic typing interface of the logical relation with declarative typing provides metatheoretic consequences of the existence of normal forms, among which normalization, injectivity of type constructors and subject reduction. Using those, we can show that algorithmic typing is sound directly by induction, and also that it fits the generic typing interface of the logical relation, which lets us derive that it is complete with respect to declarative typing.

This part of the proof is close to Abel, Öhman, and Vezzosi [2] and Adjedj et al. [3]. The main change is that we adapt algorithmic conversion to reflect the addition of compacted neutrals in our definition of normal forms, by introducing a third mutually defined relation to compare these compacted neutrals. The main idea is summed up in rules `LISTNECONV` and `LISTNEMAP` below: when comparing compacted neutrals, we use the new relation $\approx_{map}$, which simulates the behaviour of the logical relation from Figure 10 on compacted neutrals.

$$ \text{LISTNECONV} \frac{\Gamma \vdash_{\text{map}} c \approx_{\text{map}} c' \triangleleft \mathbf{List} A}{\Gamma \vdash_{\text{map}} c \cong_h c' \triangleleft \mathbf{List} A} $$

$$ \text{LISTNEMAP} \frac{\Gamma \vdash_{\text{map}} n \approx_h n' \triangleright \mathbf{List} A \qquad \Gamma, x : A \vdash f x \cong x \triangleleft B}{\Gamma \vdash_{\text{map}} \text{map}_{\mathbf{List}} f n \approx_{\text{map}} n' \triangleleft \mathbf{List} B} $$

Using this second, algorithmic, instance as a specification, we can show the soundness and completeness of a conversion-checking function extending that of Adjedj et al. [3] with lists and
$$ \Gamma \vdash_{\text{sub}} T \preceq_h T' \triangleleft $$

Reduced type *T* is a subtype of reduced type *T'*

$$ \begin{array}{ccc} \text{UNISUB} & \frac{\Gamma \vdash_{\text{sub}} \text{Type}_i \preceq_h \text{Type}_i \triangleleft}{\Gamma \vdash_{\text{sub}} \text{Type}_i \preceq_h \text{Type}_i \triangleleft} & \text{PRODSUB} \frac{\Gamma \vdash_{\text{sub}} \Gamma, x : A' \vdash_{\text{sub}} B \preceq B' \triangleleft \Pi x : A.B \preceq_h \Pi x : A'.B' \triangleleft}{\Gamma \vdash_{\text{sub}} \Pi x : A.B \preceq_h \Pi x : A'.B' \triangleleft} \\ \text{LISTSUB} & \frac{\Gamma \vdash_{\text{sub}} A \preceq A' \triangleleft}{\Gamma \vdash_{\text{sub}} \text{List} A \preceq_h \text{List} A' \triangleleft} & \text{NEUSUB} \frac{\Gamma \vdash_{\text{sub}} n \approx_h n' \triangleright T}{\Gamma \vdash_{\text{sub}} n \preceq_h n' \triangleleft} \end{array} $$

<caption>Fig. 11. Algorithmic subtyping between reduced types (extends Figure 5, complete rules: Appendix C.7)</caption>

neutral compaction. Thus, via the equivalence of declarative and algorithmic conversion, we obtain decidability of the rich equational theory of (declarative) MLTT$_{map}$. The details of the function's internals are given in Appendix B.5.

# 5 SUBTYPING, COERCIVE AND SUBSUMPTIVE

The main application we develop for our definitional functor laws is structural subtyping. More precisely, we describe two extensions of MLTT. The first, MLTT$_{sub}$, has subsumptive subtyping: whenever $\vdash_{sub} t : A \preceq A'$, then also $\vdash_{sub} t : A'$, leaving subtyping implicit. The second, MLTT$_{coe}$, features coercive subtyping, witnessed by an operator coe$_{A,A'}$ t explicitly marking where subtyping is used and well-typed whenever $\vdash_{coe} t : A \preceq A'$. The computational behaviour of coe on each type former is informed by the corresponding map in MLTT$_{map}$. Structural coercions can hence be studied modularly in MLTT$_{map}$ and tied together in MLTT$_{coe}$.

In Section 5.1, we give algorithmic presentations of MLTT$_{coe}$ and MLTT$_{sub}$. In the context of a proof assistant or dependently typed programming language, MLTT$_{sub}$ would be the flexible, user-facing system, and MLTT$_{coe}$ its well-behaved specification. We do not develop the equivalence between this algorithmic presentation of MLTT$_{coe}$ and its declarative variant, as its proof is similar to the one for MLTT$_{map}$.

Section 5.3 relates MLTT$_{coe}$ and MLTT$_{sub}$: there is a simple erasure $|\cdot|$ from the former to the latter which removes coercions, and we show it is type-preserving; conversely, we show that any well-typed MLTT$_{sub}$ term can be elaborated to a well-typed MLTT$_{coe}$ term. The extra definitional functor laws are essential at this stage, to ensure that all equalities valid in MLTT$_{sub}$ still hold in MLTT$_{coe}$. Since we are in a dependently typed system, if equations valid in MLTT$_{sub}$ failed to hold in MLTT$_{coe}$, elaboration could not be type-preserving. Finally, Section 5.4 discusses the implications of this equivalence for coherence.

## 5.1 The Type Systems MLTT<sub>sub</sub> and MLTT<sub>coe</sub>

We focus on the structural aspect of subtyping, and a base case is needed to have a non-trivial subtyping relation, i.e. to relate more types than conversion. We use record types with width and depth subtyping as an illustrative and typical instance for such a base case, but other forms of subtyping would work as well, for instance refinement types with subtyping induced by the implication order on predicates.
$$ \Gamma \vdash_{\text{sub}} T \preceq_h T' \triangleleft \quad \text{Reduced type } T \text{ is a subtype of reduced type } T' $$

$$ \begin{array}{ccc} \text{UNISUB} & \frac{\Gamma \vdash_{\text{sub}} \text{Type}_i \preceq_h \text{Type}_i \triangleleft}{\Gamma \vdash_{\text{sub}} \text{Type}_i \preceq_h \text{Type}_i \triangleleft} & \text{PRODSUB} \frac{\Gamma \vdash_{\text{sub}} \Gamma, x : A' \vdash_{\text{sub}} B \preceq B' \triangleleft \Pi x : A.B \preceq_h \Pi x : A'.B' \triangleleft}{\Gamma \vdash_{\text{sub}} \Pi x : A.B \preceq_h \Pi x : A'.B' \triangleleft} \\ \text{LISTSUB} & \frac{\Gamma \vdash_{\text{sub}} A \preceq A' \triangleleft}{\Gamma \vdash_{\text{sub}} \text{List } A \preceq_h \text{List } A' \triangleleft} & \text{NEUSUB} \frac{\Gamma \vdash_{\text{sub}} n \approx_h n' \triangleright T}{\Gamma \vdash_{\text{sub}} n \preceq_h n' \triangleleft} \end{array} $$

<caption>Fig. 11. Algorithmic subtyping between reduced types (extends Figure 5, complete rules: Appendix C.7)</caption>

neutral compaction. Thus, via the equivalence of declarative and algorithmic conversion, we obtain decidability of the rich equational theory of (declarative) MLTT$_{map}$. The details of the function's internals are given in Appendix B.5.

# 5 SUBTYPING, COERCIVE AND SUBSUMPTIVE

The main application we develop for our definitional functor laws is structural subtyping. More precisely, we describe two extensions of MLTT. The first, MLTT$_{sub}$, has subsumptive subtyping: whenever $\vdash_{sub} t : A \preceq A'$, then also $\vdash_{sub} t : A'$, leaving subtyping implicit. The second, MLTT$_{coe}$, features coercive subtyping, witnessed by an operator coe$_{A,A'}$ t explicitly marking where subtyping is used and well-typed whenever $\vdash_{coe} t : A \preceq A'$. The computational behaviour of coe on each type former is informed by the corresponding map in MLTT$_{map}$. Structural coercions can hence be studied modularly in MLTT$_{map}$ and tied together in MLTT$_{coe}$.

In Section 5.1, we give algorithmic presentations of MLTT$_{coe}$ and MLTT$_{sub}$. In the context of a proof assistant or dependently typed programming language, MLTT$_{sub}$ would be the flexible, user-facing system, and MLTT$_{coe}$ its well-behaved specification. We do not develop the equivalence between this algorithmic presentation of MLTT$_{coe}$ and its declarative variant, as its proof is similar to the one for MLTT$_{map}$.

Section 5.3 relates MLTT$_{coe}$ and MLTT$_{sub}$: there is a simple erasure $|\cdot|$ from the former to the latter which removes coercions, and we show it is type-preserving; conversely, we show that any well-typed MLTT$_{sub}$ term can be elaborated to a well-typed MLTT$_{coe}$ term. The extra definitional functor laws are essential at this stage, to ensure that all equalities valid in MLTT$_{sub}$ still hold in MLTT$_{coe}$. Since we are in a dependently typed system, if equations valid in MLTT$_{sub}$ failed to hold in MLTT$_{coe}$, elaboration could not be type-preserving. Finally, Section 5.4 discusses the implications of this equivalence for coherence.

## 5.1 The Type Systems MLTT<sub>sub</sub> and MLTT<sub>coe</sub>

We focus on the structural aspect of subtyping, and a base case is needed to have a non-trivial subtyping relation, i.e. to relate more types than conversion. We use record types with width and depth subtyping as an illustrative and typical instance for such a base case, but other forms of subtyping would work as well, for instance refinement types with subtyping induced by the implication order on predicates.
$$ \mathcal{R}EC\mathcal{T}\mathcal{Y} \quad \frac{\mathcal{L} \in \mathcal{P}_f(\text{ Label})}{\forall l \in \mathcal{L}. \quad \Gamma \vdash_{\text{sub}} A_l \triangleleft} $$

$$ \mathcal{R}EC\mathcal{S}\mathcal{U}\mathcal{B} \quad \frac{\mathcal{K} \subseteq \mathcal{L} \quad \forall k \in \mathcal{K}. \quad \Gamma \vdash_{\text{sub}} A_k \preceq B_k \triangleleft}{\Gamma \vdash_{\text{sub}} \{l : A_l\}_{l \in \mathcal{L}} \preceq_{\mathcal{H}} \{k : B_k\}_{k \in \mathcal{K}} \triangleleft} $$

<caption>Fig. 12. Records, typing and subtyping (extends Figures 5 and 11, complete rules: Appendices C.5 and C.6)</caption>

Algorithmic MLTT<sub>sub</sub>. This system replaces CHECK with the following rule, which uses subtyping ≲ instead of conversion:

$$ \mathcal{C}HECK\mathcal{S}\mathcal{U}\mathcal{B} \quad \frac{\Gamma \vdash_{\text{sub}} t \triangleright T' \quad \Gamma \vdash_{\text{sub}} T' \preceq T \triangleleft}{\Gamma \vdash_{\text{sub}} t \triangleleft T} $$

Subtyping, defined in Figure 11, orients type-level conversion from Figure 5, taking into account co- and contravariance. It relies on neutral comparison and term-level conversion, both of which are not altered with respect to Figure 5: subtyping is a type-level concept only.

A type of records for a non-trivial instance of subtyping. While the rules of Figure 11 let us propagate subtyping structurally through type formers, for the resulting system to be any different from MLTT, we need some base non-trivial subtyping. Its exact choice is largely orthogonal to the focus of this paper on the structural aspect of subtyping, and indeed the development of this section is relatively independent of it. Still, for our subtyping not to be degenerate, we must fix something.

We pick records as a simple example, presented in Figure 12. We fix a countable set of labels Lbl, and for each finite subset L ⊆ Lbl and L-indexed family of types A<sub>l</sub> we introduce a (non-dependent) record type {l : A<sub>l</sub>}<sub>l∈L</sub>.<sup>12</sup> To each record type corresponds a record constructor {l := a<sub>l</sub>}<sub>l∈L</sub>, as well as projections t.l corresponding to labels l ∈ L. Subtyping between record types is defined as inclusion of the set of labels, and pairwise subtyping of types at the same label, i.e. both depth and width subtyping. Full rules for record constructors and projections are given in Appendix C.5.

Algorithmic MLTT<sub>coe</sub>. In contrast with MLTT<sub>sub</sub>, rule CHECK in MLTT<sub>coe</sub> is not altered. Instead, subtyping is only allowed when explicitly marked by coe, as follows:

$$ \mathcal{C}\mathcal{O}\mathcal{E} \quad \frac{\Gamma \vdash_{\text{coe}} A \triangleleft \quad \Gamma \vdash_{\text{coe}} A' \triangleleft \quad \Gamma \vdash_{\text{coe}} t \triangleleft A \quad \Gamma \vdash_{\text{coe}} A \preceq A' \triangleleft}{\Gamma \vdash_{\text{coe}} \text{coe}_{A,A'} t \triangleright A'} $$

Reduction must of course be extended to give an operational behaviour to coe, and is given in Figure 13, together with normal forms. Operationally, coe<sub>A,A'</sub> t reduces the types A and A' to head normal forms, then behaves like the relevant map, propagating coe recursively. Since coe<sub>A,A'</sub> t is well-typed only when A is a subtype of A', the type formers of their head normal forms have to agree, ensuring that we can always rely on this behaviour to enact structural subtyping. As for map, rule COE<sub>COE</sub> lets us compact a succession of stuck coe. This only applies to positive types (characterized by nf<sup>⊕</sup>): we do not compact coercions between negative/extensional types, but wait for the term to be observed to trigger further reduction.

Neutral conversion is described at the top of Figure 14 and features an additional comparison between compacted neutrals similar to MLTT<sub>map</sub> (LISTNECONV). Rule NCOE is a congruence for coercions, where the source and target types necessarily agree by typing invariants, and are thus not compared. Rules NCOEL and NCOER handle identity coercions. Accordingly, ≈<sub>coe</sub> is carefully used whenever normal forms can be compacted neutrals, e.g. at neutral and positive types, as

<footnote n="12"><sup>12</sup>We choose to avoid dependency mainly for the sake of simplicity, but see no difficulty to have dependent records instead.</footnote>
$$ \mathcal{R}EC\text{TY} \quad \frac{\mathcal{L} \in \mathcal{P}_f(\text{ Label})}{\forall l \in \mathcal{L}. \quad \Gamma \vdash_{\text{sub}} A_l \triangleleft} $$

$$ \mathcal{R}EC\text{SUB} \quad \frac{\mathcal{K} \subseteq \mathcal{L}}{\forall k \in \mathcal{K}. \quad \Gamma \vdash_{\text{sub}} A_k \preceq B_k \triangleleft} $$

<caption>Fig. 12. Records, typing and subtyping (extends Figures 5 and 11, complete rules: Appendices C.5 and C.6)</caption>

Algorithmic MLTT<sub>sub</sub>. This system replaces CHECK with the following rule, which uses subtyping ≲ instead of conversion:

$$ \mathcal{C}HECK\text{SUB} \quad \frac{\Gamma \vdash_{\text{sub}} t \triangleright T' \qquad \Gamma \vdash_{\text{sub}} T' \preceq T \triangleleft}{\Gamma \vdash_{\text{sub}} t \triangleleft T} $$

Subtyping, defined in Figure 11, orients type-level conversion from Figure 5, taking into account co- and contravariance. It relies on neutral comparison and term-level conversion, both of which are not altered with respect to Figure 5: subtyping is a type-level concept only.

A type of records for a non-trivial instance of subtyping. While the rules of Figure 11 let us propagate subtyping structurally through type formers, for the resulting system to be any different from MLTT, we need some base non-trivial subtyping. Its exact choice is largely orthogonal to the focus of this paper on the structural aspect of subtyping, and indeed the development of this section is relatively independent of it. Still, for our subtyping not to be degenerate, we must fix something.

We pick records as a simple example, presented in Figure 12. We fix a countable set of labels Lbl, and for each finite subset L ⊆ Lbl and L-indexed family of types A<sub>l</sub> we introduce a (non-dependent) record type {l : A<sub>l</sub>}<sub>l∈L</sub>.<sup>12</sup> To each record type corresponds a record constructor {l := a<sub>l</sub>}<sub>l∈L</sub>, as well as projections t.l corresponding to labels l ∈ L. Subtyping between record types is defined as inclusion of the set of labels, and pairwise subtyping of types at the same label, i.e. both depth and width subtyping. Full rules for record constructors and projections are given in Appendix C.5.

Algorithmic MLTT<sub>coe</sub>. In contrast with MLTT<sub>sub</sub>, rule CHECK in MLTT<sub>coe</sub> is not altered. Instead, subtyping is only allowed when explicitly marked by coe, as follows:

$$ \mathcal{C}\text{OE} \quad \frac{\Gamma \vdash_{\text{coe}} A \triangleleft \qquad \Gamma \vdash_{\text{coe}} A' \triangleleft \qquad \Gamma \vdash_{\text{coe}} t \triangleleft A \qquad \Gamma \vdash_{\text{coe}} A \preceq A' \triangleleft}{\Gamma \vdash_{\text{coe}} \text{coe}_{A,A'} t \triangleright A'} $$

Reduction must of course be extended to give an operational behaviour to coe, and is given in Figure 13, together with normal forms. Operationally, coe<sub>A,A'</sub> t reduces the types A and A' to head normal forms, then behaves like the relevant map, propagating coe recursively. Since coe<sub>A,A'</sub> t is well-typed only when A is a subtype of A', the type formers of their head normal forms have to agree, ensuring that we can always rely on this behaviour to enact structural subtyping. As for map, rule COE<sub>COE</sub> lets us compact a succession of stuck coe. This only applies to positive types (characterized by nf<sup>⊕</sup>): we do not compact coercions between negative/extensional types, but wait for the term to be observed to trigger further reduction.

Neutral conversion is described at the top of Figure 14 and features an additional comparison between compacted neutrals similar to MLTT<sub>map</sub> (LISTNECONV). Rule NCOE is a congruence for coercions, where the source and target types necessarily agree by typing invariants, and are thus not compared. Rules NCOEL and NCOER handle identity coercions. Accordingly, ≈<sub>coe</sub> is carefully used whenever normal forms can be compacted neutrals, e.g. at neutral and positive types, as

<footnote n="12"><sup>12</sup>We choose to avoid dependency mainly for the sake of simplicity, but see no difficulty to have dependent records instead.</footnote>
<figure><img src="image_6.png" /><figcaption>Fig. 13. Weak-head reduction rules for coercion (extends Figure 4, complete rules: Appendix C.8)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 14. Algorithmic comparison of neutrals in MLTT<sub>coe</sub> (extends Figure 5, complete rules: Appendix C.9)</figcaption></figure>

shown at the bottom of Figure 14. Apart from this change, conversion at the term and type level and subtyping are similar to those of MLTT<sub>sub</sub>.

## 5.2 Metatheoretic properties of MLTT<sub>coe</sub>

All the metatheoretic properties of MLTT<sub>map</sub> mentioned in Section 4 carry over to MLTT<sub>coe</sub>. In particular, MLTT<sub>coe</sub> admits weak-head normal forms, a key property in order to properly describe the relationship between subsumptive and coercive subtyping. Following the approach for MLTT<sub>map</sub>, we establish this property by first introducing a declarative version MLTT<sub>coe</sub> of MLTT<sub>coe</sub>, whose
<figure><img src="image_8.png" /><figcaption>Fig. 13. Weak-head reduction rules for coercion (extends Figure 4, complete rules: Appendix C.8)</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 14. Algorithmic comparison of neutrals in MLTT<sub>coe</sub> (extends Figure 5, complete rules: Appendix C.9)</figcaption></figure>

shown at the bottom of Figure 14. Apart from this change, conversion at the term and type level and subtyping are similar to those of MLTT<sub>sub</sub>.

## 5.2 Metatheoretic properties of MLTT<sub>coe</sub>

All the metatheoretic properties of MLTT<sub>map</sub> mentioned in Section 4 carry over to MLTT<sub>coe</sub>. In particular, MLTT<sub>coe</sub> admits weak-head normal forms, a key property in order to properly describe the relationship between subsumptive and coercive subtyping. Following the approach for MLTT<sub>map</sub>, we establish this property by first introducing a declarative version MLTT<sub>coe</sub> of MLTT<sub>coe</sub>, whose
normalisation is obtained through a logical relation, and then, using a further instance of the
logical relation, show that the algorithmic and declarative systems with coercive subtyping are
equivalent. As a by-product, the equivalence also implies that inferred types in the algorithmic
system are principal.

Declarative MLTT<sub>coe</sub>. The declarative presentation of MLTT<sub>coe</sub>, noted ⊢<sub>coe</sub>, straightforwardly extends MLTT (Figures 2 and 3) with typing and conversion rules for records and coe similar to the ones of the algorithmic presentation. Most importantly, it contains the following two rules for definitional identity and composition of coercions.

$$
\text{COEID} \quad \frac{\Gamma \vdash_{\text{coe}} t : A}{\Gamma \vdash_{\text{coe}} \text{coe}_{A,A} t \cong t : A}
$$

$$
\text{COE TRANS} \quad \frac{\Gamma \vdash_{\text{coe}} t : A \qquad \Gamma \vdash_{\text{coe}} A \preceq A' \qquad \Gamma \vdash_{\text{coe}} A' \preceq A''}{\Gamma \vdash_{\text{coe}} \text{coe}_{A',A''} \text{coe}_{A,A'} t \cong \text{coe}_{A,A''} t : A''}
$$

The complete presentation can be found in Appendix C.10. MLTT<sub>coe</sub> serves as a baseline to establish the metatheoretical properties of MLTT<sub>coe</sub>. In particular, it normalizes.

THEOREM 5.1 (WEAK-HEAD NORMALIZATION). If $\Gamma \vdash_{\text{coe}} t : T$, then there exists a weak-head normal form $t'$ such that $t \leadsto^* t'$.

Proof ideas from MLTT<sub>map</sub> carry over to MLTT<sub>coe</sub>, and we did not mechanize this part of the
paper, focusing our formalization effort on the most challenging aspect of the theory. We sketch
how to extend the logical relation for MLTT<sub>map</sub> to MLTT<sub>coe</sub> – the proofs of equivalence between
the declarative and algorithmic systems from the logical relation then remain mostly unchanged.

PROOF SKETCH (EXTENDING THE LOGICAL RELATION TO MLTT<sub>coe</sub>). MLTT<sub>coe</sub> has three main dif-
ferences compared to MLTT<sub>map</sub>: record types, subtyping and coercions.

First, we need to define the logical relation at record types and show the validity of introduction and elimination forms. Since, records behave as iterated Cartesian products, the reducibility proof carries over. Thus, reducibility at record types is defined as reducibility of each projection.

Second, we need to extend reducible type-level conversion to handle subtyping. As the structure of the two judgements is exactly the same, apart from the base subtyping case, we can parame-trize reducible conversion by a *conversion problem*,<fnref n="13" /> a three-valued variant indicating conversion, subtyping, or supertyping, the latter being needed to handle contravariance and the left bias of reducible conversion, which is defined on a proof of reducibility of its left type.

Finally, we need to show that coe<sub>A,A'</sub> t is reducible whenever A is a reducible subtype of A',
and t is reducible at A. Because of the former, both must have normal forms which are either
constructed with the same type former F, both record types, or both neutrals. In the first case,
coe<sub>A,A'</sub> t behaves like map<sub>F</sub>, and the proofs from Section 4 carry over. If A and A' are both neutral,
coe<sub>A,A'</sub> t might compact if t is a coercion, but this is also similar to the case of a neutral map for
lists in MLTT<sub>map</sub>, and so the proof from Section 4 carries over again.

We are left with the case of record types. We need to show that if *t* is reducible at {*l*: *A*<sub>*l*</sub>}<sub>*l*∈*L*</sub> which is a reducible subtype of {*k*: *B*<sub>*k*</sub>}<sub>*k*∈*K*</sub> then coe<{{*l*: *A*<sub>*l*</sub>}<sub>*l*∈*L*</sub>, {*k*: *B*<sub>*k*</sub>}<sub>*k*∈*K*</sub>} *t* is reducible. By definition of reducibility at record types as reducibility of all projections, and closure of reducibility by anti-reduction, it is enough to show that each coe<sub>*A*<sub>*k*</sub>, *B*<sub>*k*</sub></sub> *t.k* is reducible at *B*<sub>*k*</sub> for *k* ∈ *K*. Combining the reducibility of *t.k* obtained from that of *t*, together with the induction hypothesis on the reducible subtyping *A*<sub>*k*</sub> ≁ *B*<sub>*k*</sub> completes this step. □

<footnote n="13"><sup>13</sup>This technique is borrowed from the way cumulativity is handled in META COQ [51].</footnote>
normalisation is obtained through a logical relation, and then, using a further instance of the
logical relation, show that the algorithmic and declarative systems with coercive subtyping are
equivalent. As a by-product, the equivalence also implies that inferred types in the algorithmic
system are principal.

Declarative MLTT<sub>coe</sub>. The declarative presentation of MLTT<sub>coe</sub>, noted ⊢<sub>coe</sub>, straightforwardly extends MLTT (Figures 2 and 3) with typing and conversion rules for records and coe similar to the ones of the algorithmic presentation. Most importantly, it contains the following two rules for definitional identity and composition of coercions.

$$
COEID \quad \frac{\Gamma \vdash_{\mathrm{coe}} t : A}{\Gamma \vdash_{\mathrm{coe}} \mathrm{coe}_{A,A} t \cong t : A}
$$

$$
COETRANS \quad \frac{\Gamma \vdash_{\text{coe}} t : A \qquad \Gamma \vdash_{\text{coe}} A \preceq A' \qquad \Gamma \vdash_{\text{coe}} A' \preceq A''}{\Gamma \vdash_{\text{coe}} \text{coe}_{A',A''} \text{coe}_{A,A'} t \cong \text{coe}_{A,A''} t : A''}
$$

The complete presentation can be found in Appendix C.10. MLTT<sub>coe</sub> serves as a baseline to establish the metatheoretical properties of MLTT<sub>coe</sub>. In particular, it normalizes.

THEOREM 5.1 (WEAK-HEAD NORMALIZATION). If $\Gamma \vdash_{\mathrm{coe}} t : T$, then there exists a weak-head normal form $t'$ such that $t \leadsto^* t'$.

Proof ideas from MLTT<sub>map</sub> carry over to MLTT<sub>coe</sub>, and we did not mechanize this part of the
paper, focusing our formalization effort on the most challenging aspect of the theory. We sketch
how to extend the logical relation for MLTT<sub>map</sub> to MLTT<sub>coe</sub> – the proofs of equivalence between
the declarative and algorithmic systems from the logical relation then remain mostly unchanged.

PROOF SKETCH (EXTENDING THE LOGICAL RELATION TO MLTT<sub>coe</sub>). MLTT<sub>coe</sub> has three main dif-
ferences compared to MLTT<sub>map</sub>: record types, subtyping and coercions.

First, we need to define the logical relation at record types and show the validity of introduction and elimination forms. Since, records behave as iterated Cartesian products, the reducibility proof carries over. Thus, reducibility at record types is defined as reducibility of each projection.

Second, we need to extend reducible type-level conversion to handle subtyping. As the structure
of the two judgements is exactly the same, apart from the base subtyping case, we can parame-
trize reducible conversion by a conversion problem,<fnref n="13" /> a three-valued variant indicating conversion,
subtyping, or supertyping, the latter being needed to handle contravariance and the left bias of
reducible conversion, which is defined on a proof of reducibility of its left type.

Finally, we need to show that coe<sub>A,A'</sub> t is reducible whenever A is a reducible subtype of A',
and t is reducible at A. Because of the former, both must have normal forms which are either
constructed with the same type former F, both record types, or both neutrals. In the first case,
coe<sub>A,A'</sub> t behaves like map<sub>F</sub>, and the proofs from Section 4 carry over. If A and A' are both neutral,
coe<sub>A,A'</sub> t might compact if t is a coercion, but this is also similar to the case of a neutral map for
lists in MLTT<sub>map</sub>, and so the proof from Section 4 carries over again.

We are left with the case of record types. We need to show that if *t* is reducible at {*l*: *A*<sub>*l*</sub>}<sub>*l*∈*L*</sub> which is a reducible subtype of {*k*: *B*<sub>*k*</sub>}<sub>*k*∈*K*</sub> then coe<{{*l*: *A*<sub>*l*</sub>}<sub>*l*∈*L*</sub>, {*k*: *B*<sub>*k*</sub>}<sub>*k*∈*K*</sub>} *t* is reducible. By definition of reducibility at record types as reducibility of all projections, and closure of reducibility by anti-reduction, it is enough to show that each coe<sub>*A*<sub>*k*</sub>, *B*<sub>*k*</sub></sub> *t.k* is reducible at *B*<sub>*k*</sub> for *k* ∈ *K*. Combining the reducibility of *t.k* obtained from that of *t*, together with the induction hypothesis on the reducible subtyping *A*<sub>*k*</sub> ≁ *B*<sub>*k*</sub> completes this step. □

<footnote n="13"><sup>13</sup>This technique is borrowed from the way cumulativity is handled in META COQ [51].</footnote>
*Equivalence of algorithmic and declarative typing.* In order to transfer the weak-head normalization result of MLTT<sub>coe</sub> to MLTT<sub>coe</sub>, we use a second instantiation the logical relation sketched above and obtain soundness and completeness of MLTT<sub>coe</sub> with respect to MLTT<sub>coe</sub>.

**THEOREM 5.2 (SOUNDNESS AND COMPLETENESS OF ALGORITHMIC TYPING).** If $\vdash_{\text{coe}} \Gamma$ and $\Gamma \vdash_{\text{coe}} t \triangleleft T$ then $\Gamma \vdash_{\text{coe}} t : T$, and similarly for the other judgements. Conversely, if $\Gamma \vdash_{\text{coe}} t : T$, then $\Gamma \vdash_{\text{coe}} t \triangleleft T$, and similarly for the other judgements.

As a corollary, if $\Gamma \vdash_{\text{coe}} t : T$ then there exists $T_p$ such that $\Gamma \vdash_{\text{coe}} t \triangleleft T'$ and $\Gamma \vdash_{\text{coe}} T_p \preceq T \triangleleft$, and by uniqueness of the inferred type, $T_p$ is actually the principal type of $t$.

## 5.3 Elaboration and Erasure

We can now turn to the correspondence between MLTT<sub>sub</sub> and MLTT<sub>coe</sub>. The translation in the forward direction, erasure $|\cdot|$, removes coercions $|\text{coe}_{A,A'} t| = t$ and is otherwise a congruence. It is lifted pointwise to contexts. We first show that erasure is sound, meaning that it preserves typing and conversion, and then that it is also invertible, i.e. that any well-typed MLTT<sub>sub</sub> term $t'$ elaborates to a well-typed MLTT<sub>coe</sub> term $t$ whose erasure is $t' = |t|$.

*Soundness of Erasure.* Erasure translates from a constrained system to a more liberal one. Establishing its soundness, e.g. that conversion and typing are preserved, is relatively easy, as long as the reduction rules of Figure 13 are designed so that erasure preserves them. Indeed, the key point is that reduction rules for coe do not change the structure of the erased term, and so erase to exactly zero steps of reduction. In contrast, the rule below is inadequate, as it would η-expand terms at function types more in MLTT<sub>coe</sub> than in MLTT<sub>sub</sub>:

$$ \text{coe}_{\Pi x:A'.B', \Pi x:A.B} f \rightsquigarrow^1 \lambda x : A. \text{coe}_{B' [\text{coe}_{A,A'} x], B} (f \text{coe}_{A,A'} x). $$

The two terms remain nonetheless convertible. By induction on MLTT<sub>coe</sub>'s typing derivation, one can then show that erasure preserves conversion and subtyping, and finally typing.

**THEOREM 5.3 (ERASURE PRESERVES TYPING).** If $\Gamma \vdash_{\text{coe}} t \triangleleft T$ holds and its inputs are well-formed, then $|\Gamma| \vdash_{\text{sub}} |t| \triangleleft |T|$.

*Elaboration.* Elaborating back from MLTT<sub>sub</sub> to MLTT<sub>coe</sub> is more challenging: as we add annotations, we must ensure that these do not hinder conversion. We follow the proof strategy of a similar proof of elaboration soundness in Lennon-Bertrand et al. [35]. The core of the argument are so-called “catch-up lemmas”, which ensure that annotations never block redexes. As an example, here is the one for function types.

**LEMMA 5.4 (CATCH UP, FUNCTION TYPE).** If $\Gamma \vdash_{\text{coe}} f a \triangleleft B$ and $|f| = \lambda x : A'. t'$, then there exists $t$ such that $|t| = t'$ and $f a \rightsquigarrow^* t[a]$.

From these catch-up lemmas it follows that erasure is a backward simulation, therefore that it preserves subtyping, and finally that it is type-preserving. Proofs are all by induction, and given in Appendix D.2.

**LEMMA 5.5 (ERASURE IS A BACKWARD SIMULATION).** Assume that $\Gamma \vdash_{\text{coe}} t : T$. If $|t| \rightsquigarrow^* u'$, with $u'$ a weak-head normal form, then $t \rightsquigarrow^* u$, with $u$ a weak-head normal form such that $|u| = u'$.

**LEMMA 5.6 (ELABORATION PRESERVES SUBTYPING).** The following implications hold whenever the inputs of the conclusions are well-formed:

(1) if $|\Gamma| \vdash_{\text{sub}} |T| \preceq |U| \triangleleft$, then $\Gamma \vdash_{\text{coe}} T \preceq U \triangleleft$;

(2) if $|\Gamma| \vdash_{\text{sub}} |t| \cong |u| \triangleleft |T|$, then $\Gamma \vdash_{\text{coe}} t \cong u \triangleleft T$;
*Equivalence of algorithmic and declarative typing.* In order to transfer the weak-head normalization result of MLTT<sub>coe</sub> to MLTT<sub>coe</sub>, we use a second instantiation the logical relation sketched above and obtain soundness and completeness of MLTT<sub>coe</sub> with respect to MLTT<sub>coe</sub>.

**THEOREM 5.2 (SOUNDNESS AND COMPLETENESS OF ALGORITHMIC TYPING).** If $\vdash_{\text{coe}} \Gamma$ and $\Gamma \vdash_{\text{coe}} t \triangleleft T$ then $\Gamma \vdash_{\text{coe}} t : T$, and similarly for the other judgements. Conversely, if $\Gamma \vdash_{\text{coe}} t : T$, then $\Gamma \vdash_{\text{coe}} t \triangleleft T$, and similarly for the other judgements.

As a corollary, if $\Gamma \vdash_{\text{coe}} t : T$ then there exists $T_p$ such that $\Gamma \vdash_{\text{coe}} t \triangleleft T'$ and $\Gamma \vdash_{\text{coe}} T_p \preceq T \triangleleft$, and by uniqueness of the inferred type, $T_p$ is actually the principal type of $t$.

## 5.3 Elaboration and Erasure

We can now turn to the correspondence between MLTT<sub>sub</sub> and MLTT<sub>coe</sub>. The translation in the forward direction, erasure $|\cdot|$, removes coercions $|\text{coe}_{A,A'} t| = t$ and is otherwise a congruence. It is lifted pointwise to contexts. We first show that erasure is sound, meaning that it preserves typing and conversion, and then that it is also invertible, i.e. that any well-typed MLTT<sub>sub</sub> term $t'$ elaborates to a well-typed MLTT<sub>coe</sub> term $t$ whose erasure is $t' = |t|$.

*Soundness of Erasure.* Erasure translates from a constrained system to a more liberal one. Establishing its soundness, e.g. that conversion and typing are preserved, is relatively easy, as long as the reduction rules of Figure 13 are designed so that erasure preserves them. Indeed, the key point is that reduction rules for coe do not change the structure of the erased term, and so erase to exactly zero steps of reduction. In contrast, the rule below is inadequate, as it would η-expand terms at function types more in MLTT<sub>coe</sub> than in MLTT<sub>sub</sub>:

$$ \text{coe}_{\Pi x:A'.B', \Pi x:A.B} f \rightsquigarrow^1 \lambda x : A. \text{coe}_{B' [\text{coe}_{A,A'} x], B} (f \text{coe}_{A,A'} x). $$

The two terms remain nonetheless convertible. By induction on MLTT<sub>coe</sub>'s typing derivation, one can then show that erasure preserves conversion and subtyping, and finally typing.

**THEOREM 5.3 (ERASURE PRESERVES TYPING).** If $\Gamma \vdash_{\text{coe}} t \triangleleft T$ holds and its inputs are well-formed, then $|\Gamma| \vdash_{\text{sub}} |t| \triangleleft |T|$.

*Elaboration.* Elaborating back from MLTT<sub>sub</sub> to MLTT<sub>coe</sub> is more challenging: as we add annotations, we must ensure that these do not hinder conversion. We follow the proof strategy of a similar proof of elaboration soundness in Lennon-Bertrand et al. [35]. The core of the argument are so-called “catch-up lemmas”, which ensure that annotations never block redexes. As an example, here is the one for function types.

**LEMMA 5.4 (CATCH UP, FUNCTION TYPE).** If $\Gamma \vdash_{\text{coe}} f a \triangleleft B$ and $|f| = \lambda x : A'. t'$, then there exists $t$ such that $|t| = t'$ and $f a \rightsquigarrow^* t[a]$.

From these catch-up lemmas it follows that erasure is a backward simulation, therefore that it preserves subtyping, and finally that it is type-preserving. Proofs are all by induction, and given in Appendix D.2.

**LEMMA 5.5 (ERASURE IS A BACKWARD SIMULATION).** Assume that $\Gamma \vdash_{\text{coe}} t : T$. If $|t| \rightsquigarrow^* u'$, with $u'$ a weak-head normal form, then $t \rightsquigarrow^* u$, with $u$ a weak-head normal form such that $|u| = u'$.

**LEMMA 5.6 (ELABORATION PRESERVES SUBTYPING).** The following implications hold whenever the inputs of the conclusions are well-formed:

(1) if $|\Gamma| \vdash_{\text{sub}} |T| \preceq |U| \triangleleft$, then $\Gamma \vdash_{\text{coe}} T \preceq U \triangleleft$;

(2) if $|\Gamma| \vdash_{\text{sub}} |t| \cong |u| \triangleleft |T|$, then $\Gamma \vdash_{\text{coe}} t \cong u \triangleleft T$;
(3) if $|\Gamma| \vdash_{\text{sub}} |t| \approx |u| \triangleright T$, then $\Gamma \vdash_{\text{coe}} t \approx u \triangleright T$;

(4) and similarly for the other judgements.

Finally, the main theorem states that we can elaborate terms using implicit subtyping to explicit coercions, in a type-preserving way.

**COROLLARY 5.7 (ELABORATION).** If $\vdash_{\text{coe}} \Gamma$, $\Gamma \vdash_{\text{coe}} T \triangleleft$ and $|\Gamma| \vdash_{\text{sub}} t' \triangleleft |T|$, then there exists $t$ such that $\Gamma \vdash_{\text{coe}} t \triangleleft T$, and $|t| = t'$.

Importantly, to establish this equivalence we do not need to develop any meta-theory for MLTT<sub>sub</sub>: having the meta-theory of MLTT<sub>coe</sub> is enough!

Nonetheless, now that the equivalence between the two systems has been established, we can use it to transport meta-theoretic properties, such as normalization, from MLTT<sub>coe</sub> to MLTT<sub>sub</sub>.

## 5.4 Coherence

An important property of elaboration is coherence, stating that the elaboration of a well-typed term does not depend on its typing derivation. In our algorithmic setting, a term has at most one typing derivation and so at most one elaboration. However, multiple well-typed terms in MLTT<sub>coe</sub> can still erase to the same MLTT<sub>sub</sub> term. While only one of them is the result of elaboration as defined in Corollary 5.7, all these distinct terms should still behave similarly. The following is a direct consequence of Lemma 5.6, and shows that the equations imposed on coe are enough to give us a very strong form of coherence: it holds up to definitional equality, rather than in a weaker, semantic way. Another way to look at this is that the scenario of Example 1.2 cannot happen, thanks to our new equations: if two terms erase to the same coercion-free one in MLTT<sub>sub</sub>, then they must be convertible in MLTT<sub>coe</sub>. Hidden coercions cannot be responsible for failures of conversion.

**THEOREM 5.8 (COHERENCE).** If $t, u$ are such that $\Gamma \vdash_{\text{coe}} t \triangleleft T$ and $\Gamma \vdash_{\text{coe}} u \triangleleft T$, with $\vdash_{\text{coe}} \Gamma$ and $\Gamma \vdash_{\text{coe}} T \triangleleft$, and moreover $|t| = |u|$ (i.e. $t$ and $u$ correspond to the same MLTT<sub>sub</sub> term), then $\Gamma \vdash_{\text{coe}} t \cong u \triangleleft T$.

**PROOF.** By reflexivity, (obtained through the equivalence with the declarative system), $\Gamma \vdash_{\text{coe}} t \cong t \triangleleft T$. Using Theorem 5.3 (soundness of erasure), we get $|\Gamma| \vdash_{\text{sub}} |t| \cong |t| \triangleleft |T|$, and so also $|\Gamma| \vdash_{\text{sub}} |t| \cong |u| \triangleleft |T|$. But then by Lemma 5.6 (elaboration preserving conversion), we can come back, and obtain $\Gamma \vdash_{\text{coe}} t \cong u \triangleleft T$. $\square$

As particular cases of this coherence theorem, we can now exhibit the necessity of the functor laws, sharpening the informal argument in the introduction. For the identity law, any well-typed MLTT<sub>coe</sub> term $\text{coe}_{A,A} t$ erases to $|\text{coe}_{A,A} t| = |t|$ in MLTT<sub>sub</sub>, and by coherence we obtain that the conversion $\Gamma \vdash_{\text{coe}} \text{coe}_{A,A} t \cong t \triangleleft A$ is required in MLTT<sub>coe</sub>. For the composition law, we have for adequately well-typed terms that $|\text{coe}_{B,C} \text{coe}_{A,B} t| = |t| = |\text{coe}_{A,C} t|$, hence by coherence the conversion $\Gamma \vdash_{\text{coe}} \text{coe}_{B,C} \text{coe}_{A,B} t \cong \text{coe}_{A,C} t \triangleleft$ must hold in MLTT<sub>coe</sub> as well.

## 6 RELATED AND FUTURE WORK

*Adding Definitional Equations to Dependent Type Theory.* Strub [53] endows a dependent type theory with additional equations from first order decidable theories, with further extensions to a universe hierarchy and large eliminations in Jouannaud and Strub [30] and Barras et al. [11]. Equational theories can sometimes be presented by a confluent set of rewrite rules, a case advocated by Cockx, Tabareau, and Winterhalter [18]. They show through counter-examples that ensuring type preservation in dependent type theory is a subtle matter and do not ensure normalization of the resulting theory. On the theoretical side, categorical tools are being developed to prove general conservativity and strictification results for type theories [12, 13] extending the seminal work
(3) if $|\Gamma| \vdash_{\text{sub}} |t| \approx |u| \triangleright T$, then $\Gamma \vdash_{\text{coe}} t \approx u \triangleright T$;

(4) and similarly for the other judgements.

Finally, the main theorem states that we can elaborate terms using implicit subtyping to explicit
coercions, in a type-preserving way.

COROLLARY 5.7 (ELABORATION). If $\vdash_{\text{coe}} \Gamma$, $\Gamma \vdash_{\text{coe}} T \triangleleft$ and $|\Gamma| \vdash_{\text{sub}} t' \triangleleft |T|$, then there exists $t$ such that $\Gamma \vdash_{\text{coe}} t \triangleleft T$, and $|t| = t'$.

Importantly, to establish this equivalence we do not need to develop any meta-theory for MLTT<sub>sub</sub>: having the meta-theory of MLTT<sub>coe</sub> is enough!

Nonetheless, now that the equivalence between the two systems has been established, we can
use it to transport meta-theoretic properties, such as normalization, from MLTT<sub>coe</sub> to MLTT<sub>sub</sub>.

5.4 Coherence

An important property of elaboration is coherence, stating that the elaboration of a well-typed term
does not depend on its typing derivation. In our algorithmic setting, a term has at most one typing
derivation and so at most one elaboration. However, multiple well-typed terms in MLTT<sub>coe</sub> can still
erase to the same MLTT<sub>sub</sub> term. While only one of them is the result of elaboration as defined
in Corollary 5.7, all these distinct terms should still behave similarly. The following is a direct
consequence of Lemma 5.6, and shows that the equations imposed on coe are enough to give us a
very strong form of coherence: it holds up to definitional equality, rather than in a weaker, semantic
way. Another way to look at this is that the scenario of Example 1.2 cannot happen, thanks to our
new equations: if two terms erase to the same coercion-free one in MLTT<sub>sub</sub>, then they must be
convertible in MLTT<sub>coe</sub>. Hidden coercions cannot be responsible for failures of conversion.

THEOREM 5.8 (COHERENCE). If $t, u$ are such that $\Gamma \vdash_{\text{coe}} t \triangleleft T$ and $\Gamma \vdash_{\text{coe}} u \triangleleft T$, with $\vdash_{\text{coe}} \Gamma$ and $\Gamma \vdash_{\text{coe}} T \triangleleft$, and moreover $|t| = |u|$ (i.e. $t$ and $u$ correspond to the same MLTT<sub>sub</sub> term), then $\Gamma \vdash_{\text{coe}} t \cong u \triangleleft T$.

PROOF. By reflexivity, (obtained through the equivalence with the declarative system), $\Gamma \vdash_{\text{coe}} t \cong t \triangleleft T$. Using Theorem 5.3 (soundness of erasure), we get $|\Gamma| \vdash_{\text{sub}} |t| \cong |t| \triangleleft |T|$, and so also $|\Gamma| \vdash_{\text{sub}} |t| \cong |u| \triangleleft |T|$. But then by Lemma 5.6 (elaboration preserving conversion), we can come back, and obtain $\Gamma \vdash_{\text{coe}} t \cong u \triangleleft T$. $\square$

As particular cases of this coherence theorem, we can now exhibit the necessity of the functor
laws, sharpening the informal argument in the introduction. For the identity law, any well-typed
MLTT<sub>coe</sub> term $\text{coe}_{A,A} t$ erases to $|\text{coe}_{A,A} t| = |t|$ in MLTT<sub>sub</sub>, and by coherence we obtain that
the conversion $\Gamma \vdash_{\text{coe}} \text{coe}_{A,A} t \cong t \triangleleft A$ is required in MLTT<sub>coe</sub>. For the composition law, we have
for adequately well-typed terms that $|\text{coe}_{B,C} \text{coe}_{A,B} t| = |t| = |\text{coe}_{A,C} t|$, hence by coherence the
conversion $\Gamma \vdash_{\text{coe}} \text{coe}_{B,C} \text{coe}_{A,B} t \cong \text{coe}_{A,C} t \triangleleft$ must hold in MLTT<sub>coe</sub> as well.

# 6 RELATED AND FUTURE WORK

Adding Definitional Equations to Dependent Type Theory. Strub [53] endows a dependent type
theory with additional equations from first order decidable theories, with further extensions to a
universe hierarchy and large eliminations in Jouannaud and Strub [30] and Barras et al. [11]. Equa-
tional theories can sometimes be presented by a confluent set of rewrite rules, a case advocated
by Cockx, Tabareau, and Winterhalter [18]. They show through counter-examples that ensuring
type preservation in dependent type theory is a subtle matter and do not ensure normalization of
the resulting theory. On the theoretical side, categorical tools are being developed to prove gen-
eral conservativity and strictification results for type theories [12, 13] extending the seminal work
of Hofmann [26] on conservativity of extensional type theory with respect to intensional type theory [60].

*Formalized Metatheory with Logical Relations.* Allais, McBride, and Boutillier [6] propose to add a variety of fusion laws for lists, including our functor laws, to a simply typed λ-calculus, only sketching an extension to dependent types. The three classes of normal forms (see Figures 9 and 13) is inspired from their work. While we depart from their normalization by evaluation approach to obtain fine-grained results on convergence of iterated weak-head reduction, we expect that the original strategy should extend to dependent types. Formalizing logical relations for MLTT is a difficult exercise, pioneered by Abel, Öhman, and Vezzosi [2] in AGDA using inductive-recursive definitions, and Wieczorek and Biernacki [58] in COQ using impredicativity. We build upon and extend a Coq reimplementation of the former [3].

*Cast and Coercion Operators.* Pujet and Tabareau [47, 48] extend Abel, Öhman, and Vezzosi [2] to establish the metatheory of observational type theory [7]. Their work features a cast operator behaving similarly to coe, but guarded by an internal proof of equality instead of an external subtyping derivation. Their cast does not satisfy definitional transitivity, and we give evidence in Appendix A that such an extension would break metatheoretical properties. Another cast primitive with a similar operational behaviour appears in cast calculi for gradual typing [49], and indeed our proof that elaboration is type preserving in Section 5.3 is inspired by a similar one for GCIC, which combines gradual and dependent types [35]. In this case, casting is allowed between any two types, but the absence of guard is compensated by the possibility of runtime errors, making the type theory inconsistent.

*Functorial Maps for Inductive Type Schemes.* Luo and Adams [38] describe the construction of map for a class of strictly positive operators on paper, but do not implement it. Deriving map-like construction is a typical example of metaprogramming frameworks for proof assistants, e.g. COQ-ELPI [20, 55] in COQ, and the generics AGDA library [22] derives a fold operation, from which map can be easily obtained. In a simply typed setting, Barral and Soloviev [10] employ rewriting techniques, in particular rewriting postponement, to show that an oriented variant of the functor laws are confluent and normalizing. These techniques rely on normalization, and could not be easily adapted to the dependent setting, however the idea of postponing the reduction step for identity appears in our logical relation as well. In a short abstract, McBride and Nordvall Forsberg [44] investigate a notion of functorial adapters that generalizes and unifies both the *CHECK* rule from bidirectional typing and the *COE* rule from *MLTT<sub>coe</sub>*.

*Subtyping, Dependent Types and Algorithmic Derivations.* Coherence of coercions in presence of structural subtyping is a challenging problem. To address the issue, Luo and Luo [39] introduce a notion of weak transitivity, weakening the coherence of the transitivity up to propositional equality. This solution does not interact well with dependency, forcing them to restrict structural subtyping to a class of non-dependent inductives, e.g. excluding (positive) Σ. Luo and Adams [38] show that the transitivity of coercions is admissible in presence of definitional compositions – called χ-rules there – for inductive schemata. They rely on a conjecture that strong normalization and subject reduction hold in presence of these χ-rules, explicitly mentioning that the metatheory with those additional equality rules is “largely unknown”. We provide such results, and have formalized them for *List*. We use a completely different proof technique, that scales to a theory with universes and large elimination. Both aforementioned papers employ a strict order for subtyping and do not consider the functor law for the identity, nor tackle decidability of type-checking.

Aspinall and Compagnoni [9] investigate the relationship between subtyping and dependent types using algorithmic derivations to control the subtyping derivations for a variant of λP, a
of Hofmann [26] on conservativity of extensional type theory with respect to intensional type
theory [60].

*Formalized Metatheory with Logical Relations.* Allais, McBride, and Boutillier [6] propose to add a variety of fusion laws for lists, including our functor laws, to a simply typed λ-calculus, only sketching an extension to dependent types. The three classes of normal forms (see Figures 9 and 13) is inspired from their work. While we depart from their normalization by evaluation approach to obtain fine-grained results on convergence of iterated weak-head reduction, we expect that the original strategy should extend to dependent types. Formalizing logical relations for MLTT is a difficult exercise, pioneered by Abel, Öhman, and Vezzosi [2] in AGDA using inductive-recursive definitions, and Wieczorek and Biernacki [58] in COQ using impredicativity. We build upon and extend a Coq reimplementation of the former [3].

*Cast and Coercion Operators.* Pujet and Tabareau [47, 48] extend Abel, Öhman, and Vezzosi [2] to establish the metatheory of observational type theory [7]. Their work features a cast operator behaving similarly to coe, but guarded by an internal proof of equality instead of an external subtyping derivation. Their cast does not satisfy definitional transitivity, and we give evidence in Appendix A that such an extension would break metatheoretical properties. Another cast primitive with a similar operational behaviour appears in cast calculi for gradual typing [49], and indeed our proof that elaboration is type preserving in Section 5.3 is inspired by a similar one for GCIC, which combines gradual and dependent types [35]. In this case, casting is allowed between any two types, but the absence of guard is compensated by the possibility of runtime errors, making the type theory inconsistent.

*Functorial Maps for Inductive Type Schemes.* Luo and Adams [38] describe the construction of map for a class of strictly positive operators on paper, but do not implement it. Deriving map-like construction is a typical example of metaprogramming frameworks for proof assistants, e.g. Coq-ELPI [20, 55] in Coq, and the generics AGDA library [22] derives a fold operation, from which map can be easily obtained. In a simply typed setting, Barral and Soloviev [10] employ rewriting techniques, in particular rewriting postponement, to show that an oriented variant of the functor laws are confluent and normalizing. These techniques rely on normalization, and could not be easily adapted to the dependent setting, however the idea of postponing the reduction step for identity appears in our logical relation as well. In a short abstract, McBride and Nordvall Forsberg [44] investigate a notion of functorial adapters that generalizes and unifies both the *CHECK* rule from bidirectional typing and the *COE* rule from *MLTT<sub>coe</sub>*.

*Subtyping, Dependent Types and Algorithmic Derivations.* Coherence of coercions in presence of structural subtyping is a challenging problem. To address the issue, Luo and Luo [39] introduce a notion of weak transitivity, weakening the coherence of the transitivity up to propositional equality. This solution does not interact well with dependency, forcing them to restrict structural subtyping to a class of non-dependent inductives, e.g. excluding (positive) Σ. Luo and Adams [38] show that the transitivity of coercions is admissible in presence of definitional compositions – called χ-rules there – for inductive schemata. They rely on a conjecture that strong normalization and subject reduction hold in presence of these χ-rules, explicitly mentioning that the metatheory with those additional equality rules is “largely unknown”. We provide such results, and have formalized them for *List*. We use a completely different proof technique, that scales to a theory with universes and large elimination. Both aforementioned papers employ a strict order for subtyping and do not consider the functor law for the identity, nor tackle decidability of type-checking.

Aspinall and Compagnoni [9] investigate the relationship between subtyping and dependent types using algorithmic derivations to control the subtyping derivations for a variant of λP, a
type theory logically much weaker than MLTT. Lungu and Luo [37] study an elaboration of a subsumptive presentation into coercive one in presence of a coherent signature of subtyping relations between base types. Assuming normalization, they show that subtyping extends to Π types, setting aside other parametrized types. While they work over an abstract signature of coercions, the functor laws we study are needed to instantiate this signature with meaningful datatypes while respecting their assumptions. We explain the relation of these algorithmic system with bidirectional systems, notably the one of Abel, Öhman, and Vezzosi [2], contributing to a sharper picture.

*Integration with Other Forms of Subtyping.* As we mentioned in Section 5, our design of base subtyping was guided by simplicity. Our work on structural subtyping should integrate mostly seamlessly with other, more ambitious forms of subtyping. Coercions between dependent records form the foundation of hierarchical organizations of mathematical structures [4, 19, 59], and should be a simple extension of our framework. This could lead to vast simplification of the complex apparatus currently needed to deal with these hierarchies.

Refinement subtyping is heavily used in F\* but also in COQ's PROGRAM [50] to specify the behaviour of programs. Relativizing any result of decidability of type-checking to that of the chosen fragment of refinements, an implementation of refinement subtyping using definitionally irrelevant propositions [24] to preserve coherence<fnref n="14" /> should be within reach.

Our techniques for structural subtyping should also apply well in the context of algebraic approaches to cumulativity between universes [31, 52]. Cumulativity goes beyond mere subtyping, as it also involves definitional isomorphisms between two copies of the same type at different universe levels. Our definitional functor laws already allow these to interact well with map operations, but it would be interesting to investigate which extra definitional equations are needed – and can be realized – to make structural cumulativity work seamlessly, hopefully obtaining a translation from Russel-style to Tarski-style universes similar to our elaboration from MLTT<sub>sub</sub> to MLTT<sub>coe</sub>.

*Data Availability Statement.* An archive containing the formalization presented in Section 4 is available at [33]. The Coq code is supplemented with a report and a Docker image.

*Acknowledgments.* The authors thank the anonymous reviewers for their feedback. The many useful discussions with Assia Mahboubi, Enzo Crance, Nicolas Tabareau and Loïc Pujet helped a lot to develop the material that led to this paper.

## REFERENCES

[1] Michael Gordon Abbott, Thorsten Altenkirch, and Neil Ghani. "Containers: Constructing strictly positive types". In: *Theor. Comput. Sci.* 342.1 (2005), pp. 3–27. doi: 10.1016/j.tcs.2005.06.002. URL: https://doi.org/10.1016/j.tcs.2005.06.002.

[2] Andreas Abel, Joakim Öhman, and Andrea Vezzosi. "Decidability of Conversion for Type Theory in Type Theory". In: *Proc. ACM Program. Lang. 2.POLP* (Dec. 2017). doi: 10.1145/3158111.

[3] Arthur Adjedj et al. "Martin-Löf à la Coq". In: *Proceedings of the 13th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2024*. 2024.

[4] Reynald Affeldt et al. "Competing inheritance paths in dependent type theory: a case study in functional analysis". In: *IJCAR 2020 - International Joint Conference on Automated Reasoning*. Paris, France, June 2020, pp. 1–19. URL: https://inria.hal.science/hal-02463336.

[5] Agda Development Team. *Agda 2.6.3 documentation*. 2023. URL: https://agda.readthedocs.io/en/v2.6.3/.

<footnote n="14">¹⁴With proof-relevant propositions, different proofs of $p \Rightarrow q$ induce different coercions between $\{x \mid p\}$ and $\{x \mid q\}$, breaking coherence.</footnote>
type theory logically much weaker than MLTT. Lungu and Luo [37] study an elaboration of a sub-
sumptive presentation into coercive one in presence of a coherent signature of subtyping relations
between base types. Assuming normalization, they show that subtyping extends to Π types, set-
ting aside other parametrized types. While they work over an abstract signature of coercions, the
functor laws we study are needed to instantiate this signature with meaningful datatypes while re-
specting their assumptions. We explain the relation of these algorithmic system with bidirectional
systems, notably the one of Abel, Öhman, and Vezzosi [2], contributing to a sharper picture.

*Integration with Other Forms of Subtyping.* As we mentioned in Section 5, our design of base subtyping was guided by simplicity. Our work on structural subtyping should integrate mostly seamlessly with other, more ambitious forms of subtyping. Coercions between dependent records form the foundation of hierarchical organizations of mathematical structures [4, 19, 59], and should be a simple extension of our framework. This could lead to vast simplification of the complex apparatus currently needed to deal with these hierarchies.

Refinement subtyping is heavily used in F\* but also in COQ's PROGRAM [50] to specify the behaviour of programs. Relativizing any result of decidability of type-checking to that of the chosen fragment of refinements, an implementation of refinement subtyping using definitionally irrelevant propositions [24] to preserve coherence<fnref n="14" /> should be within reach.

Our techniques for structural subtyping should also apply well in the context of algebraic ap-
proaches to cumulativity between universes [31, 52]. Cumulativity goes beyond mere subtyping,
as it also involves definitional isomorphisms between two copies of the same type at different uni-
verse levels. Our definitional functor laws already allow these to interact well with map operations,
but it would be interesting to investigate which extra definitional equations are needed – and can
be realized – to make structural cumulativity work seamlessly, hopefully obtaining a translation
from Russel-style to Tarski-style universes similar to our elaboration from MLTT<sub>sub</sub> to MLTT<sub>coe</sub>.

*Data Availability Statement.* An archive containing the formalization presented in Section 4 is
available at [33]. The Coq code is supplemented with a report and a Docker image.

*Acknowledgments.* The authors thank the anonymous reviewers for their feedback. The many useful discussions with Assia Mahboubi, Enzo Crance, Nicolas Tabareau and Loïc Pujet helped a lot to develop the material that led to this paper.

REFERENCES

[1] Michael Gordon Abbott, Thorsten Altenkirch, and Neil Ghani. "Containers: Constructing strictly positive types". In: *Theor. Comput. Sci.* 342.1 (2005), pp. 3–27. doi: 10.1016/j.tcs.2005.06.002. URL: https://doi.org/10.1016/j.tcs.2005.06.002.

[2] Andreas Abel, Joakim Øhman, and Andrea Vezzosi. “Decidability of Conversion for Type Theory in Type Theory”. In: *Proc. ACM Program. Lang. 2.POLP* (Dec. 2017). doi: 10.1145/3158111.

[3] Arthur Adjedj et al. “Martin-Löf à la Coq”. In: *Proceedings of the 13th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2024*. 2024.

[4] Reynald Affeldt et al. “Competing inheritance paths in dependent type theory: a case study in functional analysis”. In: *IJCAR 2020 - International Joint Conference on Automated Reasoning*. Paris, France, June 2020, pp. 1–19. URL: https://inria.hal.science/hal-02463336.

[5] Agda Development Team. *Agda 2.6.3 documentation*. 2023. URL: https://agda.readthedocs.io/en/v2.6.3/.

<footnote n="14">¹⁴With proof-relevant propositions, different proofs of $p \Rightarrow q$ induce different coercions between $\{x | p\}$ and $\{x | q\}$, breaking coherence.</footnote>
[6] Guillaume Allais, Conor McBride, and Pierre Boutillier. "New Equations for Neutral Terms: A Sound and Complete Decision Procedure, Formalized". In: *Proceedings of the 2013 ACM SIGPLAN Workshop on Dependently-Typed Programming*. DTP '13. Boston, Massachusetts, USA: Association for Computing Machinery, 2013, pp. 13–24. ISBN: 9781450323840. DOI: 10.1145/2502409.2502411. URL: https://doi.org/10.1145/2502409.2502411.

[7] Thorsten Altenkirch, Conor McBride, and Wouter Swierstra. "Observational Equality, Now!" In: *Proceedings of the 2007 Workshop on Programming Languages Meets Program Verification*. PLPV '07. Freiburg, Germany: Association for Computing Machinery, 2007, pp. 57–68. ISBN: 9781595936776. DOI: 10.1145/1292597.1292608.

[8] Thorsten Altenkirch et al. "Indexed containers". In: *J. Funct. Program*. 25 (2015). DOI: 10.1017/S095679681500009X. URL: https://doi.org/10.1017/S095679681500009X.

[9] David Aspinall and Adriana Compagnoni. "Subtyping dependent types". In: *Theoretical Computer Science* 266.1 (2001), pp. 273–309. ISSN: 0304-3975. DOI: https://doi.org/10.1016/S0304-3975(00)00175-4. URL: https://www.sciencedirect.com/science/article/pii/S0304397500001754.

[10] Freiric Barral and Sergei Soloviev. "Inductive Type Schemas as Functors". In: *Computer Science - Theory and Applications, First International Symposium on Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings*. Ed. by Dima Grigoriev, John Harrison, and Edward A. Hirsch. Vol. 3967. Lecture Notes in Computer Science. Springer, 2006, pp. 35–45. ISBN: 3-540-34166-8. DOI: 10.1007/11753728\_7. URL: https://doi.org/10.1007/11753728%5C_7.

[11] Bruno Barras et al. "CoQMTU: A Higher-Order Type Theory with a Predicative Hierarchy of Universes Parametrized by a Decidable First-Order Theory". In: *Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, June 21-24, 2011, Toronto, Ontario, Canada*. IEEE Computer Society, 2011, pp. 143–151. ISBN: 978-0-7695-4412-0. DOI: 10.1109/LICS.2011.37. URL: https://doi.org/10.1109/LICS.2011.37.

[12] Rafaël Bocquet. "Strictification of Weakly Stable Type-Theoretic Structures Using Generic Contexts". In: *27th International Conference on Types for Proofs and Programs, TYPES 2021, June 14-18, 2021, Leiden, The Netherlands (Virtual Conference)*. Ed. by Henning Basold, Jesper Cockx, and Silvia Ghilezan. Vol. 239. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 3:1–3:23. ISBN: 978-3-95977-254-9. DOI: 10.4230/LIPIcs.TYPES.2021.3. URL: https://doi.org/10.4230/LIPIcs.TYPES.2021.3.

[13] Rafaël Bocquet. "Towards coherence theorems for equational extensions of type theories". In: *CoRR abs/2304.10343* (2023). DOI: 10.48550/arXiv.2304.10343. arXiv: 2304.10343. URL: https://doi.org/10.48550/arXiv.2304.10343.

[14] Edwin C. Brady. "Idris 2: Quantitative Type Theory in Practice (Artifact)". In: *Dagstuhl Artifacts Ser.* 7.2 (2021), 10:1–10:7. DOI: 10.4230/DARTS.7.2.10. URL: https://doi.org/10.4230/DARTS.7.2.10.

[15] Simon Castellan, Pierre Clairambault, and Peter Dybjer. "Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended version)". In: *Log. Methods Comput. Sci.* 13.4 (2017). DOI: 10.23638/LMCS-13(4:22)2017. URL: https://doi.org/10.23638/LMCS-13(4:22)2017.

[16] Jesper Cockx. *Disable all subtyping by default?* https://github.com/agda/agda/issues/4474. Accessed: 2023-07-10. 2020.

[17] Jesper Cockx. "Type Theory Unchained: Extending Agda with User-Defined Rewrite Rules". In: *25th International Conference on Types for Proofs and Programs (TYPES 2019)*. Ed. by Marc Bezem and Assia Mahboubi. Vol. 175. Leibniz International Proceedings in Informationics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
[6] Guillaume Allais, Conor McBride, and Pierre Boutillier. "New Equations for Neutral Terms: A Sound and Complete Decision Procedure, Formalized". In: *Proceedings of the 2013 ACM SIGPLAN Workshop on Dependently-Typed Programming*. DTP '13. Boston, Massachusetts, USA: Association for Computing Machinery, 2013, pp. 13–24. ISBN: 9781450323840. DOI: 10.1145/2502409.2502411. URL: https://doi.org/10.1145/2502409.2502411.

[7] Thorsten Altenkirch, Conor McBride, and Wouter Swierstra. "Observational Equality, Now!" In: *Proceedings of the 2007 Workshop on Programming Languages Meets Program Verification*. PLPV '07. Freiburg, Germany: Association for Computing Machinery, 2007, pp. 57–68. ISBN: 9781595936776. DOI: 10.1145/1292597.1292608.

[8] Thorsten Altenkirch et al. "Indexed containers". In: *J. Funct. Program*. 25 (2015). DOI: 10.1017/S095679681500009X. URL: https://doi.org/10.1017/S095679681500009X.

[9] David Aspinall and Adriana Compagnoni. "Subtyping dependent types". In: *Theoretical Computer Science* 266.1 (2001), pp. 273–309. ISSN: 0304-3975. DOI: https://doi.org/10.1016/S0304-3975(00)00175-4. URL: https://www.sciencedirect.com/science/article/pii/S0304397500001754.

[10] Freiric Barral and Sergei Soloviev. "Inductive Type Schemas as Functors". In: *Computer Science - Theory and Applications, First International Symposium on Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings*. Ed. by Dima Grigoriev, John Harrison, and Edward A. Hirsch. Vol. 3967. Lecture Notes in Computer Science. Springer, 2006, pp. 35–45. ISBN: 3-540-34166-8. DOI: 10.1007/11753728\_7. URL: https://doi.org/10.1007/11753728%5C_7.

[11] Bruno Barras et al. "CoQMTU: A Higher-Order Type Theory with a Predicative Hierarchy of Universes Parametrized by a Decidable First-Order Theory". In: *Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, June 21-24, 2011, Toronto, Ontario, Canada*. IEEE Computer Society, 2011, pp. 143–151. ISBN: 978-0-7695-4412-0. DOI: 10.1109/LICS.2011.37. URL: https://doi.org/10.1109/LICS.2011.37.

[12] Rafaël Bocquet. "Strictification of Weakly Stable Type-Theoretic Structures Using Generic Contexts". In: *27th International Conference on Types for Proofs and Programs, TYPES 2021, June 14-18, 2021, Leiden, The Netherlands (Virtual Conference)*. Ed. by Henning Basold, Jesper Cockx, and Silvia Ghilezan. Vol. 239. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 3:1–3:23. ISBN: 978-3-95977-254-9. DOI: 10.4230/LIPIcs.TYPES.2021.3. URL: https://doi.org/10.4230/LIPIcs.TYPES.2021.3.

[13] Rafaël Bocquet. "Towards coherence theorems for equational extensions of type theories". In: *CoRR abs/2304.10343* (2023). DOI: 10.48550/arXiv.2304.10343. arXiv: 2304.10343. URL: https://doi.org/10.48550/arXiv.2304.10343.

[14] Edwin C. Brady. "Idris 2: Quantitative Type Theory in Practice (Artifact)". In: *Dagstuhl Artifacts Ser.* 7.2 (2021), 10:1–10:7. DOI: 10.4230/DARTS.7.2.10. URL: https://doi.org/10.4230/DARTS.7.2.10.

[15] Simon Castellan, Pierre Clairambault, and Peter Dybjer. "Undecidability of Equality in the Free Locally Cartesian Closed Category (Extended version)". In: *Log. Methods Comput. Sci.* 13.4 (2017). DOI: 10.23638/LMCS-13(4:22)2017. URL: https://doi.org/10.23638/LMCS-13(4:22)2017.

[16] Jesper Cockx. *Disable all subtyping by default?* https://github.com/agda/agda/issues/4474. Accessed: 2023-07-10. 2020.

[17] Jesper Cockx. "Type Theory Unchained: Extending Agda with User-Defined Rewrite Rules". In: *25th International Conference on Types for Proofs and Programs (TYPES 2019)*. Ed. by Marc Bezem and Assia Mahboubi. Vol. 175. Leibniz International Proceedings in Informationics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.