The Take 3 Semantics, Revisited

In my post about intersection types as denotations, I conjectured that the simple "take 3" denotational semantics is equivalent to an intersection type system. I haven't settled that question per se, but I've done something just as good, which is to show that everything that I've done with the intersection type system can also be done with the "take 3" semantics (with a minor modification).

Recall that the main difference between the "take 3" semantics and the intersection type system is how subsumption of functions is handled. The "take 3" semantics defined function application as follows, using the subset operator $\sqsubseteq$ to require the argument $v_2$ to include all the entries in the parameter $v'_2$, while allowing $v_2$ to have possibly more entries. $$\begin{align*} E[\!| e_1\;e_2 |\!](\rho) &= \left\{ v_3 \middle| \begin{array}{l} \exists v_1 v_2 v'_2.\, v_1 {\in} E[\!| e_1 |\!](\rho) \land v_2 {\in} E[\!| e_2 |\!](\rho) \\ \land\, \{ v'_2\mapsto v_3 \} \sqsubseteq v_1 \land v'_2 \sqsubseteq v_2 \end{array} \right\} \end{align*}$$ Values are either numbers or functions. Functions are represented as a finite tables mapping values to values. $$\begin{array}{lrcl} \text{tables} & T & ::= & \{ v_1\mapsto v'_1,\ldots,v_n\mapsto v'_n \} \\ \text{values} & v & ::= & n \mid T \end{array}$$ and $\sqsubseteq$ is defined as equality on numbers and subset for function tables: $$\begin{gather*} \frac{}{n \sqsubseteq n} \qquad \frac{T_1 \subseteq T_2}{T_1 \sqsubseteq T_2} \end{gather*}$$ Recall that $\subseteq$ is defined in terms of equality on elements.

In an intersection type system (without subsumption), function application uses subtyping. Here's one way to formulate the typing rule for application: $$\frac{\Gamma \vdash_2 e_1: C \quad \Gamma \vdash_2 e_2 : A \quad \quad C <: A' \to B \quad A <: A'} {\Gamma \vdash_2 e_1 \; e_2 : B}$$ Types are defined as follows $$\begin{array}{lrcl} \text{types} & A,B,C & ::= & n \mid A \to B \mid A \land B \mid \top \end{array}$$ and the subtyping relation is given below. $$\begin{gather*} \frac{}{n <: n}(a) \quad \frac{}{\top <: \top}(b) \quad \frac{}{A \to B <: \top}(c) \quad \frac{A' <: A \quad B <: B'} {A \to B <: A' \to B'}(d) \\[2ex] \frac{C <: A \quad C <: B}{C <: A \wedge B}(e) \quad \frac{}{A \wedge B <: A}(f) \quad \frac{}{A \wedge B <: B}(g) \\[2ex] \frac{}{(C\to A) \wedge (C \to B) <: C \to (A \wedge B)}(h) \end{gather*}$$ Recall that values and types are isomorphic (and dual) to eachother in this setting. Here's the functions $\mathcal{T}$ and $\mathcal{V}$ that map back and forth between values and types. $$\begin{align*} \mathcal{T}(n) &= n \\ \mathcal{T}( \{ v_1 \mapsto v'_1, \ldots, v_n \mapsto v'_n \} ) &= \mathcal{T}(v_1) {\to} \mathcal{T}(v'_1) \land \cdots \land \mathcal{T}(v_n) {\to} \mathcal{T}(v'_n) \\[2ex] \mathcal{V}(n) &= n \\ \mathcal{V}(A \to B) &= \{ \mathcal{V}(A)\mapsto\mathcal{V}(B) \} \\ \mathcal{V}(A \land B) &= \mathcal{V}(A) \cup \mathcal{V}(B)\\ \mathcal{V}(\top) &= \emptyset \end{align*}$$

Given that values and types are really the same, the the typing rule for application is almost the same as the equation for the denotation of $E[\!| e_1\;e_2 |\!](\rho)$. The only real difference is the use of $<:$ versus $\sqsubseteq$. However, subtyping is a larger relation than $\sqsubseteq$, i.e., $v_1 \sqsubseteq v_2$ implies $\mathcal{T}(v_1) <: \mathcal{T}(v_2)$ but it is not the case that $A <: B$ implies $\mathcal{V}(A) \sqsubseteq \mathcal{V}(B)$. Subtyping is larger because of rules $(d)$ and $(h)$. The other rules just express the dual of $\subseteq$.

So the natural question is whether subtyping needs to be bigger than $\sqsubseteq$, or would we get by with just $\sqsubseteq$? In my last post, I mentioned that rule $(h)$ was not necessary. Indeed, I removed it from the Isabelle formalization without disturbing the proofs of whole-program soundness and completeness wrt. operational semantics, and was able to carry on and prove soundness wrt. contextual equivalence. This morning I also replaced rule $(d)$ with a rule that only allows equal function types to be subtypes. $$\frac{}{A \to B <: A \to B}(d')$$ The proofs went through again! Though I did have to make two minor changes in the type system without subsumption to ensure that it stays equivalent to the version of the type system with subsumption. I used the rule given above for function application instead of $$\frac{\Gamma \vdash_2 e_1: C \quad \Gamma \vdash_2 e_2 : A \quad \quad C <: A \to B} {\Gamma \vdash_2 e_1 \; e_2 : B}$$ Also, I had to change the typing rule for $\lambda$ to use subtyping to relate the body's type to the return type. $$\frac{\Gamma,x:A \vdash e : B' \qquad B' <: B} {\Gamma \vdash \lambda x.\, e : A \to B}$$ Transposing this back into the land of denotational semantics and values, we get the following equation for the meaning of $\lambda$, in which everything in the return specification $v_2$ must be contained in the value $v'_2$ produced by the body. $$E[\!| \lambda x.\; e |\!] (\rho) = \left\{ v \middle| \begin{array}{l}\forall v_1 v_2. \{v_1\mapsto v_2\} \sqsubseteq v \implies \\ \exists v_2'.\; v'_2 \in E[\!| e |\!] (\rho(x{:=}v_1)) \,\land\, v_2 \sqsubseteq v'_2 \end{array} \right\}$$

So with this little change, the "take 3" semantics is a great semantics for the call-by-value untyped lambda calculus! For whole programs, it's sound and complete with respect to the standard operational semantics, and it is also sound with respect to contextual equivalence.