Exercise session 6 — Dependent functional programming — Solutions

Authors:

Yannick Forster

Théo Winterhalter

Files:
Set Default Goal Selector "!".

From Stdlib Require Import Arith List Lia.
Import ListNotations.

From Equations Require Import Equations.

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_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eq_nat_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eq_nat_equation_4 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

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
n, m: nat
h: eq_nat n m = true

n = m
h: eq_nat 0 0 = true
Heqcall: true = eq_nat 0 0

0 = 0
n: nat
h: eq_nat 0 (S n) = true
Heqcall: false = eq_nat 0 (S n)
0 = S n
n: nat
h: eq_nat (S n) 0 = true
Heqcall: false = eq_nat (S n) 0
S n = 0
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)
S n = S m
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)

S n = S m
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)

n = m
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)

eq_nat n m = true
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)
{| pr1 := n; pr2 := m |} = {| pr1 := n; pr2 := m |}
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = true -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 = m0
h: eq_nat (S n) (S m) = true
Heqcall: eq_nat n m = eq_nat (S n) (S m)
eq_nat n m = eq_nat n m
all: congruence. Qed.
n, m: nat

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

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

n <> m
h: eq_nat 0 0 = false
Heqcall: true = eq_nat 0 0

0 <> 0
n: nat
h: eq_nat 0 (S n) = false
Heqcall: false = eq_nat 0 (S n)
0 <> S n
n: nat
h: eq_nat (S n) 0 = false
Heqcall: false = eq_nat (S n) 0
S n <> 0
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = false -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 <> m0
h: eq_nat (S n) (S m) = false
Heqcall: eq_nat n m = eq_nat (S n) (S m)
S n <> S m
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = false -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 <> m0
h: eq_nat (S n) (S m) = false
Heqcall: eq_nat n m = eq_nat (S n) (S m)

S n <> S m
n, m: nat
H: forall n0 m0 : nat, eq_nat n0 m0 = false -> {| pr1 := n; pr2 := m |} = {| pr1 := n0; pr2 := m0 |} -> eq_nat n m = eq_nat n0 m0 -> n0 <> m0
h: eq_nat (S n) (S m) = false
Heqcall: eq_nat n m = eq_nat (S n) (S m)
e: S n = S m

False
m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat (S m) (S m) = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0

False
m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0

False
m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0

eq_nat ?n ?m = false
m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0
{| pr1 := m; pr2 := m |} = {| pr1 := ?n; pr2 := ?m |}
m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0
eq_nat m m = eq_nat ?n ?m
m: nat
Heqcall: eq_nat m m = eq_nat (S m) (S m)
h: eq_nat m m = false
H: forall n m0 : nat, eq_nat n m0 = false -> {| pr1 := m; pr2 := m |} = {| pr1 := n; pr2 := m0 |} -> eq_nat m m = eq_nat n m0 -> n <> m0
?n = ?m
all: eauto. Qed.

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 } := match eq_nat n m as x return eq_nat n m = x -> _ with | true => fun e => left (eq_nat_eq e) | false => fun e => right (neq_nat_neq e) end eq_refl. (* From the lecture: *) 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}.

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)) : 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 tl {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: 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 :=
  match v in vec _ m return
    vec B m -> vec (A * B) m
  with
  | vnil => fun _ => vnil
  | vcons a v => fun w => vcons (a, hd w) (zip' v (tl w))
  end w.

(* From the lecture: *)

Inductive fin : nat -> Type :=
| fin0 n : fin (S n)
| finS n (x : fin n) : fin (S n).

Arguments fin0 {n}.
Arguments finS {n}.

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

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_equation_2 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

forall (A : Type) (a : A) (P : forall n : nat, vec A n -> Prop), P 0 vnil -> (forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))) -> forall n : nat, P n (repeat a n)

forall (A : Type) (a : A) (P : forall n : nat, vec A n -> Prop), P 0 vnil -> (forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))) -> forall n : nat, P n (repeat a n)
A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat

P n (repeat a n)
A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))

P 0 (repeat a 0)
A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat
IHn: P n (repeat a n)
P (S n) (repeat a (S n))
A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))

P 0 (repeat a 0)
apply hnil.
A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat
IHn: P n (repeat a n)

P (S n) (repeat a (S n))
A: Type
a: A
P: forall n : nat, vec A n -> Prop
hnil: P 0 vnil
hcons: forall n : nat, P n (repeat a n) -> P (S n) (vcons a (repeat a n))
n: nat
IHn: P n (repeat a n)

