Dependent functional programming

Authors:

Yannick Forster

Théo Winterhalter

Files:

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.

The command has indeed failed with message: Cannot guess decreasing argument of fix.

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 nat

S (length l1 + length l2) < S (length l1 + S (length l2))
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 nat

S (length l1 + length l2) < S (length l1 + S (length l2))
lia.
merge_unfold_eq has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_clause_3_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_clause_3_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_graph, merge_clause_3_graph are defined
merge_graph_mut, merge_clause_3_graph_mut are recursively defined
merge_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
merge_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

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.

eq_nat_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eq_nat_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eq_nat_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

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.
(** val merge : nat list -> nat list -> nat list **) let merge a b = let rec fix_F x = match let _,pr2 = x in pr2 with | [] -> let pr1,_ = x in pr1 | n :: l -> (match let pr1,_ = x in pr1 with | [] -> n :: l | n0 :: l0 -> if le_dec n0 n then n0 :: (let y = l0,(n :: l) in fix_F y) else n :: (let y = (n0 :: l0),l in fix_F y)) in fix_F (a,b)

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 nat

In x (merge l1 l2) <-> In x l1 \/ In x l2
x: nat
l1, l2: list nat

In x (merge l1 l2) <-> In x l1 \/ In x l2
x: nat
l1, l2: list nat

forall l0 : list nat, In x l0 <-> In x l0 \/ In x []
x: nat
l1, l2: list nat
forall (n : nat) (l : list nat), In x (n :: l) <-> In x [] \/ In x (n :: l)
x: nat
l1, l2: list nat
forall (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 nat
forall (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)
all: firstorder congruence. Qed.

Let us look at a simpler example to see what it does.

neg_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
neg_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
neg_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
neg_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

See all the things it generated about neg.

FunctionalInduction_neg: FunctionalInduction neg
neg_graph_correct: forall b : bool, neg_graph b (neg b)
neg_equation_2: neg false = true
neg_equation_1: neg true = false
neg_elim: forall P : bool -> bool -> Type, P true false -> P false true -> forall b : bool, P b (neg b)
FunctionalElimination_neg: FunctionalElimination neg (forall P : bool -> bool -> Type, P true false -> P false true -> forall b : bool, P b (neg b)) 3

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.

neg_elim : forall P : bool -> bool -> Type, P true false -> P false true -> forall b : bool, P b (neg b) neg_elim is not universe polymorphic Arguments neg_elim P%_function_scope neg_graph_equation_1 neg_graph_equation_2 b%_bool_scope neg_elim is transparent Expands to: Constant lesson6_part1.neg_elim Declared in toplevel input, characters 968-1045

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) = b

forall b : bool, neg (neg b) = b

neg (neg true) = true

neg (neg false) = false

neg (neg true) = true

true = true
reflexivity.

neg (neg false) = false

false = false
reflexivity. Abort.

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) = b

forall b : bool, neg (neg b) = b

forall b : bool, neg (neg b) = b
(* Without it [cbn] below does nothing. *)

neg (neg true) = true

neg (neg false) = false

true = true

false = false
all: reflexivity. Abort.

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) = b

forall b : bool, neg (neg b) = b
b: bool

neg (neg b) = b
b: bool

(fun b0 b1 : bool => neg b1 = b0) b (neg b)
b: bool

neg false = true
b: bool
neg true = false
b: bool

neg false = true
b: bool

true = true
reflexivity.
b: bool

neg true = false
reflexivity. (* Actually [reflexivity] works. *) Abort.

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) = b

forall b : bool, neg (neg b) = b
b: bool

neg (neg b) = b
Heqcall: false = neg true

neg false = true
Heqcall: true = neg false
neg true = false
all: reflexivity. Qed.

Equations syntax is quite permissive and allows us to use notations.

Reserved Notation "x +++ y" (at level 60, right associativity).

app_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
app_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
app_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
app_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

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 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': list A

P [] 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')
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 A

