Intersection Types as Denotations

In my previous post I described a simple denotational semantics for the CBV lambda calculus in which the meaning of a $\lambda$ function is a set of tables. For example, here is a glimpse at some of the tables in the meaning of $\lambda x. x+2$.

$$E[\!| (\lambda x. x+2) |\!](\emptyset) = \left\{ \begin{array}{l} \emptyset, \\ \{ 5\mapsto 7 \},\\ \{ 0\mapsto 2, 1 \mapsto 3 \},\\ \{ 0\mapsto 2, 1\mapsto 3, 5 \mapsto 7 \}, \\ \vdots \end{array} \right\}$$

Since then I've been reading the literature starting from an observation by Alan Jeffrey that this semantics seems similar to the domain logic in Abramsky's Ph.D. thesis (1987). That in turn pointed me to the early literature on intersection types, which were invented in the late 1970's by Coppo, Dezani-Ciancaglini, Salle, and Pottinger. It turns out that one of the motivations for intersection types was to create a denotational semantics for the lambda calculus. Furthermore, it seems that intersection types are closely related to my simple denotational semantics!

The intersection types for the pure lambda calculus included function types, intersections, and a top type:

$$A,B,C ::= A \to B \mid A \wedge B \mid \top$$ For our purposes we shall also add singleton types for numbers. $$A,B,C ::= A \to B \mid A \wedge B \mid \top \mid n$$ So the number $2$ has the singleton type $2$ and any function that maps $0$ to $2$ will have the type $0 \to 2$. Any function that maps $0$ to $2$ and also maps $1$ to $3$ has the intersection type $$(0 \to 2) \wedge (1 \to 3)$$ These types are starting to look a lot like the tables above! Indeed, even the empty table $\emptyset$ corresponds to the top type $\top$, they both can be associated with any $\lambda$ function.

The addition of the singleton number types introduces a choice regarding the top type $\top$. Does it include the numbers and functions or just functions? We shall go with the later, which corresponds to the $\nu$ type in the literature (Egidi, Honsell, Rocca 1992).

Now that we have glimpsed the correspondence between tables and intersection types, let's review the typing rules for the implicitly typed lambda calculus with singletons, intersections, and $\top$.

$$\begin{gather*} \frac{}{\Gamma \vdash n : n} \\[2ex] \frac{}{\Gamma \vdash \lambda x.\,e : \top}(\top\,\mathrm{intro}) \quad \frac{\Gamma \vdash e : A \quad \Gamma \vdash e : B} {\Gamma \vdash e : A \wedge B}(\wedge\,\mathrm{intro}) \\[2ex] \frac{\Gamma \vdash e : A \quad A <: B} {\Gamma \vdash e : B}(\mathrm{Sub}) \quad \frac{x:A \in \Gamma}{\Gamma \vdash x : A} \\[2ex] \frac{\Gamma,x:A \vdash e : B} {\Gamma \vdash \lambda x.\, e : A \to B} \quad \frac{\Gamma \vdash e_1: A \to B \quad \Gamma \vdash e_2 : A} {\Gamma \vdash e_1 \; e_2 : B}(\to\mathrm{elim}) \end{gather*}$$ where subtyping is defined as follows $$\begin{gather*} \frac{}{n <: n} \quad \frac{}{\top <: \top} \quad \frac{}{A \to B <: \top} \quad \frac{A' <: A \quad B <: B'} {A \to B <: A' \to B'} \\[2ex] \frac{C <: A \quad C <: B}{C <: A \wedge B} \quad \frac{}{A \wedge B <: A} \quad \frac{}{A \wedge B <: B} \\[2ex] \frac{}{(C\to A) \wedge (C \to B) <: C \to (A \wedge B)} \end{gather*}$$

With intersection types, one can write the same type in many different ways. For example, the type $5$ is the same as $5 \wedge 5$. One common way to define such equalities is in terms of subtyping: $A = B$ iff $A <: B$ and $B <: A$.

So how does one define a semantics using intersection types? Barendregt, Coppo, Dezani-Ciancaglini (1983) (BCD) define the meaning of an expression $e$ to be the set of types for which it is typable, something like