P n (repeat a n)
assumption. Qed.
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
A: Type
a: A
n: nat

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

(fun (n0 : nat) (v : vec A n0) => forall m : fin n0, vnth v m = a) n (repeat a n)
A: Type
a: A
n: nat

forall m : fin 0, vnth vnil m = a
A: Type
a: A
n: nat
forall n0 : nat, (forall m : fin n0, vnth (repeat a n0) m = a) -> forall m : fin (S n0), vnth (vcons a (repeat a n0)) m = a
A: Type
a: A
n: nat

forall m : fin 0, vnth vnil m = a
A: Type
a: A
n: nat
m: fin 0

vnth vnil m = a
dependent elimination m.
A: Type
a: A
n: nat

forall n0 : nat, (forall m : fin n0, vnth (repeat a n0) m = a) -> forall m : fin (S n0), vnth (vcons a (repeat a n0)) m = a
A: Type
a: A
n, m: nat
ih: forall m0 : fin m, vnth (repeat a m) m0 = a
k: fin (S m)

vnth (vcons a (repeat a m)) k = a
A: Type
a: A
n, n0: nat
ih: forall m : fin n0, vnth (repeat a n0) m = a

vnth (vcons a (repeat a n0)) fin0 = a
A: Type
a: A
n, n1: nat
ih: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1
vnth (vcons a (repeat a n1)) (finS x) = a
A: Type
a: A
n, n0: nat
ih: forall m : fin n0, vnth (repeat a n0) m = a

vnth (vcons a (repeat a n0)) fin0 = a
A: Type
a: A
n, n0: nat
ih: forall m : fin n0, vnth (repeat a n0) m = a

a = a
reflexivity.
A: Type
a: A
n, n1: nat
ih: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1

vnth (vcons a (repeat a n1)) (finS x) = a
simp vnth. Abort.

The proof is easier with funelim.

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
A: Type
a: A
m: fin 0
Heqcall: vnil = repeat a 0

vnth vnil m = a
A: Type
a: A
n: nat
H: forall m : fin n, vnth (repeat a n) m = a
m: fin (S n)
Heqcall: vcons a (repeat a n) = repeat a (S n)
vnth (vcons a (repeat a n)) m = a
A: Type
a: A
m: fin 0
Heqcall: vnil = repeat a 0

vnth vnil m = a
dependent elimination m.
A: Type
a: A
n: nat
H: forall m : fin n, vnth (repeat a n) m = a
m: fin (S n)
Heqcall: vcons a (repeat a n) = repeat a (S n)

vnth (vcons a (repeat a n)) m = a
A: Type
a: A
n0: nat
H: forall m : fin n0, vnth (repeat a n0) m = a
Heqcall: vcons a (repeat a n0) = repeat a (S n0)

vnth (vcons a (repeat a n0)) fin0 = a
A: Type
a: A
n1: nat
H: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1
Heqcall: vcons a (repeat a n1) = repeat a (S n1)
vnth (vcons a (repeat a n1)) (finS x) = a
A: Type
a: A
n0: nat
H: forall m : fin n0, vnth (repeat a n0) m = a
Heqcall: vcons a (repeat a n0) = repeat a (S n0)

vnth (vcons a (repeat a n0)) fin0 = a
A: Type
a: A
n0: nat
H: forall m : fin n0, vnth (repeat a n0) m = a
Heqcall: vcons a (repeat a n0) = repeat a (S n0)

a = a
reflexivity.
A: Type
a: A
n1: nat
H: forall m : fin n1, vnth (repeat a n1) m = a
x: fin n1
Heqcall: vcons a (repeat a n1) = repeat a (S n1)

vnth (vcons a (repeat a n1)) (finS x) = a
simp vnth. Qed.

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.

vmap_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vmap_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vmap_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
vmap_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
A, B: Type
n: nat
f: A -> B
v: vec A n
m: fin n

vnth (vmap f v) m = f (vnth v m)
A, B: Type
n: nat
f: A -> B
v: vec A n
m: fin n

vnth (vmap f v) m = f (vnth v m)
A, B: Type
f: A -> B
m: fin 0
Heqcall: vnil = vmap f vnil