P [] 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')
a: A
l, l': list A
ih: forall l' : list A, P l l' (l +++ l')

P (a :: l) l' ((a :: 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 l l' (l +++ l')
eapply ih. Qed.

The one Equations generated is very similar.

app_elim : forall P : forall A : Type, list A -> list A -> list A -> Type, (forall (A : Type) (l' : list A), P A [] l' l') -> (forall (A : Type) (a : A) (l l' : list A), P A l l' (l +++ l') -> P A (a :: l) l' (a :: l +++ l')) -> forall (A : Type) (l l' : list A), P A l l' (l +++ l') app_elim is not universe polymorphic Arguments app_elim (P app_graph_equation_1 app_graph_equation_2)%_function_scope A%_type_scope (l l')%_list_scope app_elim is transparent Expands to: Constant lesson6_part1.app_elim Declared in toplevel input, characters 1782-1918

Once again we apply it using funelim.

A: Type
x, y, z: list A

x +++ y +++ z = (x +++ y) +++ z
A: Type
x, y, z: list A

x +++ y +++ z = (x +++ y) +++ z
A: Type
l', z: list A
Heqcall: l' = [] +++ l'

[] +++ l' +++ z = l' +++ z
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') +++ z
A: Type
l', z: list A
Heqcall: l' = [] +++ l'

[] +++ l' +++ z = l' +++ z
auto.
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') +++ z
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') +++ z
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') +++ z
reflexivity. Qed.
A: Type
l: list A

l +++ [] = l
A: Type
l: list A

l +++ [] = l
A: Type
Heqcall: [] = [] +++ []

[] = []
A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []
a :: l +++ [] = a :: l
A: Type
Heqcall: [] = [] +++ []

[] = []
reflexivity.
A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []

a :: l +++ [] = a :: l
A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []

a :: l +++ [] = a :: l
A: Type
a: A
l: list A
H: l +++ [] = l
Heqcall: a :: l +++ [] = (a :: l) +++ []

a :: l = a :: l
reflexivity. Qed.
Exercise: Specification of eq_nat

Prove the following two lemmas specifying your eq_nat using funelim.

n, m: nat

eq_nat n m = true -> n = m
n, m: nat

eq_nat n m = true -> n = m
Admitted.
n, m: nat

eq_nat n m = false -> n <> m
n, m: nat

eq_nat n m = false -> n <> m
Admitted.

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.

filter_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
filter_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
filter_clause_2_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
filter_clause_2_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
filter_graph, filter_clause_2_graph are defined
filter_graph_mut, filter_clause_2_graph_mut are recursively defined
filter_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
filter_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

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 A

filter l (fun _ : A => true) = l
A: Type
l: list A

filter l (fun _ : A => true) = l
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 :: l
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
A: Type
Heqcall: [] = filter [] (fun _ : A => true)

[] = []
reflexivity.
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 :: l
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 :: l
reflexivity.
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
discriminate. Qed.

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.

equal_obligations has type-checked, generating 3 obligations
Solving obligations automatically...
No more obligations remaining
equal_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_equation_4 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_clause_2_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_clause_2_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_graph, equal_clause_2_graph are defined
equal_graph_mut, equal_clause_2_graph_mut are recursively defined
equal_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
equal_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

You can also extract programs written with Equations and it looks reasonable.

(** val equal : nat -> nat -> bool **) let rec equal n m = match n with | O -> (match m with | O -> true | S _ -> false) | S n0 -> (match m with | O -> false | S n1 -> equal n0 n1)

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.

  
split_two_obligations has type-checked, generating 1 obligation
Solving obligations automatically...
1 obligation remaining
Obligation 1 of split_two_obligations: (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)).

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)

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))
lia.
No more obligations remaining
split_two_unfold_eq has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
split_two_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
split_two_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
split_two_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
split_two_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
split_two_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
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 = true

n = m
n, m: nat
e: eq_nat n m = true

eq_nat n m = true
assumption.
n, m: nat
e: eq_nat n m = false

{n = m} + {n <> m}
n, m: nat
e: eq_nat n m = false

n <> m
n, m: nat
e: eq_nat n m = false

eq_nat n m = false
assumption. Qed. Definition eq_dec_term (n m : nat) : { n = m } + { n <> m } := REPLACE_ME.

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.

head = fun (A : Type) (n : nat) (v : vec A (S n)) => match v in vec _ n0 return match n0 with | 0 => IDProp | S _ => A end with | vnil => idProp | vcons a _ => a end : forall {A : Type} {n : nat}, vec A (S n) -> A Arguments head {A}%_type_scope {n}%_nat_scope v

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.

The command has indeed failed with message: Non exhaustive pattern-matching: no clause found for patterns vnil, vcons _ _

Thankfully, Equations knows how to do it!

zip_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
zip_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
zip_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
zip_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

The term is quite complicated, it's nice we didn't have to write it ourselves.

zip = fix zip (A B : Type) (n : nat) (v : vec A n) (v' : vec B n) {struct v} : vec (A * B) n := match v in vec _ n0 return vec B n0 -> vec (A * B) n0 with | vnil => fun v'0 : vec B 0 => match v'0 in vec _ n0 return n0 = 0 -> vec (A * B) 0 with | vnil => apply_noConfusion 0 0 (fun _ : True => vnil) | @vcons _ _ n0 _ => apply_noConfusion (S n0) 0 (False_rect (vec (A * B) 0)) end eq_refl | @vcons _ a n0 v0 => fun v'0 : vec B (S n0) => match v'0 in vec _ n1 return n1 = S n0 -> vec (A * B) (S n0) with | vnil => apply_noConfusion 0 (S n0) (False_rect (vec (A * B) (S n0))) | @vcons _ a0 n1 v1 => apply_noConfusion (S n1) (S n0) (fun H : n1 = n0 => DepElim.solution_left n0 (fun v2 : vec B n0 => vcons (a, a0) (zip A B n0 v0 v2)) n1 H v1) end eq_refl end v' : forall {A B : Type} {n : nat}, vec A n -> vec B n -> vec (A * B) n Arguments zip {A B}%_type_scope {n}%_nat_scope v v'
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.

vnth_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vnth_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vnth_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vnth_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vnth_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

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)
A: Type
n0: nat
a: A
v: vec A n0

