# Simply-typed lambda calculus

Read TAPL 9 and 11.1-5.

The simply-typed lambda calculus (λ→ for short) adds a type system to the untyped lambda calculus.

## Syntax

The initial definition of λ→ (p. 103) only has one syntax rule for types, namely `T ::= T → T`

. In order for there to be any finite types, we need some base types (cf. Exercise 9.2.1).

```
T ::= Nat
Bool
T → T
```

## Type checking

The typing rules are similar in structure to big-step operational semantics, and typing contexts (`Γ`

) are similar to environments. The way that they map onto an algorithm is that the typing contexts are computed top-down on the syntax tree (bottom-up on the proof tree), but the types are computed bottom-up on the syntax tree (top-down on the proof tree). The pseudocode for type checking looks like this:

```
function typecheck(t, Γ)
if t = x
return Γ(x), {}
else if t = λx:T
```_{1}.t_{2}
T_{2} = typecheck(t_{2}, Γ ∪ {x:T_{1}})
return T_{1}→T_{2}
else if t = t_{1} t_{2}
T_{1}_{1}→T_{1}_{2} = typecheck(t_{1}, Γ)
T_{2} = typecheck(t_{2}, Γ)
if T_{1}_{1} ≠ T_{2} then fail
return T_{1}_{2}

Notice how the typing context is passed as an argument and the type is returned.

## Properties

Section 9.3 proves various properties of the simply-typed lambda-calculus leading up to type safety. One important property is strong normalization (every term halts), whose proof is deferred to Chapter 12 (which you are not expected to read).

One consequence of this is that the simply-typed lambda calculus is not Turing complete – there are some programs (even programs that always halt) that can’t be written in it. There are two things missing that keep it from being Turing complete, described below.

### No recursion

No fixed-point combinator can be defined in the simply-typed lambda calculus (because the fixed-point combinator could be used to write a non-halting term, and that would contradict normalization). There are various ways of adding it back in, including:

- adding it as a primitive (p. 142-145)
- mutable state (Exercise 13.5.8)
- recursive types (p. 273)

But even adding the fixed-point combinator still isn’t enough to restore Turing completeness. With a fixed-point combinator, not every term halts, but it remains decidable whether a given term halts [2]. That’s not true for Turing machines (the halting problem is undecidable), so there must still be a computable function that is not definable in λ→ with `fix`

.

### No numbers

Another casualty of adding types is Church numerals. If we assume some type `A`

, we can define them as:

` c`_{0} ≡ λs:A→A. λz:A. z
c_{1} ≡ λs:A→A. λz:A. s z
c_{2} ≡ λs:A→A. λz:A. s (s z)

and so on, so that each has type `(A→A)→A→A`

. For brevity, let’s write this as `CN A`

. A seemingly minor trouble is that if you want to use Church numerals to iterate a function, you can only do this for functions of type `A→A`

. If you want to iterate a function of another type, then you must define a new set of Church numerals for that type.

But this seemingly minor trouble will become a big one. Let’s keep going:

```
scc ≡ λn:CN A. λs:A→A. λz:A. s (n s z)
plus ≡ λm:CN A. λn:CN A. m scc n # wrong
```

This definition of `plus`

is wrong, because `m`

wants a function of type `A→A`

, but `scc`

doesn’t have that type! The definition in the book works:

` plus ≡ λm:CN A. λn:CN A. λs:A→A. λz:A. m s (n s z)`

Again, the book’s definition of `times`

, but the alternative definition on page 500 works:

`times ≡ λm:CN A. λn:CN A. λs:A→A. λz:A. m (n s) z`

But it turns out that the set of functions that can be defined on Church numerals is extremely limited [1] and doesn’t even include the predecessor function. For example, the predecessor function `prd`

given in the book, given `c`

, starts with a pair _{n}:CN A`zz ≡ pair c`

and applies the function_{0} c_{0}

` ss ≡ λp. pair (snd p) (scc (snd p))`

to it `n`

times to give `pair c`

. Then the first member of this pair is the predecessor._{n}_{-}_{1} c_{n}

The problem is that we want `prd`

to have type `CN A → CN A`

, which means that `zz`

must be a pair of `CN A`

’s (let’s write this as `CN A × CN A`

). But in order to apply `ss`

to it `n`

times, we need a representation of `n`

that is of type `CN (CN A × CN A)`

, and it’s not clear how to convert our `c`

of type _{n}`CN A`

to type `CN (CN A × CN A)`

.

More generally, this means that if we define, say, linked lists, we won’t be able to define `cdr`

, or if we define binary trees, we won’t be able to find the left or right child of a node.

## PCF

Combining the simply-typed lambda calculus with numbers and Booleans (Chapter 8) and `fix`

(11.11) forms a language known as PCF (Programming Computable Functions), which is Turing-complete.

The new rules for `fix`

are:

```
t ::= ...
fix t
fix (λx:T
```_{1}. t_{2}) ⟶ [x↦fix (λx:T_{1}. t_{2})]t_{2}
Γ ⊢ t : T→T
————————————— (T-Fix)
Γ ⊢ fix t : T

We showed how to simulate a Turing machine in the untyped lambda calculus using two lists to represent the tape. In PCF, we can use numbers to represent lists.

Pierce (p. 143) defines an `iseven`

function; here, we define an `isodd`

function:

```
isodd ≡ fix (λh:Nat→Bool. λn:Nat.
if iszero n then false
else if iszero (pred n) then true
else h (pred (pred n)))
```

Similarly, define a `half`

function that divides by two, discarding the remainder:

```
half ≡ fix (λt:Nat→Nat. λn:Nat.
if iszero n then 0
else if iszero (pred n) then 0
else succ (t (pred (pred n))))
```

We can then represent a list of Booleans using numbers:

```
nil ≡ 0
head ≡ isodd
tail ≡ half
```

## References

[1] Richard Statman. 1979. The typed λ-calculus is not elementary recursive. *Theoretical Computer Science* 9, 1 (1979), 73–81. DOI:https://doi.org/10.1016/0304-3975(79)90007-0

[2] Richard Statman. 2002. On the lambda Y calclulus. In *Proc. LICS*, 159. DOI:https://doi.org/10.1109/LICS.2002.1029825