vnth vnil m = f (vnth vnil m)
A, B: Type
n0: nat
f: A -> B
a: A
v: vec A n0
H: forall m : fin n0, vnth (vmap f v) m = f (vnth v m)
m: fin (S n0)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)
vnth (vcons (f a) (vmap f v)) m = f (vnth (vcons a v) m)
A, B: Type
f: A -> B
m: fin 0
Heqcall: vnil = vmap f vnil

vnth vnil m = f (vnth vnil m)
A, B: Type
f: A -> B
m: fin 0
Heqcall: vnil = vmap f vnil

vnth vnil m = f (vnth vnil m)
dependent elimination m.
A, B: Type
n0: nat
f: A -> B
a: A
v: vec A n0
H: forall m : fin n0, vnth (vmap f v) m = f (vnth v m)
m: fin (S n0)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)

vnth (vcons (f a) (vmap f v)) m = f (vnth (vcons a v) m)
A, B: Type
n0: nat
f: A -> B
a: A
v: vec A n0
H: forall m : fin n0, vnth (vmap f v) m = f (vnth v m)
m: fin (S n0)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)

vnth (vcons (f a) (vmap f v)) m = f (vnth (vcons a v) m)
A, B: Type
n: nat
f: A -> B
a: A
v: vec A n
H: forall m : fin n, vnth (vmap f v) m = f (vnth v m)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)

vnth (vcons (f a) (vmap f v)) fin0 = f (vnth (vcons a v) fin0)
A, B: Type
n1: nat
f: A -> B
a: A
v: vec A n1
H: forall m : fin n1, vnth (vmap f v) m = f (vnth v m)
x: fin n1
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)
vnth (vcons (f a) (vmap f v)) (finS x) = f (vnth (vcons a v) (finS x))
A, B: Type
n: nat
f: A -> B
a: A
v: vec A n
H: forall m : fin n, vnth (vmap f v) m = f (vnth v m)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)

vnth (vcons (f a) (vmap f v)) fin0 = f (vnth (vcons a v) fin0)
A, B: Type
n: nat
f: A -> B
a: A
v: vec A n
H: forall m : fin n, vnth (vmap f v) m = f (vnth v m)
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)

f a = f a
reflexivity.
A, B: Type
n1: nat
f: A -> B
a: A
v: vec A n1
H: forall m : fin n1, vnth (vmap f v) m = f (vnth v m)
x: fin n1
Heqcall: vcons (f a) (vmap f v) = vmap f (vcons a v)

vnth (vcons (f a) (vmap f v)) (finS x) = f (vnth (vcons a v) (finS x))
simp vnth. Qed.
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop

P 0 vnil vnil -> (forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))) -> forall (n : nat) (v : vec A n), P n v (vmap f v)
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop

P 0 vnil vnil -> (forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))) -> forall (n : nat) (v : vec A n), P n v (vmap f v)
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
n: nat
v: vec A n

P n v (vmap f v)
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))

P 0 vnil (vmap f vnil)
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
a: A
n: nat
v: vec A n
IHv: P n v (vmap f v)
P (S n) (vcons a v) (vmap f (vcons a v))
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))

P 0 vnil (vmap f vnil)
apply h0.
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
a: A
n: nat
v: vec A n
IHv: P n v (vmap f v)

P (S n) (vcons a v) (vmap f (vcons a v))
A, B: Type
f: A -> B
P: forall n : nat, vec A n -> vec B n -> Prop
h0: P 0 vnil vnil
hS: forall (a : A) (n : nat) (v : vec A n), P n v (vmap f v) -> P (S n) (vcons a v) (vcons (f a) (vmap f v))
a: A
n: nat
v: vec A n
IHv: P n v (vmap f v)

P n v (vmap f v)
assumption. Qed.

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.

rev_acc_obligations has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
rev_acc_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
rev_acc_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
rev_acc_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
rev_acc_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

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).

ihead_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
ihead_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
ihead_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
ihead_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
itail_obligations has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
itail_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
itail_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
itail_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
itail_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
(* From the lecture: *) Inductive type := tunit | tarrow (a b : type). Notation "A ~> B" := (tarrow A B) (at level 20, right associativity). Definition env := vec type. 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) ) ). Set Equations Transparent.

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
Definition isnil {A n} (v : vec A n) := match v with | vnil => True | _ => False end.
n: nat
E: env n
A: type

isnil E -> stuck E A -> False
n: nat
E: env n
A: type

isnil E -> stuck E A -> False
n: nat
E: env n
A: type
h: isnil E
s: stuck E A