vcons a v = vcons (head (vcons a v)) (tail (vcons a v))
reflexivity. Qed.

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.

NoConfusionPackage_fin has type-checked, generating 4 obligations
Solving obligations automatically...
No more obligations remaining
NoConfusionHomPackage_fin has type-checked, generating 4 obligations
Solving obligations automatically...
No more obligations remaining
NoConfusionPackage_vec has type-checked, generating 4 obligations
Solving obligations automatically...
No more obligations remaining
A, B: Type
n: nat
v: vec A n
v': vec B n
x: fin n

vnth (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 n

vnth (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) fin0

vnth (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) fin0

vnth (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) fin0

vnth (zip (vcons a v) (vcons a0 v0)) fin0 = (a, vnth (vcons a0 v0) 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) fin0

(a, a0) = (a, a0)
reflexivity.
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
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))
simp zip vnth. (* Sometimes [simp] will also solve the goal. *) Qed.
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.

repeat_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
repeat_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
repeat_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

REPLACE_ME

REPLACE_ME
Admitted.
A: Type
a: A
n: nat
m: fin n

vnth (repeat a n) m = a
A: Type
a: A
n: nat
m: fin n

vnth (repeat a n) m = a
Admitted.
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.

The command has indeed failed with message: In environment rev_acc : let H := fixproto in forall (A : Type) (n m : nat), vec A n -> vec A m -> vec A (n + m) A : Type n0 : nat m : nat a : A v : vec A n0 acc : vec A m The term "rev_acc A n0 (S m) v (vcons a acc)" has type "vec A (n0 + S m)" while it is expected to have type "vec A (S n0 + m)".
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…

test : forall A B : type, term vnil ((A ~> B) ~> A ~> B)

We cannot write terms that are ill-typed in STLC, such as applying tstar to itself.

The command has indeed failed with message: The term "tstar" has type "term ?E tunit" while it is expected to have type "term ?E (?A ~> ?B)".

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:

extend_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
extend_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
extend_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
extend_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

We are now ready to interpret terms!

interp_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
interp_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
interp_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
interp_equation_4 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
interp_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
interp_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

We can test on a few examples and see them get normalised.

= fun (x : unit -> unit) (x0 : unit) => x x0 : interp_type ((tunit ~> tunit) ~> tunit ~> tunit)
= fun (x : unit -> unit) (x0 : unit) => x x0 : interp_type ((tunit ~> tunit) ~> tunit ~> tunit)
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.

normal, stuck are defined
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}.
NoConfusionPackage_type has type-checked, generating 4 obligations
Solving obligations automatically...
No more obligations remaining

REPLACE_ME

REPLACE_ME
Admitted.

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'

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) (u : A) (e : u = u) (P : A -> Type) (t : P u), transport e t = t

forall (A : Type) (u : A) (e : u = u) (P : A -> Type) (t : P u), transport e t = t
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 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 : nat), equiv (vec A n) (ilist A n)

forall (A : Type) (n : nat), equiv (vec A n) (ilist A n)
Admitted.
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) ?Goal
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) ?Goal
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)
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 n1
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)
apply fin0.
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 n1

fin (S m)
apply finS, r, 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)

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 n1
vnth (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) 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)

A = A
reflexivity.
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 n1

vnth (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)
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 n1

vnth (vcons A E) (finS x) = vnth (vcons A F) (finS (r x))
simp vnth.
xren_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
xren_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
xren_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idren_obligations has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idren_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idren_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idren_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
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 n

vnth 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 n

vnth 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 n

vnth G (r' (r x)) = vnth G (r' (r x))
reflexivity.
rencomp_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
rencomp_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
rencomp_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
weak_obligations has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
weak_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
weak_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
weak_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nren_obligations has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nren_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nren_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nren_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sren_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sren_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nren_graph, sren_graph are defined
nren_graph_mut, sren_graph_mut are recursively defined
nren_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nren_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sem_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sem_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sem_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sem_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

Semantic valuation:

Definition sval {n m} (E : env n) (F : env m) :=
  forall x, sem F (vnth E x).

semren_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
semren_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
semren_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
renval_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
renval_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
renval_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sextend_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sextend_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
sextend_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eval_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eval_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eval_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
reify_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
reify_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
reflect_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
reflect_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
reify_graph, reflect_graph are defined
reify_graph_mut, reflect_graph_mut are recursively defined
reify_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
reify_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idval_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idval_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
idval_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nbe_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nbe_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
nbe_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
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). *)