Lambda-Calculus and Type Theory Part I

Lambda-Calculus and Type Theory Part I

Ugo Dal Lago

Scuola Estiva AILA, Gargnano, August 2018

Preterms

I Let Υ denote a countably infinite set of symbols, called variables.

I A preterm is an expression derived by way of the following grammar:

M ::= x

|

|

where x ∈ Υ.

I We use the following notational conventions:

1. The outermost parentheses in a preterm are omitted.

2. Application associates to the left; ((M N )L) is abbreviated (M N L).

3. Abstraction associates to the right: (λx(λyM )) is abbreviated (λxλyM ).

4. A sequence of abstractions (λx1(λx2. . . (λxnM ) . . .)) can be written as (λx1. . . xn.M ).

Substitution on Preterms

I Define the set FV (M ) of free variables of M as follows:

FV (x) = {x};

FV (λxM ) = FV (M ) − {x};

FV (M N ) = FV (M ) ∪ FV (N ).

I An occurrence of a term M in another term N is a subexpression of N which is syntactically equal to M .

I The substitution of N for x in M , written M [x := N ], is defined iff no free occurrence of x in M is in an occurrence of a term λyL in M , where y ∈ FV (N ):

x[x := N ] = N ; y[x := N ] = y;

(P Q)[x := N ] = P [x := N ]Q[x := N ];

(λxP )[x := N ] = λxP ;

(λyP )[x := N ] = λyP [x := N ].

α-Equivalence

I The relation =_α (aka α-conversion) is the smallest transitive and reflexive relation on preterms satisfying the following:

I If y /∈ FV (M ) and M [x := y] is defined, then λxM =_αλyM [x := y];

I If M =_αN , then λxM =_αλxN for all variable x;

I If M =αN , then M L =αN L and LM =αLN .

Lemma

The relation =_α is an equivalence relation.

Lemma

If M =_α N and L =αP , then M [x := L] =αN [x := P ], provided both sides are defined.

Lemma

For all M, N and for every variable x, there exists L such that M =α L and the substitution L[x := N ] is defined.

Terms

I Define the set Λ of λ-terms as the quotient set of =_α over preterms:

Λ = {[M ]α | M is a preterm}, where [M ]_α= {N | M =α N }.

I For λ-terms M and N , we define the substitution

M [x := N ] as follows: let M = [L]_α and N = [P ]_α where Q = L[x := P ] is defined, then M [x := N ] is [Q]_α.

I Substitution is well-defined but also a total operation.

I In the following:

I We will work with terms.

I But we will give definitions and proofs following the

structure of the underlying preterms, being sure that what we do “makes sense”. We will thus use the following

notation for λ-terms:

LP = [M N ]_αwhere L = [M ]_αand P = [N ]_α λxL = [λxP ]αwhere L = [P ]α

x = [x]α

β-Reduction

I A relation  on Λ is compatible iff it satisfies the following two conditions for all M, N, L ∈ Λ:

1. If M  N then λxM  λxN for every x.

2. If M  N then M L  N L and LM  LN .

I The least compatible relation →_β on Λ such that (λxM )N →_β M [x := N ] is called β-reduction.

I Any term of the form (λxM )N is called a β-redex, and M [x := N ] is the result of contracting the redex.

I A β-normal form is a term M ∈ Λ such that there is no N with M →_β N . The set of normal forms is NFβ.

I A β-reduction sequence is any finite or infinite sequence of terms M₀, M1, . . . such that

M₀ →_β M₁ →_β M₂ →_β · · ·

I The transitive and reflexive closure of →_β is indicated with

β.

Confluence

I Given any relation , its transitive closure is indicated as

⁺, while its reflexive and transitive closure is indicated as

^∗.

I A relation  is said to be confluent iff for every M, N, L, the following holds

M ^∗ N ∧ M ^∗L implies ∃P.N ^∗P ∧ L ^∗P

Theorem

The relation →_β on Λ is confluent.

Corollary

If M β N and M β L where N, L ∈ NFβ, then N = L.

Proof of Confluence: The Main Ingredients

I The relation ⇒_β is the least relation on Λ such that:

1. x ⇒_βx for every variable x;

2. If M ⇒_βN , then λxM ⇒_βλxN ;

3. If M ⇒_βN and L ⇒_βP , then M L ⇒_βN P ;

4. If M ⇒_βN and L ⇒_βP , then (λxM )L ⇒_βN [x := P ].

I The complete development of a term M is defined as follows:

x^†= x (λxM )^†= λxM^†

(M N )^†= M^†N^†if M is not an abstraction;

((λxM )N )^†= M^†[x := N^†]

Proposition

If M ⇒_β N , then N ⇒_β M^†.

Normalization

I A term M is normalizing iff M β N , where N ∈ NF_β. In that case N is said to be the normal form of M . The set of normalizing terms is WN_β.

I A term M is said to be strongly normalizing iff all reduction sequences starting at M are finite. The set of strongly normalizing terms is SN_β.

I A reduction strategy F is a map from Λ to Λ such that F (M ) = M whenever M ∈ NF_β, and M →_β F (M ) otherwise.

I A reduction strategy F is normalizing iff for every

normalizing M there is a natural number n ∈ N such that Fⁿ(M ) ∈ NF_β.

I In the leftmost reduction strategy L : Λ → Λ, L(M ) is obtained by contracting the leftmost redex in M , if any.

Theorem

L is a normalizing reduction strategy.

Expressiveness

I The boolean values T and F can be encoded as λ-terms as follows:

T := λxy.x F := λxy.y

I If M, N ∈ Λ, then hM, N i stands for the term λx(xM N ), where x /∈ FV (M ) ∪ FV (N ).

I Any natural number n ∈ N can be encoded as follows:

n := λxy.xⁿy

where xⁿ(y) stands for x(x(· · · (y) · · · )), with n occurrences of x.

I A partial function f : N^k→ N is λ-definable iff there is Mf ∈ Λ such that:

1. If f (n1, . . . , nk) = m, then Mfn1· · · nk ^βm.

2. If f (n1, . . . , nk) is undefined, then Mfn1· · · nk has no normal form.

Universality

Theorem

The λ-definable functions are precisely the partial recursive ones.

I Some functions and operators which are useful are the following ones:

if M then N else L := M N L;

π1:= λx(xT );

π₂:= λx(xF );

zero? := λx.x(λyF )T .

Corollary

The problem of checking whether M has a normal form is undecidable.