False
n: nat
E: env n
h: isnil E
x: fin n

False
n: nat
E: env n
h: isnil E
A, B: type
s: stuck E (A ~> B)
u: normal E A
IHs: isnil E -> False
False
n: nat
E: env n
h: isnil E
x: fin n

False
E: env 0
h: isnil E
x: fin 0

False
n: nat
E: env (S n)
h: isnil E
x: fin (S n)
False
E: env 0
h: isnil E
x: fin 0

False
dependent elimination x.
n: nat
E: env (S n)
h: isnil E
x: fin (S n)

False
n0: nat
a: type
v: vec type n0
h: isnil (vcons a v)
x: fin (S n0)

False
contradiction.
n: nat
E: env n
h: isnil E
A, B: type
s: stuck E (A ~> B)
u: normal E A
IHs: isnil E -> False

False
eauto. Qed.

forall t : normal vnil (tunit ~> tunit), exists b : normal (vcons tunit vnil) tunit, t = nlam tunit b

forall t : normal vnil (tunit ~> tunit), exists b : normal (vcons tunit vnil) tunit, t = nlam tunit b
t: normal vnil (tunit ~> tunit)

exists b : normal (vcons tunit vnil) tunit, t = nlam tunit b
b: normal (vcons tunit vnil) tunit

exists b0 : normal (vcons tunit vnil) tunit, nlam tunit b = nlam tunit b0
s: stuck vnil (tunit ~> tunit)
exists b : normal (vcons tunit vnil) tunit, s = nlam tunit b
b: normal (vcons tunit vnil) tunit

exists b0 : normal (vcons tunit vnil) tunit, nlam tunit b = nlam tunit b0
eauto.
s: stuck vnil (tunit ~> tunit)

exists b : normal (vcons tunit vnil) tunit, s = nlam tunit b
s: stuck vnil (tunit ~> tunit)

False
s: False

False
s: stuck vnil (tunit ~> tunit)
isnil vnil
s: stuck vnil (tunit ~> tunit)

isnil vnil
constructor. Qed.

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'
A: Type
n: nat
l: list A
e: length l = n
l': list A
e': length l' = n
h: proj1_sig ⟨ l | e ⟩ = proj1_sig ⟨ l' | e' ⟩

⟨ l | e ⟩ = ⟨ l' | e' ⟩
A: Type
n: nat
l: list A
e: length l = n
l': list A
e': length l' = n
h: l = l'

⟨ l | e ⟩ = ⟨ l' | e' ⟩
A: Type
n: nat
l: list A
e, e': length l = n

⟨ l | e ⟩ = ⟨ l | e' ⟩
A: Type
n: nat
l: list A
e, e': length l = n

e = e'
A: Type
l: list A
e: length l = length l

e = eq_refl
apply K. Qed. 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 }. Fixpoint to_list {A n} (v : vec A n) : list A := match v with | vnil => [] | vcons a v => a :: to_list v end.

forall (A : Type) (n : nat) (v : vec A n), length (to_list v) = n

forall (A : Type) (n : nat) (v : vec A n), length (to_list v) = n
A: Type
n: nat
v: vec A n

length (to_list v) = n
A: Type

length (to_list vnil) = 0
A: Type
a: A
n: nat
v: vec A n
ih: length (to_list v) = n
length (to_list (vcons a v)) = S n
A: Type

length (to_list vnil) = 0
reflexivity.
A: Type
a: A
n: nat
v: vec A n
ih: length (to_list v) = n

length (to_list (vcons a v)) = S n
exact (f_equal S ih). Defined.
to_vec_equation_1 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
to_vec_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
to_vec_graph_correct has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
to_vec_elim has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining

From K we can eliminate useless transports.


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

transport e t = t
A: Type
u: A
e: u = u
P: A -> Type
t: P u

transport eq_refl t = t
reflexivity. Qed.

Now we prove that transport commutes with vcons.


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)
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)
A: Type
n: nat
e: S n = S n
a: A
v: vec A n

transport e (vcons a v) = vcons a (transport eq_refl v)
A: Type
n: nat
e: S n = S n
a: A
v: vec A n

transport e (vcons a v) = vcons a v
A: Type
n: nat
e: S n = S n
a: A
v: vec A n

vcons a v = vcons a v
reflexivity. Qed.

forall (A : Type) (n : nat), equiv (vec A n) (ilist A n)

forall (A : Type) (n : nat), equiv (vec A n) (ilist A n)
A: Type
n: nat

