$$ \llbracket \alpha \rrbracket_K = \begin{cases} \alpha & \text{if } K(\alpha) = \bullet \\ (\text{low}_K(L, T) \lor \alpha) \land \text{upp}_K(U, T) & \text{if } K(\alpha) = (L, U, T) \end{cases} $$

$$ \llbracket \tau_1 \to \tau_2 \rrbracket_K = \llbracket \tau_1 \rrbracket_K \to \llbracket \tau_2 \rrbracket_K $$ $$ \llbracket \tau_1 \times \tau_2 \rrbracket_K = \llbracket \tau_1 \rrbracket_K \times \llbracket \tau_2 \rrbracket_K $$

where:

$$ \text{low}_K(L, T) = \bigvee_{\gamma \in L} \text{tag}(\bigwedge_{\gamma \in T} \llbracket \tau \rrbracket_K) $$ $$ \text{upp}_K(U, T) = \begin{cases} \bigvee_{\gamma \in U} \text{tag}(\bigwedge_{\gamma \in T} \llbracket \tau \rrbracket_K) & \text{if } U \neq \mathcal{L} \\ \bigvee_{\gamma \in \text{dom}(T)} \text{tag}(\bigwedge_{\gamma \in T} \llbracket \tau \rrbracket_K) \lor (1_v \land \bigvee_{\gamma \in \text{dom}(T)} \text{tag}(1)) & \text{if } U = \mathcal{L} \end{cases} $$

<caption>**Figure 12.** Translation of k-types to s-types.</caption>

We define the translation of type schemes as $\llbracket \forall A. K' \triangleright \tau \rrbracket_K = \forall A. \llbracket \tau \rrbracket_{K,K'}$ and of type environments by translating each type scheme pointwise.

**Lemma A.29.** For any k-type $\tau$ in a non-recursive kinding environment $K$, we have $\text{var}(\llbracket \tau \rrbracket_K) \subseteq \text{var}_K(\tau)$. Likewise, for any k-scheme $\sigma$ and k-type environment $\Gamma$, we have $\text{var}(\llbracket \sigma \rrbracket_K) \subseteq \text{var}_K(\sigma)$ and $\text{var}(\llbracket \Gamma \rrbracket_K) \subseteq \text{var}_K(\Gamma)$.

*Proof.* The translation does not introduce new variables, therefore we can show $\text{var}(\llbracket \tau \rrbracket_K) \subseteq \text{var}_K(\tau)$ by induction on $w(\tau, K)$. We extend this straightforwardly to type schemes and environments. $\square$

**Lemma A.30.** Let $p$ be a pattern and $t \le \lceil p \rceil$ an s-type. If $K \vdash p: \tau \Rightarrow \Gamma$ and $t \le \llbracket \tau \rrbracket_K$, then, for all $x \in \text{capt}(p)$, $(t//p)(x) \le \llbracket \Gamma(x) \rrbracket_K$.

*Proof.* By structural induction on $p$.

Cases $p = -$ and $p = c$ There is nothing to prove since $\text{capt}(p) = \emptyset$.

Case $p = x$ We have

$$ K \vdash p: \tau \Rightarrow \{x: \tau\} \quad t//x = \{x: t\} $$

and must prove $\{x: t\}(x) \le \llbracket \{x: \tau\}(x) \rrbracket_K$, that is, $t \le \llbracket \tau \rrbracket_K$, which is true by hypothesis.

Case $p = (p_1, p_2)$ We have

$$ K \vdash p: \tau_1 \times \tau_2 \Rightarrow \Gamma \quad \Gamma = \Gamma_1 \cup \Gamma_2 \quad \forall i. K \vdash p_i: \tau_i \Rightarrow \Gamma_i $$ $$ t//p = \pi_1(t)//p_1 \cup \pi_2(t)//p_2. $$

Since $t \le \llbracket \tau_1 \rrbracket_K \times \llbracket \tau_2 \rrbracket_K$, by Property A.31 we have $\pi_i(t) \le \llbracket \tau_i \rrbracket_K$. Likewise, $\pi_i(t) \le \lceil p_i \rceil$. We apply the induction hypothesis to conclude.

Case $p = \text{tag}(p_1)$ We have

$$ K \vdash p: \alpha \Rightarrow \Gamma \quad K \vdash p_1: \tau_1 \Rightarrow \Gamma $$ $$ K(\alpha) = (L, U, T) \quad (\text{tag} \in U \text{ implies } \text{tag}: \tau_1 \in T) \quad t//p = \pi_{\text{tag}}(t)//p_1. $$

Since $t \le \lceil \text{tag}(p_1) \rceil = \lceil \text{tag}(\lceil p_1 \rceil) \rceil$, by Property A.32 we have $\pi_{\text{tag}}(t) \le \lceil p_1 \rceil$. We next prove $\pi_{\text{tag}}(t) \le \llbracket \tau_1 \rrbracket_K$, which allows us to apply the induction hypothesis and conclude.

The translation of $\alpha$ is $\llbracket \alpha \rrbracket_K = (\text{low}_K(L, T) \lor \alpha) \land \text{upp}_K(U, T)$. We have $t \le \llbracket \alpha \rrbracket_K$ and hence $t \le \text{upp}_K(U, T)$. Since $t \le \text{tag}(1)$, $t \le \text{upp}_K(U, T) \land \text{tag}(1)$. We distribute the intersection over the summands of $\text{upp}_K(U, T)$, which is a union.

If $\text{tag} \notin U$ (in which case $U \ne \mathcal{L}$), then all summands have the form $\text{tag}_1(\tau')$ and for each $\text{tag}_1$ we have $\text{tag}_1 \ne \text{tag}:$ hence, the intersection is empty and thus we have $t \le \emptyset \simeq \text{tag}(\emptyset)$. Then $\pi_{\text{tag}}(t) \le \emptyset \le \llbracket \tau_1 \rrbracket_K$.

If $\text{tag} \in U$, then necessarily $\text{tag} \in \text{dom}(T)$ holds as well. In that case the intersection $\text{upp}_K(U, T) \land \text{tag}(1)$ is equivalent to $\text{tag}(\bigwedge_{\gamma \in T} \llbracket \tau' \rrbracket_K)$. Hence $t \le \text{tag}(\bigwedge_{\gamma' \in T} \llbracket \tau' \rrbracket_K)$ and $\pi_{\text{tag}}(t) \le \bigwedge_{\gamma' \in T} \llbracket \tau' \rrbracket_K$. Since $\text{tag}: \tau_1 \in T$, $\bigwedge_{\gamma' \in T} \llbracket \tau' \rrbracket_K \le \llbracket \tau_1 \rrbracket_K$, from which follows $\pi_{\text{tag}}(t) \le \llbracket \tau_1 \rrbracket_K$.

Case $p = p_1 \& p_2$ We directly apply the induction hypothesis to both sub-patterns and conclude.
`tag ∉ dom(T)`, then `tag ∉ dom(T')`, in which case both `u` and `u'` admit it with any argument type. If `tag ∈ dom(T)`, either `tag ∈ dom(T')` or not. In the former case, `u` admits a smaller argument type than `u'` because `T'θ ⊆ T`. The same occurs in the latter case, since `u'` admits `tag` with any argument type.

