1
$\begingroup$

To evaluate some typed lambda calculus applications, the type of the function might have to be "lifted" in order to match the type of the value it is applied to. For example, in the exponential operator for Church numerals $$\lambda n . \lambda m . m\ n,$$ the $m$ cannot be directly applied to $n$, because $m$ expects a first argument of type

$$a \rightarrow a$$

and $n$ has type

$$(a \rightarrow a) \rightarrow a \rightarrow a.$$

But since the type variable $a$ in $m$ can be any type, it can also be $t = a \rightarrow a$. Then the type of $m$ becomes

$$((a \rightarrow a) \rightarrow (a \rightarrow a)) \rightarrow (a \rightarrow a) \rightarrow (a \rightarrow a).$$

Now, the first argument of $m$ has the right type, so $m$ can be applied to $n$.

In simply typed lambda calculus, we are not allowed to do the type substitution

$$a = a \rightarrow a,$$

but I believe we might be able to interpret it in another manner.

If we view simply typed lambda calculus with one type variable as a category with signatures as objects and terms as arrows, this lifting seems to be a bi-endofunctor $\operatorname L$, from $t$ and $m$, of mixed variance in $t$ and covariant and Cartesian closed in $m$ (is that correct?). My question is: does this bifunctor fulfill some universal property in that category?

$\endgroup$
1
  • $\begingroup$ What do you mean by "the type of the function might have to be "lifted" in order to match the type of the value it is applied to"? The Church numeral representation is an encoding for the untyped lambda calculus, so there are no types. Do you actually mean to refer to the polymorphic lambda calculus? $\endgroup$
    – varkor
    Commented Aug 18, 2023 at 9:39

0

You must log in to answer this question.