$$[\!| e |\!](\Gamma) = \{ A \mid \Gamma \vdash e : A \}$$ For a simple type system (without intersection), such as semantics would not be useful. Any term with self application (needed for recursion) would not type check and therefore its meaning would be the empty set. But with intersection types, the semantics gives a non-empty meaning to all terminating programs!

The next question is, how does the BCD semantics relate to my simple table-based semantics? One difference is that the intersection type system has two rules that are not syntax directed: $(\wedge\,\mathrm{intro})$ and (Sub). However, we can get rid of these rules. The $(\wedge\,\mathrm{intro})$ rule is not needed for numbers, only for functions. So one should be able to move all uses of the $(\wedge\,\mathrm{intro})$ rules to $\lambda$'s.

$$\frac{\Gamma \vdash \lambda x.\, e : A \quad \Gamma \vdash \lambda x.\; e : B} {\Gamma \vdash \lambda x.\, e : A \wedge B}$$ To get rid of (Sub), we need to modify $(\to\mathrm{elim})$ to allow for the possibility that $e_1$ is not literally of function type. $$\frac{\Gamma \vdash e_1 : C \quad C <: A \to B \quad \Gamma \vdash e_2 : A} {\Gamma \vdash e_1 \; e_2 : B}$$

All of the rules are now syntax directed, though we now have three rules for $\lambda$, but those rules handle the three different possible types for a $\lambda$ function: $A \to B$, $A \wedge B$, and $\top$. Next we observe that a relation is isomorphic to a function that produces a set. So we change from $\Gamma \vdash e : A$ to $E[\!| e |\!](\Gamma) = \mathcal{A}$ where $\mathcal{A}$ ranges over sets of types, i.e., $\mathcal{A} \in \mathcal{P}(A)$. We make use of an auxiliary function $F$ to define the meaning of $\lambda$ functions.

$$\begin{align*} E[\!| n |\!](\Gamma) & = \{ n \} \\ E[\!| x |\!](\Gamma) & = \{ \Gamma(x) \} \\ E[\!| \lambda x.\, e |\!](\Gamma) & = \{ A \mid F(A,x,e,\Gamma) \} \\ E[\!| e_1 \; e_2 |\!](\Gamma) & = \left\{ B \middle| \begin{array}{l} C \in E[\!| e_1 |\!](\Gamma) \\ \land\; A \in E[\!| e_2 |\!](\Gamma) \\ \land\; C <: A \to B \end{array} \right\} \\ \\ F(A \to B, x,e,\Gamma) &= B \in E[\!| e |\!](\Gamma(x:=A)) \\ F(A \wedge B, x,e,\Gamma) &= F(A, x,e,\Gamma) \land F(B, x,e,\Gamma) \\ F(\top, x,e,\Gamma) &= \mathrm{true} \end{align*}$$

I conjecture that this semantics is equivalent to the "take 3" semantics. There are a couple remaining differences and here's why I don't think they matter. Regarding the case for $\lambda$ in $E$, the type $A$ can be viewed as an alternative representation for a table. The function $F$ essentially checks that all entries in the table jive with the meaning of the $\lambda$'s body, which is what the clause for $\lambda$ does in the ``take 3'' semantics. Regarding the case for application in $E$, the $C$ is a table and $C <: A \to B$ means that there is some entry $A' \to B'$ in the table $C$ such that $A' \to B' <: A \to B$, which means $A <: A'$ and $B' <: B$. The $A <: A'$ corresponds to our use of $\sqsubseteq$ in the "take 3" semantics. The $B' <: B$ doesn't matter.

There's an interesting duality and change of viewpoint going on here between the table-based semantics and the intersection types. The table-based semantics is concerned with what values are produced by a program whereas the intersection type system is concerned with specifying what kind of values are allowed, but the types are so precise that it becomes dual in a strong sense to the values themselves. To make this precise, we can talk about tables in terms of their finite graphs (sets of pairs), and create them using $\emptyset$, union, and a singleton input-output pair $\{(v_1,v_2)\}$. With this formulation, tables are literally dual to types, with $\{(v_1,v_2)\}$ corresponding to $v_1 \to v_2$, union corresponding to intersection, empty set corresponding to $\top$, and $T_1 \subseteq T_2$ corresponding to $T_2 <: T_1$.