If $U \neq \mathcal{L}$, then $U'$ could be $\mathcal{L}$ or not. In either case we can prove, for each `tag ∈ U`, that `u'` admits `tag` with a larger argument type than `u` does.

Case $\tau = b$ Straightforward, since a basic type is translated into itself and is never affected by substitutions.

Case $\tau = \tau_1 \to \tau_2$ By the induction hypothesis we have $\llbracket \tau_i \rrbracket_{K,K'} \theta' \simeq \llbracket \tau_i \theta \rrbracket_K$ for both $i$. Then

$$ 
\begin{align*}
\llbracket \tau_1 \to \tau_2 \rrbracket_{K,K'} \theta' &= (\llbracket \tau_1 \rrbracket_{K,K'} \theta') \to (\llbracket \tau_2 \rrbracket_{K,K'} \theta') \simeq \llbracket \tau_1 \theta \rrbracket_K \to \llbracket \tau_2 \theta \rrbracket_K \\
&= (\llbracket \tau_1 \theta \to \tau_2 \theta \rrbracket_K) = (\llbracket (\tau_1 \to \tau_2) \theta \rrbracket_K).
\end{align*}
$$

Case $\tau = \tau_1 \times \tau_2$ Analogous to the previous case. $\square$

**Lemma A.32.** If $\emptyset \vdash_{\emptyset} v: \llbracket \tau \rrbracket_K$, then there exists a value $v'$ such that $K; \emptyset \vdash_{\emptyset} v': \tau$ and, for every pattern $p, v/p = \Omega \iff v'/p = \Omega$.

*Proof.* By structural induction on $v$.

Note that values are always typed by an application of the typing rule corresponding to their form (Ts-Const, Ts-Abstr, Ts-Pair, or Ts-Tag) to appropriate premises, possibly followed by applications of Ts-Subsum. Hence, if $\emptyset \vdash_{\emptyset} v: t$, there is a type $t' \le t$ such that $\emptyset \vdash_{\emptyset} v: t'$ and that the last typing rule used to derive $\emptyset \vdash_{\emptyset} v: t'$ is one of the four above, given by the form of $v$.

Case $v = c$ We have $\llbracket \tau \rrbracket_K \ge c$. Hence $\tau = b_c$, as the translation of any other $\tau$ is disjoint from $c$. Then we can take $v' = v$.

Case $v = (v_1, v_2)$ We have $\llbracket \tau \rrbracket_K \ge t_1 \times t_2$ for some $t_1$ and $t_2$. Hence $\tau = \tau_1 \times \tau_2$: any other $\tau$ would translate to a type disjoint from all products. Therefore $\emptyset \vdash_{\emptyset} v: \llbracket \tau_1 \rrbracket_K \times \llbracket \tau_2 \rrbracket_K$. By Lemma A.12 we have $\emptyset \vdash_{\emptyset} v_i: \llbracket \tau_i \rrbracket_K$ for both $i$; then by the induction hypothesis we find $v'_i$ for both $i$ and let $v' = (v'_1, v'_2)$.

Case $v = `tag(v_1)$ We have $\llbracket \tau \rrbracket_K \ge `tag(t_1)$ and $\emptyset \vdash_{\emptyset} v: `tag(t_1)$ for some $t_1 \le \emptyset$ (since $t_1$ types the value $v_1$). Therefore, by the same reasoning as above, $\tau = \alpha$ with $K(\alpha) = (L, U, T)$. Since $\llbracket \tau \rrbracket_K \ge `tag(t_1)$, we have `tag ∈ L` and therefore `tag: $\tau_1 \in T$` for some $\tau_1$ such that $t_1 \le \llbracket \tau_1 \rrbracket_K$. Then we have $\emptyset \vdash_{\emptyset} v_1: \llbracket \tau_1 \rrbracket_K$; we may apply the induction hypothesis to find a value $v'_1$ and let $v' = `tag(v'_1)$.

Case $v = \lambda x. e$ Note that an abstraction is only accepted by patterns which accept any value, so any two abstractions fail to match exactly the same patterns.

We have $\emptyset \vdash_{\emptyset} v: t_1 \to t_2$ for some $t_1 \to t_2 \le \llbracket \tau \rrbracket_K$. Hence we know $\tau$ is of the form $\tau_1 \to \tau_2$; thus we have $\emptyset \vdash_{\emptyset} v: \llbracket \tau_1 \rrbracket_K \to \llbracket \tau_2 \rrbracket_K$. We take $v'$ to be the function $\lambda x. \gamma (\lambda f. \lambda x. f x) x$, which never terminates and can be assigned any arrow type. $\square$

**Lemma A.33.** Let $K$ be a kinding environment, $\tau$ a $k$-type, and $P$ a set of patterns. If $\tau \preceq_K P$, then $\llbracket \tau \rrbracket_K \le \bigvee_{p \in P} \lceil p \rceil$.

*Proof.* By contradiction, assume that $\tau \preceq_K P$ holds but $\llbracket \tau \rrbracket_K \not\le \bigvee_{p \in P} \lceil p \rceil$. The latter condition implies that there exists a value $v$ in the interpretation of $\llbracket \tau \rrbracket_K$ which is not in the interpretation of $\bigvee_{p \in P} \lceil p \rceil$. Because the definition of accepted type is exact with respect to the semantics of pattern matching, we have $v/p = \Omega$ for all $p \in P$. We also have $\emptyset \vdash_{\emptyset} v: \llbracket \tau \rrbracket_K$ since $v$ is in the interpretation of that type (typing is complete with respect to the interpretation if we restrict ourselves to translations of $k$-types).

By Lemma A.32, from $v$ we can build a value $v'$ such that $K; \emptyset \vdash_{\emptyset} v': \tau$ and, for every pattern $p, v/p = \Omega \iff v'/p = \Omega$. We reach a contradiction, since $\tau \preceq_K P$ and $K; \emptyset \vdash_{\emptyset} v': \tau$ imply that there exists a $p \in P$ such that $v'/p \ne \Omega$, whereas we have $v/p = \Omega$ for all $p \in P$. $\square$

**Theorem A.34** (Preservation of typing). Let $e$ be an expression, $K$ a non-recursive kinding environment, $\Gamma$ a $k$-type environment, and $\tau$ a $k$-type. If $K; \Gamma \vdash_K e: \tau$, then $\llbracket \Gamma \rrbracket_K \vdash_{\vdash_K} e: \llbracket \tau \rrbracket_K$.

*Proof.* By induction on the derivation of $K; \Gamma \vdash_K e: \tau$. We reason by cases on the last applied rule.

Case Tk-Var We have

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
K; \Gamma \vdash_{\vdash_K} x: \tau & \tau \in \text{inst}_K(\Gamma(x)) & \text{hence} \\
\Gamma(x) = \forall A. K_x \triangleright \tau_x & \tau = \tau_x \theta & \text{dom}(\theta) \subseteq A \\
& K, K_x \vdash \theta: K &
\end{array}
$$
Case $p = p_1|p_2$ We have

$$K \vdash p: \tau \Rightarrow \Gamma \quad \forall i. \ K \vdash p_i: \tau \Rightarrow \Gamma$$
$$t//p = (t \wedge \{p_1\})//p_1 \ \mathsf{W} \ (t \setminus \{p_1\})//p_2.$$

Since $t \wedge \{p_1\} \vdash t \setminus \{p_1\}$ and $t \wedge \{p_1\} \vdash t$ are subtypes of $t$, they are also subtypes of $\llbracket \tau \rrbracket_K$. We can apply the induction hypothesis and, for each $x$, derive both that $(t \wedge \{p_1\})//p_1)(x) \leq \llbracket \Gamma(x) \rrbracket_K$ and that $(t \setminus \{p_1\})//p_2)(x) \leq \llbracket \Gamma(x) \rrbracket_K$. Hence, $(t//p)(x) \leq \llbracket \Gamma(x) \rrbracket_K$. $\square$

**Lemma A.31 (Translation of type substitutions).** Let $K, K'$ be two non-recursive kinding environments such that $dom(K') \cap (dom(K) \cup var_\emptyset(K)) = \emptyset$. Let $\theta$ be a $k$-type substitution such that $dom(\theta) \subseteq dom(K')$ and $K, K' \vdash \theta: K$.

Let $\theta'$ be the $\mathfrak{s}$-type substitution defined as $[\llbracket \alpha \theta \rrbracket_K / \alpha \mid \alpha \in dom(K')]$. For every $k$-type $\tau$, we have $\llbracket \tau \rrbracket_{K,K'} \cong \llbracket \tau \theta \rrbracket_K$.

*Proof.* By complete induction on $w(\tau, (K, K'))$. We proceed by cases on $\tau$ and assume that the lemma holds for all $\tau'$ such that $w(\tau', (K, K')) < w(\tau, (K, K'))$.

*Case $\tau = \alpha$, with $(K, K')(\alpha) = \bullet$* We have $\llbracket \alpha \rrbracket_{K,K'} = \alpha$, hence $\llbracket \alpha \rrbracket_{K,K'} \theta' = \alpha \theta'$. Either $\alpha \in dom(K)$ or $\alpha \in dom(K')$ (the domains are disjoint). In the former case, $\alpha \theta = \alpha$ and $\alpha \theta' = \alpha$. Thus we have $\llbracket \alpha \rrbracket_{K,K'} \theta' = \alpha = \llbracket \alpha \theta \rrbracket_K$. In the latter, $\alpha \theta' = \llbracket \alpha \theta \rrbracket_K$ holds by definition of $\theta'$.

*Case $\tau = \alpha$, with $K(\alpha) = (L, U, T)$ and $\alpha \notin dom(K')$* We have $\llbracket \alpha \rrbracket_{K,K'} = \llbracket \alpha \rrbracket_K$ because no variable in the kind of $\alpha$ is in $dom(K')$. For the same reason, since the translation does not add variables, $\llbracket \alpha \rrbracket_{K,K'} \theta' = \llbracket \alpha \rrbracket_K$. Additionally, $\alpha \theta = \alpha$, so also $\llbracket \alpha \theta \rrbracket_K = \llbracket \alpha \rrbracket_K$.

*Case $\tau = \alpha$, with $K'(\alpha) = (L', U', T')$* Because $K, K' \vdash \theta: K$, we know that $\alpha \theta$ is some variable $\beta$ such that $K(\beta) = (L, U, T)$ and $(L, U, T) \models (L', U', T' \theta)$.

We have

$$\llbracket \alpha \theta \rrbracket_K = \llbracket \beta \rrbracket_K = (\mathrm{low}_K(L, T) \vee \beta) \wedge \mathrm{upp}_K(U, T)$$

and

$$\begin{align*}
\llbracket \alpha \rrbracket_{K,K'} \theta' &= ((\mathrm{low}_{K,K'}(L', T') \vee \alpha) \wedge \mathrm{upp}_{K,K'}(U', T')) \theta' \\
&= (\mathrm{low}_{K,K'}(L', T') \theta' \vee \alpha \theta') \wedge \mathrm{upp}_{K,K'}(U', T') \theta' \\
&= (\mathrm{low}_{K,K'}(L', T') \theta' \vee ((\mathrm{low}_K(L, T) \vee \beta) \wedge \mathrm{upp}_K(U, T))) \wedge \mathrm{upp}_{K,K'}(U', T') \theta'.
\end{align*}$$

Let us define

$$l = \mathrm{low}_K(L, T)$$

$$u = \mathrm{upp}_K(U, T)$$

$$l' = \mathrm{low}_{K,K'}(L', T') \theta'$$

$$u' = \mathrm{upp}_{K,K'}(U', T') \theta'$$

and assume that the following hold (we prove them below):

$$l \leq u \qquad l' \leq u' \qquad l' \leq l \qquad u \leq u'$$

Then we have also $l' \leq u$ by transitivity. Whenever $t \leq t'$, we have $t \wedge t' \cong t$ and $t \vee t' \cong t'$.

Thus we have the following equivalences:

$$\begin{align*}
\llbracket \alpha \rrbracket_{K,K'} \theta' &= (l' \vee ((l \vee \beta) \wedge u)) \wedge u' \\
&\cong (l' \wedge u') \vee ((l \vee \beta) \wedge u \wedge u') && \text{distributivity} \\
&\cong l' \vee ((l \vee \beta) \wedge u) && l' \leq u' \text{ and } u \leq u' \\
&\cong (l' \vee l \vee \beta) \wedge (l' \vee u) && \text{distributivity} \\
&\cong (l \vee \beta) \wedge u && l' \leq l \text{ and } l' \leq u
\end{align*}$$

by which we conclude.

We now prove our four assumptions. The first, $l \leq u$, holds because $L \subseteq U$ and $L \subseteq dom(T)$: hence each branch of $l$ appears in $u$ as well. The second is analogous.

For the other assumptions, note that $\llbracket \tau \rrbracket_{K,K'} \theta' \cong \llbracket \tau' \theta \rrbracket_K$ holds for all $\tau'$ in the range of $T'$. To prove $l' \leq l$, note that $L' \subseteq L$ and $T' \theta \subseteq T$. In $l'$, we distribute the application of $\theta'$ over all the summands of the union and inside all variant type constructors. Then, we show `tag(\wedge_{tag: \tau' \in T'} \llbracket \tau' \rrbracket_{K,K'} \theta') \leq l` for each `tag` in $L'$. We have `tag(\wedge_{tag: \tau' \in T'} \llbracket \tau' \rrbracket_{K,K'} \theta') \cong \wedge_{tag: \tau' \in T'} \llbracket \tau' \theta \rrbracket_K = `tag(\wedge_{tag: \tau' \in T'} \llbracket \tau' \theta \rrbracket_K)`. Since $L' \subseteq L$, there is a summand of $l$ with the same tag. Since `tag` is in the lower bound, it has a single type in both $T$ and $T'$ and, since $T' \theta \subseteq T$, the type it has in $T$ must be $\tau' \theta$.

To prove $u \leq u'$, note that $U \subseteq U'$. If $U = \mathcal{L}$, then $U' = \mathcal{L}$. Then both $u$ and $u'$ are unions of two types: the union of tags mentioned respectively in $T$ and $T'$ and the rest. For each `tag`, if
and must show $[[\Gamma]]_K \vdash_\S x: [[\tau]]_K$. Since $[[\Gamma]]_K(x) = \forall A. [[\tau_x]]_{K,K_x}$, by Ts-Var we can derive $[[\tau_x]]_{K,K_x} \theta'$ for any $\S$-type substitution $\theta'$ with $\mathrm{dom}(\theta') \subseteq A$.

Consider the $\S$-type substitution $\theta' = [[\alpha\theta]]_K/\alpha$ $| \alpha \in A$. We have $[[\tau_x]]_{K,K_x} \theta' \simeq [[\tau_x\theta]]_K$ by Lemma A.31 (we can assume the conditions on the domain of $K_x$ to hold by renaming the variables in A). Hence, we derive $[[\tau_x]]_{K,K_x} \theta'$ by Ts-Var and then $[[\tau_x\theta]]_K$ by subsumption.

**Case Tk-Const** We have

$$K; \Gamma \vdash_{\mathfrak{K}} c : b_c \quad [[b_c]]_K = b_c$$

and may derive $[[\Gamma]]_K \vdash_\S c$ by Ts-Const and $[[\Gamma]]_K \vdash_\S c$ by subsumption.

**Case Tk-Abstr** We have

$$K; \Gamma \vdash_{\mathfrak{K}} \lambda x. e_1 : \tau_1 \to \tau_2 \qquad K; \Gamma, \{x: \tau_1\} \vdash_{\mathfrak{K}} e_1 : \tau_2 \qquad [[\tau_1 \to \tau_2]]_K = [[\tau_1]]_K \to [[\tau_2]]_K.$$

By the induction hypothesis we derive $[[\Gamma]]_K, \{x: [[\tau_1]]_K\} \vdash_\S e_1: [[\tau_2]]_K$, then we apply Ts-Abstr.

**Cases Tk-Appl, Tk-Pair, and Tk-Fix** Straightforward application of the induction hypothesis.

**Case Tk-Tag** We have

$$K; \Gamma \vdash_{\mathfrak{K}} \text{'tag}(e_1): \alpha \qquad K; \Gamma \vdash_{\mathfrak{K}} e_1 : \tau_1 \qquad K(\alpha) = (L, U, T) \qquad \text{'tag} \in L \qquad \text{'tag}: \tau_1 \in T \\ [[\alpha]]_K = (\mathrm{low}_K(L, T) \lor \alpha) \land \mathrm{upp}_K(U, T).$$

We derive $[[\Gamma]]_K \vdash_\S e_1: [[\tau_1]]_K$ by the induction hypothesis, then $[[\Gamma]]_K \vdash_\S \text{'tag}(e_1): \text{'tag}([[[\tau_1]]_K])$ by Ts-Tag. We show that $\text{'tag}([[[\tau_1]]_K]) \le [[\alpha]]_K$ holds: hence, we may derive the supertype by subsumption.

Since $\text{'tag} \in L$ and hence $\text{'tag} \in \mathrm{dom}(T)$, both $\mathrm{low}_K(L, T)$ and $\mathrm{upp}_K(U, T)$ contain a summand $\text{'tag}(\bigwedge_{\text{'tag}: \tau_1 \in T} [[\tau'_i]]_K)$. Since $\text{'tag}: \tau_1 \in T$ and no other type may be associated to $\text{'tag}$, the intersection has a single factor $[[\tau_1]]_K$. Thus we have both $\text{'tag}([[[\tau_1]]_K]) \le \mathrm{low}_K(L, T)$ and $\text{'tag}([[[\tau_1]]_K]) \le \mathrm{upp}_K(U, T)$; hence, $\text{'tag}([[[\tau_1]]_K]) \le [[\alpha]]_K$.

**Case Tk-Match** We have

$$K; \Gamma \vdash_{\mathfrak{K}} \text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I}: \tau \\ K; \Gamma \vdash_{\mathfrak{K}} e_0: \tau_0 \qquad \tau_0 \preceq_K \{p_i \mid i \in I\} \\ \forall i \in I. \quad K \vdash p_i: \tau_0 \Rightarrow \Gamma_i \qquad K; \Gamma, \mathrm{gen}_{K;\Gamma}(\Gamma_i) \vdash_{\mathfrak{K}} e_i: \tau$$

and must show

$$[[\Gamma]]_K \vdash_\S \text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I}: [[\tau]]_K$$

which we prove by establishing, for some types $t_0$ and $t_i$, $t'_i$ for each $i$, that

$$[[\Gamma]]_K \vdash_\S e_0: t_0 \qquad t_0 \le \bigvee_{i \in I} [p_i] \qquad t_i = (t_0 \setminus \bigvee_{j<i} [p_j]) \land [p_i] \\ \forall i \in I. \quad [[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i) \vdash_\S e_i: t'_i \qquad \bigvee_{i \in I} t'_i \le [[\tau]]_K.$$

and then applying Ts-Match, followed by Ts-Subsum if necessary.

By the induction hypothesis we derive $[[\Gamma]]_K \vdash_\S e_0: [[\tau_0]]_K$ and hence have $t_0 = [[\tau_0]]_K$. By Lemma A.33, we have $t_0 \le \bigvee_{i \in I} [p_i]$. For every branch, $t_i \le t_0$ and $t_i \le [p_i]$; therefore, we can apply Lemma A.30 and derive that $(t_i//p_i)(x) \le [[\Gamma_i(x)]]_K$ holds for every $x \in \mathrm{capt}(p_i)$.

For each branch, we derive $[[\Gamma]]_K, [[\mathrm{gen}_{K;\Gamma}(\Gamma_i)]]_K \vdash_\S e_i: [[\tau]]_K$ by the induction hypothesis. We derive $[[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i) \vdash_\S e_i: [[\tau]]_K$ by Lemma A.22 by proving $[[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i) \subseteq [[\Gamma]]_K, \mathrm{gen}_{[K;\Gamma](\Gamma_i)}[K] \subseteq \mathrm{mvar}([[[\Gamma]]_K, \mathrm{gen}_{[K;\Gamma](\Gamma_i)}[K])$. and $\mathrm{mvar}([[[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i)] \subseteq \mathrm{mvar}([[[\Gamma]]_K, \mathrm{gen}_{[K;\Gamma](\Gamma_i)}[K])$.

The latter is straightforward. For the former, for each $x \in \mathrm{capt}(p_i)$—say $\Gamma_i(x) = \tau_x$ and $(t_i//p_i)(x) = t_x$—we must show $\mathrm{gen}_{[[\Gamma]]_K}(t_x) \subseteq [[\mathrm{gen}_{K;\Gamma}(\tau_x)]]_K$. This holds because $t_x \le [[\tau_x]]_K$ and because, by Lemma A.29, $\mathrm{var}([[[\Gamma]]_K]) \subseteq \mathrm{var}_K(\Gamma)$.

We can thus choose $t'_i = [[\tau]]_K$ for all branches, satisfying $\bigvee_{i \in I} t'_i \le [[\tau]]_K$. $\square$

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

## A.4 Type reconstruction

### A.4.1 Definition of type reconstruction for $\mathfrak{S}$

**Definition A.38 (Constraints).** A constraint $c$ is a term inductively generated by the following grammar:

$$c ::= t \leq t \mid x \leq t \mid \mathrm{def} \Gamma \ \mathrm{in} \ C \ \mathrm{let} \ [C](\Gamma_i \ \mathrm{in} \ C_i)_{i \in I}$$

where C ranges over constraint sets, that is, finite sets of constraints, and where the range of every type environment $\Gamma$ in constraints of the form $\mathrm{def}$ or $\mathrm{let}$ only contains types (i.e., trivial type schemes).

We give different definitions of constraint generation and rewriting here than those in Section 5, because we keep track explicitly of the new variables introduced during the derivation, rather than
`tag ∉ dom(T)`, then `tag ∉ dom(T')`, in which case both `u` and `u'` admit it with any argument type. If `tag ∈ dom(T)`, either `tag ∈ dom(T')` or not. In the former case, `u` admits a smaller argument type than `u'` because `T'θ ⊆ T`. The same occurs in the latter case, since `u'` admits `tag` with any argument type.

If $U \neq \mathcal{L}$, then $U'$ could be $\mathcal{L}$ or not. In either case we can prove, for each `tag ∈ U`, that `u'` admits `tag` with a larger argument type than `u` does.

Case $\tau = b$ Straightforward, since a basic type is translated into itself and is never affected by substitutions.

Case $\tau = \tau_1 \to \tau_2$ By the induction hypothesis we have $[[\tau_i]]_{K,K'} \theta' \simeq [[\tau_i \theta]]_K$ for both $i$. Then

$$ 
\begin{align*}
[[\tau_1 \to \tau_2]]_{K,K'} \theta' &= ([[\tau_1]]_{K,K'} \theta') \to ([[\tau_2]]_{K,K'} \theta') \simeq [[\tau_1 \theta]]_K \to [[\tau_2 \theta]]_K \\
&= [[(\tau_1 \theta) \to (\tau_2 \theta)]]_K = [[(\tau_1 \to \tau_2) \theta]]_K .
\end{align*}
$$

Case $\tau = \tau_1 \times \tau_2$ Analogous to the previous case. $\square$

**Lemma A.32.** If $\emptyset \vdash_{\emptyset} v: [[\tau]]_K$, then there exists a value $v'$ such that $K; \emptyset \vdash_{\emptyset} v': \tau$ and, for every pattern $p, v/p = \Omega \iff v'/p = \Omega$.

*Proof.* By structural induction on $v$.

Note that values are always typed by an application of the typing rule corresponding to their form (*Ts-Const*, *Ts-Abstr*, *Ts-Pair*, or *Ts-Tag*) to appropriate premises, possibly followed by applications of *Ts-Subsum*. Hence, if $\emptyset \vdash_{\emptyset} v: t$, there is a type $t' \le t$ such that $\emptyset \vdash_{\emptyset} v: t'$ and that the last typing rule used to derive $\emptyset \vdash_{\emptyset} v: t'$ is one of the four above, given by the form of $v$.

Case $v = c$ We have $[[\tau]]_K \ge c$. Hence $\tau = b_c$, as the translation of any other $\tau$ is disjoint from $c$. Then we can take $v' = v$.

Case $v = (v_1, v_2)$ We have $[[\tau]]_K \ge t_1 \times t_2$ for some $t_1$ and $t_2$. Hence $\tau = \tau_1 \times \tau_2$: any other $\tau$ would translate to a type disjoint from all products. Therefore $\emptyset \vdash_{\emptyset} v: [[\tau_1]]_K \times [[\tau_2]]_K$. By Lemma A.12 we have $\emptyset \vdash_{\emptyset} v_i: [[\tau_i]]_K$ for both $i$; then by the induction hypothesis we find $v_i'$ for both $i$ and let $v' = (v_1', v_2')$.

Case $v = `tag(v_1)$ We have $[[\tau]]_K \ge `tag(t_1)$ and $\emptyset \vdash_{\emptyset} v: `tag(t_1)$ for some $t_1 \not\le \emptyset$ (since $t_1$ types the value $v_1$). Therefore, by the same reasoning as above, $\tau = \alpha$ with $K(\alpha) = (L, U, T)$. Since $[[\tau]]_K \ge `tag(t_1)$, we have `tag $\in L$ and therefore `tag: $\tau_1 \in T$ for some $\tau_1$ such that $t_1 \le [[\tau_1]]_K$. Then we have $\emptyset \vdash_{\emptyset} v_1: [[\tau_1]]_K$; we may apply the induction hypothesis to find a value $v_1'$ and let $v' = `tag(v_1')$.

Case $v = \lambda x. e$ Note that an abstraction is only accepted by patterns which accept any value, so any two abstractions fail to match exactly the same patterns.

We have $\emptyset \vdash_{\emptyset} v: t_1 \to t_2$ for some $t_1 \to t_2 \le [[\tau]]_K$. Hence we know $\tau$ is of the form $\tau_1 \to \tau_2$; thus we have $\emptyset \vdash_{\emptyset} v: [[\tau_1]]_K \to [[\tau_2]]_K$. We take $v'$ to be the function $\lambda x. \gamma (\lambda f. \lambda x. f x) x$, which never terminates and can be assigned any arrow type. $\square$

**Lemma A.33.** Let $K$ be a kinding environment, $\tau$ a k-type, and $P$ a set of patterns. If $\tau \preceq_K P$, then $[[\tau]]_K \le \bigvee_{p \in P} [[p]]$.

*Proof.* By contradiction, assume that $\tau \preceq_K P$ holds but $[[\tau]]_K \not\le \bigvee_{p \in P} [[p]]$. The latter condition implies that there exists a value $v$ in the interpretation of $[[\tau]]_K$ which is not in the interpretation of $\bigvee_{p \in P} [[p]]$. Because the definition of accepted type is exact with respect to the semantics of pattern matching, we have $v/p = \Omega$ for all $p \in P$. We also have $\emptyset \vdash_{\emptyset} v: [[\tau]]_K$ since $v$ is in the interpretation of that type (typing is complete with respect to the interpretation if we restrict ourselves to translations of k-types).

By Lemma A.32, from $v$ we can build a value $v'$ such that $K; \emptyset \vdash_{\emptyset} v': \tau$ and, for every pattern $p, v/p = \Omega \iff v'/p = \Omega$. We reach a contradiction, since $\tau \preceq_K P$ and $K; \emptyset \vdash_{\emptyset} v': \tau$ imply that there exists a $p \in P$ such that $v'/p \ne \Omega$, whereas we have $v/p = \Omega$ for all $p \in P$. $\square$

**Theorem A.34** (Preservation of typing). Let $e$ be an expression, $K$ a non-recursive kinding environment, $\Gamma$ a k-type environment, and $\tau$ a k-type. If $K; \Gamma \vdash_K e: \tau$, then $[[\Gamma]]_K \vdash_{\vdash_K} e: [[\tau]]_K$.

*Proof.* By induction on the derivation of $K; \Gamma \vdash_K e: \tau$. We reason by cases on the last applied rule.

Case *Tk-Var* We have

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
K; \Gamma \vdash_K x: \tau & \tau \in \mathrm{inst}_K(\Gamma(x)) & \text{hence} \\
\Gamma(x) = \forall A. K_x \triangleright \tau_x & \tau = \tau_x \theta & \mathrm{dom}(\theta) \subseteq A \\
& K, K_x \vdash \theta: K &
\end{array}
$$
<figure><img src="image_4.png" /><figcaption>**Figure 13.** Constraint generation for pattern environments.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 14.** Constraint generation rules with explicit variable introduction.</figcaption></figure>

informally requiring them to be fresh. For instance, in $e: t \Rightarrow_A C$, $A$ is the set of variables which appear in $C$ but not in $t$. We will omit it for soundness proofs, where it is not relevant.

We use the symbol $\uplus$ to denote the union of two disjoint sets. Therefore, when we write $A_1 \uplus A_2$, we require $A_1$ and $A_2$ to be disjoint. When we require this for sets of type variables, the condition is always satisfiable by an appropriate choice of variables, since there is an infinite supply to choose from.

**Definition A.39 (Freshness).** We say that a type variable $\alpha$ is fresh with respect to a set of type variables $A$, and write $\alpha \nvdash A$, if $\alpha \notin A$. We write $A \nvdash A'$ if $\forall \alpha \in A. \alpha \nvdash A'$.

We extend this to define freshness with respect to types, type environments, and type substitutions: we write $\alpha \nvdash t$ if $\alpha \nvdash \text{var}(t)$, $\alpha \nvdash \Gamma$ if $\alpha \nvdash \text{var}(\Gamma)$, and $\alpha \nvdash \theta$ if $\alpha \nvdash (\text{dom}(\theta) \cup \text{var}(\theta))$.

**Definition A.40 (Environment generation for pattern matching).** The environment generation relation for pattern matching $t\\/p \Rightarrow_A (\Gamma, C)$ is defined by the rules in Figure 13.

**Definition A.41 (Constraint generation).** The constraint generation relation $e: t \Rightarrow_A C$ is defined by the rules in Figure 14.
and must show $[[\Gamma]]_K \vdash_\S x: [[\tau]]_K$. Since $[[\Gamma]]_K(x) = \forall A. [[\tau_x]]_{K, K_x}$, by Ts-Var we can derive $[[\tau_x]]_{K, K_x} \theta'$ for any $\S$-type substitution $\theta'$ with $\mathrm{dom}(\theta') \subseteq A$.

Consider the $\S$-type substitution $\theta' = [[\alpha\theta]]_K/\alpha$ $| \alpha \in A$. We have $[[\tau_x]]_{K, K_x} \theta' \simeq [[\tau_x\theta]]_K$ by Lemma A.31 (we can assume the conditions on the domain of $K_x$ to hold by renaming the variables in A). Hence, we derive $[[\tau_x]]_{K, K_x} \theta'$ by Ts-Var and then $[[\tau_x\theta]]_K$ by subsumption.

**Case Tk-Const** We have

$$K; \Gamma \vdash_{\mathfrak{K}} c : b_c \quad [[b_c]]_K = b_c$$

and may derive $[[\Gamma]]_K \vdash_\S c$ by Ts-Const and $[[\Gamma]]_K \vdash_\S c$ by subsumption.

**Case Tk-Abstr** We have

$$K; \Gamma \vdash_{\mathfrak{K}} \lambda x. e_1 : \tau_1 \to \tau_2 \qquad K; \Gamma, \{x: \tau_1\} \vdash_{\mathfrak{K}} e_1 : \tau_2 \qquad [[\tau_1 \to \tau_2]]_K = [[\tau_1]]_K \to [[\tau_2]]_K$$

By the induction hypothesis we derive $[[\Gamma]]_K, \{x: [[\tau_1]]_K\} \vdash_\S e_1: [[\tau_2]]_K$, then we apply Ts-Abstr.

**Cases Tk-Appl, Tk-Pair, and Tk-Fix** Straightforward application of the induction hypothesis.

**Case Tk-Tag** We have

$$K; \Gamma \vdash_{\mathfrak{K}} 'tag(e_1): \alpha \qquad K; \Gamma \vdash_{\mathfrak{K}} e_1 : \tau_1 \qquad K(\alpha) = (L, U, T) \qquad 'tag \in L \quad 'tag: \tau_1 \in T \\ [[\alpha]]_K = (\mathrm{low}_K(L, T) \lor \alpha) \land \mathrm{upp}_K(U, T).$$

We derive $[[\Gamma]]_K \vdash_\S e_1: [[\tau_1]]_K$ by the induction hypothesis, then $[[\Gamma]]_K \vdash_\S 'tag(e_1): 'tag([\tau_1]]_K)$ by Ts-Tag. We show that '$tag([\tau_1]]_K) \le [[\alpha]]_K$ holds: hence, we may derive the supertype by subsumption.

Since '$tag \in L$ and hence '$tag \in \mathrm{dom}(T)$, both $\mathrm{low}_K(L, T)$ and $\mathrm{upp}_K(U, T)$ contain a summand '$tag(\bigwedge_{i \in I} 'tag: \tau_i \in T)[\tau_i]]_K)$. Since '$tag: \tau_1 \in T$ and no other type may be associated to '$tag$, the intersection has a single factor $[[\tau_1]]_K$. Thus we have both '$tag([\tau_1]]_K) \le \mathrm{low}_K(L, T)$ and '$tag([\tau_1]]_K) \le \mathrm{upp}_K(U, T)$; hence, '$tag([\tau_1]]_K) \le [[\alpha]]_K$.

**Case Tk-Match** We have

$$K; \Gamma \vdash_{\mathfrak{K}} \mathrm{match} e_0 \text{ with } (p_i \to e_i)_{i \in I}: \tau \\ K; \Gamma \vdash_{\mathfrak{K}} e_0: \tau_0 \qquad \tau_0 \preceq_K \{p_i \mid i \in I\} \\ \forall i \in I. K \vdash p_i: \tau_0 \Rightarrow \Gamma_i \qquad K; \Gamma, \mathrm{gen}_{K;\Gamma}(\Gamma_i) \vdash_{\mathfrak{K}} e_i: \tau$$

and must show

$$[[\Gamma]]_K \vdash_\S \mathrm{match} e_0 \text{ with } (p_i \to e_i)_{i \in I}: [[\tau]]_K$$

which we prove by establishing, for some types $t_0$ and $t_i$, $t'_i$ for each $i$, that

$$[[\Gamma]]_K \vdash_\S e_0: t_0 \qquad t_0 \le \bigvee_{i \in I} [p_i] \qquad t_i = (t_0 \setminus \bigvee_{j<i} [p_j]) \land [p_i] \\ \forall i \in I. [[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i) \vdash_\S e_i: t'_i \qquad \bigvee_{i \in I} t'_i \le [[\tau]]_K.$$

and then applying Ts-Match, followed by Ts-Subsum if necessary.

By the induction hypothesis we derive $[[\Gamma]]_K \vdash_\S e_0: [[\tau_0]]_K$ and hence have $t_0 = [[\tau_0]]_K$. By Lemma A.33, we have $t_0 \le \bigvee_{i \in I} [p_i]$. For every branch, $t_i \le t_0$ and $t_i \le [p_i]$; therefore, we can apply Lemma A.30 and derive that $(t_i//p_i)(x) \le [[\Gamma_i(x)]_K)$ holds for every $x \in \mathrm{capt}(p_i)$.

For each branch, we derive $[[\Gamma]]_K, [[\mathrm{gen}_{K;\Gamma}(\Gamma_i)]_K] \vdash_\S e_i: [[\tau]]_K$ by the induction hypothesis. We derive $[[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i) \vdash_\S e_i: [[\tau]]_K$ by Lemma A.22 by proving $[[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i) \subseteq [[\Gamma]]_K, \mathrm{gen}_{[K;\Gamma]}(\Gamma_i)]_K$ and $\mathrm{mvar}([[[\Gamma]]_K, \mathrm{gen}_{[[\Gamma]]_K}(t_i//p_i))) \subseteq \mathrm{mvar}([[[\Gamma]]_K, \mathrm{gen}_{[K;\Gamma]}(\Gamma_i)]_K)$. The latter is straightforward. For the former, for each $x \in \mathrm{capt}(p_i)$—say $\Gamma_i(x) = \tau_x$ and $(t_i//p_i)(x) = t_x$—we must show $\mathrm{gen}_{[[\Gamma]]_K}(t_x) \subseteq [[\mathrm{gen}_{K;\Gamma}(\tau_x)]_K]$. This holds because $t_x \le [[\tau_x]]_K$ and because, by Lemma A.29, $\mathrm{var}([[[\Gamma]]_K] \subseteq \mathrm{var}_K(\Gamma))$.

We can thus choose $t'_i = [[\tau]]_K$ for all branches, satisfying $\bigvee_{i \in I} t'_i \le [[\tau]]_K$. $\square$

## A.4 Type reconstruction

### A.4.1 Definition of type reconstruction for $\mathfrak{S}$

**Definition A.38 (Constraints).** A constraint $c$ is a term inductively generated by the following grammar:

$$c ::= t \leq t \mid x \leq t \mid \mathrm{def} \Gamma \ \mathrm{in} \ C \ \mathrm{let} \ [C](\Gamma_i \ \mathrm{in} \ C_i)_{i \in I}$$

where C ranges over constraint sets, that is, finite sets of constraints, and where the range of every type environment $\Gamma$ in constraints of the form $\mathrm{def}$ or $\mathrm{let}$ only contains types (i.e., trivial type schemes).

We give different definitions of constraint generation and rewriting here than those in Section 5, because we keep track explicitly of the new variables introduced during the derivation, rather than
$$
\begin{array}{ccc}
\overline{t|\|\_ \Rightarrow \emptyset (\emptyset, \emptyset)} & \overline{t|\|x \Rightarrow \emptyset (\{x: t\}, \emptyset)} & \overline{t|\|c \Rightarrow \emptyset (\emptyset, \emptyset)} \\[1.5em]
\frac{\alpha_1|\|p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad \alpha_2|\|p_2 \Rightarrow_{A_2} (\Gamma_2, C_2)}{t|\|(p_1, p_2) \Rightarrow_{A_1 \uplus A_2 \uplus \{\alpha_1, \alpha_2\}} (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\})} & A_1, A_2, \alpha_1, \alpha_2 \nvdash t & \\[1.5em]
\frac{\alpha|\|p \Rightarrow_A (\Gamma, C) \quad \frac{t|\|p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad t|\|p_2 \Rightarrow_{A_2} (\Gamma_2, C_2)}{t|\|p_1 \& p_2 \Rightarrow_{A_1 \uplus A_2} (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2)}}{t|\|\upharpoonright(p) \Rightarrow_{A \uplus \{\alpha\}} (\Gamma, C \cup \{t \le \upharpoonright tag(\alpha)\})} & A, \alpha \nvdash t & \\[1.5em]
\frac{(t \wedge \lceil p_1 \rceil)|\|p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad (t \setminus \lceil p_1 \rceil)|\|p_2 \Rightarrow_{A_2} (\Gamma_2, C_2)}{t|\|p_1|p_2 \Rightarrow_{A_1 \uplus A_2} (\{x: \Gamma_1(x) \vee \Gamma_2(x) \mid x \in \text{capt}(p_1)\}, C_1 \cup C_2)} & &
\end{array}
$$

<caption>**Figure 13.** Constraint generation for pattern environments.</caption>

$$
\begin{array}{l@{\qquad}l}
\text{TRS-Var} & \overline{x: t \Rightarrow \emptyset \{x \leq t\}} \qquad \overline{\text{TRS-Const} \quad c: t \Rightarrow \emptyset \{c \leq t\}} \\[1.5em]
\text{TRS-Abstr} & \frac{e: \beta \Rightarrow_A C}{\lambda x. e: t \Rightarrow_{A \uplus \{\alpha, \beta\}} \{\text{def } \{x: \alpha\} \text{ in } C, \alpha \to \beta \leq t\}} A, \alpha, \beta \nvdash t \\[1.5em]
\text{TRS-Appl} & \frac{e_1: \alpha \to \beta \Rightarrow_{A_1} C_1 \quad e_2: \alpha \Rightarrow_{A_2} C_2}{e_1 e_2: t \Rightarrow_{A_1 \uplus A_2 \uplus \{\alpha, \beta\}} C_1 \cup C_2 \cup \{\beta \leq t\}} A_1, A_2, \alpha, \beta \nvdash t \\[1.5em]
\text{TRS-Pair} & \frac{e_1: \alpha_1 \Rightarrow_{A_1} C_1 \quad e_2: \alpha_2 \Rightarrow_{A_2} C_2}{(e_1, e_2): t \Rightarrow_{A_1 \uplus A_2 \uplus \{\alpha_1, \alpha_2\}} C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \leq t\}} A_1, A_2, \alpha_1, \alpha_2 \nvdash t \\[1.5em]
\text{TRS-Tag} & \frac{e: \alpha \Rightarrow_A C}{\upharpoonright tag(e): t \Rightarrow_{A \uplus \{\alpha\}} C \cup \{\upharpoonright tag(\alpha) \leq t\}} A, \alpha \nvdash t \\[1.5em]
\text{TRS-Match} & \frac{e_0: \alpha \Rightarrow_{A_0} C_0 \quad t_i = (\alpha \setminus \bigcup_{j<i} \lceil p_j \rceil) \wedge \lceil p_i \rceil}{\forall i \in I \quad t_i|\|p_i \Rightarrow_{A_i} (\Gamma_i, C_i) \quad e_i: \beta \Rightarrow_{A'_i} C'_i} \\
& \qquad C'_0 = C_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \leq \bigcup_{i \in I} \lceil p_i \rceil\} \\
& \qquad A = A_0 \uplus (\biguplus_{i \in I} A_i) \uplus (\biguplus_{i \in I} A'_i) \cup \{\alpha, \beta\} \\
& \qquad \frac{\text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I}: t \Rightarrow_A \{\text{let } [C'_0](\Gamma_i \text{ in } C'_i)_{i \in I}, \beta \leq t\}}{A \nvdash t}
\end{array}
$$

<caption>**Figure 14.** Constraint generation rules with explicit variable introduction.</caption>

informally requiring them to be fresh. For instance, in $e: t \Rightarrow_A C$, $A$ is the set of variables which appear in $C$ but not in $t$. We will omit it for soundness proofs, where it is not relevant.

We use the symbol $\uplus$ to denote the union of two disjoint sets. Therefore, when we write $A_1 \uplus A_2$, we require $A_1$ and $A_2$ to be disjoint. When we require this for sets of type variables, the condition is always satisfiable by an appropriate choice of variables, since there is an infinite supply to choose from.

**Definition A.39 (Freshness).** We say that a type variable $\alpha$ is fresh with respect to a set of type variables $A$, and write $\alpha \nvdash A$, if $\alpha \notin A$. We write $A \nvdash A'$ if $\forall \alpha \in A$. $\alpha \nvdash A'$.

We extend this to define freshness with respect to types, type environments, and type substitutions: we write $\alpha \nvdash t$ if $\alpha \nvdash \text{var}(t)$, $\alpha \nvdash \Gamma$ if $\alpha \nvdash \text{var}(\Gamma)$, and $\alpha \nvdash \theta$ if $\alpha \nvdash (\text{dom}(\theta) \cup \text{var}(\theta))$.

**Definition A.40 (Environment generation for pattern matching).** The environment generation relation for pattern matching $t|\|p \Rightarrow_A (\Gamma, C)$ is defined by the rules in Figure 13.

**Definition A.41 (Constraint generation).** The constraint generation relation $e: t \Rightarrow_A C$ is defined by the rules in Figure 14.
Case $p = (p_1, p_2)$ We have

$$ t///p \Rightarrow (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\}) \quad \forall i. \alpha_i///p_i \Rightarrow (\Gamma_i, C_i). $$

Each $x \in \text{capt}(p)$ is either in $\text{capt}(p_1)$ or in $\text{capt}(p_2)$. Let $x \in \text{capt}(p_i)$; then, we must show $(\pi_i(t'))//_{p_i}(x) \le \Gamma_i(x)\theta$. This follows from the induction hypothesis, since $t' \le t\theta \le \alpha_1\theta \times \alpha_2\theta$ implies $\pi_i(t') \le \alpha_i\theta$ by Property A.31.

Case $p = \text{tag}(p_1)$ We have

$$ t///\text{tag}(p) \Rightarrow (\Gamma, C \cup \{t \le \text{tag}(\alpha)\}) \quad \alpha///p \Rightarrow (\Gamma, C). $$

Analogous to the previous case. We can apply the induction hypothesis, because $t' \le t\theta \le \text{tag}(\alpha)\theta$ implies $\pi_{\text{tag}}(t') \le \alpha\theta$ by Property A.32.

Case $p = p_1 \& p_2$ Every $x \in \text{capt}(p)$ is either in $\text{capt}(p_1)$ or in $\text{capt}(p_2)$. Let $x \in \text{capt}(p_i)$; then, we apply the induction hypothesis to $p_i$ to conclude.

Case $p = p_1|p_2$ We have

$$ t///p_1|p_2 \Rightarrow (\{x: \Gamma_1(x) \lor \Gamma_2(x) \mid x \in \text{capt}(p_1)\}, C_1 \cup C_2) \\ (t \land \lceil p_1 \rceil)///p_1 \Rightarrow (\Gamma_1, C_1) \quad (t \land \lceil p_1 \rceil)///p_2 \Rightarrow (\Gamma_2, C_2). $$

By the induction hypothesis applied to both $p_1$ and $p_2$ we derive, for all $x$,

$$ (t' \land \lceil p_1 \rceil//p_1)(x) \le \Gamma_1(x)\theta \quad (t' \land \lceil p_1 \rceil//p_2)(x) \le \Gamma_2(x)\theta $$

from which we can conclude

$$ (t''//p)(x) = (t' \land \lceil p_1 \rceil//p_1)(x) \lor (t' \land \lceil p_1 \rceil//p_2)(x) \le \Gamma_1(x)\theta \lor \Gamma_2(x)\theta. \quad \square $$

**Lemma A.38** (Precise solution to environment reconstruction constraints). Let $p$ be a pattern, $t$ a type, and $\theta$ a type substitution such that $t\theta \le \lceil p \rceil$. Let $t///p \Rightarrow_A (\Gamma, C)$, with $A \nvdash \text{dom}(\theta)$.

There exists a type substitution $\theta'$ such that $\text{dom}(\theta') = A$, that $(\theta \cup \theta') \Vdash C$, and that, for all $x \in \text{capt}(p)$, $\Gamma(x)(\theta \cup \theta') \le (t\theta//p)(x)$.

*Proof.* By structural induction on $p$.

Cases $p = \_\_\_$ and $p = c$ In both cases we take $\theta' = []$.

Case $p = x$ We have

$$ t///x \Rightarrow \emptyset (\{x: t\}, \emptyset). $$

We take $\theta' = []$ and have $t(\theta \cup \theta') \le t\theta$.

Case $p = (p_1, p_2)$ We have

$$ t///(p_1, p_2) \Rightarrow_{A_1 \bowtie A_2 \bowtie \{\alpha_1, \alpha_2\}} (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\}) \\ \alpha_1///p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad \alpha_2///p_2 \Rightarrow_{A_2} (\Gamma_2, C_2) \quad A_1, A_2, \alpha_1, \alpha_2 \nvdash t. $$

Let $\theta^* = \theta \cup [\pi_1(t\theta)/\alpha_1, \pi_2(t\theta)/\alpha_2]$. We have $t\theta' = t\theta$ and $t\theta' \le \lceil(p_1, p_2)\rceil = \lceil p_1 \rceil \times \lceil p_2 \rceil$; thus, by Property A.31, $\pi_i(t\theta') \le \lceil p_i \rceil$. We also have $A_i \nvdash \text{dom}(\theta^*)$, $\alpha_i$ for both $i$, since $\{\alpha_1, \alpha_2\}$ is disjoint from each $A_i$.

We can therefore apply the induction hypothesis to $p_i$, $\alpha_i$, and $\theta^*$, for both $i$. We derive from each that there is a substitution $\theta'_i$ with domain $A_i$, such that $(\theta^* \cup \theta'_i) \Vdash C_i$ and, for all $x \in \text{capt}(p_i)$, $\Gamma_i(x)(\theta^* \cup \theta'_i) \le (\alpha_i\theta^*//p_i)(x)$.

We take $\theta' = [\pi_1(t\theta)/\alpha_1, \pi_2(t\theta)/\alpha_2] \cup \theta'_1 \cup \theta'_2$. We have $(\theta \cup \theta') \Vdash C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\}$ since it satisfies $C_1$ and $C_2$ and since $t\theta \le (\alpha_1 \times \alpha_2)\theta' = \pi_1(t\theta) \times \pi_2(t\theta)$.

Case $p = \text{tag}(p_1)$ We have

$$ t///\text{tag}(p_1) \Rightarrow_{A_1 \bowtie \{\alpha\}} (\Gamma_1, C_1 \cup \{t \le \text{tag}(\alpha)\}) \quad \alpha///p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad A_1, \alpha \nvdash t. $$

Analogously to the previous case, we construct $\theta^* = \theta \cup [\pi_{\text{tag}}(t\theta)/\alpha]$ and apply the induction hypothesis to $p_1$, $\alpha$, and $\theta^*$. We derive $\theta'_1$ and take $\theta' = [\pi_{\text{tag}}(t\theta)/\alpha] \cup \theta'_1$.

Case $p = p_1 \& p_2$ We have

$$ t///p_1 \& p_2 \Rightarrow_{A_1 \bowtie A_2} (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2) \quad t///p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad t///p_2 \Rightarrow_{A_2} (\Gamma_2, C_2). $$

For both $i$, we apply the induction hypothesis to $p_i$, $t$, and $\theta$ to derive $\theta'_i$. We take $\theta' = \theta'_1 \cup \theta'_2$.
$$
\begin{array}{c}
\begin{array}{c}
\forall i \in I \quad \Gamma \vdash c_i \rightsquigarrow A_i \quad D_i \\
\Gamma \vdash \{c_i \mid i \in I\} \rightsquigarrow \biguplus_{i \in I} A_i \bigcup_{i \in I} D_i
\end{array}
\\[1.5em]
\begin{array}{c}
\Gamma \vdash t \leq t' \rightsquigarrow \emptyset \quad \{t \leq t'\} \\
\Gamma \vdash t \leq t \rightsquigarrow \{\beta_1, \dots, \beta_n\} \quad \{t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n] \leq t\}
\end{array}
\\[1.5em]
\begin{array}{c}
\Gamma \vdash C_0 \rightsquigarrow A_0 \quad D_0 \quad \theta_0 \in \text{tally}(D_0) \\
\forall i \in I \quad \Gamma, \text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0) \vdash C_i \rightsquigarrow A_i \quad D_i \\
A = A_0 \uplus (\biguplus_{i \in I} A_i) \uplus \text{var}(\theta_0) \\
\Gamma \vdash \text{let } [C_0](\Gamma_i \text{ in } C_i)_{i \in I} \rightsquigarrow \text{equiv}(\theta_0) \cup \bigcup_{i \in I} D_i
\end{array}
\\[1.5em]
\begin{array}{l}
\text{equiv}(\theta) = \bigcup_{\alpha \in \text{dom}(\theta)} \{\alpha \preceq \alpha\theta, \alpha\theta \preceq \alpha\}. \\
\text{Definition A.44 (Constraint rewriting).} \quad \textit{The constraint rewriting relation } \Gamma \vdash c \rightsquigarrow A \textit{ between type environments, constraints or constraint sets, and type-constraint sets is defined by the rules in Figure 15.} \\
\text{Definition A.45 (Tallying problem).} \quad \textit{Let } D \textit{ be a type-constraint set. A type substitution } \theta \textit{ is a solution to the tallying problem of } D \textit{ if it satisfies } D, \textit{ that is, if } \theta \models D.
\end{array}
\end{array}
$$

<caption>**Figure 15.** Constraint rewriting rules with explicit variable introduction.</caption>

Note that all rules include a constraint of the form (·) $\leq t$. We add this constraint everywhere to streamline the proofs; in practice, it can be dropped from TRS-Appl and TRS-Match by using directly *t* instead of *β* to generate constraints for the sub-expressions.

**Definition A.42 (Type-constraint set).** A type-constraint set *D* is a set of constraints of the form *t* ≤ *t'*, where *t* and *t'* are types.

We say that a type substitution θ satisfies a type-constraint set D, written θ ⊧ D, if tθ ≤ t'θ holds for every t ≤ t' in D.

**Definition A.43 (Equivalent type-constraint set).** The equivalent type-constraint set equiv(θ) of a type substitution θ is defined as

$$
\mathrm{equiv}(\theta) = \bigcup_{\alpha \in \mathrm{dom}(\theta)} \{\alpha \preceq \alpha\theta, \alpha\theta \preceq \alpha\}.
$$

**Definition A.44 (Constraint rewriting).** The constraint rewriting relation $\Gamma \vdash c \rightsquigarrow A D$ between type environments, constraints or constraint sets, and type-constraint sets is defined by the rules in Figure 15.

**Definition A.45 (Tallying problem).** Let *D* be a type-constraint set. A type substitution *θ* is a solution to the tallying problem of *D* if it satisfies *D*, that is, if *θ* $\vdash$ *D*.

**Property A.46 (Tallying algorithm).** There exists a terminating algorithm tally such that, for any type-constraint set *D*, tally(*D*) is a finite, possibly empty, set of type substitutions.

**Theorem A.35 (Soundness and completeness of tally).** Let *D* be a type-constraint set. For any type substitution *θ*:

• if $\theta \in \text{tally}(D)$, then $\theta \models D$;

• if $\theta \models D$, then $\exists \theta' \in \text{tally}(D)$, $\theta''$. $\forall \alpha \notin \text{var}(\theta')$. $\alpha\theta \simeq \alpha\theta'\theta''$.

Furthermore, if $\theta \in \text{tally}(D)$, then $\text{dom}(\theta)$ is the set of variables appearing in $D$ and $\text{var}(\theta)$ is a set of fresh variables of the same cardinality. In the completeness property above, for $\theta''$ we can take $\theta \cup \theta'''$ where $\text{dom}(\theta''') = \text{var}(\theta')$.

### A.4.2 Properties of type reconstruction for $\mathfrak{S}$

**Lemma A.36.** Given a constraint set *C*, we write var(*C*) for the set of variables appearing in it. The following properties hold:

• whenever $t///p \Rightarrow_A (\Gamma, C)$, we have var($C$) $\subseteq$ var($t$) $\cup A$, var($\Gamma$) $\subseteq$ var($t$) $\cup A$, and $A \nvdash t$;

• whenever $e: t \Rightarrow_A C$, we have var($C$) $\subseteq$ var($t$) $\cup A$ and $A \nvdash t$;

• whenever $\Gamma \vdash C \rightsquigarrow A D$, we have var($D$) $\subseteq$ var($C$) $\cup \text{var}(\Gamma) \cup A$.

*Proof.* Straightforward proofs by induction on the derivations. $\square$

**Lemma A.37 (Correctness of environment reconstruction).** Let *p* be a pattern and *t*, *t'* two types, with *t'* $\le$ $\lceil p \rceil$. Let $t///p \Rightarrow (\Gamma, C)$. If *θ* is a type substitution such that *θ* $\vdash$ *C* and *t'* $\le$ *tθ*, then, for all *x* $\in$ capt(*p*), (*t'*//p)(*x*) $\le$ $\Gamma(x)\theta$.

*Proof.* By structural induction on *p*.

Cases *p* = _ and *p* = c There is nothing to prove since capt(*p*) = $\emptyset$.

Case *p* = x We have

$$
t///x \Rightarrow (\{x: t\}, \emptyset) \quad (t'//x)(x) = t'
$$

and must show $t' \le t\theta$, which we know by hypothesis.
Case $p = p_1|p_2$ We have

$$ t///p_1|p_2 \Rightarrow_{A_1 \bowtie A_2} (\{x: \Gamma_1(x) \lor \Gamma_2(x) \mid x \in \text{capt}(x)\}, C_1 \cup C_2) \\ (t \land \lceil p_1 \rceil, \text{ and } \theta \text{ to derive } \theta'_1). \text{ We apply it to } p_2, \\ t \land \lceil p_1 \rceil, \text{ and } \theta \text{ to derive } \theta'_2; \text{ here, note that } t\theta \le \lceil p_1 \rceil \lor \lceil p_2 \rceil \text{ implies } t\theta \land \lceil p_1 \rceil \le \lceil p_2 \rceil. \text{ We take } \theta' = \theta'_1 \cup \theta'_2. \text{ We have } (\theta \cup \theta') \vdash C \text{ since it satisfies } C_1 \text{ and } C_2. \text{ Furthermore, for all } x, \text{ we have } \Gamma_1(x)(\theta \cup \theta'_1) \le (t\theta \land \lceil p_1 \rceil//p_1)(x) \text{ and } \Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta \land \lceil p_1 \rceil//p_2)(x). \text{ Then, } \Gamma_1(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta') \lor \Gamma_2(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2), \text{ since } A_1 \text{ and } A_2 \text{ are disjoint and both are disjoint from var}(t). \text{ Finally, } \Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta//p)(x). \square $$

We apply the induction hypothesis to $p_1$, $t \land \lceil p_1 \rceil$, and $\theta$ to derive $\theta'_1$. We apply it to $p_2$, $t \land \lceil p_1 \rceil$, and $\theta$ to derive $\theta'_2$; here, note that $t\theta \le \lceil p_1 \rceil \lor \lceil p_2 \rceil$ implies $t\theta \land \lceil p_1 \rceil \le \lceil p_2 \rceil$.

We take $\theta' = \theta'_1 \cup \theta'_2$. We have $(\theta \cup \theta') \vdash C$ since it satisfies $C_1$ and $C_2$. Furthermore, for all $x$, we have $\Gamma_1(x)(\theta \cup \theta'_1) \le (t\theta \land \lceil p_1 \rceil//p_1)(x)$ and $\Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta \land \lceil p_1 \rceil//p_2)(x)$. Then, $\Gamma_1(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta') \lor \Gamma_2(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2)$, since $A_1$ and $A_2$ are disjoint and both are disjoint from var($t$). Finally, $\Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta//p)(x)$. $\square$

**Theorem A.39** (Soundness of constraint generation and rewriting). Let $e$ be an expression, $t$ a type, and $\Gamma$ a type environment. If $e: t \Rightarrow C, \Gamma \vdash C \rightsquigarrow D$, and $\theta \vdash D$, then $\Gamma \theta \vdash_S e: t\theta$.

*Proof.* By structural induction on $e$.

Case $e = x$ We have

$$ x: t \Rightarrow \{x \dot{\le} t\} \\ \Gamma \vdash \{x \dot{\le} t\} \rightsquigarrow \{t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n] \dot{\le} t\} \qquad \Gamma(x) = \forall \{\alpha_1, \dots, \alpha_n\}. t_x. $$

Let $A = \{\alpha_1, \dots, \alpha_n\}$. By $\alpha$-renaming we assume $A \not\cong \theta$; then we have $(\Gamma\theta)(x) = (\forall A. t_x)\theta = \forall A. (t_x\theta)$. Consider the substitution $\theta_x = [\beta_1\theta/\alpha_1, \dots, \beta_n\theta/\alpha_n]$. It has domain $A$, so we can derive $\Gamma\theta \vdash_S x: t_x\theta_x$.

We show $t_x\theta_x = t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta$ by showing $\alpha\theta_x = \alpha[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta$ holds for all $\alpha \in \text{var}(t_x)$. Either $\alpha \in A$ or not. In the first case, $\alpha = \alpha_i$ for some $i$; then $\alpha\theta_x = \alpha\theta_x = \beta_i\theta$ and $\alpha[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta = \beta_i\theta$. In the latter, $\alpha \ne \alpha_i$ for all $i$; then $\alpha\theta_x = \alpha\theta$, since $\text{var}(\alpha\theta) \cap \text{dom}(\theta_x) = \emptyset$ and $\alpha[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta = \alpha\theta$.

Therefore we derive $\Gamma\theta \vdash_S x: t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta$ by Ts-Var. Finally, since $\theta \vdash t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n] \dot{\le} t$, we derive $\Gamma\theta \vdash_S x: t\theta$ by subsumption.

Case $e = c$ We have

$$ c: t \Rightarrow \{c \dot{\le} t\} \qquad \Gamma \vdash \{c \dot{\le} t\} \rightsquigarrow \{c \dot{\le} t\}. $$

Analogously to the previous case, we first apply Ts-Const and then conclude by subsumption.

Case $e = \lambda x. e_1$ We have

$$ \lambda x. e_1: t \Rightarrow \{\text{def}\{x:\alpha\} \text{ in } C_1, \alpha \to \beta \dot{\le} t\} \qquad e_1: \beta \Rightarrow C_1 \\ \Gamma \vdash \{\text{def}\{x:\alpha\} \text{ in } C_1, \alpha \to \beta \dot{\le} t\} \rightsquigarrow D_1 \cup \{\alpha \to \beta \dot{\le} t\} \qquad \Gamma, \{x:\alpha\} \vdash C_1 \rightsquigarrow D_1. $$

By the induction hypothesis we derive $\Gamma\theta, \{x:\alpha\} \vdash_S e_1: \beta\theta$. We apply Ts-Abstr to derive $\Gamma\theta \vdash_S \lambda x. e_1: (\alpha \to \beta)\theta$. Since $\theta \vdash D$, we have $(\alpha \to \beta)\theta \le t\theta$. Hence, we derive by subsumption $\Gamma\theta \vdash_S \lambda x. e_1: t\theta$.

Case $e = e_1 e_2$ We have

$$ e_1 e_2: t \Rightarrow C_1 \cup C_2 \cup \{\beta \dot{\le} t\} \qquad e_1: \alpha \to \beta \Rightarrow C_1 \qquad e_2: \alpha \Rightarrow C_2 \\ \Gamma \vdash C_1 \cup C_2 \cup \{\beta \dot{\le} t\} \rightsquigarrow D_1 \cup D_2 \cup \{\beta \dot{\le} t\} \qquad \Gamma \vdash C_1 \rightsquigarrow D_1 \qquad \Gamma \vdash C_2 \rightsquigarrow D_2. $$

We derive $\Gamma\theta \vdash_S e_1: (\alpha\theta) \to (\beta\theta)$ and $\Gamma\theta \vdash_S e_2: \alpha\theta$ by the induction hypothesis. Then by Ts-Appl we derive $\Gamma\theta \vdash_S e_1 e_2: \beta\theta$, and finally—since $\beta\theta \le t\theta$—we conclude by subsumption.

Case $e = (e_1, e_2)$ We have

$$ (e_1, e_2): t \Rightarrow C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \qquad e_1: \alpha_1 \Rightarrow C_1 \qquad e_2: \alpha_2 \Rightarrow C_2 \\ \Gamma \vdash C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \rightsquigarrow D_1 \cup D_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \\ \Gamma \vdash C_1 \rightsquigarrow D_1 \qquad \Gamma \vdash C_2 \rightsquigarrow D_2. $$

We have $\Gamma\theta \vdash_S e_i: \alpha_i\theta$ for both $i$ by the induction hypothesis. Then, we derive $\Gamma\theta \vdash_S (e_1, e_2): (\alpha_1 \times \alpha_2)\theta$ by Ts-Pair, and finally conclude by subsumption.

Case $e = \text{'tag}(e_1)$ We have

$$ \text{'tag}(e_1): t \Rightarrow C \qquad C = C_1 \cup \{\text{'tag}(\alpha) \dot{\le} t\} \qquad e_1: \alpha \Rightarrow C_1 \\ \Gamma \vdash C \rightsquigarrow D \qquad D = D_1 \cup \{\text{'tag}(\alpha) \dot{\le} t\} \qquad \Gamma \vdash C_1 \rightsquigarrow D_1. $$

Analogous to the previous case. We apply the induction hypothesis, then Ts-Tag, then subsumption.
Case $p = (p_1, p_2)$ We have

$$ t///p \Rightarrow (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\}) \quad \forall i. \alpha_i///p_i \Rightarrow (\Gamma_i, C_i). $$

Each $x \in \text{capt}(p)$ is either in $\text{capt}(p_1)$ or in $\text{capt}(p_2)$. Let $x \in \text{capt}(p_i)$; then, we must show $(\pi_i(t')//p_i)(x) \le \Gamma_i(x)\theta$. This follows from the induction hypothesis, since $t' \le t\theta \le \alpha_1\theta \times \alpha_2\theta$ implies $\pi_i(t') \le \alpha_i\theta$ by Property A.31.

Case $p = \text{'tag}(p_1)$ We have

$$ t///\text{'tag}(p) \Rightarrow (\Gamma, C \cup \{t \le \text{'tag}(\alpha)\}) \quad \alpha///p \Rightarrow (\Gamma, C). $$

Analogous to the previous case. We can apply the induction hypothesis, because $t' \le t\theta \le \text{'tag}(\alpha)\theta$ implies $\pi_{\text{'tag}}(t') \le \alpha\theta$ by Property A.32.

Case $p = p_1 \& p_2$ Every $x \in \text{capt}(p)$ is either in $\text{capt}(p_1)$ or in $\text{capt}(p_2)$. Let $x \in \text{capt}(p_i)$; then, we apply the induction hypothesis to $p_i$ to conclude.

Case $p = p_1|p_2$ We have

$$ t///p_1|p_2 \Rightarrow (\{x: \Gamma_1(x) \lor \Gamma_2(x) \mid x \in \text{capt}(p_1)\}, C_1 \cup C_2) \\ (t \land \lceil p_1 \rceil)///p_1 \Rightarrow (\Gamma_1, C_1) \quad (t \land \lceil p_1 \rceil)///p_2 \Rightarrow (\Gamma_2, C_2). $$

By the induction hypothesis applied to both $p_1$ and $p_2$ we derive, for all $x$,

$$ (t' \land \lceil p_1 \rceil///p_1)(x) \le \Gamma_1(x)\theta \quad (t' \land \lceil p_1 \rceil///p_2)(x) \le \Gamma_2(x)\theta $$

from which we can conclude

$$ (t''//p)(x) = (t' \land \lceil p_1 \rceil//p_1)(x) \lor (t' \land \lceil p_1 \rceil//p_2)(x) \le \Gamma_1(x)\theta \lor \Gamma_2(x)\theta. \quad \square $$

**Lemma A.38** (Precise solution to environment reconstruction constraints). Let $p$ be a pattern, $t$ a type, and $\theta$ a type substitution such that $t\theta \le \lceil p \rceil$. Let $t///p \Rightarrow_A (\Gamma, C)$, with $A \nvdash \text{dom}(\theta)$.

There exists a type substitution $\theta'$ such that $\text{dom}(\theta') = A$, that $(\theta \cup \theta') \models C$, and that, for all $x \in \text{capt}(p)$, $\Gamma(x)(\theta \cup \theta') \le (t\theta//p)(x)$.

*Proof.* By structural induction on $p$.

Cases $p = -$ and $p = c$ In both cases we take $\theta' = []$.

Case $p = x$ We have

$$ t///x \Rightarrow \emptyset (\{x: t\}, \emptyset). $$

We take $\theta' = []$ and have $t(\theta \cup \theta') \le t\theta$.

Case $p = (p_1, p_2)$ We have

$$ t///(p_1, p_2) \Rightarrow_{A_1 \bowtie A_2 \bowtie \{\alpha_1, \alpha_2\}} (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\}) \\ \alpha_1///p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad \alpha_2///p_2 \Rightarrow_{A_2} (\Gamma_2, C_2) \quad A_1, A_2, \alpha_1, \alpha_2 \nvDash t. $$

Let $\theta^* = \theta \cup [\pi_1(t\theta)/\alpha_1, \pi_2(t\theta)/\alpha_2]$. We have $t\theta' = t\theta$ and $t\theta' \le \lceil(p_1, p_2)\rceil = \lceil p_1 \rceil \times \lceil p_2 \rceil$; thus, by Property A.31, $\pi_i(t\theta') \le \lceil p_i \rceil$. We also have $A_i \nvDash \text{dom}(\theta^*)$, $\alpha_i$ for both $i$, since $\{\alpha_1, \alpha_2\}$ is disjoint from each $A_i$.

We can therefore apply the induction hypothesis to $p_i$, $\alpha_i$, and $\theta^*$, for both $i$. We derive from each that there is a substitution $\theta'_i$ with domain $A_i$, such that $(\theta^* \cup \theta'_i) \models C_i$ and, for all $x \in \text{capt}(p_i)$, $\Gamma_i(x)(\theta^* \cup \theta'_i) \le (\alpha_i\theta^*//p_i)(x)$.

We take $\theta' = [\pi_1(t\theta)/\alpha_1, \pi_2(t\theta)/\alpha_2] \cup \theta'_1 \cup \theta'_2$. We have $(\theta \cup \theta') \models C_1 \cup C_2 \cup \{t \le \alpha_1 \times \alpha_2\}$ since it satisfies $C_1$ and $C_2$ and since $t\theta \le (\alpha_1 \times \alpha_2)\theta' = \pi_1(t\theta) \times \pi_2(t\theta)$.

Case $p = \text{'tag}(p_1)$ We have

$$ t///\text{'tag}(p_1) \Rightarrow_{A_1 \bowtie \{\alpha\}} (\Gamma_1, C_1 \cup \{t \le \text{'tag}(\alpha)\}) \quad \alpha///p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad A_1, \alpha \nvDash t. $$

Analogously to the previous case, we construct $\theta^* = \theta \cup [\pi_{\text{'tag}}(t\theta)/\alpha]$ and apply the induction hypothesis to $p_1$, $\alpha$, and $\theta^*$. We derive $\theta'_1$ and take $\theta' = [\pi_{\text{'tag}}(t\theta)/\alpha] \cup \theta'_1$.

Case $p = p_1 \& p_2$ We have

$$ t///p_1 \& p_2 \Rightarrow_{A_1 \bowtie A_2} (\Gamma_1 \cup \Gamma_2, C_1 \cup C_2) \quad t///p_1 \Rightarrow_{A_1} (\Gamma_1, C_1) \quad t///p_2 \Rightarrow_{A_2} (\Gamma_2, C_2). $$

For both $i$, we apply the induction hypothesis to $p_i$, $t$, and $\theta$ to derive $\theta'_i$. We take $\theta' = \theta'_1 \cup \theta'_2$.
Case e = match e₀ with (pᵢ → eᵢ)ᵢ∈I We have

match e₀ with (pᵢ → eᵢ)ᵢ∈I : t ⇒ C

$$
C = \{\text{let } [C'_0](\Gamma_i \text{ in } C'_i)_{i \in I}, \beta \preceq t\}
$$

$$
C'_{0} = C_{0} \cup (\bigcup_{i \in I} C_{i}) \cup \{\alpha \preceq \bigvee_{i \in I} [p_{i}]\} \quad e_{0}: \alpha \Rightarrow C_{0}
$$

$$
\forall i \in I \quad t_i = (\alpha \setminus \bigvee_{j<i} [p_j]) \wedge [p_i] \quad t_i / / / p_i \Rightarrow (\Gamma_i, C_i) \quad e_i : \beta \Rightarrow C'_i
$$

$$
\Gamma \vdash C \leadsto D
$$

$$
\Gamma \vdash C'_0 \leadsto D'_0
$$

$$
\Gamma \vdash C_0 \leadsto D_0 \qquad D'_0 = D_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \preceq \bigvee_{i \in I} [p_i]\}
$$

$$
\theta_0 \in \mathbf{tally}(D'_0) \quad \forall i \in I. \quad \Gamma, \mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0) \vdash C'_i \leadsto D'_i
$$

$$
D = \text{equiv}(\theta_0) \cup (\bigcup_{i \in I} D'_{i}) \cup \{\beta \preceq t\}
$$

and we must show Γθ ⊢ₖ match e₀ with (pᵢ → eᵢ)ᵢ∈I : tθ.

We prove it by establishing, for some types $\hat{t}_0$ and $\hat{t}'_i$ for each $i$, that

$$
\Gamma \theta \vdash_{\S} e_0 : \hat{t}_0 \qquad \hat{t}_0 \le \bigvee_{i \in I} [p_i] \qquad \hat{t}_i = (\hat{t}_0 \setminus \bigvee_{j<i} [p_j]) \wedge [p_i]
$$

$$
\forall i \in I. \quad \Gamma \theta, \mathrm{gen}_{\Gamma \theta} (\hat{t}_i // p_i) \vdash_{\S} e_i : \hat{t}'_i \quad \forall i \in I, \hat{t}'_i \le t \theta .
$$

Since $\theta_0 \in \mathbf{tally}(D'_0)$, $\theta_0 \vdash D'_0$ and thus $\theta_0 \vdash D_0$. Then, from

$$
e_0 : \alpha \Rightarrow C_0 \qquad \Gamma \vdash C_0 \leadsto D_0 \qquad \theta_0 \vdash D_0
$$

we derive Γθ ⊢ₖ e₀: αθ₀ by the induction hypothesis.

Let A = var(αθ₀) \ mvar(Γθ₀) = {α₁, ..., αₙ}. Let B = {β₁, ..., βₙ} be a set of type
variables such that B ⊢ Γ, θ, θ₀ and let θ* = [β₁/α₁, ..., βₙ/αₙ]. We derive Γθ₀ ⊢ₖ e₀: αθ₀θ*
by Corollary A.24, since θ* does not act on meaningful variables of Γθ₀. By Lemma A.23,
we derive Γθ₀θ ⊢ₖ e₀: αθ₀θ*θ; by Lemma A.22, Γθ ⊢ₖ e₀: αθ₀θ*θ (we prove the required
premises below).

We take $\hat{t}_0 = \alpha\theta_0\theta^*\theta$. We have $\alpha\theta_0\theta^*\theta \le \bigvee_{i\in I}[p_i]$ because $\theta_0 \Vdash D'_0$ implies $\alpha\theta_0 \le \bigvee_{i\in I}[p_i]$ and because subtyping is preserved by substitutions (recall that the accepted types of patterns are closed). We also have $\hat{t}_i = t_i\theta_0\theta^*\theta$ for all $i$.

For each branch *i*, from

$$
e_i : \beta \Rightarrow C'_i \quad \Gamma, \mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0) \vdash C'_i \leadsto D'_i \quad \theta \Vdash D'_i
$$

we derive Γθ, (gen<sub>Γθ₀</sub>(Γᵢθ₀))θ ⊢<sub>§</sub> eᵢ: βθ by the induction hypothesis. We derive by Lemma A.22
Γθ, gen<sub>Γθ</sub>(t̂ᵢ//pᵢ) ⊢<sub>§</sub> eᵢ: βθ (we prove the premises below). Thus we have t̂ᵢ = βθ for every
branch; we apply Ts-Match to derive Γθ ⊢<sub>§</sub> match e₀ with (pᵢ → eᵢ)ᵢ∈I: βθ, then subsumption
to derive Γθ ⊢<sub>§</sub> match e₀ with (pᵢ → eᵢ)ᵢ∈I: tθ.

Proof of Γθ ⊢ₖ e₀: αθ₀θ*θ from Γθ₀ ⊢ₖ e₀: αθ₀θ*θ To apply Lemma A.22, we must show

$$
\Gamma \theta \sqsubseteq \Gamma \theta_0 \theta \quad \mathrm{mvar}(\Gamma \theta) \subseteq \mathrm{mvar}(\Gamma \theta_0 \theta).
$$

To prove Γθ ⊑ Γθ₀θ, consider an arbitrary (x : ∀Aₓ.tₓ) ∈ Γ. By α-renaming, we assume
Aₓ ♯ θ, θ₀; then, we must prove ∀Aₓ.tₓθ ⊑ ∀Aₓ.tₓθ₀θ. For every γ, γθ ≃ γθ₀θ since
θ ⊧ equiv(θ₀). Hence, tₓθ ≃ tₓθ₀θ.

Since $t_{x}\theta \simeq t_{x}\theta_{0}\theta$ implies $\mathrm{mvar}(t_{x}\theta) = \mathrm{mvar}(t_{x}\theta_{0}\theta)$ by Lemma A.19, this also shows $\mathrm{mvar}(\Gamma\theta) \subseteq \mathrm{mvar}(\Gamma\theta_{0}\theta)$.

Proof of Γθ, gen<sub>Γθ</sub>(t̂ᵢ//pᵢ) ⊢ₖ eᵢ: βθ from Γθ, (gen<sub>Γθ₀</sub>(Γᵢθ₀))θ ⊢ₖ eᵢ: βθ By Lemma A.22, we can prove the result by showing

$$
\Gamma \theta, \mathrm{gen}_{\Gamma \theta} (\hat{t}_i // p_i) \sqsubseteq \Gamma \theta, (\mathrm{gen}_{\Gamma \theta_0} (\Gamma_i \theta_0)) \theta \\
\qquad \mathrm{mvar}(\Gamma \theta, \mathrm{gen}_{\Gamma \theta} (\hat{t}_i // p_i)) \subseteq \mathrm{mvar}(\Gamma \theta, (\mathrm{gen}_{\Gamma \theta_0} (\Gamma_i \theta_0)) \theta).
$$

The second condition is straightforward. For the first, we prove, for every $x \in \mathrm{capt}(p_i)$,
$\mathrm{gen}_{\Gamma\theta}((\hat{t}_i//p_i)(x)) \subseteq (\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)(x))\theta$. Let $\Gamma_i(x) = t_x$. Then, $\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0(x)) = \forall A.t_x\theta_0$, where A is $\mathrm{var}(\alpha\theta_0) \setminus \mathrm{mvar}(\Gamma\theta_0)$ as defined above (not all variables in A appear in $t_x\theta_0$, but schemes are defined disregarding useless quantification). By $\alpha$-renaming, we have $\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0(x)) = \forall B.t_x\theta_0\theta^*$ and, since $B \vdash \theta$, $(\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0(x))\theta = \forall B.t_x\theta_0\theta^*\theta$.

Since $\hat{t}_i \le \hat{t}_0 = \alpha\theta_0\theta^*\theta$ and since $\theta \circ \theta^* \circ \theta_0 \vdash C_i$ (because $\theta_0 \vdash C_i$), by Lemma A.37 we have $(\hat{t}_i//p_i)(x) \le t_x\theta_0\theta^*\theta$. Then, $\mathrm{gen}_{\Gamma\theta}((\hat{t}_i//p_i)(x)) \subseteq \forall B.t_x\theta_0\theta^*\theta$ holds because all variables in B may be quantified when generalizing $(\hat{t}_i//p_i)(x)$, since no $\beta_i$ appears in $\Gamma\theta$. $\square$

**Theorem A.40** (Completeness of constraint generation and rewriting). Let e be an expression, t a type, and Γ a type environment. Let θ be a type substitution such that Γθ ⊢ₖ e: tθ.
Case $p = p_1|p_2$ We have

$$t///p_1|p_2 \Rightarrow_{A_1 \bowtie A_2} (\{x: \Gamma_1(x) \lor \Gamma_2(x) \mid x \in \text{capt}(x)\}, C_1 \cup C_2) \\ (t \land \lceil p_1 \rceil, \text{and } \theta \text{ to derive } \theta'_1). \text{ We apply it to } p_2, \\ t \land \lceil p_1 \rceil, \text{ and } \theta \text{ to derive } \theta'_2; \text{ here, note that } t\theta \le \lceil p_1 \rceil \lor \lceil p_2 \rceil \text{ implies } t\theta \land \lceil p_1 \rceil \le \lceil p_2 \rceil. \text{ We take } \theta' = \theta'_1 \cup \theta'_2. \text{ We have } (\theta \cup \theta') \vdash_C \text{ since it satisfies } C_1 \text{ and } C_2. \text{ Furthermore, for} \\ \text{all } x, \text{ we have } \Gamma_1(x)(\theta \cup \theta'_1) \le (t\theta \land \lceil p_1 \rceil//p_1)(x) \text{ and } \Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta \land \lceil p_1 \rceil//p_2)(x). \\ \text{Then, } \Gamma_1(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta') \lor \Gamma_2(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2), \text{ since } A_1 \text{ and } A_2 \text{ are disjoint and both are disjoint from var}(t). \text{ Finally, } \Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2) \le \\ (t\theta//p)(x). \quad \square$$

We apply the induction hypothesis to $p_1$, $t \land \lceil p_1 \rceil$, and $\theta$ to derive $\theta'_1$. We apply it to $p_2$, $t \land \lceil p_1 \rceil$, and $\theta$ to derive $\theta'_2$; here, note that $t\theta \le \lceil p_1 \rceil \lor \lceil p_2 \rceil$ implies $t\theta \land \lceil p_1 \rceil \le \lceil p_2 \rceil$.

We take $\theta' = \theta'_1 \cup \theta'_2$. We have $(\theta \cup \theta') \vdash_C \text{ since it satisfies } C_1 \text{ and } C_2$. Furthermore, for all $x$, we have $\Gamma_1(x)(\theta \cup \theta'_1) \le (t\theta \land \lceil p_1 \rceil//p_1)(x)$ and $\Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta \land \lceil p_1 \rceil//p_2)(x)$. Then, $\Gamma_1(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta') \lor \Gamma_2(x)(\theta \cup \theta') = \Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2)$, since $A_1$ and $A_2$ are disjoint and both are disjoint from var($t$). Finally, $\Gamma_1(x)(\theta \cup \theta'_1) \lor \Gamma_2(x)(\theta \cup \theta'_2) \le (t\theta//p)(x)$. $\square$

**Theorem A.39** (Soundness of constraint generation and rewriting). Let $e$ be an expression, $t$ a type, and $\Gamma$ a type environment. If $e: t \Rightarrow C, \Gamma \vdash C \rightsquigarrow D$, and $\theta \vdash D$, then $\Gamma \theta \vdash_S e: t\theta$.

*Proof.* By structural induction on $e$.

Case $e = x$ We have

$$x: t \Rightarrow \{x \dot{\le} t\} \\ \Gamma \vdash \{x \dot{\le} t\} \rightsquigarrow \{t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n] \dot{\le} t\} \qquad \Gamma(x) = \forall \{\alpha_1, \dots, \alpha_n\}. t_x.$$

Let $A = \{\alpha_1, \dots, \alpha_n\}$. By $\alpha$-renaming we assume $A \not\cong \theta$; then we have $(\Gamma\theta)(x) = (\forall A. t_x)\theta = \forall A. (t_x\theta)$. Consider the substitution $\theta_x = [\beta_1\theta/\alpha_1, \dots, \beta_n\theta/\alpha_n]$. It has domain $A$, so we can derive $\Gamma\theta \vdash_S x: t_x\theta_x$.

We show $t_x\theta_x = t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta$ by showing $\alpha\theta_x = \alpha[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta$ holds for all $\alpha \in \text{var}(t_x)$. Either $\alpha \in A$ or not. In the first case, $\alpha = \alpha_i$ for some $i$; then $\alpha\theta_x = \alpha\theta_x = \beta_i\theta$ and $\alpha[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta = \beta_i\theta$. In the latter, $\alpha \ne \alpha_i$ for all $i$; then $\alpha\theta_x = \alpha\theta$, since $\text{var}(\alpha\theta) \cap \text{dom}(\theta_x) = \emptyset$ and $\alpha[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta = \alpha\theta$.

Therefore we derive $\Gamma\theta \vdash_S x: t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]\theta$ by Ts-Var. Finally, since $\theta \vdash t_x[\beta_1/\alpha_1, \dots, \beta_n/\alpha_n] \dot{\le} t$, we derive $\Gamma\theta \vdash_S x: t\theta$ by subsumption.

Case $e = c$ We have

$$c: t \Rightarrow \{c \dot{\le} t\} \qquad \Gamma \vdash \{c \dot{\le} t\} \rightsquigarrow \{c \dot{\le} t\}.$$

Analogously to the previous case, we first apply Ts-Const and then conclude by subsumption.

Case $e = \lambda x. e_1$ We have

$$\lambda x. e_1: t \Rightarrow \{\text{def}\{x: \alpha\} \text{ in } C_1, \alpha \to \beta \dot{\le} t\} \qquad e_1: \beta \Rightarrow C_1 \\ \Gamma \vdash \{\text{def}\{x: \alpha\} \text{ in } C_1, \alpha \to \beta \dot{\le} t\} \rightsquigarrow D_1 \cup \{\alpha \to \beta \dot{\le} t\} \qquad \Gamma, \{x: \alpha\} \vdash C_1 \rightsquigarrow D_1.$$

By the induction hypothesis we derive $\Gamma\theta, \{x: \alpha\}\vdash_S e_1: \beta\theta$. We apply Ts-Abstr to derive $\Gamma\theta \vdash_S \lambda x. e_1: (\alpha \to \beta)\theta$. Since $\theta \vdash D$, we have $(\alpha \to \beta)\theta \le t\theta$. Hence, we derive by subsumption $\Gamma\theta \vdash_S \lambda x. e_1: t\theta$.

Case $e = e_1 e_2$ We have

$$e_1 e_2: t \Rightarrow C_1 \cup C_2 \cup \{\beta \dot{\le} t\} \qquad e_1: \alpha \to \beta \Rightarrow C_1 \qquad e_2: \alpha \Rightarrow C_2 \\ \Gamma \vdash C_1 \cup C_2 \cup \{\beta \dot{\le} t\} \rightsquigarrow D_1 \cup D_2 \cup \{\beta \dot{\le} t\} \qquad \Gamma \vdash C_1 \rightsquigarrow D_1 \qquad \Gamma \vdash C_2 \rightsquigarrow D_2.$$

We derive $\Gamma\theta \vdash_S e_1: (\alpha\theta) \to (\beta\theta)$ and $\Gamma\theta \vdash_S e_2: \alpha\theta$ by the induction hypothesis. Then by Ts-Appl we derive $\Gamma\theta \vdash_S e_1 e_2: \beta\theta$, and finally—since $\beta\theta \le t\theta$—we conclude by subsumption.

Case $e = (e_1, e_2)$ We have

$$(e_1, e_2): t \Rightarrow C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \qquad e_1: \alpha_1 \Rightarrow C_1 \qquad e_2: \alpha_2 \Rightarrow C_2 \\ \Gamma \vdash C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \rightsquigarrow D_1 \cup D_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \\ \Gamma \vdash C_1 \rightsquigarrow D_1 \qquad \Gamma \vdash C_2 \rightsquigarrow D_2.$$

We have $\Gamma\theta \vdash_S e_i: \alpha_i\theta$ for both $i$ by the induction hypothesis. Then, we derive $\Gamma\theta \vdash_S (e_1, e_2): (\alpha_1 \times \alpha_2)\theta$ by Ts-Pair, and finally conclude by subsumption.

Case $e = \text{'tag}(e_1)$ We have

$$\text{'tag}(e_1): t \Rightarrow C \qquad C = C_1 \cup \{\text{'tag}(\alpha) \dot{\le} t\} \qquad e_1: \alpha \Rightarrow C_1 \\ \Gamma \vdash C \rightsquigarrow D \qquad D = D_1 \cup \{\text{'tag}(\alpha) \dot{\le} t\} \qquad \Gamma \vdash C_1 \rightsquigarrow D_1.$$

Analogous to the previous case. We apply the induction hypothesis, then Ts-Tag, then subsumption.
Let $e: t \Rightarrow_A C$, with $A \nvdash \Gamma$, $\text{dom}(\theta)$. There exist a type-constraint set $D$, a set of fresh type variables $A'$, and a type substitution $\theta'$, with $\text{dom}(\theta') = A \cup A'$, such that $\Gamma \vdash C \rightsquigarrow A' D$ and $(\theta \cup \theta') \Vdash D$.

*Proof.* By structural induction on $e$.

*Case e = x* We have

$$x: t \Rightarrow \emptyset \{x \dot{\le} t\} \\ \Gamma \theta \vdash_S x: t \theta \qquad (\Gamma \theta)(x) = \forall A_x. t_x \qquad \text{dom}(\theta_x) \subseteq A_x \qquad t_x \theta_x \theta \le t \theta.$$

Given $A_x = \{\alpha_1, \dots, \alpha_n\}$, we pick a set $A' = \{\beta_1, \dots, \beta_n\}$ of fresh variables. Let $\hat{\theta} = [\beta_i/\alpha_i | \alpha_i \in A_x]$. We have $\Gamma \vdash \{x \dot{\le} t\} \rightsquigarrow_{A'} \{t_x \hat{\theta} \dot{\le} t\}$.

We pick $\theta' = [\alpha_i \theta_x \theta / \beta_i | \beta_i \in A']$. It remains to prove that $(\theta \cup \theta') \Vdash \{t_x \hat{\theta} \dot{\le} t\}$, that is, that

$$t_x \hat{\theta} (\theta \cup \theta') \le t (\theta \cup \theta') = t \theta$$

(the equality above holds because the variables in $A'$ are fresh).

We prove $t_x \hat{\theta} (\theta \cup \theta') = t_x \theta_x \theta$ (from which we can conclude because $t_x \theta_x \theta \le t \theta$). We prove it by showing $\gamma \hat{\theta} (\theta \cup \theta') = \gamma \theta_x \theta$ for every $\gamma \in \text{var}(t_x)$. If $\gamma \in A_x$, then $\gamma = \alpha_i$ for some $i$. Then, $\gamma \hat{\theta} = \beta_i$ and $\gamma \hat{\theta} (\theta \cup \theta') = \alpha_i \theta_x \theta$. If $\gamma \notin A_x$, then $\gamma \hat{\theta} (\theta \cup \theta') = \gamma \theta$ (the variables $\theta'$ is defined on do not appear in $t_x$); likewise, $\gamma \theta_x \theta = \gamma \theta$ since $\theta_x$ is only defined on variables in $A_x$.

*Case e = c* We have

$$c: t \Rightarrow \emptyset \{c \dot{\le} t\} \qquad \Gamma \theta \vdash_S c: t \theta \qquad c \le t \theta.$$

We have $\Gamma \vdash \{c \dot{\le} t\} \rightsquigarrow \emptyset \{c \dot{\le} t\}$. Let $\theta' = []$. We have $(\theta \cup \theta') \Vdash \{c \dot{\le} t\}$ because $c \theta = c \le t \theta$.

*Case e = $\lambda x. e_1$* We have

$$\lambda x. e_1: t \Rightarrow_{A_1 \upharpoonright \{\alpha, \beta\}} \{\text{def } \{x: \alpha\} \text{ in } C_1, \alpha \to \beta \dot{\le} t\} \qquad e_1: \beta \Rightarrow_{A_1} C_1 \qquad A_1, \alpha, \beta \nvdash t \\ \Gamma \theta \vdash_S \lambda x. e_1: t \theta \qquad \Gamma \theta, \{x: t_1\} \vdash_S e_1: t_2 \qquad t_1 \to t_2 \le t \theta.$$

Let $\theta^* = \theta \cup [t_1/\alpha, t_2/\beta]$. Note that $\Gamma \theta^* = \Gamma \theta$ and $t \theta^* = t \theta$, because $\{\alpha_1, \alpha_2\} \nvdash \Gamma, t$.

We have $(\Gamma, \{x: \alpha\}) \theta^* \vdash_S e_1: \beta \theta^*, e_1: \beta \Rightarrow_{A_1} C_1$, and $A_1 \nvdash \text{dom}(\theta^*)$. By the induction hypothesis, therefore, $\Gamma, \{x: \alpha\} \vdash C_1 \rightsquigarrow_{A_1'} D_1$ and $(\theta^* \cup \theta_1') \Vdash D_1$, for some $D_1, A_1', \theta_1'$ such that $\text{dom}(\theta_1') = A_1 \cup A_1'$ and that the variables in $A_1'$ are fresh.

$\Gamma, \{x: \alpha\} \vdash C_1 \rightsquigarrow_{A_1'} D_1$ implies $\Gamma \vdash \text{def } \{x: \alpha\} \text{ in } C_1 \rightsquigarrow_{A_1'} D_1$. Hence, we have $\Gamma \vdash C \rightsquigarrow_{A_1'} D = D_1 \cup \{\alpha \to \beta \dot{\le} t\}$. Let $\theta' = [t_1/\alpha, t_2/\beta] \cup \theta_1'$. It is defined on the correct domain and it solves the constraints, since it solves $D_1$ and since $(\alpha \to \beta) \theta' = t_1 \to t_2 \le t \theta$.

*Case e = $e_1 e_2$* We have

$$e_1 e_2: t \Rightarrow_{A_1 \upharpoonright A_2 \upharpoonright \{\alpha, \beta\}} C_1 \cup C_2 \cup \{\beta \dot{\le} t\} \\ e_1: \alpha \to \beta \Rightarrow_{A_1} C_1 \qquad e_2: \alpha \Rightarrow_{A_2} C_2 \qquad A_1, A_2, \alpha, \beta \nvdash t \\ \Gamma \theta \vdash_S e_1 e_2: t \theta \qquad \Gamma \theta \vdash_S e_1: t_1 \to t_2 \qquad \Gamma \theta \vdash_S e_2: t_1 \qquad t_2 \le t \theta.$$

Let $\theta^* = \theta \cup [t_1/\alpha, t_2/\beta]$. Note that $\Gamma \theta^* = \Gamma \theta$ and $t \theta^* = t \theta$, since $\alpha, \beta \nvdash \Gamma, t$.

We have $\Gamma \theta \vdash_S e_1: (\alpha \to \beta) \theta^*, e_1: \alpha \to \beta \Rightarrow_{A_1} C_1$, and $A_1 \nvdash \text{dom}(\theta^*)$. By the induction hypothesis, therefore, $\Gamma \vdash C_1 \rightsquigarrow_{A_1'} D_1$ and $(\theta^* \cup \theta_1') \Vdash D_1$, for some $D_1$ and $\theta_1'$ with $\text{dom}(\theta_1') = A_1 \cup A_1'$.

Likewise, by applying the induction hypothesis to the derivation for $e_2$, we derive $\Gamma \vdash C_2 \rightsquigarrow_{A_2'} D_2$ and $(\theta^* \cup \theta_2') \Vdash D_2$, for some $D_2$ and $\theta_2'$ with $\text{dom}(\theta_2') = A_2 \cup A_2'$.

We can thus conclude that $\Gamma \vdash C \rightsquigarrow_{A_1' \cup A_2'} D = D_1 \cup D_2 \cup \{\beta \dot{\le} t\}$. Let $\theta' = [t_1/\alpha, t_2/\beta] \cup \theta_1' \cup \theta_2'$. It is defined on the correct domain and $\theta \cup \theta'$ solves the constraints: it solves both $D_1$ and $D_2$, and $\beta(\theta \cup \theta') = \beta \theta' = t_2 \le t \theta = t(\theta \cup \theta')$.

*Case e = $(e_1, e_2)$* We have

$$(e_1, e_2): t \Rightarrow_{A_1 \upharpoonright A_2 \upharpoonright \{\alpha_1, \alpha_2\}} C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \\ e_1: \alpha_1 \Rightarrow_{A_1} C_1 \qquad e_2: \alpha_2 \Rightarrow_{A_2} C_2 \qquad A_1, A_2, \alpha_1, \alpha_2 \nvdash t \\ \Gamma \theta \vdash_S (e_1, e_2): t \theta \qquad \Gamma \theta \vdash_S e_1: t_1 \qquad \Gamma \theta \vdash_S e_2: t_2 \qquad t_1 \times t_2 \le t \theta.$$

Analogous to the previous case. We define $\theta^* = \theta \cup [t_1/\alpha_1, t_2/\alpha_2]$ and proceed as above.
Case e = match e₀ with (pᵢ → eᵢ)ᵢ∈I We have

match e₀ with (pᵢ → eᵢ)ᵢ∈I : t ⇒ C

$$
C = \{\text{let } [C'_0](\Gamma_i \text{ in } C'_i)_{i \in I}, \beta \preceq t\}
$$

$$
C'_{0} = C_{0} \cup (\bigcup_{i \in I} C_{i}) \cup \{\alpha \preceq \bigvee_{i \in I} \{p_{i}\}\} \quad e_{0}: \alpha \Rightarrow C_{0}
$$

$$
\forall i \in I \quad t_i = (\alpha \ \mathbb{V}_{j<i} \{p_j\}) \wedge \{p_i\} \quad t_i / / / p_i \Rightarrow (\Gamma_i, C_i) \quad e_i : \beta \Rightarrow C'_i
$$

$$
\Gamma \vdash C \leadsto D
$$

$$
\Gamma \vdash C'_{0} \leadsto D'_{0}
$$

$$
\Gamma \vdash C_0 \leadsto D_0 \qquad D'_0 = D_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \preceq \bigvee_{i \in I} \{p_i\}\}
$$

$$
\theta_0 \in \text{tally}(D'_0)
$$

$$
\forall i \in I. \Gamma, \text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0) \vdash C'_i \leadsto D'_i
$$

$$
D = \text{equiv}(\theta_0) \cup (\bigcup_{i \in I} D'_{i}) \cup \{\beta \preceq t\}
$$

and we must show $\Gamma\theta \vdash_{\S} \text{match } e_0$ with $(p_i \to e_i)_{i \in I}: t\theta$.

We prove it by establishing, for some types $\hat{t}_0$ and $\hat{t}'_i$ for each $i$, that

$$
\Gamma \theta \vdash_{\S} e_0 : \hat{t}_0 \qquad \hat{t}_0 \leq \bigvee_{i \in I} \{p_i\}
$$

$$
\hat{t}_i = (\hat{t}_0 \setminus \bigvee_{j<i} \{p_j\}) \wedge \{p_i\}
$$

$$
\forall i \in I. \quad \Gamma \theta, \operatorname{gen}_{\Gamma \theta}(\hat{t}_i // p_i) \vdash_{\S} e_i : \hat{t}'_i \quad \bigvee_{i \in I} \hat{t}'_i \le t \theta .
$$

Since $\theta_0 \in \text{tally}(D'_0)$, $\theta_0 \vdash D'_0$ and thus $\theta_0 \vdash D_0$. Then, from

$$
e_0 : \alpha \Rightarrow C_0 \quad \Gamma \vdash C_0 \leadsto D_0 \quad \theta_0 \vdash D_0
$$

we derive $\Gamma\theta_0 \vdash_{\S} e_0: \alpha\theta_0\theta$ by the induction hypothesis.

Let $A = \text{var}(\alpha\theta_0) \setminus \text{mvar}(\Gamma\theta_0) = \{\alpha_1, \dots, \alpha_n\}$. Let $B = \{\beta_1, \dots, \beta_n\}$ be a set of type variables such that $B \nvdash \Gamma, \theta, \theta_0$ and let $\theta^* = [\beta_1/\alpha_1, \dots, \beta_n/\alpha_n]$. We derive $\Gamma\theta_0 \vdash_{\S} e_0: \alpha\theta_0\theta^*$ by Corollary A.24, since $\theta^*$ does not act on meaningful variables of $\Gamma\theta_0$. By Lemma A.23, we derive $\Gamma\theta_0\theta \vdash_{\S} e_0: \alpha\theta_0\theta^*\theta$; by Lemma A.22, $\Gamma\theta \vdash_{\S} e_0: \alpha\theta_0\theta^*\theta$ (we prove the required premises below).

We take $\hat{t}_0 = \alpha\theta_0\theta^*\theta$. We have $\alpha\theta_0\theta^*\theta \le \bigvee_{i \in I} \{p_i\}$ because $\theta_0 \Vdash D'_0$ implies $\alpha\theta_0 \le \bigvee_{i \in I} \{p_i\}$ and because subtyping is preserved by substitutions (recall that the accepted types of patterns are closed). We also have $\hat{t}_i = t_i\theta_0\theta^*\theta$ for all $i$.

For each branch $i$, from

$$
e_i : \beta \Rightarrow C'_i \quad \Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0) \vdash C'_i \leadsto D'_i \quad \theta \Vdash D'_i
$$

we derive $\Gamma\theta, (\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta \vdash_{\S} e_i: \beta\theta$ by the induction hypothesis. We derive by Lemma A.22 $\Gamma\theta, \operatorname{gen}_{\Gamma\theta}(\hat{t}_i//p_i) \vdash_{\S} e_i: \beta\theta$ (we prove the premises below). Thus we have $\hat{t}_i = \beta\theta$ for every branch; we apply Ts-Match to derive $\Gamma\theta \vdash_{\S} \text{match } e_0$ with $(p_i \to e_i)_{i \in I}: \beta\theta$, then subsumption to derive $\Gamma\theta \vdash_{\S} \text{match } e_0$ with $(p_i \to e_i)_{i \in I}: t\theta$.

Proof of $\Gamma\theta \vdash_{\S} e_0: \alpha\theta_0\theta^*\theta$ from $\Gamma\theta_0\theta \vdash_{\S} e_0: \alpha\theta_0\theta^*\theta$ To apply Lemma A.22, we must show

$$
\Gamma \theta \sqsubseteq \Gamma \theta_0 \theta \quad \text{mvar}(\Gamma \theta) \subseteq \text{mvar}(\Gamma \theta_0 \theta).
$$

To prove $\Gamma\theta \sqsubseteq \Gamma\theta_0\theta$, consider an arbitrary $(x: \forall A_x. t_x) \in \Gamma$. By $\alpha$-renaming, we assume $A_x \nvdash \theta, \theta_0$; then, we must prove $\forall A_x. t_x\theta \sqsubseteq \forall A_x. t_x\theta_0\theta$. For every $\gamma, \gamma\theta \simeq \gamma\theta_0\theta$ since $\theta \Vdash \text{equiv}(\theta_0)$. Hence, $t_x\theta \simeq t_x\theta_0\theta$.

Since $t_{x}\theta \simeq t_{x}\theta_{0}\theta$ implies $\text{mvar}(t_{x}\theta) = \text{mvar}(t_{x}\theta_{0}\theta)$ by Lemma A.19, this also shows
$\text{mvar}(\Gamma\theta) \subseteq \text{mvar}(\Gamma\theta_{0}\theta)$.

Proof of $\Gamma\theta, \operatorname{gen}_{\Gamma\theta}(\hat{t}_i//p_i) \vdash_{\S} e_i: \beta\theta$ from $\Gamma\theta, (\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta \vdash_{\S} e_i: \beta\theta$ By Lemma A.22, we can prove the result by showing

$$
\begin{align*}
& \Gamma\theta, \operatorname{gen}_{\Gamma\theta}(\hat{t}_i//p_i) \sqsubseteq \Gamma\theta, (\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta \\
& \qquad \operatorname{mvar}(\Gamma\theta, \operatorname{gen}_{\Gamma\theta}(\hat{t}_i//p_i)) \subseteq \operatorname{mvar}(\Gamma\theta, (\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta).
\end{align*}
$$

The second condition is straightforward. For the first, we prove, for every $x \in \text{capt}(p_i)$,
$\text{gen}_{\Gamma\theta}((\hat{t}_i//p_i)(x)) \sqsubseteq (\text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)(x))\theta$. Let $\Gamma_i(x) = t_x$. Then, $\text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0(x)) = \forall A. t_x\theta_0$, where $A$ is $\text{var}(\alpha\theta_0) \setminus \text{mvar}(\Gamma\theta_0)$ as defined above (not all variables in $A$ appear in $t_x\theta_0$, but schemes are defined disregarding useless quantification). By $\alpha$-renaming, we have $\text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0(x)) = \forall B. t_x\theta_0\theta^*$ and, since $B \nvdash \theta, (\text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)(x))\theta = \forall B. t_x\theta_0\theta^*\theta$.

Since $\hat{t}_i \le \hat{t}_0 = \alpha\theta_0\theta^*\theta$ and since $\theta \circ \theta^* \circ \theta_0 \Vdash C_i$ (because $\theta_0 \Vdash C_i$), by Lemma A.37 we have $(\hat{t}_i//p_i)(x) \le t_x\theta_0\theta^*\theta$. Then, $\text{gen}_{\Gamma\theta}((\hat{t}_i//p_i)(x)) \sqsubseteq \forall B. t_x\theta_0\theta^*\theta$ holds because all variables in $B$ may be quantified when generalizing $(\hat{f}_i//p_i)(x)$, since no $\beta_i$ appears in $\Gamma\theta$. $\square$

**Theorem A.40** (Completeness of constraint generation and rewriting). Let $e$ be an expression, $t$ a type, and $\Gamma$ a type environment. Let $\theta$ be a type substitution such that $\Gamma\theta \vdash_{\S} e: t\theta$.
Case $e = \text{'tag}(e_1)$ We have

$$
\begin{align*}
\text{'tag}(e_1) : t &\Rightarrow_{A_1 \uplus \{\alpha\}} C_1 \cup \{\text{'tag}(\alpha) \dot{\leq} t\} & e_1 : \alpha &\Rightarrow_{A_1} C_1 & A_1, \alpha \not\leq t \\
\Gamma \theta \vdash_{\S} \text{'tag}(e) : t \theta &\quad \Gamma \theta \vdash_{\S} e_1 : t_1 & \text{'tag}(t_1) &\leq t \theta .
\end{align*}
$$

Analogous to the two previous cases. Here we define $\theta^* = \theta \cup [t_1/\alpha]$.

Case $e = \text{match } e_0$ with $(p_i \to e_i)_{i \in I}$ We have

$$
\begin{align*}
\text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I} : t &\Rightarrow_A \{\text{let } [C'_0](\Gamma_i \text{ in } C'_i), \beta \dot{\leq} t\} \\
& e_0 : \alpha \Rightarrow_{A_0} C_0 \qquad t_i = (\alpha \setminus \bigcup_{j<i} \{p_j\}) \wedge \{p_i\} \\
& \forall i \in I \qquad t_i \text{///} p_i \Rightarrow_{A_i} (\Gamma_i, C_i) \qquad e_i : \beta \Rightarrow_{A'_i} C'_i \\
& C'_0 = C_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \dot{\leq} \bigcup_{i \in I} \{p_i\}\} \\
& A = A_0 \uplus (\biguplus_{i \in I} A_i) \uplus (\biguplus_{i \in I} A'_i) \uplus \{\alpha, \beta\} \\
\Gamma \theta \vdash_{\S} \text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I} : t \theta \\
& \Gamma \theta \vdash_{\S} e_0 : t_0 \qquad t_0 \leq \bigcup_{i \in I} \{p_i\} \qquad t_i^* = (t_0 \setminus \bigcup_{j<i} \{p_j\}) \wedge \{p_i\} \\
& \forall i \in I \qquad \Gamma \theta, \text{gen}_{\Gamma \theta}(t_i^* // p_i) \vdash_{\S} e_i : t_i' \qquad t' = \bigcup_{i \in I} t_i' \leq t \theta .
\end{align*}
$$

Let $\theta^* = \theta \cup [t_0/\alpha]$. Then we have

$$
e_0 : \alpha \Rightarrow_{A_0} C_0 \qquad \Gamma \theta^* \vdash_{\S} e_0 : \alpha \theta^* \qquad A_0 \not\vdash \Gamma, \text{dom}(\theta^*)
$$

and, by the induction hypothesis, we find $D_0$, $A'_0$ (containing fresh variables), and $\theta'_0$ such that

$$
\Gamma \vdash C_0 \rightsquigarrow_{A_0'} D_0 \qquad \theta^* \cup \theta_0' \Vdash D_0 \qquad \mathrm{dom}(\theta_0') = A_0 \cup A_0'.
$$

From $\Gamma \vdash C_0 \rightsquigarrow_{A_0'} D_0$ we can derive

$$
\Gamma \vdash C'_0 \rightsquigarrow_{A'_0} D'_0 = D_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \dot{\leq} \bigcup_{i \in I} \{p_i\}\}
$$

because subtyping constraints are always rewritten to themselves.

For each branch $i$, note that $t_i \theta^* = t_i^*$. By Lemma A.38, we can find $\theta_i^*$ such that

$$
\mathrm{dom}(\theta_i^*) = A_i \qquad \theta^* \cup \theta_i^* \Vdash C_i \qquad \forall x \in \mathrm{capt}(p_i). \quad \Gamma(x)(\theta^* \cup \theta_i^*) \le (t_i^* // p_i)(x).
$$

Note also that $\theta^* \Vdash \alpha \dot{\leq} \bigcup_{i \in I} \{p_i\}$. We therefore have $\theta^* \cup \theta_0' \cup (\bigcup_{i \in I} \theta_i^*) \Vdash D_0'$. Let $\theta^{**} = \theta^* \cup \theta_0' \cup (\bigcup_{i \in I} \theta_i^*)$.

By the properties of tallying, if $\text{var}(D'_0) = \{\alpha_1, \dots, \alpha_n\}$ and given a set $B = \{\alpha'_1, \dots, \alpha'_n\}$ of fresh variables, there exist two substitutions $\theta_0 \in \text{tally}(D'_0)$ and $\theta_0''$ such that

$$
\begin{align*}
\mathrm{dom}(\theta_0) &= \mathrm{var}(D'_0) & \mathrm{var}(\theta_0) &= B & \mathrm{dom}(\theta_0'') &= B \\
\forall \gamma \notin \mathrm{var}(\theta_0) &\quad \gamma\theta_0(\theta^{**} \cup \theta_0'') &\approx &\gamma\theta^{**}.
\end{align*}
$$

Let $\theta^\top = \theta^{**} \cup [t'/\beta] \cup \theta_0''$. To apply the induction hypothesis for a branch $i$, we need

$$
e_i : \beta \Rightarrow_{A_i'} C_i' \quad (\Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)) \theta^\top \vdash_{\S} e_i : \beta\theta^\top \quad A_i' \not\vdash \Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0), \operatorname{dom}(\theta^\top).
$$

We derive the typing judgment above by subsumption and by weakening (we prove the premises below). As for the freshness condition, note that the variables in $\Gamma\theta_0$ are all either in $\Gamma$ or in $\text{var}(\theta_0)$; in the latter case, they are fresh by our choice of $B$.

By applying the induction hypothesis to each branch $i$, we therefore find $D_i$, $A_i''$ (of fresh variables), and $\theta_i''$ such that

$$
\Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0) \vdash C'_i \rightsquigarrow_{A_i''} D_i \qquad \theta^\top \cup \theta_i' \Vdash D_i \qquad \operatorname{dom}(\theta_i') = A_i' \cup A_i''.
$$

Hence, we have

$$
\Gamma \theta \vdash \{\text{let } [C'_0](\Gamma_i \text{ in } C'_i), \beta \dot{\leq} t\} \rightsquigarrow_{A'} \text{equiv}(\theta_0) \cup (\bigcup_{i \in I} D_i) \cup \{\beta \dot{\leq} t\},
$$

where $A' = A'_0 \cup (\bigcup_{i \in I} A_i'') \cup \text{var}(\theta_0)$.

We take $\theta' = [t_0/\alpha, t'/\beta] \cup \theta'_0 \cup (\bigcup_{i \in I} \theta_i^*) \cup \theta_0'' \cup (\bigcup_{i \in I} \theta_i')$. It has the correct domain; we must only show

$$
\theta \cup \theta' \Vdash \text{equiv}(\theta_0) \cup (\bigcup_{i \in I} D_i) \cup \{\beta \dot{\leq} t\}.
$$

The last constraint is satisfied since $\beta(\theta \cup \theta') = t' \le t\theta$. Constraints in $\text{equiv}(\theta_0)$ are of the form $\alpha \le \alpha\theta_0$ or $\alpha\theta_0 \le \alpha$, for $\alpha \in \text{dom}(\theta_0)$. Since these $\alpha$ are not in $\text{var}(\theta_0)$, we have $\alpha\theta_0(\theta^{**} \cup \theta_0'') \simeq \alpha\theta^{**}$ and hence $\alpha\theta_0(\theta \cup \theta') \simeq \alpha(\theta \cup \theta')$. For each $i$, since $\theta^\top \cup \theta_i' \Vdash D_i$, we have also $\theta \cup \theta' \Vdash D_i$ (the other substitutions we add are not defined on the variables in $D_i$).

*Proof of* $(\Gamma, \text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top \vdash_{\S} e_i : \beta\theta^\top$ from $\Gamma\theta, \text{gen}_{\Gamma\theta}(t_i^*//p_i) \vdash_{\S} e_i : t_i'$. From $\Gamma\theta, \text{gen}_{\Gamma\theta}(t_i^*//p_i) \vdash_{\S} e_i : t_i'$, we derive $\Gamma\theta, \text{gen}_{\Gamma\theta}(t_i^*//p_i) \vdash_{\S} e_i : \beta\theta^\top$ by subsumption, since $t_i' \le t' = \beta\theta^\top$. We
Let $e: t \Rightarrow_A C$, with $A \nvdash \Gamma$, $\text{dom}(\theta)$. There exist a type-constraint set $D$, a set of fresh type variables $A'$, and a type substitution $\theta'$, with $\text{dom}(\theta') = A \cup A'$, such that $\Gamma \vdash C \rightsquigarrow A' D$ and $(\theta \cup \theta') \Vdash D$.

*Proof.* By structural induction on $e$.

*Case e = x* We have

$$x: t \Rightarrow \emptyset \{x \dot{\le} t\} \\ \Gamma \theta \vdash_{\emptyset} x: t \theta \qquad (\Gamma \theta)(x) = \forall A_x. t_x \qquad \text{dom}(\theta_x) \subseteq A_x \qquad t_x \theta_x \theta \le t \theta.$$

Given $A_x = \{\alpha_1, \dots, \alpha_n\}$, we pick a set $A' = \{\beta_1, \dots, \beta_n\}$ of fresh variables. Let $\hat{\theta} = [\beta_i/\alpha_i | \alpha_i \in A_x]$. We have $\Gamma \vdash \{x \dot{\le} t\} \rightsquigarrow_{A'} \{t_x \hat{\theta} \dot{\le} t\}$.

We pick $\theta' = [\alpha_i \theta_x \theta/\beta_i | \beta_i \in A']$. It remains to prove that $(\theta \cup \theta') \Vdash \{t_x \hat{\theta} \dot{\le} t\}$, that is, that

$$t_x \hat{\theta}(\theta \cup \theta') \le t(\theta \cup \theta') = t\theta$$

(the equality above holds because the variables in $A'$ are fresh).

We prove $t_x \hat{\theta}(\theta \cup \theta') = t_x \theta_x \theta$ (from which we can conclude because $t_x \theta_x \theta \le t\theta$). We prove it by showing $\gamma \hat{\theta}(\theta \cup \theta') = \gamma \theta_x \theta$ for every $\gamma \in \text{var}(t_x)$. If $\gamma \in A_x$, then $\gamma = \alpha_i$ for some $i$. Then, $\gamma \hat{\theta} = \beta_i$ and $\gamma \hat{\theta}(\theta \cup \theta') = \alpha_i \theta_x \theta$. If $\gamma \notin A_x$, then $\gamma \hat{\theta}(\theta \cup \theta') = \gamma \theta$ (the variables $\theta'$ is defined on do not appear in $t_x$); likewise, $\gamma \theta_x \theta = \gamma \theta$ since $\theta_x$ is only defined on variables in $A_x$.

*Case e = c* We have

$$c: t \Rightarrow \emptyset \{c \dot{\le} t\} \qquad \Gamma \theta \vdash_{\emptyset} c: t \theta \qquad c \le t \theta.$$

We have $\Gamma \vdash \{c \dot{\le} t\} \rightsquigarrow \emptyset \{c \dot{\le} t\}$. Let $\theta' = []$. We have $(\theta \cup \theta') \Vdash \{c \dot{\le} t\}$ because $c\theta = c \le t\theta$.

*Case e = $\lambda x. e_1$* We have

$$\lambda x. e_1: t \Rightarrow_{A_1 \upharpoonright \{\alpha, \beta\}} \{\text{def } \{x: \alpha\} \text{ in } C_1, \alpha \to \beta \dot{\le} t\} \qquad e_1: \beta \Rightarrow_{A_1} C_1 \qquad A_1, \alpha, \beta \nvdash t \\ \Gamma \theta \vdash_{\emptyset} \lambda x. e_1: t \theta \qquad \Gamma \theta, \{x: t_1\} \vdash_{\emptyset} e_1: t_2 \qquad t_1 \to t_2 \le t \theta.$$

Let $\theta^* = \theta \cup [t_1/\alpha, t_2/\beta]$. Note that $\Gamma \theta^* = \Gamma \theta$ and $t \theta^* = t \theta$, because $\{\alpha_1, \alpha_2\} \nvdash \Gamma, t$.

We have $(\Gamma, \{x: \alpha\}) \theta^* \vdash_{\emptyset} e_1: \beta \theta^*, e_1: \beta \Rightarrow_{A_1} C_1$, and $A_1 \nvdash \text{dom}(\theta^*)$. By the induction hypothesis, therefore, $\Gamma, \{x: \alpha\} \vdash C_1 \rightsquigarrow_{A_1'} D_1$ and $(\theta^* \cup \theta_1') \Vdash D_1$, for some $D_1, A_1', \theta_1'$ such that $\text{dom}(\theta_1') = A_1 \cup A_1'$ and that the variables in $A_1'$ are fresh.

$\Gamma, \{x: \alpha\} \vdash C_1 \rightsquigarrow_{A_1'} D_1$ implies $\Gamma \vdash \text{def } \{x: \alpha\} \text{ in } C_1 \rightsquigarrow_{A_1'} D_1$. Hence, we have $\Gamma \vdash C \rightsquigarrow_{A_1'} D = D_1 \cup \{\alpha \to \beta \dot{\le} t\}$. Let $\theta' = [t_1/\alpha, t_2/\beta] \cup \theta_1'$. It is defined on the correct domain and it solves the constraints, since it solves $D_1$ and since $(\alpha \to \beta)\theta' = t_1 \to t_2 \le t\theta$.

*Case e = $e_1 e_2$* We have

$$e_1 e_2: t \Rightarrow_{A_1 \upharpoonright A_2 \upharpoonright \{\alpha, \beta\}} C_1 \cup C_2 \cup \{\beta \dot{\le} t\} \\ e_1: \alpha \to \beta \Rightarrow_{A_1} C_1 \qquad e_2: \alpha \Rightarrow_{A_2} C_2 \qquad A_1, A_2, \alpha, \beta \nvdash t \\ \Gamma \theta \vdash_{\emptyset} e_1 e_2: t \theta \qquad \Gamma \theta \vdash_{\emptyset} e_1: t_1 \to t_2 \qquad \Gamma \theta \vdash_{\emptyset} e_2: t_1 \qquad t_2 \le t \theta.$$

Let $\theta^* = \theta \cup [t_1/\alpha, t_2/\beta]$. Note that $\Gamma \theta^* = \Gamma \theta$ and $t \theta^* = t \theta$, since $\alpha, \beta \nvdash \Gamma, t$.

We have $\Gamma \theta \vdash_{\emptyset} e_1: (\alpha \to \beta)\theta^*, e_1: \alpha \to \beta \Rightarrow_{A_1} C_1$, and $A_1 \nvdash \text{dom}(\theta^*)$. By the induction hypothesis, therefore, $\Gamma \vdash C_1 \rightsquigarrow_{A_1'} D_1$ and $(\theta^* \cup \theta_1') \Vdash D_1$, for some $D_1$ and $\theta_1'$ with $\text{dom}(\theta_1') = A_1 \cup A_1'$.

Likewise, by applying the induction hypothesis to the derivation for $e_2$, we derive $\Gamma \vdash C_2 \rightsquigarrow_{A_2'} D_2$ and $(\theta^* \cup \theta_2') \Vdash D_2$, for some $D_2$ and $\theta_2'$ with $\text{dom}(\theta_2') = A_2 \cup A_2'$.

We can thus conclude that $\Gamma \vdash C \rightsquigarrow_{A_1' \cup A_2'} D = D_1 \cup D_2 \cup \{\beta \dot{\le} t\}$. Let $\theta' = [t_1/\alpha, t_2/\beta] \cup \theta_1' \cup \theta_2'$. It is defined on the correct domain and $\theta \cup \theta'$ solves the constraints: it solves both $D_1$ and $D_2$, and $\beta(\theta \cup \theta') = \beta\theta' = t_2 \le t\theta = t(\theta \cup \theta')$.

*Case e = $(e_1, e_2)$* We have

$$(e_1, e_2): t \Rightarrow_{A_1 \upharpoonright A_2 \upharpoonright \{\alpha_1, \alpha_2\}} C_1 \cup C_2 \cup \{\alpha_1 \times \alpha_2 \dot{\le} t\} \\ e_1: \alpha_1 \Rightarrow_{A_1} C_1 \qquad e_2: \alpha_2 \Rightarrow_{A_2} C_2 \qquad A_1, A_2, \alpha_1, \alpha_2 \nvdash t \\ \Gamma \theta \vdash_{\emptyset} (e_1, e_2): t \theta \qquad \Gamma \theta \vdash_{\emptyset} e_1: t_1 \qquad \Gamma \theta \vdash_{\emptyset} e_2: t_2 \qquad t_1 \times t_2 \le t \theta.$$

Analogous to the previous case. We define $\theta^* = \theta \cup [t_1/\alpha_1, t_2/\alpha_2]$ and proceed as above.
then apply Lemma A.22, which requires us to show the two premises

$$ (\Gamma, \mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top \subseteq \Gamma\theta, \mathrm{gen}_{\Gamma\theta}(t_i^*//p_i) \\ \mathrm{mvar}((\Gamma, \mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \mathrm{mvar}(\Gamma\theta, \mathrm{gen}_{\Gamma\theta}(t_i^*//p_i)). $$

Note that $\Gamma\theta = \Gamma\theta^\top$ since the two substitutions only differ on variables introduced by constraint generation or tallying. Simplifying, we need to show

$$ \mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)\theta^\top \subseteq \mathrm{gen}_{\Gamma\theta}(t_i^*//p_i) \qquad \mathrm{mvar}((\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \mathrm{mvar}(\Gamma\theta). $$

To prove the former, consider $x \in \mathrm{capt}(p_i)$ and let $\Gamma_i(x) = t_x$. We must show $\mathrm{gen}_{\Gamma\theta_0}(t_x\theta_0)\theta^\top \subseteq \mathrm{gen}_{\Gamma\theta}((t_i^*//p_i)(x))$. We have

$$ \mathrm{gen}_{\Gamma\theta_0}(t_x\theta_0) = \forall B_x. t_x\theta_0 \qquad B_x = \mathrm{var}(t_x\theta_0) \setminus \mathrm{mvar}(\Gamma\theta_0). $$

Note that all variables in $\mathrm{var}(t_x\theta_0)$ are in $\mathrm{var}(\theta_0)$: this is because all variables in $\mathrm{var}(t_x)$ occur in $D'_0$ ($\alpha$ occurs in the exhaustiveness constraint, variables introduced by pattern environment generation occur in $C_i$) and hence are in the domain of $\theta_0$. Then, $B_x \subseteq B$: its elements are some of the $\alpha'_i$ in $B$. Consider a set $B'_x = \{\alpha''_i | \alpha'_i \in B_x\}$ of fresh variables and the renaming $\tilde{\theta} = [\alpha''_i/\alpha'_i | \alpha'_i \in B_x]$; we have

$$ \mathrm{gen}_{\Gamma\theta_0}(t_x\theta_0) = \forall B'_x. t_x\theta_0\tilde{\theta} \qquad B_x = \mathrm{var}(t_x\theta_0) \setminus \mathrm{mvar}(\Gamma\theta_0). $$

and, since the variables in $B'_x$ are fresh,

$$ (\mathrm{gen}_{\Gamma\theta_0}(t_x\theta_0))\theta^\top = \forall B'_x. t_x\theta_0\tilde{\theta}\theta^\top. $$

Consider an arbitrary instance $(t_i^*//p_i)(x)\tilde{\theta}$ of $\mathrm{gen}_{\Gamma\theta}((t_i^*//p_i)(x))$; we have $\mathrm{dom}(\tilde{\theta}) \subseteq \mathrm{var}((t_i^*//p_i)(x)) \setminus \mathrm{mvar}(\Gamma\theta)$. We must show that there exists an instance of $(\mathrm{gen}_{\Gamma\theta_0}(t_x\theta_0))\theta^\top$ which is a subtype of it. We take the instance $t_x\theta_0\tilde{\theta}\theta^\top\tilde{\theta}$, with $\tilde{\theta} = [\beta_i\theta^\top\tilde{\theta}/\beta'_i | \beta'_i \in B'_x]$. We have $t_x\theta_0\tilde{\theta}\theta^\top\tilde{\theta} = t_x\theta_0\theta^\top\tilde{\theta}$; for each $\alpha'_i \in \mathrm{var}(t_x\theta_0)$,

$$ \alpha'_i\tilde{\theta}\theta^\top\tilde{\theta} = \alpha''_i\theta^\top\tilde{\theta} = \alpha''_i\tilde{\theta} $$

(since all $\alpha''_i$ are fresh), and $\alpha''_i\tilde{\theta} = \alpha'_i\theta^\top\tilde{\theta}$. We have $t_x\theta_0\tilde{\theta}\theta^\top\tilde{\theta} \simeq t_x\theta^\top\tilde{\theta}$ and $t_x\theta^\top\tilde{\theta} \le (t_i^*//p_i)(x)\tilde{\theta}$ since $t_x\theta^\top \le (t_i^*//p_i)(x)$.

As for the condition on variables, we have $\mathrm{mvar}((\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \mathrm{var}((\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top)$. Since $\mathrm{var}(\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)) \subseteq \mathrm{mvar}(\Gamma\theta_0)$, $\mathrm{var}((\mathrm{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \mathrm{mvar}(\Gamma\theta_0\theta^\top) = \mathrm{mvar}(\Gamma\theta)$. $\square$

## A.5 Extensions

We give full definitions for the three variants of the $\mathcal{S}$ system that we have sketched in Section 6.

### A.5.1 Overloaded functions

To remove the restriction on the use of intersection types for functions, we change the typing rule $\mathrm{Ts-Abstr}$: we allow the derivation of an intersection of arrow types for a $\lambda$-abstraction if each of these types is derivable. The modified rule is the following.

$$ \mathrm{Ts-Abstr} \quad \frac{\forall j \in J. \Gamma, \{x: t'_j\} \vdash e: t_j}{\Gamma \vdash \lambda x. e. \bigwedge_{j \in J} t'_j \to t_j} $$

Furthermore, we change the typing rule for pattern matching so that redundant branches are excluded from typing. This is necessary to use intersections effectively for pattern matching: in practice, to be able to assign to a function defined by pattern matching one arrow type for each branch.

$$ \Gamma \vdash_{\mathfrak{s}} e_0: t_0 \qquad t_0 \le \bigvee_{i \in I} \lceil p_i \rceil \qquad t_i = (t_0 \setminus \bigvee_{j<i} \lceil p_j \rceil) \wedge \lceil p_i \rceil \\ \forall i \in I \quad \begin{cases} t'_i = \emptyset & \text{if } t_i \le \emptyset \\ \Gamma, \mathrm{gen}_{\Gamma}(t_i//p_i) \vdash_{\mathfrak{s}} e_i: t'_i & \text{otherwise} \end{cases} \\ \mathrm{Ts-Match} \qquad \Gamma \vdash_{\mathfrak{s}} \mathrm{match} \ e_0 \ \mathrm{with} \ (p_i \to e_i)_{i \in I}: \bigvee_{i \in I} t'_i $$

Finally, we also change the rule $\mathrm{Ts-Var}$ for variables: we allow a variable to be typed with any intersection of instantiations, rather than just with a single instantiation.

$$ \mathrm{Ts-Var} \quad \frac{\forall i \in I. t_i \in \mathrm{inst}(\Gamma(x))}{\Gamma \vdash_{\mathfrak{s}} x: \bigwedge_{i \in I} t_i} $$

This allows us to instantiate type schemes which express parametric polymorphism (for instance, $\forall \alpha. \alpha \to \alpha$) into types which express ad hoc polymorphism (e.g., $(\mathit{bool} \to \mathit{bool}) \wedge (\mathit{int} \to \mathit{int}))$.
Case $e = \text{'tag}(e_1)$ We have

$$
\begin{align*}
\text{'tag}(e_1) : t &\Rightarrow_{A_1 \uplus \{\alpha\}} C_1 \cup \{\text{'tag}(\alpha) \dot{\le} t\} & e_1 : \alpha &\Rightarrow_{A_1} C_1 & A_1, \alpha \not\le t \\
\Gamma \theta \vdash_{\S} \text{'tag}(e) : t \theta &\quad \Gamma \theta \vdash_{\S} e_1 : t_1 & \text{'tag}(t_1) &\le t \theta .
\end{align*}
$$

Analogous to the two previous cases. Here we define $\theta^* = \theta \cup [t_1/\alpha]$.

Case $e = \text{match } e_0$ with $(p_i \to e_i)_{i \in I}$ We have

$$
\begin{align*}
\text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I} : t &\Rightarrow_A \{\text{let } [C'_0](\Gamma_i \text{ in } C'_i), \beta \dot{\le} t\} \\
& e_0 : \alpha \Rightarrow_{A_0} C_0 \qquad t_i = (\alpha \setminus \bigcup_{j<i} \{p_j\}) \wedge \{p_i\} \\
& \forall i \in I \qquad t_i \text{///} p_i \Rightarrow_{A_i} (\Gamma_i, C_i) \qquad e_i : \beta \Rightarrow_{A'_i} C'_i \\
& C'_0 = C_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \dot{\le} \bigcup_{i \in I} \{p_i\}\} \\
& A = A_0 \uplus (\biguplus_{i \in I} A_i) \uplus (\biguplus_{i \in I} A'_i) \uplus \{\alpha, \beta\} \\
\Gamma \theta \vdash_{\S} \text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I} : t \theta \\
& \Gamma \theta \vdash_{\S} e_0 : t_0 \qquad t_0 \le \bigcup_{i \in I} \{p_i\} \qquad t_i^* = (t_0 \setminus \bigcup_{j<i} \{p_j\}) \wedge \{p_i\} \\
& \forall i \in I \qquad \Gamma \theta, \text{gen}_{\Gamma \theta}(t_i^* \text{//} p_i) \vdash_{\S} e_i : t_i' \qquad t' = \bigcup_{i \in I} t_i' \le t \theta .
\end{align*}
$$

Let $\theta^* = \theta \cup [t_0/\alpha]$. Then we have

$$
e_0 : \alpha \Rightarrow_{A_0} C_0 \qquad \Gamma \theta^* \vdash_{\S} e_0 : \alpha \theta^* \qquad A_0 \not\vdash \Gamma, \text{dom}(\theta^*)
$$

and, by the induction hypothesis, we find $D_0$, $A'_0$ (containing fresh variables), and $\theta'_0$ such that

$$
\Gamma \vdash C_0 \rightsquigarrow_{A'_0} D_0 \qquad \theta^* \cup \theta'_0 \Vdash D_0 \qquad \mathrm{dom}(\theta'_0) = A_0 \cup A'_0.
$$

From $\Gamma \vdash C_0 \rightsquigarrow_{A'_0} D_0$ we can derive

$$
\Gamma \vdash C'_0 \rightsquigarrow_{A'_0} D'_0 = D_0 \cup (\bigcup_{i \in I} C_i) \cup \{\alpha \dot{\le} \bigcup_{i \in I} \{p_i\}\}
$$

because subtyping constraints are always rewritten to themselves.

For each branch $i$, note that $t_i \theta^* = t_i^*$. By Lemma A.38, we can find $\theta_i^*$ such that

$$
\mathrm{dom}(\theta_i^*) = A_i \qquad \theta^* \cup \theta_i^* \Vdash C_i \qquad \forall x \in \mathrm{capt}(p_i). \quad \Gamma(x)(\theta^* \cup \theta_i^*) \le (t_i^* \parallel p_i)(x).
$$

Note also that $\theta^* \Vdash \alpha \dot{\le} \bigcup_{i \in I} \{p_i\}$. We therefore have $\theta^* \cup \theta'_0 \cup (\bigcup_{i \in I} \theta_i^*) \Vdash D'_0$. Let $\theta^{**} = \theta^* \cup \theta'_0 \cup (\bigcup_{i \in I} \theta_i^*)$.

By the properties of tallying, if $\text{var}(D'_0) = \{\alpha_1, \dots, \alpha_n\}$ and given a set $B = \{\alpha'_1, \dots, \alpha'_n\}$ of fresh variables, there exist two substitutions $\theta_0 \in \text{tally}(D'_0)$ and $\theta_0''$ such that

$$
\begin{align*}
\mathrm{dom}(\theta_0) &= \mathrm{var}(D'_0) & \mathrm{var}(\theta_0) &= B & \mathrm{dom}(\theta_0'') &= B \\
\forall \gamma \notin \mathrm{var}(\theta_0). & \gamma\theta_0(\theta^{**} \cup \theta_0'') & \approx & \gamma\theta^{**}.
\end{align*}
$$

Let $\theta^\top = \theta^{**} \cup [t'/\beta] \cup \theta_0''$. To apply the induction hypothesis for a branch $i$, we need

$$
e_i : \beta \Rightarrow_{A'_i} C'_i \quad (\Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i \theta_0)) \theta^\top \vdash_{\S} e_i : \beta \theta^\top \quad A'_i \not\vdash \Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i \theta_0), \operatorname{dom}(\theta^\top).
$$

We derive the typing judgment above by subsumption and by weakening (we prove the premises below). As for the freshness condition, note that the variables in $\Gamma\theta_0$ are all either in $\Gamma$ or in $\text{var}(\theta_0)$; in the latter case, they are fresh by our choice of $B$.

By applying the induction hypothesis to each branch $i$, we therefore find $D_i$, $A_i''$ (of fresh variables), and $\theta_i''$ such that

$$
\Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i \theta_0) \vdash C'_i \rightsquigarrow_{A_i''} D_i \qquad \theta^\top \cup \theta_i' \Vdash D_i \qquad \operatorname{dom}(\theta_i') = A_i' \cup A_i''.
$$

Hence, we have

$$
\Gamma \theta \vdash \{ \text{let } [C'_0](\Gamma_i \text{ in } C'_i), \beta \dot{\le} t \} \rightsquigarrow_{A'} \text{equiv}(\theta_0) \cup (\bigcup_{i \in I} D_i) \cup \{ \beta \dot{\le} t \},
$$

where $A' = A'_0 \cup (\bigcup_{i \in I} A_i'') \cup \text{var}(\theta_0)$.

We take $\theta' = [t_0/\alpha, t'/\beta] \cup \theta'_0 \cup (\bigcup_{i \in I} \theta_i^*) \cup \theta_0'' \cup (\bigcup_{i \in I} \theta_i')$. It has the correct domain; we must only show

$$
\theta \cup \theta' \Vdash \text{equiv}(\theta_0) \cup (\bigcup_{i \in I} D_i) \cup \{\beta \dot{\le} t\}.
$$

The last constraint is satisfied since $\beta(\theta \cup \theta') = t' \le t\theta$. Constraints in $\text{equiv}(\theta_0)$ are of the form $\alpha \le \alpha\theta_0$ or $\alpha\theta_0 \le \alpha$, for $\alpha \in \text{dom}(\theta_0)$. Since these $\alpha$ are not in $\text{var}(\theta_0)$, we have $\alpha\theta_0(\theta^{**} \cup \theta_0'') \simeq \alpha\theta^{**}$ and hence $\alpha\theta_0(\theta \cup \theta') \simeq \alpha(\theta \cup \theta')$. For each $i$, since $\theta^\top \cup \theta_i^' \Vdash D_i$, we have also $\theta \cup \theta' \Vdash D_i$ (the other substitutions we add are not defined on the variables in $D_i$).

*Proof of* $(\Gamma, \text{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top \vdash_{\S} e_i : \beta\theta^\top$ from $\Gamma\theta, \text{gen}_{\Gamma\theta}(t_i^*//p_i) \vdash_{\S} e_i : t_i'$. From $\Gamma\theta, \text{gen}_{\Gamma\theta}(t_i^*//p_i) \vdash_{\S} e_i : t_i'$, we derive $\Gamma\theta, \text{gen}_{\Gamma\theta}(t_i^*//p_i) \vdash_{\S} e_i : \beta\theta^\top$ by subsumption, since $t_i' \le t' = \beta\theta^\top$. We
### A.5.2 Refining the type of expressions in pattern matching

The extension we present here improves the typing of pattern matching by introducing more precise types for some variables in the matched expression when typing the branches. These refined types take into account which patterns have been selected and which have not; they are introduced for variables that appear in the matched expression, possibly below pairs or variant constructors, but not inside applications or match constructs.

We reuse pattern environment generation to describe the derivation of these refined types. However, we need to introduce a new production for patterns to use when translating expressions to patterns:

$$p ::= \dots | \langle p, p \rangle.$$

Patterns of the form $\langle p, p \rangle$ should not occur in programs; they are only for internal use in the type system. Unlike normal pair patterns, these patterns may include repeated variables.

We need not define the dynamic semantics of these patterns, as it won't be used. We define their accepted type as $\lceil \langle p_1, p_2 \rangle \rceil = \lceil p_1 \rceil \times \lceil p_2 \rceil$ and environment generation as

$$t // \langle p_1, p_2 \rangle = \pi_1(t) // p_1 \mathrel{\&} \pi_2(t) // p_2,$$

where $\mathrel{\&}$, defined as

$$(\Gamma \mathrel{\&} \Gamma')(x) = \begin{cases} \Gamma(x) & \text{if } x \in \text{dom}(\Gamma) \setminus \text{dom}(\Gamma') \\ \Gamma'(x) & \text{if } x \in \text{dom}(\Gamma') \setminus \text{dom}(\Gamma) \\ \Gamma(x) \wedge \Gamma'(x) & \text{if } x \in \text{dom}(\Gamma) \cap \text{dom}(\Gamma') \end{cases}$$

is the pointwise intersection of type environments.

We define a translation $\langle \cdot \rangle$ of expressions to patterns. It preserves variables and variants, converts pairs to the new form, and turns everything else into a wildcard.

$$\langle e \rangle = \begin{cases} x & \text{if } e = x \\ \langle \langle e_1 \rangle, \langle e_2 \rangle \rangle & \text{if } e = (e_1, e_2) \\ \text{'tag}(\langle e_1 \rangle) & \text{if } e = \text{'tag}(e_1) \\ \_ & \text{otherwise} \end{cases}$$

We change the typing rule for pattern matching as follows.

$$\underset{\text{Ts-Match}}{\Gamma \vdash_{\mathfrak{s}} e_0 : t_0} \qquad \begin{array}{l} t_0 \le \bigvee_{i \in I} \langle p_i \rangle \wedge \langle \langle e_0 \rangle \rangle \qquad t_i = (t_0 \wedge \bigvee_{j<i} \langle p_j \rangle) \wedge \langle p_i \rangle \\ \forall i \in I \qquad \Gamma, \text{gen}_{\Gamma}(t_i // \langle e_0 \rangle), \text{gen}_{\Gamma}(t_i // p_i) \vdash_{\mathfrak{s}} e_i : t'_i \end{array}$$

The main difference is the addition of the type environment $\text{gen}_{\Gamma}(t_i // \langle e_0 \rangle)$ which provides the refined types for the variables in $\langle e_0 \rangle$. This environment is added before the usual one for the pattern $p_i$: hence, the capture variables of $p_i$ still take precedence.

We also add the requirement $t_0 \le \lceil \langle e_0 \rangle \rceil$ to ensure $t_i // \langle e_0 \rangle$ is well defined. This is not restrictive because any well-typed $e$ can be typed with a subtype of $\lceil \langle e \rangle \rceil$.

### A.5.3 Applicability to OCaml

We change the semantics of pattern matching to include undefined results. These occur when matching constants of different basic types or when matching different constructors (for instance, a constant and a pair). We use the following definition.

**Definition A.47 (Semantics of pattern matching).** We write $v/p$ for the result of matching a value $v$ against a pattern $p$. We have either $v/p = \zeta$, where $\zeta$ is a substitution defined on the variables in $capt(p)$, $v/p = \Omega$, or $v/p = \mathfrak{U}$. In the first case, we say that $v$ matches $p$ (or that $p$ accepts $v$); in the second, we say that matching fails; in the third, we say that it is undefined.

The definition of $v/p$ is given inductively in Figure 16.

Recall that the function $b_c(\cdot)$ (used here for $v/c$) assigns a basic type $b_c$ to each constant $c$.

The notions of reduction are unchanged, but the rule R-Match is made more restrictive by the changed definition of $v/p$: a match expression reduces only if matching succeeds for a branch and fails—but is never undefined—for all previous branches. The type system should therefore ensure that, in a well-typed expression match $v$ with $(p_i \to e_i)_{i \in I}$, $v/p_i = \mathfrak{U}$ never happens. While this is true for $\mathfrak{K}$, $\mathfrak{S}$ has to be restricted to ensure this.

We first define the compatible type $\lceil p \rceil$ of a pattern $p$ inductively as follows:

$$\lceil \underline{x} \rceil = \lceil x \rceil = \mathfrak{1} \qquad \lceil c \rceil = b_c$$

$$\lceil (p_1, p_2) \rceil = \lceil p_1 \rceil \times \lceil p_2 \rceil$$

$$\lceil \text{'tag}(p) \rceil = \text{'tag}(\lceil p \rceil) \lor (\mathfrak{1}_{\mathfrak{V}} \land \text{'tag}(\mathfrak{1}))$$

$$\lceil p_1 \& p_2 \rceil = \lceil p_1 \rceil \wedge \lceil p_2 \rceil$$

$$\lceil p_1 | p_2 \rceil = \lceil p_1 \rceil \lor \lceil p_2 \rceil,$$
then apply Lemma A.22, which requires us to show the two premises

$$ (\Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top \subseteq \Gamma\theta, \operatorname{gen}_{\Gamma\theta}(t_i^*//p_i) \\ \operatorname{mvar}((\Gamma, \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \operatorname{mvar}(\Gamma\theta, \operatorname{gen}_{\Gamma\theta}(t_i^*//p_i)). $$

Note that $\Gamma\theta = \Gamma\theta^\top$ since the two substitutions only differ on variables introduced by constraint generation or tallying. Simplifying, we need to show

$$ \operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)\theta^\top \subseteq \operatorname{gen}_{\Gamma\theta}(t_i^*//p_i) \qquad \operatorname{mvar}((\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \operatorname{mvar}(\Gamma\theta). $$

To prove the former, consider $x \in \operatorname{capt}(p_i)$ and let $\Gamma_i(x) = t_x$. We must show $\operatorname{gen}_{\Gamma\theta_0}(t_x\theta_0)\theta^\top \subseteq \operatorname{gen}_{\Gamma\theta}((t_i^*//p_i)(x))$. We have

$$ \operatorname{gen}_{\Gamma\theta_0}(t_x\theta_0) = \forall B_x. t_x\theta_0 \qquad B_x = \operatorname{var}(t_x\theta_0) \setminus \operatorname{mvar}(\Gamma\theta_0). $$

Note that all variables in $\operatorname{var}(t_x\theta_0)$ are in $\operatorname{var}(\theta_0)$: this is because all variables in $\operatorname{var}(t_x)$ occur in $D'_0$ ($\alpha$ occurs in the exhaustiveness constraint, variables introduced by pattern environment generation occur in $C_i$) and hence are in the domain of $\theta_0$. Then, $B_x \subseteq B$: its elements are some of the $\alpha'_i$ in $B$. Consider a set $B'_x = \{\alpha''_i | \alpha'_i \in B_x\}$ of fresh variables and the renaming $\tilde{\theta} = [\alpha''_i/\alpha'_i | \alpha'_i \in B_x]$; we have

$$ \operatorname{gen}_{\Gamma\theta_0}(t_x\theta_0) = \forall B'_x. t_x\theta_0\tilde{\theta} \qquad B_x = \operatorname{var}(t_x\theta_0) \setminus \operatorname{mvar}(\Gamma\theta_0). $$

and, since the variables in $B'_x$ are fresh,

$$ (\operatorname{gen}_{\Gamma\theta_0}(t_x\theta_0))\theta^\top = \forall B'_x. t_x\theta_0\tilde{\theta}\theta^\top. $$

Consider an arbitrary instance $(t_i^*//p_i)(x)\tilde{\theta}$ of $\operatorname{gen}_{\Gamma\theta}((t_i^*//p_i)(x))$; we have $\operatorname{dom}(\tilde{\theta}) \subseteq \operatorname{var}((t_i^*//p_i)(x)) \setminus \operatorname{mvar}(\Gamma\theta)$. We must show that there exists an instance of $(\operatorname{gen}_{\Gamma\theta_0}(t_x\theta_0))\theta^\top$ which is a subtype of it. We take the instance $t_x\theta_0\tilde{\theta}\theta^\top\tilde{\theta}$, with $\tilde{\theta} = [\beta_i\theta^\top\tilde{\theta}/\beta'_i | \beta'_i \in B'_x]$. We have $t_x\theta_0\tilde{\theta}\theta^\top\tilde{\theta} = t_x\theta_0\theta^\top\tilde{\theta}$: for each $\alpha'_i \in \operatorname{var}(t_x\theta_0)$,

$$ \alpha'_i\tilde{\theta}\theta^\top\tilde{\theta} = \alpha''_i\theta^\top\tilde{\theta} = \alpha''_i\tilde{\theta} $$

(since all $\alpha''_i$ are fresh), and $\alpha''_i\tilde{\theta} = \alpha'_i\theta^\top\tilde{\theta}$. We have $t_x\theta_0\tilde{\theta}\theta^\top\tilde{\theta} \simeq t_x\theta^\top\tilde{\theta}$ and $t_x\theta^\top\tilde{\theta} \le (t_i^*//p_i)(x)\tilde{\theta}$ since $t_x\theta^\top \le (t_i^*//p_i)(x)$.

As for the condition on variables, we have $\operatorname{mvar}((\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \operatorname{var}((\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top)$. Since $\operatorname{var}(\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0)) \subseteq \operatorname{mvar}(\Gamma\theta_0)$, $\operatorname{var}((\operatorname{gen}_{\Gamma\theta_0}(\Gamma_i\theta_0))\theta^\top) \subseteq \operatorname{mvar}(\Gamma\theta_0\theta^\top) = \square$

## A.5 Extensions

We give full definitions for the three variants of the $\mathbb{S}$ system that we have sketched in Section 6.

### A.5.1 Overloaded functions

To remove the restriction on the use of intersection types for functions, we change the typing rule $\mathit{Ts-Abstr}$: we allow the derivation of an intersection of arrow types for a $\lambda$-abstraction if each of these types is derivable. The modified rule is the following.

$$ \mathit{Ts-Abstr} \quad \frac{\forall j \in J. \Gamma, \{x: t'_j\} \vdash e: t_j}{\Gamma \vdash \lambda x. e. \bigwedge_{j \in J} t'_j \to t_j} $$

Furthermore, we change the typing rule for pattern matching so that redundant branches are excluded from typing. This is necessary to use intersections effectively for pattern matching: in practice, to be able to assign to a function defined by pattern matching one arrow type for each branch.

$$ \Gamma \vdash_{\mathfrak{s}} e_0: t_0 \qquad t_0 \le \bigvee_{i \in I} \langle p_i \rangle \qquad t_i = (t_0 \setminus \bigvee_{j<i} \langle p_j \rangle) \wedge \langle p_i \rangle \\ \forall i \in I \quad \begin{cases} t'_i = \emptyset & \text{if } t_i \le \emptyset \\ \Gamma, \operatorname{gen}_{\Gamma}(t_i//p_i) \vdash_{\mathfrak{s}} e_i: t'_i & \text{otherwise} \end{cases} \\ \mathit{Ts-Match} \quad \Gamma \vdash_{\mathfrak{s}} \mathit{match} \ e_0 \text{ with } (p_i \to e_i)_{i \in I}: \bigvee_{i \in I} t'_i $$

Finally, we also change the rule $\mathit{Ts-Var}$ for variables: we allow a variable to be typed with any intersection of instantiations, rather than just with a single instantiation.

$$ \mathit{Ts-Var} \quad \frac{\forall i \in I. t_i \in \operatorname{inst}(\Gamma(x))}{\Gamma \vdash_{\mathfrak{s}} x: \bigwedge_{i \in I} t_i} $$

This allows us to instantiate type schemes which express parametric polymorphism (for instance, $\forall \alpha. \alpha \to \alpha$) into types which express ad hoc polymorphism (e.g., $(\mathit{bool} \to \mathit{bool}) \wedge (\mathit{int} \to \mathit{int}))$.
$v/\_ = []$

$v/x = [v/x]$

$$v/c = \begin{cases} [] & \text{if } v = c \\ \Omega & \text{if } v \in C, b_v = b_c, \text{ and } v \neq c \\ \cup & \text{otherwise} \end{cases}$$

$$v/(p_1, p_2) = \begin{cases} \varsigma_1 \cup \varsigma_2 & \text{if } v = (v_1, v_2) \text{ and } \forall i. v_i/p_i = \varsigma_i \\ \Omega & \text{if } v = (v_1, v_2), \exists i. v_i/p_i = \Omega, \text{ and } \forall i. v_i/p_i \neq \cup \\ \cup & \text{otherwise} \end{cases}$$

$$v/\text{'tag}(p_1) = \begin{cases} \varsigma_1 & \text{if } v = \text{'tag}(v_1) \text{ and } v_1/p_1 = \varsigma_1 \\ \Omega & \text{if } v = \text{'tag}(v_1) \text{ and } v_1/p_1 = \Omega \text{ or if } v = \text{'tag}_1(v_1) \text{ and } \text{'tag}_1 \neq \text{'tag} \\ \cup & \text{otherwise} \end{cases}$$

$$v/p_1 \& p_2 = \begin{cases} \varsigma_1 \cup \varsigma_2 & \text{if } \forall i. v/p_i = \varsigma_i \\ \Omega & \text{if } \exists i. v/p_i = \Omega \text{ and } \forall i. v/p_i \neq \cup \\ \cup & \text{otherwise} \end{cases}$$

$$v/p_1|p_2 = \begin{cases} v/p_1 & \text{if } v/p_1 \neq \Omega \\ v/p_2 & \text{otherwise} \end{cases}$$

<caption>**Figure 16.** Semantics of pattern matching including undefined results.</caption>

where $\mathbb{1}_v$ is the top type for variants, defined in Section 4.3, Footnote 5. For all well-typed values $v$, $\Gamma \vdash_S v: [p]$ holds if and only if $v/p \neq \cup$.

We change the rule for pattern matching by requiring the type $t_0$ we assign to the matched expression to be a subtype of all compatible types $[p_i]$.

$$\begin{array}{l} \Gamma \vdash_S e_0 : t_0 \qquad t_0 \le \bigvee_{i \in I} \langle p_i \rangle \wedge \bigwedge_{i \in I} [p_i] \qquad t_i = (t_0 \setminus \bigvee_{j<i} \langle p_j \rangle) \wedge \langle p_i \rangle \\ \text{Ts-Match} \qquad \forall i \in I \qquad \Gamma, \text{gen}_\Gamma(t_i // p_i) \vdash_S e_i : t'_i \\ \hline \Gamma \vdash_S \text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I}: \bigvee_{i \in I} t'_i \end{array}$$

Note that this condition is somewhat more restrictive than necessary: patterns which follow a catch-all (wildcard or variable) pattern—or in general that are useless because previous patterns already cover all cases—can be left out of the intersection. The precise condition would be

$$t_0 \le \bigvee_{i \in I} (\langle p_i \rangle \wedge \bigwedge_{j<i} [p_j]) ,$$

but we choose the simpler condition since they only differ in case there is redundancy.
### A.5.2 Refining the type of expressions in pattern matching

The extension we present here improves the typing of pattern matching by introducing more precise types for some variables in the matched expression when typing the branches. These refined types take into account which patterns have been selected and which have not; they are introduced for variables that appear in the matched expression, possibly below pairs or variant constructors, but not inside applications or match constructs.

We reuse pattern environment generation to describe the derivation of these refined types. However, we need to introduce a new production for patterns to use when translating expressions to patterns:

$$p ::= \dots | \langle p, p \rangle.$$

Patterns of the form $\langle p, p \rangle$ should not occur in programs; they are only for internal use in the type system. Unlike normal pair patterns, these patterns may include repeated variables.

We need not define the dynamic semantics of these patterns, as it won't be used. We define their accepted type as $\lceil \langle p_1, p_2 \rangle \rceil = \lceil p_1 \rceil \times \lceil p_2 \rceil$ and environment generation as

$$t // \langle p_1, p_2 \rangle = \pi_1(t) // p_1 \bowtie \pi_2(t) // p_2,$$

where $\bowtie$, defined as

$$(\Gamma \bowtie \Gamma')(x) = \begin{cases} \Gamma(x) & \text{if } x \in \text{dom}(\Gamma) \setminus \text{dom}(\Gamma') \\ \Gamma'(x) & \text{if } x \in \text{dom}(\Gamma') \setminus \text{dom}(\Gamma) \\ \Gamma(x) \wedge \Gamma'(x) & \text{if } x \in \text{dom}(\Gamma) \cap \text{dom}(\Gamma') \end{cases}$$

is the pointwise intersection of type environments.

We define a translation $\langle \cdot \rangle$ of expressions to patterns. It preserves variables and variants, converts pairs to the new form, and turns everything else into a wildcard.

$$\langle e \rangle = \begin{cases} x & \text{if } e = x \\ \langle \langle e_1 \rangle, \langle e_2 \rangle \rangle & \text{if } e = (e_1, e_2) \\ \text{'tag}(\langle e_1 \rangle) & \text{if } e = \text{'tag}(e_1) \\ \_ & \text{otherwise} \end{cases}$$

We change the typing rule for pattern matching as follows.

$$\underset{\text{Ts-Match}}{\Gamma \vdash_S e_0 : t_0} \qquad \begin{array}{l} t_0 \le \bigvee_{i \in I} \lceil p_i \rceil \wedge \lceil \langle e_0 \rangle \rceil \qquad t_i = (t_0 \wedge \bigvee_{j<i} \lceil p_j \rceil) \wedge \lceil p_i \rceil \\ \forall i \in I \quad \Gamma, \text{gen}_\Gamma(t_i // \langle e_0 \rangle), \text{gen}_\Gamma(t_i // p_i) \vdash_S e_i : t'_i \\ \hline \Gamma \vdash_S \text{ match } e_0 \text{ with } (p_i \to e_i)_{i \in I} : \bigvee_{i \in I} t'_i \end{array}$$

The main difference is the addition of the type environment $\text{gen}_\Gamma(t_i//\langle e_0 \rangle)$ which provides the refined types for the variables in $\langle e_0 \rangle$. This environment is added before the usual one for the pattern $p_i$: hence, the capture variables of $p_i$ still take precedence.

We also add the requirement $t_0 \le \lceil \langle e_0 \rangle \rceil$ to ensure $t_i // \langle e_0 \rangle$ is well defined. This is not restrictive because any well-typed $e$ can be typed with a subtype of $\lceil \langle e \rangle \rceil$.

### A.5.3 Applicability to OCaml

We change the semantics of pattern matching to include undefined results. These occur when matching constants of different basic types or when matching different constructors (for instance, a constant and a pair). We use the following definition.

**Definition A.47 (Semantics of pattern matching).** We write $v/p$ for the result of matching a value $v$ against a pattern $p$. We have either $v/p = \zeta$, where $\zeta$ is a substitution defined on the variables in $capt(p)$, $v/p = \Omega$, or $v/p = \tilde{\Omega}$. In the first case, we say that $v$ matches $p$ (or that $p$ accepts $v$); in the second, we say that matching fails; in the third, we say that it is undefined.

The definition of $v/p$ is given inductively in Figure 16.

Recall that the function $b_c(\cdot)$ (used here for $v/c$) assigns a basic type $b_c$ to each constant $c$.

The notions of reduction are unchanged, but the rule R-Match is made more restrictive by the changed definition of $v/p$: a match expression reduces only if matching succeeds for a branch and fails—but is never undefined—for all previous branches. The type system should therefore ensure that, in a well-typed expression match $v$ with $(p_i \to e_i)_{i \in I}$, $v/p_i = \tilde{\Omega}$ never happens. While this is true for $\mathbb{K}$, $\mathbb{S}$ has to be restricted to ensure this.

We first define the compatible type $\lceil p \rceil$ of a pattern $p$ inductively as follows:

$$\lceil \cdot \rceil = \lceil x \rceil = \mathbb{1} \qquad \lceil c \rceil = b_c$$

$$\lceil (p_1, p_2) \rceil = \lceil p_1 \rceil \times \lceil p_2 \rceil \qquad \lceil \text{'tag}(p) \rceil = \text{'tag}(\lceil p \rceil) \lor (\mathbb{1}_\vee \land \text{'tag}(\mathbb{1}))$$

$$\lceil p_1 \& p_2 \rceil = \lceil p_1 \rceil \wedge \lceil p_2 \rceil \qquad \lceil p_1 | p_2 \rceil = \lceil p_1 \rceil \vee \lceil p_2 \rceil,$$
$v/- = []$

$v/x = [v/x]$

$v/c = \begin{cases} [] & \text{if } v = c \\ \Omega & \text{if } v \in C, b_v = b_c, \text{ and } v \neq c \\ \Upsilon & \text{otherwise} \end{cases}$

$v/(p_1, p_2) = \begin{cases} \varsigma_1 \cup \varsigma_2 & \text{if } v = (v_1, v_2) \text{ and } \forall i. v_i/p_i = \varsigma_i \\ \Omega & \text{if } v = (v_1, v_2), \exists i. v_i/p_i = \Omega, \text{ and } \forall i. v_i/p_i \neq \Upsilon \\ \Upsilon & \text{otherwise} \end{cases}$

$v/\text{'tag}(p_1) = \begin{cases} \varsigma_1 & \text{if } v = \text{'tag}(v_1) \text{ and } v_1/p_1 = \varsigma_1 \\ \Omega & \text{if } v = \text{'tag}(v_1) \text{ and } v_1/p_1 = \Omega \text{ or if } v = \text{'tag}_1(v_1) \text{ and } \text{'tag}_1 \neq \text{'tag} \\ \Upsilon & \text{otherwise} \end{cases}$

$v/p_1 \& p_2 = \begin{cases} \varsigma_1 \cup \varsigma_2 & \text{if } \forall i. v/p_i = \varsigma_i \\ \Omega & \text{if } \exists i. v/p_i = \Omega \text{ and } \forall i. v/p_i \neq \Upsilon \\ \Upsilon & \text{otherwise} \end{cases}$

$v/p_1|p_2 = \begin{cases} v/p_1 & \text{if } v/p_1 \neq \Omega \\ v/p_2 & \text{otherwise} \end{cases}$

<caption>**Figure 16.** Semantics of pattern matching including undefined results.</caption>

where $\mathbb{1}_v$ is the top type for variants, defined in Section 4.3, Footnote 5. For all well-typed values $v$, $\Gamma \vdash_S v: [p]$ holds if and only if $v/p \neq \Upsilon$.

We change the rule for pattern matching by requiring the type $t_0$ we assign to the matched expression to be a subtype of all compatible types $[p_i]$.

$$ \begin{array}{c} \Gamma \vdash_S e_0 : t_0 \qquad t_0 \le \bigvee_{i \in I} \langle p_i \rangle \wedge \bigwedge_{i \in I} [p_i] \qquad t_i = (t_0 \setminus \bigvee_{j<i} \langle p_j \rangle) \wedge \langle p_i \rangle \\ \text{Ts-Match} \qquad \forall i \in I \qquad \Gamma, \text{gen}_\Gamma(t_i//p_i) \vdash_S e_i : t'_i \\ \hline \Gamma \vdash_S \text{match } e_0 \text{ with } (p_i \to e_i)_{i \in I}: \bigvee_{i \in I} t'_i \end{array} $$

Note that this condition is somewhat more restrictive than necessary: patterns which follow a catch-all (wildcard or variable) pattern—or in general that are useless because previous patterns already cover all cases—can be left out of the intersection. The precise condition would be

$$ t_0 \le \bigvee_{i \in I} (\langle p_i \rangle \wedge \bigwedge_{j<i} [p_j]) , $$

but we choose the simpler condition since they only differ in case there is redundancy.