The Simply Typed Lambda-Calculus

Our job for this chapter: Formalize a small functional language and its type system Language: The simply typed lambda-calculus.

• A small subset of Coq's built-in functional language...
• ...but we'll use different concrete syntax (for consistency with standard treatments of the STLC)

Main new technical challenges:

• variable binding
• substitution

Overview

Begin with some set of base types (here, just Bool) Add:

• variables
• function abstractions
• application

Informal concrete syntax: The λ symbol (backslash, in ascii) in a function abstraction λx:T₁.t₂ is generally written as a greek letter "lambda" (hence the name of the calculus). The variable x is called the parameter to the function; the term t₁ is its body. The annotation :T specifies the type of arguments that the function can be applied to.

Some examples:

• λx:Bool. x
  The identity function for booleans.
• (λx:Bool. x) true
  The identity function for booleans, applied to the boolean true.
• λx:Bool. if x then false else true
  The boolean "not" function.
• λx:Bool. true
  The constant function that takes every (boolean) argument to true.

• λx:Bool. λy:Bool. x
  A two-argument function that takes two booleans and returns the first one. (Note that, as in Coq, a two-argument function is really a one-argument function whose body is also a one-argument function.)
• (λx:Bool. λy:Bool. x) false true
  A two-argument function that takes two booleans and returns the first one, applied to the booleans false and true.
  Note that, as in Coq, application associates to the left — i.e., this expression is parsed as ((λx:Bool. λy:Bool. x) false) true.
• λf:Bool→Bool. f (f true)
  A higher-order function that takes a function f (from booleans to booleans) as an argument, applies f to true, and applies f again to the result.
• (λf:Bool→Bool. f (f true)) (λx:Bool. false)
  The same higher-order function, applied to the constantly false function.

Note that all functions are anonymous. We'll see how to add named function declarations as syntactic sugar in the next chapter.

The types of the STLC include Bool for boolean values and arrow types for functions. For example:

• λx:Bool. false has type Bool→Bool
• λx:Bool. x has type Bool→Bool
• (λx:Bool. x) true has type Bool
• λx:Bool. λy:Bool. x has type Bool→Bool→Bool (i.e. Bool → (Bool→Bool))
• (λx:Bool. λy:Bool. x) false has type Bool→Bool
• (λx:Bool. λy:Bool. x) false true has type Bool

Syntax

Let's begin by formalizing the syntax of the STLC.

Types

Terms

Note that an abstraction λx:T.t (formally, tabs x T t) is always annotated with the type T of its parameter, in contrast to Coq (and other functional languages like ML, Haskell, etc.), which use type inference to fill in missing annotations. We're not considering type inference here, to keep things simple.

Some examples...

idB = λx:Bool. x

idBB = λx:Bool→Bool. x

idBBBB = λx:(Bool→Bool) → (Bool→Bool). x

k = λx:Bool. λy:Bool. x

notB = λx:Bool. if x then false else true

(We write these as Notations rather than Definitions to make things easier for auto.)

Operational Semantics

To define the small-step semantics of STLC terms...

• We begin by defining the set of values.
• Next, we define free variables and substitution. (These are used in the reduction rule for application expressions.)
• Finally, we give the small-step relation itself.

Values

To define the values of the STLC, we have a few cases to consider. First, for the boolean part of the language, the situation is clear: true and false are the only values. An if expression is never a value.

Second, an application is clearly not a value: It represents a function being invoked on some argument, which clearly still has work left to do.

Third, for abstractions, we have a choice:

• We can say that λx:T.t₁ is a value only when t₁ is a value — i.e., only if the function's body has been reduced (as much as it can be without knowing what argument it is going to be applied to).
• Or we can say that λx:T.t₁ is always a value, no matter whether t₁ is one or not — in other words, we can say that reduction stops at abstractions.

Coq, in its built-in functional programming langauge, makes the first choice — for example, yields fun x:bool ⇒ 7. Most real-world functional programming languages make the second choice — reduction of a function's body only begins when the function is actually applied to an argument. We also make the second choice here.

Finally, having made the choice not to reduce under abstractions, we don't need to worry about whether variables are values, since we'll always be reducing programs "from the outside in," and that means the step relation will always be working with closed terms (ones with no free variables).

