Dependent functional programming
In this lecture, we're going to have a look at dependently typed programming in Rocq. On the way we'll also explore the Equations package and all the nice features it provides to make your lives easier.
From Stdlib Require Import Arith List Lia. Import ListNotations. Set Default Goal Selector "!".
Well-founded recursion with Equations
If you remember merge sort, it involves a merge function that takes two sorted lists and produces a new sorted one.
Unfortunately, if we write it as follows, Rocq will not accept the definition as terminating.
We are going to load Equations to help deal with it nicely.
From Equations Require Import Equations.x: nat
l1: list nat
y: nat
n: ~ x <= y
l2: list nat
merge: forall x x0 : list nat, length x + length x0 < S (length l1 + S (length l2)) -> list natS (length l1 + length l2) < S (length l1 + S (length l2))lia.x: nat
l1: list nat
y: nat
n: ~ x <= y
l2: list nat
merge: forall x x0 : list nat, length x + length x0 < S (length l1 + S (length l2)) -> list natS (length l1 + length l2) < S (length l1 + S (length l2))
OK, so, many things happen at once here.
For one, you can see that the syntax differs from the usual definitions.
Instead we use the keyword Equations? which tells Rocq to use the Equations
package to produce the definition.
Then we have the keyword by which is telling Equations why the function is
terminating, here by saying that the quantity length l1 + length l2
decreases according to the order lt on nat.
Then the branches are given in Haskell/Agda-like syntax by giving patterns for
the whole merge l1 l2 expression.
The keyword with lets us perform a case analysis on an expression.
Finally, Equations will try to verify that the recursive calls have indeed
smaller weight; in one case it doesn't figure it out on its own so we help it
with lia.
Exercise: Decidable equality for nat
Define a Boolean equality test using Equations.
Extraction
It is possible to extract the merge function to OCaml using the following
command.
This is very useful and this feature was actually one of the main motivations behind Rocq. CompCert for instance is a compiler extracted from Rocq code.
From Stdlib Require Import ExtrOcamlBasic.
Reasoning principles
Equations actually proves more stuff for us when defining new functions. For instance it gives us useful functional induction principles.
x: nat
l1, l2: list natIn x (merge l1 l2) <-> In x l1 \/ In x l2x: nat
l1, l2: list natIn x (merge l1 l2) <-> In x l1 \/ In x l2all: firstorder congruence. Qed.x: nat
l1, l2: list natforall l0 : list nat, In x l0 <-> In x l0 \/ In x []x: nat
l1, l2: list natforall (n : nat) (l : list nat), In x (n :: l) <-> In x [] \/ In x (n :: l)x: nat
l1, l2: list natforall (x0 : nat) (l0 : list nat) (y : nat) (l : x0 <= y) (l3 : list nat), In x (merge l0 (y :: l3)) <-> In x l0 \/ In x (y :: l3) -> le_dec x0 y = left l -> In x (x0 :: merge l0 (y :: l3)) <-> In x (x0 :: l0) \/ In x (y :: l3)x: nat
l1, l2: list natforall (x0 : nat) (l0 : list nat) (y : nat) (n : ~ x0 <= y) (l3 : list nat), In x (merge (x0 :: l0) l3) <-> In x (x0 :: l0) \/ In x l3 -> le_dec x0 y = right n -> In x (y :: merge (x0 :: l0) l3) <-> In x (x0 :: l0) \/ In x (y :: l3)
Let us look at a simpler example to see what it does.
See all the things it generated about neg.
For instance, it generates a functional elimination principle.
For neg it says that to prove P b (neg b) you only need to consider the
two cases in the definition, meaning you only need to prove
P true false and P false true.
Say we want to prove that neg is involutive: we have several options.
The first one is to use destruct as before, and then to use Equations'
simp tactic.
forall b : bool, neg (neg b) = bforall b : bool, neg (neg b) = bneg (neg true) = trueneg (neg false) = falseneg (neg true) = truereflexivity.true = trueneg (neg false) = falsereflexivity. Abort.false = false
Note that Equations definitions are opaque by default, meaning
cbn, simpl and friends do not unfold them.
This is why we used simp neg which rewrites with the equations of neg.
We can change this behaviour locally using the Transparent command.
forall b : bool, neg (neg b) = bforall b : bool, neg (neg b) = b(* Without it [cbn] below does nothing. *)forall b : bool, neg (neg b) = bneg (neg true) = trueneg (neg false) = falseall: reflexivity. Abort.true = truefalse = false
Or globally by using Set Equations Transparent which will affect all
future definitions.
We can also use neg_elim!
We first use the pattern tactic which rephrases the goal as a function of its
argument (in other words pattern p rewrites the goal as P p for some P).
forall b : bool, neg (neg b) = bforall b : bool, neg (neg b) = bb: boolneg (neg b) = bb: bool(fun b0 b1 : bool => neg b1 = b0) b (neg b)b: boolneg false = trueb: boolneg true = falseb: boolneg false = truereflexivity.b: booltrue = truereflexivity. (* Actually [reflexivity] works. *) Abort.b: boolneg true = false
Even easier, we use the funelim tactic which applies neg_elim on its
own, a bit like induction applies an induction principle.
forall b : bool, neg (neg b) = bforall b : bool, neg (neg b) = bb: boolneg (neg b) = ball: reflexivity. Qed.Heqcall: false = neg trueneg false = trueHeqcall: true = neg falseneg true = false
Equations syntax is quite permissive and allows us to use notations.
Reserved Notation "x +++ y" (at level 60, right associativity).
Functional elimination and recursion
The app definition above is recursive, and Equations can generate a functional
elimination principle for it too.
We'll do it by hand first: with functional elimination the predicate always
talks about the output of the function, but also about its inputs.
This is important because often we want to relate the output with the inputs.
forall (A : Type) (P : list A -> list A -> list A -> Prop), (forall l' : list A, P [] l' l') -> (forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')) -> forall l l' : list A, P l l' (l +++ l')forall (A : Type) (P : list A -> list A -> list A -> Prop), (forall l' : list A, P [] l' l') -> (forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')) -> forall l l' : list A, P l l' (l +++ l')A: Type
P: list A -> list A -> list A -> Prop
hnil: forall l' : list A, P [] l' l'
hcons: forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')
l, l': list AP l l' (l +++ l')A: Type
P: list A -> list A -> list A -> Prop
hnil: forall l' : list A, P [] l' l'
hcons: forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')
l': list AP [] l' ([] +++ l')A: Type
P: list A -> list A -> list A -> Prop
hnil: forall l' : list A, P [] l' l'
hcons: forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')
a: A
l, l': list A
ih: forall l' : list A, P l l' (l +++ l')P (a :: l) l' ((a :: l) +++ l')apply hnil.A: Type
P: list A -> list A -> list A -> Prop
hnil: forall l' : list A, P [] l' l'
hcons: forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')
l': list AP [] l' ([] +++ l')A: Type
P: list A -> list A -> list A -> Prop
hnil: forall l' : list A, P [] l' l'
hcons: forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')
a: A
l, l': list A
ih: forall l' : list A, P l l' (l +++ l')P (a :: l) l' ((a :: l) +++ l')eapply ih. Qed.A: Type
P: list A -> list A -> list A -> Prop
hnil: forall l' : list A, P [] l' l'
hcons: forall (a : A) (l l' : list A), P l l' (l +++ l') -> P (a :: l) l' (a :: l +++ l')
a: A
l, l': list A
ih: forall l' : list A, P l l' (l +++ l')P l l' (l +++ l')
The one Equations generated is very similar.
Once again we apply it using funelim.
A: Type
x, y, z: list Ax +++ y +++ z = (x +++ y) +++ zA: Type
x, y, z: list Ax +++ y +++ z = (x +++ y) +++ zA: Type
l', z: list A
Heqcall: l' = [] +++ l'[] +++ l' +++ z = l' +++ zA: Type
a: A
l, l': list A
H: forall z : list A, l +++ l' +++ z = (l +++ l') +++ z
z: list A
Heqcall: a :: l +++ l' = (a :: l) +++ l'(a :: l) +++ l' +++ z = (a :: l +++ l') +++ zauto.A: Type
l', z: list A
Heqcall: l' = [] +++ l'[] +++ l' +++ z = l' +++ zA: Type
a: A
l, l': list A
H: forall z : list A, l +++ l' +++ z = (l +++ l') +++ z
z: list A
Heqcall: a :: l +++ l' = (a :: l) +++ l'(a :: l) +++ l' +++ z = (a :: l +++ l') +++ zA: Type
a: A
l, l': list A
H: forall z : list A, l +++ l' +++ z = (l +++ l') +++ z
z: list A
Heqcall: a :: l +++ l' = (a :: l) +++ l'a :: l +++ l' +++ z = a :: (l +++ l') +++ zreflexivity. Qed.A: Type
a: A
l, l': list A
H: forall z : list A, l +++ l' +++ z = (l +++ l') +++ z
z: list A
Heqcall: a :: l +++ l' = (a :: l) +++ l'a :: (l +++ l') +++ z = a :: (l +++ l') +++ zA: Type
l: list Al +++ [] = lA: Type
l: list Al +++ [] = lA: Type
Heqcall: [] = [] +++ [][] = []A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []a :: l +++ [] = a :: lreflexivity.A: Type
Heqcall: [] = [] +++ [][] = []A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []a :: l +++ [] = a :: lA: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []a :: l +++ [] = a :: lreflexivity. Qed.A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []a :: l = a :: l
Exercise: Specification of eq_nat
Prove the following two lemmas specifying your eq_nat using funelim.
n, m: nateq_nat n m = true -> n = mAdmitted.n, m: nateq_nat n m = true -> n = mn, m: nateq_nat n m = false -> n <> mAdmitted.n, m: nateq_nat n m = false -> n <> m
Matching on expressions
We have already seen it, but it is possible to match on expressions that are
not direct arguments of the function we define using Equations.
This is done with the with keyword.
Equations then takes this branching into account, e.g. for
funelim.
In the case of filter, funelim will yield 3 cases.
Compare that with the usual two you get by induction on the argument, followed
by a case analysis on p a.
A: Type
l: list Afilter l (fun _ : A => true) = lA: Type
l: list Afilter l (fun _ : A => true) = lA: Type
Heqcall: [] = filter [] (fun _ : A => true)[] = []A: Type
a: A
l: list A
H: filter l (fun _ : A => true) = l
Heq: true = true
Heqcall: a :: filter l (fun _ : A => true) = filter (a :: l) (fun _ : A => true)a :: filter l (fun _ : A => true) = a :: lA: Type
a: A
l: list A
H: filter l (fun _ : A => true) = l
Heq: true = false
Heqcall: filter l (fun _ : A => true) = filter (a :: l) (fun _ : A => true)filter l (fun _ : A => true) = a :: lreflexivity.A: Type
Heqcall: [] = filter [] (fun _ : A => true)[] = []A: Type
a: A
l: list A
H: filter l (fun _ : A => true) = l
Heq: true = true
Heqcall: a :: filter l (fun _ : A => true) = filter (a :: l) (fun _ : A => true)a :: filter l (fun _ : A => true) = a :: lreflexivity.A: Type
a: A
l: list A
H: filter l (fun _ : A => true) = l
Heq: true = true
Heqcall: a :: filter l (fun _ : A => true) = filter (a :: l) (fun _ : A => true)a :: l = a :: ldiscriminate. Qed.A: Type
a: A
l: list A
H: filter l (fun _ : A => true) = l
Heq: true = false
Heqcall: filter l (fun _ : A => true) = filter (a :: l) (fun _ : A => true)filter l (fun _ : A => true) = a :: l
Dependent types
Equations is able to handle dependent types as well of course.
Let us look at the following function deciding equality of natural numbers.
Given n and m it returns either a proof that n = m or a proof that
n <> m.
At the same time we're going to see that if one does not add the question mark
to Equations (Equations?), then any missing proof is going to be asked as
a so-called "proof obligation".
Before obligations are given to the user to prove, Rocq will try to use some automation to discharge them automatically.
Below we use the notation ?(n) to indicate that an argument has to be n
because of typing constraints.
We also use the underscore (_) to indicate subterms we do not want to provide,
those will become obligations as well.
You can also extract programs written with Equations and it looks reasonable.
We can tell Rocq what it should do with obligations, here: nothing! We use this setting inside a module so that it is local to it.
Module SplitTwo. #[local] Obligation Tactic := idtac.
You see that 1 obligation was generated and that it wasn't automatically solved.
It makes sense when the tactic tasked with solving obligations is idtac!
We can use the following command to focus on the obligation and prove it.
forall (A : Type) (a b : A) (l : list A), (forall (x : Type) (x0 : list x), length x0 < length (a :: b :: l) -> list (x * x)) -> length l < length (a :: b :: l)lia.forall A : Type, A -> A -> forall l : list A, (forall (x : Type) (x0 : list x), length x0 < S (S (length l)) -> list (x * x)) -> length l < S (S (length l))End SplitTwo.
Exercise: Convoy pattern
Sometimes it is useful to remember an expression that we "destruct".
For instance, in the proof of eq_dec below, destruct (eq_nat n m) eqn: e
remembers the equation e between eq_nat n m and the value it is
destructed into.
Can you do the same using only match, by defining eq_dec_term?
forall n m : nat, {n = m} + {n <> m}forall n m : nat, {n = m} + {n <> m}n, m: nat{n = m} + {n <> m}n, m: nat
e: eq_nat n m = true{n = m} + {n <> m}n, m: nat
e: eq_nat n m = false{n = m} + {n <> m}n, m: nat
e: eq_nat n m = true{n = m} + {n <> m}n, m: nat
e: eq_nat n m = truen = massumption.n, m: nat
e: eq_nat n m = trueeq_nat n m = truen, m: nat
e: eq_nat n m = false{n = m} + {n <> m}n, m: nat
e: eq_nat n m = falsen <> massumption. Qed. Definition eq_dec_term (n m : nat) : { n = m } + { n <> m } := REPLACE_ME.n, m: nat
e: eq_nat n m = falseeq_nat n m = false
Inaccessible branches
A popular dependent type is the following type of vectors, or length-indexed
lists. vec A n is the type of lists containing exactly n elements of type
A.
Inductive vec (A : Type) : nat -> Type := | vnil : vec A 0 | vcons (a : A) (n : nat) (v : vec A n) : vec A (S n). Arguments vnil {A}. Arguments vcons {A} a {n}.
We can thus write type-safe head and tail functions by stating that the list
is of length S n for some n, in other words that it is not empty.
Rocq actually figures out that the vnil case is impossible on its own.
Definition head {A n} (v : vec A (S n)) : A := match v with | vcons a v => a end. Definition tail {A n} (v : vec A (S n)) : vec A n := match v with | vcons a v => v end.
If you print the term, you will see the trick.
Let's do it by hand because it's a good exercise.
Definition head' {A n} (v : vec A (S n)) : A := match v in vec _ m return match m with | 0 => unit | S k => A end with | vnil => tt | vcons a v => a end. Definition tail' {A n} (v : vec A (S n)) : vec A n := match v in vec _ m return match m with | 0 => unit | S k => vec A k end with | vnil => tt | vcons a v => v end.
Exercise: Head and tail of vectors
Define the head and tail functions on vectors manually by filling the gaps
in the following programs.
You have to use the return clause and the vnil branch explicitly.
Definition hd {A n} (v : vec A (S n)) : REPLACE_ME := match v in vec _ m return REPLACE_ME with | vnil => REPLACE_ME | vcons a v => REPLACE_ME end. Definition tl {A n} (v : vec A (S n)) : REPLACE_ME := match v in vec _ m return REPLACE_ME with | vnil => REPLACE_ME | vcons a v => REPLACE_ME end.
Rocq is not always smart enough to see that some patterns are impossible.
Consider the following zip function, which it does not let us define.
Thankfully, Equations knows how to do it!
The term is quite complicated, it's nice we didn't have to write it ourselves.
Exercise: zip by hand
Define the zip function by hand, using Fixpoint and match (we call it
zip' to avoid a clash with the definition from the lecture notes).
Fixpoint zip' {A B n} (v : vec A n) (w : vec B n) : vec (A * B) n :=
REPLACE_ME.Another useful dependent type is that of bounded natural numbers.
fin n represents the natural numbers strictly below n.
Its name comes from the fact that fin n is the archetypical type with
exactly n elements.
Inductive fin : nat -> Type := | fin0 n : fin (S n) | finS n (x : fin n) : fin (S n). Arguments fin0 {n}. Arguments finS {n}.
This allows us to take an index in a vector that is guaranteed to be within bounds by typing.
We now have tools to reason about such dependent types.
The dependent elimination tactic is like destruct but it takes the index
into account!
A: Type
n: nat
v: vec A (S n)v = vcons (head v) (tail v)A: Type
n: nat
v: vec A (S n)v = vcons (head v) (tail v)reflexivity. Qed.A: Type
n0: nat
a: A
v: vec A n0vcons a v = vcons (head (vcons a v)) (tail (vcons a v))
With the following we can help Equations do more things.
NoConfusion and NoConfusionHom will teach Equations to discriminate
values of the type automatically and thus derive that more branches are
inaccessible.
Deriving a Signature is also used for tactics like dependent elimination
or dependent induction.
A, B: Type
n: nat
v: vec A n
v': vec B n
x: fin nvnth (zip v v') x = (vnth v x, vnth v' x)A, B: Type
n: nat
v: vec A n
v': vec B n
x: fin nvnth (zip v v') x = (vnth v x, vnth v' x)A: Type
n: nat
a: A
v: vec A n
B: Type
v': vec B (S n)
Heqcall: a = vnth (vcons a v) fin0vnth (zip (vcons a v) v') fin0 = (a, vnth v' fin0)A: Type
n1: nat
a: A
v: vec A n1
x: fin n1
H: forall (B : Type) (v' : vec B n1), vnth (zip v v') x = (vnth v x, vnth v' x)
B: Type
v': vec B (S n1)
Heqcall: vnth v x = vnth (vcons a v) (finS x)vnth (zip (vcons a v) v') (finS x) = (vnth v x, vnth v' (finS x))A: Type
n: nat
a: A
v: vec A n
B: Type
v': vec B (S n)
Heqcall: a = vnth (vcons a v) fin0vnth (zip (vcons a v) v') fin0 = (a, vnth v' fin0)A: Type
n0: nat
a: A
v: vec A n0
B: Type
a0: B
v0: vec B n0
Heqcall: a = vnth (vcons a v) fin0vnth (zip (vcons a v) (vcons a0 v0)) fin0 = (a, vnth (vcons a0 v0) fin0)reflexivity.A: Type
n0: nat
a: A
v: vec A n0
B: Type
a0: B
v0: vec B n0
Heqcall: a = vnth (vcons a v) fin0(a, a0) = (a, a0)A: Type
n1: nat
a: A
v: vec A n1
x: fin n1
H: forall (B : Type) (v' : vec B n1), vnth (zip v v') x = (vnth v x, vnth v' x)
B: Type
v': vec B (S n1)
Heqcall: vnth v x = vnth (vcons a v) (finS x)vnth (zip (vcons a v) v') (finS x) = (vnth v x, vnth v' (finS x))simp zip vnth. (* Sometimes [simp] will also solve the goal. *) Qed.A: Type
n: nat
a: A
v: vec A n
x: fin n
H: forall (B : Type) (v' : vec B n), vnth (zip v v') x = (vnth v x, vnth v' x)
B: Type
a0: B
v0: vec B n
Heqcall: vnth v x = vnth (vcons a v) (finS x)vnth (zip (vcons a v) (vcons a0 v0)) (finS x) = (vnth v x, vnth (vcons a0 v0) (finS x))
Exercise: Repeat
Define repeat such that repeat a n is a vector of length n with all
elements equal to a.
Give and prove its functional elimination principle.
Then use it to prove the associated lemma.
You can compare with the proof using funelim.
REPLACE_MEAdmitted.REPLACE_MEA: Type
a: A
n: nat
m: fin nvnth (repeat a n) m = aAdmitted.A: Type
a: A
n: nat
m: fin nvnth (repeat a n) m = a
Exercise: Map
Same thing with a map function vmap on vectors: define it and prove
that vnth (vmap f v) x is equal to something not mentioning vmap.
State and prove the functional elimination principle for vmap.
Exercise: Reversing a vector
Can you fix the definition of rev_acc below that is supposed to reverse a
vector by using an accumulator?
It should work when removing the Fail.
Definition transport {A} {P : A -> Type} {u v} (e : u = v) : P u -> P v := match e with | eq_refl => fun x => x end.
Exercise: Vectors as subset types
We could also define vectors by using subset types, as we show below.
Define the head and tail functions again for ilist.
Definition ilist (A : Type) (n : nat) :=
{ l : list A | length l = n }.Some notations so that it's nicer:
Notation "⟨ u | v ⟩" := (exist _ u v) (at level 0). Notation "⟨ u ⟩" := (⟨ u | _ ⟩) (at level 0, only parsing).
Intrinsically typed syntax
One more thing we can do with dependent types is define the simply typed λ-calculus (STLC) where the terms are well typed by construction.
We first define the types.
Inductive type := tunit | tarrow (a b : type). Notation "A ~> B" := (tarrow A B) (at level 20, right associativity).
Open terms can have variables in them so we store their types in an environment. We store them in vectors so it's easy to keep track of variables. We could have used lists as well.
Definition env := vec type.We now define terms, indexed over the environment of variables they are
allowed to mention. n lets us keep track of the length of said
environment so that we make sure variables are bound by placing them in
fin n.
term E T represents terms of type T with variables in E.
Notice how tlam represents λ and thus binds a variable in the environment
of its body.
Inductive term {n} (E : env n) : type -> Type := | tvar (x : fin n) : term E (vnth E x) | tstar : term E tunit | tlam (A : type) B (b : term (vcons A E) B) : term E (A ~> B) | tapp A B (f : term E (A ~> B)) (u : term E A) : term E B. Arguments tvar {n E}. Arguments tstar {n E}. Arguments tlam {n E} A {B}. Arguments tapp {n E A B}. Definition test A B : term vnil _ := tlam (A ~> B) ( tlam A ( tapp (tvar (E := vcons _ (vcons _ _)) (finS fin0)) (tvar fin0) ) ).
Sadly the annotation for E is necessary…
We cannot write terms that are ill-typed in STLC, such as applying tstar to
itself.
We map STLC types to Rocq types.
Fixpoint interp_type (t : type) : Type :=
match t with
| tunit => unit
| A ~> B => interp_type A -> interp_type B
end.We also define the concept of valuation of an environment.
Definition valuation {n} (E : env n) :=
forall x, interp_type (vnth E x).The empty valuation:
Definition rho0 : valuation vnil :=
fun x => match x with end.We'll tell Equations to produce transparent constants, meaning simpl and co
will be able to unfold them.
Set Equations Transparent.Extension of a valuation with a new value:
We are now ready to interpret terms!
We can test on a few examples and see them get normalised.
Exercise: Normal forms
To practice dependent elimination a bit more, we give you a new definition of terms of the simply typed λ-calculus, but this time with a dichotomy between normal terms that are values and those that are "stuck".
Show that a normal term of type tunit ~> tunit in the empty environment is
necessarily a λ, meaning some nlam.
Arguments svar {n E}. Arguments nstar {n E}. Arguments nlam {n E} A {B}. Arguments sapp {n E A B}. Arguments nstuck {n E A}.REPLACE_MEAdmitted.REPLACE_ME
Advanced exercises
The following exercises are more advanced.
Exercise: Vectors and subset types are equivalent
Show that vec A n and ilist A n are equivalent.
You may use the K axiom to prove lemma ilist_eq but it is not strictly
necessary.
Axiom K : forall A (u : A) (e : u = u), e = eq_refl.forall (A : Type) (n : nat) (l l' : ilist A n), proj1_sig l = proj1_sig l' -> l = l'Admitted. Record equiv (A B : Type) := { l_to_r : A -> B ; r_to_l : B -> A ; l_to_l : forall a, r_to_l (l_to_r a) = a ; r_to_r : forall b, l_to_r (r_to_l b) = b }.forall (A : Type) (n : nat) (l l' : ilist A n), proj1_sig l = proj1_sig l' -> l = l'forall (A : Type) (u : A) (e : u = u) (P : A -> Type) (t : P u), transport e t = tAdmitted.forall (A : Type) (u : A) (e : u = u) (P : A -> Type) (t : P u), transport e t = tforall (A : Type) (n m : nat) (e : S n = S m) (e' : n = m) (a : A) (v : vec A n), transport e (vcons a v) = vcons a (transport e' v)Admitted.forall (A : Type) (n m : nat) (e : S n = S m) (e' : n = m) (a : A) (v : vec A n), transport e (vcons a v) = vcons a (transport e' v)forall (A : Type) (n : nat), equiv (vec A n) (ilist A n)Admitted.forall (A : Type) (n : nat), equiv (vec A n) (ilist A n)
Exercise: Normalisation by evaluation
Back to λ-calculus. This time we're going to see how we can go from the term
representation of the lecture to the normal one of the exercise above.
This method is called Normalisation by Evaluation (NbE).
We give you some definitions about renamings, which are remappings of variables.
Definition ren {n m} (E : env n) (F : env m) := { f : fin n -> fin m | forall x, vnth E x = vnth F (f x) }.n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)fin (S m)n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)vnth (vcons A E) x = vnth (vcons A F) ?Goaln, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)fin (S m)n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)vnth (vcons A E) x = vnth (vcons A F) ?Goaln, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)fin (S m)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)fin (S m)n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1fin (S m)apply fin0.n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)fin (S m)apply finS, r, x.n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1fin (S m)n, m: nat
E: env n
F: env m
A: type
r: fin n -> fin m
e: forall x : fin n, vnth E x = vnth F (r x)
x: fin (S n)vnth (vcons A E) x = vnth (vcons A F) (match x in fin n0 return n0 = S n -> fin (S m) with | @fin0 n0 => apply_noConfusion (S n0) (S n) (fun H : n0 = n => DepElim.solution_left n fin0 n0 H) | @finS n0 x0 => apply_noConfusion (S n0) (S n) (fun H : n0 = n => DepElim.solution_left n (fun x1 : fin n => finS (r x1)) n0 H x0) end eq_refl)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)vnth (vcons A E) fin0 = vnth (vcons A F) (match fin0 in fin n return n = S n0 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 fin0 n H) | @finS n x => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 (fun x0 : fin n0 => finS (r x0)) n H x) end eq_refl)n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1vnth (vcons A E) (finS x) = vnth (vcons A F) (match finS x in fin n return n = S n1 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 fin0 n H) | @finS n x0 => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 (fun x1 : fin n1 => finS (r x1)) n H x0) end eq_refl)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)vnth (vcons A E) fin0 = vnth (vcons A F) (match fin0 in fin n return n = S n0 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 fin0 n H) | @finS n x => apply_noConfusion (S n) (S n0) (fun H : n = n0 => DepElim.solution_left n0 (fun x0 : fin n0 => finS (r x0)) n H x) end eq_refl)n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)vnth (vcons A E) fin0 = vnth (vcons A F) fin0reflexivity.n0, m: nat
E: env n0
F: env m
A: type
r: fin n0 -> fin m
e: forall x : fin n0, vnth E x = vnth F (r x)A = An1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1vnth (vcons A E) (finS x) = vnth (vcons A F) (match finS x in fin n return n = S n1 -> fin (S m) with | @fin0 n => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 fin0 n H) | @finS n x0 => apply_noConfusion (S n) (S n1) (fun H : n = n1 => DepElim.solution_left n1 (fun x1 : fin n1 => finS (r x1)) n H x0) end eq_refl)simp vnth.n1, m: nat
E: env n1
F: env m
A: type
r: fin n1 -> fin m
e: forall x : fin n1, vnth E x = vnth F (r x)
x: fin n1vnth (vcons A E) (finS x) = vnth (vcons A F) (finS (r x))n, m, k: nat
E: env n
F: env m
G: env k
r: fin n -> fin m
h: forall x : fin n, vnth E x = vnth F (r x)
r': fin m -> fin k
h': forall x : fin m, vnth F x = vnth G (r' x)
x: fin nvnth E x = vnth G (r' (r x))n, m, k: nat
E: env n
F: env m
G: env k
r: fin n -> fin m
h: forall x : fin n, vnth E x = vnth F (r x)
r': fin m -> fin k
h': forall x : fin m, vnth F x = vnth G (r' x)
x: fin nvnth E x = vnth G (r' (r x))reflexivity.n, m, k: nat
E: env n
F: env m
G: env k
r: fin n -> fin m
h: forall x : fin n, vnth E x = vnth F (r x)
r': fin m -> fin k
h': forall x : fin m, vnth F x = vnth G (r' x)
x: fin nvnth G (r' (r x)) = vnth G (r' (r x))
Semantic valuation:
Definition sval {n m} (E : env n) (F : env m) := forall x, sem F (vnth E x).Definition tid A : term vnil (A ~> A) := tlam A (tvar (E := vcons _ vnil) fin0).
Test on those:
(* Compute nbe (test tunit tunit). *)
(* Compute nbe (tapp (test tunit tunit) (tid tunit)). *)
(* Compute nbe (tapp (tapp (test tunit tunit) (tid tunit)) tstar). *)