1

Let $K = \lambda zy.z$ (kestrel), $M = \lambda f.ff$ (mockingbird), $I = \lambda x.x$ (identity).

Now I believe $M$, I should be subsumed inside $K$'s function body but my lecture notes say that $K M I = M$. Can anyone explain how?

Another example that confused me from my slides:

$K \space I = \lambda ab .a \space \lambda x.x = \lambda ab.(a \lambda x.x) \text{ or } (\lambda ab.a)(\lambda x.x) $?? What's the right way to interpret and why?

Taroccoesbrocco
  • 16,964
learner
  • 31
  • 4

1 Answers1

1

The $\lambda$-terms $K$, $I$, $M$ are defined as follows: \begin{align} I = \lambda x.x && K = \lambda zy.z && M = \lambda f.ff \end{align}

This means that the $\lambda$-term $KI$ is the whole $\lambda$-term $K = (\lambda zy.z)$ applied to $I$, that is, \begin{align} KI &= (\lambda zy.z)I \\ &\to_\beta \lambda y.I \\ &= \lambda yx.x \end{align}

When there is an application of three terms $RST$ (without any parentheses), by convention this means $(RS)T$, that is, first apply $R$ to $S$, and then the resulting $\lambda$-term is applied to $T$. In particular:

\begin{align} KMI &= ((\lambda zy.z)M)I \\ &\to_\beta (\lambda y.M)I \\ &\to_\beta M \end{align}

Note that in the previous reduction, we never used the definition of $M$ or $I$. So, in general, for every $\lambda$-terms $S$ and $T$, we have $KST \to_\beta^* S$.

Taroccoesbrocco
  • 16,964