Free Variables and Substitution

Now we come to the heart of the STLC: the operation of substituting one term for a variable in another term. This operation will be used below to define the operational semantics of function application, where we will need to substitute the argument term for the function parameter in the function's body. For example, we reduce to by substituting false for the parameter x in the body of the function. In general, we need to be able to substitute some given term s for occurrences of some variable x in another term t. In informal discussions, this is usually written [x:=s]t and pronounced "substitute x with s in t."

Here are some examples:

• [x:=true] (if x then x else false) yields if true then true else false
• [x:=true] x yields true
• [x:=true] (if x then x else y) yields if true then true else y
• [x:=true] y yields y
• [x:=true] false yields false (vacuous substitution)
• [x:=true] (λy:Bool. if y then x else false) yields λy:Bool. if y then true else false
• [x:=true] (λy:Bool. x) yields λy:Bool. true
• [x:=true] (λy:Bool. y) yields λy:Bool. y
• [x:=true] (λx:Bool. x) yields λx:Bool. x

The last example is very important: substituting x with true in λx:Bool. x does not yield λx:Bool. true! The reason for this is that the x in the body of λx:Bool. x is bound by the abstraction: it is a new, local name that just happens to be spelled the same as some global name x.

Here is the definition, informally... ... and formally:

Technical note: Substitution becomes trickier to define if we consider the case where s, the term being substituted for a variable in some other term, may itself contain free variables. Since we are only interested here in defining the step relation on closed terms (i.e., terms like λx:Bool. x, that do not mention variables are not bound by some enclosing lambda), we can skip this extra complexity here, but it must be dealt with when formalizing richer languages.

Reduction

value v2	(ST_AppAbs)
(λx:T.t12) v2 ⇒ [x:=v2]t12

t1 ⇒ t1'	(ST_App1)
t1 t2 ⇒ t1' t2

value v1
t2 ⇒ t2'	(ST_App2)
v1 t2 ⇒ v1 t2'

(plus the usual rules for booleans). This is call by value reduction: to reduce an application (t₁ t₂),

• first reduce t₁ to a value (a function)
• then reduce the argument t₂ to a value
• then reduce the application itself by substituting t₂ for the bound variable x in the body t₁.

The ST_AppAbs rule is often called beta-reduction.

Examples

Example: i.e.

Example: i.e.

Example: i.e.

Example: i.e.

Typing

Contexts

Question: What is the type of the term "x y"? Answer: It depends on the types of x and y! I.e., in order to assign a type to a term, we need to know what assumptions we should make about the types of its free variables. This leads us to a three-place "typing judgment", informally written Γ ⊢ t : T, where Γ is a "typing context" — a mapping from variables to their types.

We hide the definition of partial maps in a module since it is actually defined in SfLib.

Informally, we'll write Γ, x:T for "extend the partial function Γ to also map x to T." Formally, we use the function extend to add a binding to a partial map.

Typing Relation

Γ x = T	(T_Var)
Γ ⊢ x ∈ T

Γ , x:T11 ⊢ t12 ∈ T12	(T_Abs)
Γ ⊢ λx:T11.t12 ∈ T11->T12

Γ ⊢ t1 ∈ T11->T12
Γ ⊢ t2 ∈ T11	(T_App)
Γ ⊢ t1 t2 ∈ T12

	(T_True)
Γ ⊢ true ∈ Bool

	(T_False)
Γ ⊢ false ∈ Bool

Γ ⊢ t1 ∈ Bool    Γ ⊢ t2 ∈ T    Γ ⊢ t3 ∈ T	(T_If)
Γ ⊢ if t1 then t2 else t3 ∈ T

We can read the three-place relation Γ ⊢ t ∈ T as: "to the term t we can assign the type T using as types for the free variables of t the ones specified in the context Γ."

Examples

Note that since we added the has_type constructors to the hints database, auto can actually solve this one immediately.

Another example:

We can also show that terms are not typable. For example, let's formally check that there is no typing derivation assigning a type to the term λx:Bool. λy:Bool, x y — i.e.,

Another nonexample: