Take 3: Application with Subsumption for Den. Semantics of Lambda Calculus

Alan Jeffrey tweeted the following in reply to the previous post:

@jeremysiek wouldn't it be easier to change the defn of application to be
⟦MN⟧σ = { W | T ∈ ⟦M⟧σ, V ∈ ⟦N⟧σ, (V′,W) ∈ T, V′ ⊆ V }?

The idea is that, for higher order functions, if the function $M$ is expecting to ask all the questions in the table $V'$, then it is OK to apply $M$ to a table $V$ that answers more questions than $V'$. This idea is quite natural, it is like Liskov's subsumption principle but for functions instead of objects. If this change can help us with the self application problem, then it will be preferable to the graph-o-tables approach described in the previous post because it retains the simple inductive definition of values. So let's see where this takes us!

We have the original definition of values

$$\begin{array}{lrcl} \text{values} & v & ::= & n \mid \{ (v_1,v'_1),\ldots,(v_n,v'_n) \} \end{array}$$

and here is the denotational semantics, updated with Alan's suggestion to include the clause $v'_2 \sqsubseteq v_2$ in the case for application.

$$\begin{align*} E[\!| n |\!](\rho) &= \{ n \} \\ E[\!| x |\!](\rho) &= \{ \rho(x) \} \\ E[\!| \lambda x.\; e |\!](\rho) &= \{ T \mid \forall v v'. (v,v') \in T \Rightarrow v' \in E[\!|e|\!](\rho(x:=v)) \} \\ E[\!| e_1\;e_2 |\!](\rho) &= \left\{ v \middle| \begin{array}{l} \exists T v_2 v'_2. T {\in} E[\!| e_1 |\!](\rho) \land v_2 {\in} E[\!| e_2 |\!](\rho) \\ \land v'_2 \sqsubseteq v_2 \land (v'_2,v) {\in} T \end{array} \right\} \end{align*}$$

The ordering on values $\sqsubseteq$ used above is just equality on numbers and subset on function tables.

The first thing to check is whether this semantics can handle self application at all, such as

$$(\lambda f. f \; f) \; (\lambda g. \; 42)$$

Example 1. $42 \in E[\!| (\lambda f. f \; f) \; (\lambda g. \; 42) |\!](\emptyset)$
The main work is figuring out witnesses for the function tables. We're going to need the following tables:

$$\begin{align*} T_0 &= \emptyset \\ T_1 &= \{ (\emptyset, 42)\} \\ T_2 &= \{ (T_1, 42) \} \end{align*}$$ Here's the proof, working top-down, or goal driven. The important use of subsumption is the $\emptyset \sqsubseteq T_1$ below.

• $T_2 \in E[\!| (\lambda f. f \; f)|\!](\emptyset)$
  So we need to show: $42 \in E[\!| f \; f|\!](f:=T_1)$
  • $T_1 \in E[\!| f |\!](f:=T_1)$
  • $T_1 \in E[\!| f |\!](f:=T_1)$
  • $\emptyset \sqsubseteq T_1$
  • $(\emptyset, 42) \in T_1$
• $T_1 \in E[\!| (\lambda g. \; 42) |\!](\emptyset)$
  So we need to show $42 \in E[\!| 42 |\!](g:=\emptyset)$, which is immediate.
• $T_1 \sqsubseteq T_1$
• $(T_1,42) \in T_2$

Good, so this semantics can handle a simple use of self application. How about factorial? Instead of considering factorial of 3, as in the previous post, we'll go further this time and consider factorial of an arbitrary number $n$.

Example 2. We shall compute the factorial of $n$ using the strict version of the Y combinator, that is, the Z combinator.

$$\begin{align*} M & \equiv \lambda x. f \; (\lambda v. (x\; x) \; v) \\ Z & \equiv \lambda f. M \; M \\ F & \equiv \lambda n. \mathbf{if}\,n=0\,\mathbf{then}\, 1\,\mathbf{else}\, n \times r \,(n-1)\\ H & \equiv \lambda r. F \\ \mathit{fact} & \equiv Z\, H \end{align*}$$ We shall show that $$n! \in E[\!|\mathit{fact}\;n|\!](\emptyset)$$ For this example we need very many tables, but fortunately there are just a few patterns. To capture these patterns, be define the following table-producing functions. $$\begin{align*} T_F(n) &= \{ (n,n!) \} \\ T_H(n) &= \{ (\emptyset,T_F(0)), (T_F(0), T_F(1)), \ldots ,(T_F(n-1), T_F(n)) \} \\ T_M(n) &= \begin{cases} \emptyset & \text{if } n = 0 \\ \{ (T_M(n'), T_F(n')) \} \cup T_M(n') & \text{if } n = 1+n' \end{cases} \\ T_Z(n) &= \{ (T_H(n), T_F(n) )\} \end{align*}$$ $T_F(n)$ is a fragment of the factorial function, for the one input $n$. $T_H(n)$ maps each $T_F(i)$ to $T_F(i+1)$ for up to $i+1 = n$. $T_M(n)$ is the heart of the matter, and what makes the self application work. It maps successively larger versions of itself to fragments of the factorial function, that is $$T_M(n) = \left\{ \begin{array}{l} T_M(0) \mapsto T_F(0) \\ T_M(1) \mapsto T_F(1) \\ \vdots & \\ T_M(n-1) \mapsto T_F(n-1) \end{array} \right\}$$ For example, here is $T_M(4)$:

The tables $T_M$ enable self application because we have the following two crucial properties:

1. $T_M(n) \sqsubseteq T_M(1+n)$
2. $(T_M(n), T_F(n)) \in T_M(1+n)$

The main lemma's that we prove are

Lemma 1. If $n \le k$, then $T_M(1+n) \in E[\!| M |\!](f:=T_H(k))$.

Lemma 2. $T_Z(n) \in E[\!| Z |\!](\emptyset)$

If you're curious about the details for the complete proof of $n! \in E[\!|\mathit{fact}\;n|\!](\emptyset)$ you can take a look at the proof in Isabelle that I've written here.

This is all quite promising! Next we look at the proof of soundness with respect to the big step semantics.

Soundness with Respect to the Big-Step Semantics

The proof of soundness is quite similar to that of the first version, as the relation $\approx$ between the denotational and big-step values remains the same. However, the following two technical lemmas are needed to handle subsumption.

Lemma (Related Table Subsumption) If $T' \subseteq T$ and $T \approx \langle \lambda x.e, \rho \rangle$, then $T' \approx \langle \lambda x.e, \rho \rangle$.
The proof is by induction on $T'$.

Lemma (Related Value Subsumption) If $v_1 \approx v'$ and $v_2 \sqsubseteq v'$, then $v_2 \approx v'$.
The proof is by case analysis, using the previous lemma when the values are function tables.

Theorem (Soundness).
If $v \in E[\!| e |\!](\rho)$ and $\rho \approx \rho'$, then $\rho' \vdash e \Downarrow v'$ and $v \approx v'$ for some $v'$.

The mechanization of soundness in Isabelle is here.