equiv (vec A n) (ilist A n)
A: Type
n: nat
v: vec A n

length (to_list v) = n
A: Type
n: nat
pat: {l : list A | length l = n}
l: list A
e: (fun l : list A => length l = n) l
length l = n
A: Type
n: nat
forall a : vec A n, transport ?Goal0@{pat:=⟨ to_list a | ?Goal@{v:=a} ⟩; l:=to_list a; e:=?Goal@{v:=a}} (to_vec (to_list a)) = a
A: Type
n: nat
forall b : {l : list A | length l = n}, ⟨ to_list (let '⟨ l | e ⟩ := b in transport ?Goal0@{pat:=b} (to_vec l)) | ?Goal@{v:=let '⟨ l | e ⟩ := b in transport ?Goal0@{pat:=b} (to_vec l)} ⟩ = b
A: Type
n: nat
v: vec A n

length (to_list v) = n
apply length_to_list.
A: Type
n: nat
pat: {l : list A | length l = n}
l: list A
e: (fun l : list A => length l = n) l

length l = n
apply e.
A: Type
n: nat

forall a : vec A n, transport (length_to_list A n a) (to_vec (to_list a)) = a
A: Type
n: nat
v: vec A n

transport (length_to_list A n v) (to_vec (to_list v)) = v
A: Type

transport (length_to_list A 0 vnil) (to_vec (to_list vnil)) = vnil
A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = v
transport (length_to_list A (S n) (vcons a v)) (to_vec (to_list (vcons a v))) = vcons a v
A: Type

transport (length_to_list A 0 vnil) (to_vec (to_list vnil)) = vnil
A: Type

vnil = vnil
reflexivity.
A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = v

transport (length_to_list A (S n) (vcons a v)) (to_vec (to_list (vcons a v))) = vcons a v
A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = v

transport (f_equal S (length_to_list A n v)) (vcons a (to_vec (to_list v))) = vcons a v
A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = v

transport (f_equal S (length_to_list A n v)) (vcons a (to_vec (to_list v))) = vcons a v
A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = v

vcons a (transport ?e' (to_vec (to_list v))) = vcons a v
A: Type
a: A
n: nat
v: vec A n
ih: transport (length_to_list A n v) (to_vec (to_list v)) = v

transport ?e' (to_vec (to_list v)) = v
eassumption.
A: Type
n: nat

forall b : {l : list A | length l = n}, ⟨ to_list (let '⟨ l | e ⟩ := b in transport e (to_vec l)) | length_to_list A n (let '⟨ l | e ⟩ := b in transport e (to_vec l)) ⟩ = b
A: Type
n: nat
l: list A
e: length l = n

⟨ to_list (transport e (to_vec l)) | length_to_list A n (transport e (to_vec l)) ⟩ = ⟨ l | e ⟩
A: Type
n: nat
l: list A
e: length l = n

proj1_sig ⟨ to_list (transport e (to_vec l)) | length_to_list A n (transport e (to_vec l)) ⟩ = proj1_sig ⟨ l | e ⟩
A: Type
n: nat
l: list A
e: length l = n

to_list (transport e (to_vec l)) = l
A: Type
l: list A

to_list (transport eq_refl (to_vec l)) = l
A: Type
l: list A

to_list (to_vec l) = l
A: Type
Heqcall: vnil = to_vec []

to_list vnil = []
A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)
to_list (vcons a (to_vec l)) = a :: l
A: Type
Heqcall: vnil = to_vec []

to_list vnil = []
reflexivity.
A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)

to_list (vcons a (to_vec l)) = a :: l
A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)

to_list (vcons a (to_vec l)) = a :: l
A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)

a :: to_list (to_vec l) = a :: l
A: Type
a: A
l: list A
H: to_list (to_vec l) = l
Heqcall: vcons a (to_vec l) = to_vec (a :: l)

to_list (to_vec l) = l
assumption. Defined.

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_equation_2 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_equation_2 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_equation_2 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eval_equation_3 has type-checked, generating 1 obligation
Solving obligations automatically...
No more obligations remaining
eval_equation_4 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:

= nlam (tunit ~> tunit) (nlam tunit (sapp (svar (finS fin0)) (svar fin0))) : normal vnil ((tunit ~> tunit) ~> tunit ~> tunit)
= nlam tunit (svar fin0) : normal vnil (tunit ~> tunit)
= nstar : normal vnil tunit