StlcThe Simply Typed Lambda-Calculus
Set Warnings "-notation-overridden,-parsing,-deprecated-hint-without-locality".
From Coq Require Import Strings.String.
From PLF Require Import Maps.
From PLF Require Import Smallstep.
Hint Resolve update_eq : core.
From Coq Require Import Strings.String.
From PLF Require Import Maps.
From PLF Require Import Smallstep.
Hint Resolve update_eq : core.
Overview
- variables
- function abstractions
- application
t ::= x (variable)
| \x:T,t (abstraction)
| t t (application)
| true (constant true)
| false (constant false)
| if t then t else t (conditional) The \ symbol in a function abstraction \x:T,t is usually 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.
- \x:Bool, x
- (\x:Bool, x) true
- \x:Bool, if x then false else true
- \x:Bool, true
- \x:Bool, \y:Bool, x
- (\x:Bool, \y:Bool, x) false true
- \f:Bool→Bool, f (f true)
- (\f:Bool→Bool, f (f true)) (\x:Bool, false)
T ::= Bool
| T → T
- \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
Inductive tm : Type :=
| tm_var : string → tm
| tm_app : tm → tm → tm
| tm_abs : string → ty → tm → tm
| tm_true : tm
| tm_false : tm
| tm_if : tm → tm → tm → tm.
Declare Custom Entry stlc.
Notation "<{ e }>" := e (e custom stlc at level 99).
Notation "( x )" := x (in custom stlc, x at level 99).
Notation "x" := x (in custom stlc at level 0, x constr at level 0).
Notation "S -> T" := (Ty_Arrow S T) (in custom stlc at level 50, right associativity).
Notation "x y" := (tm_app x y) (in custom stlc at level 1, left associativity).
Notation "\ x : t , y" :=
(tm_abs x t y) (in custom stlc at level 90, x at level 99,
t custom stlc at level 99,
y custom stlc at level 99,
left associativity).
Coercion tm_var : string >-> tm.
Notation "'Bool'" := Ty_Bool (in custom stlc at level 0).
Notation "'if' x 'then' y 'else' z" :=
(tm_if x y z) (in custom stlc at level 89,
x custom stlc at level 99,
y custom stlc at level 99,
z custom stlc at level 99,
left associativity).
Notation "'true'" := true (at level 1).
Notation "'true'" := tm_true (in custom stlc at level 0).
Notation "'false'" := false (at level 1).
Notation "'false'" := tm_false (in custom stlc at level 0).
| tm_var : string → tm
| tm_app : tm → tm → tm
| tm_abs : string → ty → tm → tm
| tm_true : tm
| tm_false : tm
| tm_if : tm → tm → tm → tm.
Declare Custom Entry stlc.
Notation "<{ e }>" := e (e custom stlc at level 99).
Notation "( x )" := x (in custom stlc, x at level 99).
Notation "x" := x (in custom stlc at level 0, x constr at level 0).
Notation "S -> T" := (Ty_Arrow S T) (in custom stlc at level 50, right associativity).
Notation "x y" := (tm_app x y) (in custom stlc at level 1, left associativity).
Notation "\ x : t , y" :=
(tm_abs x t y) (in custom stlc at level 90, x at level 99,
t custom stlc at level 99,
y custom stlc at level 99,
left associativity).
Coercion tm_var : string >-> tm.
Notation "'Bool'" := Ty_Bool (in custom stlc at level 0).
Notation "'if' x 'then' y 'else' z" :=
(tm_if x y z) (in custom stlc at level 89,
x custom stlc at level 99,
y custom stlc at level 99,
z custom stlc at level 99,
left associativity).
Notation "'true'" := true (at level 1).
Notation "'true'" := tm_true (in custom stlc at level 0).
Notation "'false'" := false (at level 1).
Notation "'false'" := tm_false (in custom stlc at level 0).
Now we need some notation magic to set up the concrete syntax, as
we did in the Imp chapter...
Definition x : string := "x".
Definition y : string := "y".
Definition z : string := "z".
Hint Unfold x : core.
Hint Unfold y : core.
Hint Unfold z : core.
Definition y : string := "y".
Definition z : string := "z".
Hint Unfold x : core.
Hint Unfold y : core.
Hint Unfold z : core.
Note that an abstraction \x:T,t (formally, tm_abs 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.
Examples...
Notation idB :=
<{\x:Bool, x}>.
Notation idBB :=
<{\x:Bool→Bool, x}>.
Notation idBBBB :=
<{\x:((Bool→Bool)→(Bool→Bool)), x}>.
Notation k := <{\x:Bool, \y:Bool, x}>.
Notation notB := <{\x:Bool, if x then false else true}>.
<{\x:Bool, x}>.
Notation idBB :=
<{\x:Bool→Bool, x}>.
Notation idBBBB :=
<{\x:((Bool→Bool)→(Bool→Bool)), x}>.
Notation k := <{\x:Bool, \y:Bool, x}>.
Notation 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
Values
- 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.
Compute (fun x:bool ⇒ 3 + 4) 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.
Inductive value : tm → Prop :=
| v_abs : ∀ x T_{2} t_{1},
value <{\x:T_{2}, t_{1}}>
| v_true :
value <{true}>
| v_false :
value <{false}>.
Hint Constructors value : core.
| v_abs : ∀ x T_{2} t_{1},
value <{\x:T_{2}, t_{1}}>
| v_true :
value <{true}>
| v_false :
value <{false}>.
Hint Constructors value : core.
Finally, we must consider what constitutes a complete program.
Intuitively, a "complete program" must not refer to any undefined
variables. We'll see shortly how to define the free variables
in a STLC term. A complete program is closed -- that is, it
contains no free variables.
(Conversely, a term with free variables is often called an open
term.)
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.
Substitution
(\x:Bool, if x then true else x) false to
if false then true else false by substituting false for the parameter x in the body of the function.
- [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
[x:=s]x = s
[x:=s]y = y if x ≠ y
[x:=s](\x:T, t) = \x:T, t
[x:=s](\y:T, t) = \y:T, [x:=s]t if x ≠ y
[x:=s](t_{1} t_{2}) = ([x:=s]t_{1}) ([x:=s]t_{2})
[x:=s]true = true
[x:=s]false = false
[x:=s](if t_{1} then t_{2} else t_{3}) =
if [x:=s]t_{1} then [x:=s]t_{2} else [x:=s]t_{3}
Reserved Notation "'[' x ':=' s ']' t" (in custom stlc at level 20, x constr).
Fixpoint subst (x : string) (s : tm) (t : tm) : tm :=
match t with
| tm_var y ⇒
if String.eqb x y then s else t
| <{\y:T, t_{1}}> ⇒
if String.eqb x y then t else <{\y:T, [x:=s] t_{1}}>
| <{t_{1} t_{2}}> ⇒
<{([x:=s] t_{1}) ([x:=s] t_{2})}>
| <{true}> ⇒
<{true}>
| <{false}> ⇒
<{false}>
| <{if t_{1} then t_{2} else t_{3}}> ⇒
<{if ([x:=s] t_{1}) then ([x:=s] t_{2}) else ([x:=s] t_{3})}>
end
where "'[' x ':=' s ']' t" := (subst x s t) (in custom stlc).
Fixpoint subst (x : string) (s : tm) (t : tm) : tm :=
match t with
| tm_var y ⇒
if String.eqb x y then s else t
| <{\y:T, t_{1}}> ⇒
if String.eqb x y then t else <{\y:T, [x:=s] t_{1}}>
| <{t_{1} t_{2}}> ⇒
<{([x:=s] t_{1}) ([x:=s] t_{2})}>
| <{true}> ⇒
<{true}>
| <{false}> ⇒
<{false}>
| <{if t_{1} then t_{2} else t_{3}}> ⇒
<{if ([x:=s] t_{1}) then ([x:=s] t_{2}) else ([x:=s] t_{3})}>
end
where "'[' x ':=' s ']' t" := (subst x s t) (in custom stlc).
Note on notations: You might be wondering why we need parentheses
around the substitution notation in the above definition, and why
do we need to redefine the substitution notation in the stlc
custom grammar. The reason is that reserved notations in
definitions have to be defined in the general Coq grammar (and not
a custom one like stlc). This restriction only applies to the
subst definition, that is before the where ... part. From now
on, using the substitution notation in the stlc custom grammar
doesn't need any curly braces.
For example...
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.
Fortunately, since we are only interested here in defining the
step relation on closed terms (i.e., terms like \x:Bool, x
that include binders for all of the variables they mention), we
can sidestep this extra complexity, but it must be dealt with when
formalizing richer languages.
For example, using the definition of substitution above to
substitute the open term
s = \x:Bool, r (where r is a free reference to some global resource) for the free variable z in the term
t = \r:Bool, z where r is a bound variable, we would get
\r:Bool, \x:Bool, r
[]
where the free reference to [r] in [s] has been "captured" by
the binder at the beginning of [t].
Why would this be bad? Because it violates the principle that the
names of bound variables do not matter. For example, if we rename
the bound variable in [t], e.g., let
[[
t' = \w:Bool, z then [z:=s]t' is
\w:Bool, \x:Bool, r which does not behave the same as the original substitution into t:
[z:=s]t = \r:Bool, \x:Bool, r That is, renaming a bound variable in t changes how t behaves under substitution.
See, for example, [Aydemir 2008] for further discussion
of this issue.
s = \x:Bool, r (where r is a free reference to some global resource) for the free variable z in the term
t = \r:Bool, z where r is a bound variable, we would get
\r:Bool, \x:Bool, r
[]
where the free reference to [r] in [s] has been "captured" by
the binder at the beginning of [t].
Why would this be bad? Because it violates the principle that the
names of bound variables do not matter. For example, if we rename
the bound variable in [t], e.g., let
[[
t' = \w:Bool, z then [z:=s]t' is
\w:Bool, \x:Bool, r which does not behave the same as the original substitution into t:
[z:=s]t = \r:Bool, \x:Bool, r That is, renaming a bound variable in t changes how t behaves under substitution.
Exercise: 3 stars, standard (substi_correct)
The definition that we gave above uses Coq's Fixpoint facility to define substitution as a function. Suppose, instead, we wanted to define substitution as an inductive relation substi. We've begun the definition by providing the Inductive header and one of the constructors; your job is to fill in the rest of the constructors and prove that the relation you've defined coincides with the function given above.
Inductive substi (s : tm) (x : string) : tm → tm → Prop :=
| s_var1 :
substi s x (tm_var x) s
(* FILL IN HERE *)
.
Hint Constructors substi : core.
Theorem substi_correct : ∀ s x t t',
<{ [x:=s]t }> = t' ↔ substi s x t t'.
Proof.
(* FILL IN HERE *) Admitted.
☐
| s_var1 :
substi s x (tm_var x) s
(* FILL IN HERE *)
.
Hint Constructors substi : core.
Theorem substi_correct : ∀ s x t t',
<{ [x:=s]t }> = t' ↔ substi s x t t'.
Proof.
(* FILL IN HERE *) Admitted.
☐
Reduction
(\x:T,t_{12}) v_{2} --> [x:=v_{2}]t_{12} is traditionally called beta-reduction.
value v_{2} | (ST_AppAbs) |
(\x:T_{2},t_{1}) v_{2} --> [x:=v_{2}]t_{1} |
t_{1} --> t_{1}' | (ST_App1) |
t_{1} t_{2} --> t_{1}' t_{2} |
value v_{1} | |
t_{2} --> t_{2}' | (ST_App2) |
v_{1} t_{2} --> v_{1} t_{2}' |
(ST_IfTrue) | |
(if true then t_{1} else t_{2}) --> t_{1} |
(ST_IfFalse) | |
(if false then t_{1} else t_{2}) --> t_{2} |
t_{1} --> t_{1}' | (ST_If) |
(if t_{1} then t_{2} else t_{3}) --> (if t_{1}' then t_{2} else t_{3}) |
Reserved Notation "t '-->' t'" (at level 40).
Inductive step : tm → tm → Prop :=
| ST_AppAbs : ∀ x T_{2} t_{1} v_{2},
value v_{2} →
<{(\x:T_{2}, t_{1}) v_{2}}> --> <{ [x:=v_{2}]t_{1} }>
| ST_App1 : ∀ t_{1} t_{1}' t_{2},
t_{1} --> t_{1}' →
<{t_{1} t_{2}}> --> <{t_{1}' t_{2}}>
| ST_App2 : ∀ v_{1} t_{2} t_{2}',
value v_{1} →
t_{2} --> t_{2}' →
<{v_{1} t_{2}}> --> <{v_{1} t_{2}'}>
| ST_IfTrue : ∀ t_{1} t_{2},
<{if true then t_{1} else t_{2}}> --> t_{1}
| ST_IfFalse : ∀ t_{1} t_{2},
<{if false then t_{1} else t_{2}}> --> t_{2}
| ST_If : ∀ t_{1} t_{1}' t_{2} t_{3},
t_{1} --> t_{1}' →
<{if t_{1} then t_{2} else t_{3}}> --> <{if t_{1}' then t_{2} else t_{3}}>
where "t '-->' t'" := (step t t').
Hint Constructors step : core.
Notation multistep := (multi step).
Notation "t_{1} '-->*' t_{2}" := (multistep t_{1} t_{2}) (at level 40).
Inductive step : tm → tm → Prop :=
| ST_AppAbs : ∀ x T_{2} t_{1} v_{2},
value v_{2} →
<{(\x:T_{2}, t_{1}) v_{2}}> --> <{ [x:=v_{2}]t_{1} }>
| ST_App1 : ∀ t_{1} t_{1}' t_{2},
t_{1} --> t_{1}' →
<{t_{1} t_{2}}> --> <{t_{1}' t_{2}}>
| ST_App2 : ∀ v_{1} t_{2} t_{2}',
value v_{1} →
t_{2} --> t_{2}' →
<{v_{1} t_{2}}> --> <{v_{1} t_{2}'}>
| ST_IfTrue : ∀ t_{1} t_{2},
<{if true then t_{1} else t_{2}}> --> t_{1}
| ST_IfFalse : ∀ t_{1} t_{2},
<{if false then t_{1} else t_{2}}> --> t_{2}
| ST_If : ∀ t_{1} t_{1}' t_{2} t_{3},
t_{1} --> t_{1}' →
<{if t_{1} then t_{2} else t_{3}}> --> <{if t_{1}' then t_{2} else t_{3}}>
where "t '-->' t'" := (step t t').
Hint Constructors step : core.
Notation multistep := (multi step).
Notation "t_{1} '-->*' t_{2}" := (multistep t_{1} t_{2}) (at level 40).
Lemma step_example1 :
<{idBB idB}> -->* idB.
Proof.
eapply multi_step.
apply ST_AppAbs.
apply v_abs.
simpl.
apply multi_refl. Qed.
<{idBB idB}> -->* idB.
Proof.
eapply multi_step.
apply ST_AppAbs.
apply v_abs.
simpl.
apply multi_refl. Qed.
Example:
(\x:Bool→Bool, x) ((\x:Bool→Bool, x) (\x:Bool, x))
-->* \x:Bool, x i.e.,
(idBB (idBB idB)) -->* idB.
(\x:Bool→Bool, x) ((\x:Bool→Bool, x) (\x:Bool, x))
-->* \x:Bool, x i.e.,
(idBB (idBB idB)) -->* idB.
Lemma step_example2 :
<{idBB (idBB idB)}> -->* idB.
Proof.
eapply multi_step.
apply ST_App2. auto.
apply ST_AppAbs. auto.
eapply multi_step.
apply ST_AppAbs. simpl. auto.
simpl. apply multi_refl. Qed.
<{idBB (idBB idB)}> -->* idB.
Proof.
eapply multi_step.
apply ST_App2. auto.
apply ST_AppAbs. auto.
eapply multi_step.
apply ST_AppAbs. simpl. auto.
simpl. apply multi_refl. Qed.
Example:
(\x:Bool→Bool, x)
(\x:Bool, if x then false else true)
true
-->* false i.e.,
(idBB notB) true -->* false.
(\x:Bool→Bool, x)
(\x:Bool, if x then false else true)
true
-->* false i.e.,
(idBB notB) true -->* false.
Lemma step_example3 :
<{idBB notB true}> -->* <{false}>.
Proof.
eapply multi_step.
apply ST_App1. apply ST_AppAbs. auto. simpl.
eapply multi_step.
apply ST_AppAbs. auto. simpl.
eapply multi_step.
apply ST_IfTrue. apply multi_refl. Qed.
<{idBB notB true}> -->* <{false}>.
Proof.
eapply multi_step.
apply ST_App1. apply ST_AppAbs. auto. simpl.
eapply multi_step.
apply ST_AppAbs. auto. simpl.
eapply multi_step.
apply ST_IfTrue. apply multi_refl. Qed.
Example:
(\x:Bool → Bool, x)
((\x:Bool, if x then false else true) true)
-->* false i.e.,
idBB (notB true) -->* false. (Note that this term doesn't actually typecheck; even so, we can ask how it reduces.)
(\x:Bool → Bool, x)
((\x:Bool, if x then false else true) true)
-->* false i.e.,
idBB (notB true) -->* false. (Note that this term doesn't actually typecheck; even so, we can ask how it reduces.)
Lemma step_example4 :
<{idBB (notB true)}> -->* <{false}>.
Proof.
eapply multi_step.
apply ST_App2. auto.
apply ST_AppAbs. auto. simpl.
eapply multi_step.
apply ST_App2. auto.
apply ST_IfTrue.
eapply multi_step.
apply ST_AppAbs. auto. simpl.
apply multi_refl. Qed.
<{idBB (notB true)}> -->* <{false}>.
Proof.
eapply multi_step.
apply ST_App2. auto.
apply ST_AppAbs. auto. simpl.
eapply multi_step.
apply ST_App2. auto.
apply ST_IfTrue.
eapply multi_step.
apply ST_AppAbs. auto. simpl.
apply multi_refl. Qed.
We can use the normalize tactic defined in the Smallstep chapter
to simplify these proofs.
Lemma step_example1' :
<{idBB idB}> -->* idB.
Proof. normalize. Qed.
Lemma step_example2' :
<{idBB (idBB idB)}> -->* idB.
Proof. normalize. Qed.
Lemma step_example3' :
<{idBB notB true}> -->* <{false}>.
Proof. normalize. Qed.
Lemma step_example4' :
<{idBB (notB true)}> -->* <{false}>.
Proof. normalize. Qed.
<{idBB idB}> -->* idB.
Proof. normalize. Qed.
Lemma step_example2' :
<{idBB (idBB idB)}> -->* idB.
Proof. normalize. Qed.
Lemma step_example3' :
<{idBB notB true}> -->* <{false}>.
Proof. normalize. Qed.
Lemma step_example4' :
<{idBB (notB true)}> -->* <{false}>.
Proof. normalize. Qed.
Lemma step_example5 :
<{idBBBB idBB idB}>
-->* idB.
Proof.
(* FILL IN HERE *) Admitted.
Lemma step_example5_with_normalize :
<{idBBBB idBB idB}>
-->* idB.
Proof.
(* FILL IN HERE *) Admitted.
☐
<{idBBBB idBB idB}>
-->* idB.
Proof.
(* FILL IN HERE *) Admitted.
Lemma step_example5_with_normalize :
<{idBBBB idBB idB}>
-->* idB.
Proof.
(* FILL IN HERE *) Admitted.
☐
Contexts
Typing Relation
Gamma x = T_{1} | (T_Var) |
Gamma ⊢ x ∈ T_{1} |
x ⊢> T_{2} ; Gamma ⊢ t_{1} ∈ T_{1} | (T_Abs) |
Gamma ⊢ \x:T_{2},t_{1} ∈ T_{2}->T_{1} |
Gamma ⊢ t_{1} ∈ T_{2}->T_{1} | |
Gamma ⊢ t_{2} ∈ T_{2} | (T_App) |
Gamma ⊢ t_{1} t_{2} ∈ T_{1} |
(T_True) | |
Gamma ⊢ true ∈ Bool |
(T_False) | |
Gamma ⊢ false ∈ Bool |
Gamma ⊢ t_{1} ∈ Bool Gamma ⊢ t_{2} ∈ T_{1} Gamma ⊢ t_{3} ∈ T_{1} | (T_If) |
Gamma ⊢ if t_{1} then t_{2} else t_{3} ∈ T_{1} |
Reserved Notation "Gamma '⊢' t '∈' T"
(at level 101,
t custom stlc, T custom stlc at level 0).
Inductive has_type : context → tm → ty → Prop :=
| T_Var : ∀ Gamma x T_{1},
Gamma x = Some T_{1} →
Gamma ⊢ x \in T_{1}
| T_Abs : ∀ Gamma x T_{1} T_{2} t_{1},
x ⊢> T_{2} ; Gamma ⊢ t_{1} \in T_{1} →
Gamma ⊢ \x:T_{2}, t_{1} \in (T_{2} → T_{1})
| T_App : ∀ T_{1} T_{2} Gamma t_{1} t_{2},
Gamma ⊢ t_{1} \in (T_{2} → T_{1}) →
Gamma ⊢ t_{2} \in T_{2} →
Gamma ⊢ t_{1} t_{2} \in T_{1}
| T_True : ∀ Gamma,
Gamma ⊢ true \in Bool
| T_False : ∀ Gamma,
Gamma ⊢ false \in Bool
| T_If : ∀ t_{1} t_{2} t_{3} T_{1} Gamma,
Gamma ⊢ t_{1} \in Bool →
Gamma ⊢ t_{2} \in T_{1} →
Gamma ⊢ t_{3} \in T_{1} →
Gamma ⊢ if t_{1} then t_{2} else t_{3} \in T_{1}
where "Gamma '⊢' t '∈' T" := (has_type Gamma t T).
Hint Constructors has_type : core.
(at level 101,
t custom stlc, T custom stlc at level 0).
Inductive has_type : context → tm → ty → Prop :=
| T_Var : ∀ Gamma x T_{1},
Gamma x = Some T_{1} →
Gamma ⊢ x \in T_{1}
| T_Abs : ∀ Gamma x T_{1} T_{2} t_{1},
x ⊢> T_{2} ; Gamma ⊢ t_{1} \in T_{1} →
Gamma ⊢ \x:T_{2}, t_{1} \in (T_{2} → T_{1})
| T_App : ∀ T_{1} T_{2} Gamma t_{1} t_{2},
Gamma ⊢ t_{1} \in (T_{2} → T_{1}) →
Gamma ⊢ t_{2} \in T_{2} →
Gamma ⊢ t_{1} t_{2} \in T_{1}
| T_True : ∀ Gamma,
Gamma ⊢ true \in Bool
| T_False : ∀ Gamma,
Gamma ⊢ false \in Bool
| T_If : ∀ t_{1} t_{2} t_{3} T_{1} Gamma,
Gamma ⊢ t_{1} \in Bool →
Gamma ⊢ t_{2} \in T_{1} →
Gamma ⊢ t_{3} \in T_{1} →
Gamma ⊢ if t_{1} then t_{2} else t_{3} \in T_{1}
where "Gamma '⊢' t '∈' T" := (has_type Gamma t T).
Hint Constructors has_type : core.
Note that, since we added the has_type constructors to the hints
database, auto can actually solve this one immediately.
More examples:
empty ⊢ \x:A, \y:A→A, y (y x)
\in A → (A→A) → A.
empty ⊢ \x:A, \y:A→A, y (y x)
\in A → (A→A) → A.
Example typing_example_2 :
empty ⊢
\x:Bool,
\y:Bool→Bool,
(y (y x)) \in
(Bool → (Bool → Bool) → Bool).
Proof. eauto 20. Qed.
Exercise: 2 stars, standard, optional (typing_example_2_full)
Prove the same result without using auto, eauto, or eapply (or ...).
Example typing_example_2_full :
empty ⊢
\x:Bool,
\y:Bool→Bool,
(y (y x)) \in
(Bool → (Bool → Bool) → Bool).
Proof.
(* FILL IN HERE *) Admitted.
☐
empty ⊢
\x:Bool,
\y:Bool→Bool,
(y (y x)) \in
(Bool → (Bool → Bool) → Bool).
Proof.
(* FILL IN HERE *) Admitted.
☐
Exercise: 2 stars, standard (typing_example_3)
Formally prove the following typing derivation holds:empty ⊢ \x:Bool→B, \y:Bool→Bool, \z:Bool,
y (x z)
\in T.
Example typing_example_3 :
∃ T,
empty ⊢
\x:Bool→Bool,
\y:Bool→Bool,
\z:Bool,
(y (x z)) \in
T.
Proof.
(* FILL IN HERE *) Admitted.
☐
∃ T,
empty ⊢
\x:Bool→Bool,
\y:Bool→Bool,
\z:Bool,
(y (x z)) \in
T.
Proof.
(* FILL IN HERE *) Admitted.
☐
¬∃ T,
empty ⊢ \x:Bool, \y:Bool, x y \in T.
Example typing_nonexample_1 :
¬ ∃ T,
empty ⊢
\x:Bool,
\y:Bool,
(x y) \in
T.
Proof.
intros Hc. destruct Hc as [T Hc].
(* The clear tactic is useful here for tidying away bits of
the context that we're not going to need again. *)
inversion Hc; subst; clear Hc.
inversion H_{4}; subst; clear H_{4}.
inversion H_{5}; subst; clear H_{5} H_{4}.
inversion H_{2}; subst; clear H_{2}.
discriminate H_{1}.
Qed.
Exercise: 3 stars, standard, optional (typing_nonexample_3)
Another nonexample:¬(∃ S T,
empty ⊢ \x:S, x x \in T).