(*|
--------------------------------
Dependent functional programming
--------------------------------

:Authors: Yannick Forster, Théo Winterhalter
:Files:
  - `Source <../files/lesson6_part1.v>`_
  - `Exercise sheet <../files/tp6.v>`_
  - `Exercise solutions <tp6c.html>`_

.. role:: coq(code)
   :language: coq
   :class: highlight

.. default-role:: coq

.. contents:: Table of Contents
   :depth: 2
   :local:

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

(*| .. coq:: none |*)

Axiom REPLACE_ME : forall {A : Type}, A.

Set Warnings "-non-recursive".

(*| |*)

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

Fail Fixpoint merge (l1 l2 : list nat) :=
  match l1, l2 with
  | x :: l1, y :: l2 =>
    if x <=? y then
      x :: merge l1 (y :: l2)
    else
      y :: merge (x :: l1) l2
  | l1, [] => l1
  | [], l2 => l2
  end.

(*|
We are going to load Equations to help deal with it nicely.
|*)

From Equations Require Import Equations.

Equations? merge (l1 l2 : list nat) : list nat
  by wf (length l1 + length l2) lt :=
  merge l1 [] := l1 ;
  merge [] l2 := l2 ;
  merge (x :: l1) (y :: l2) with le_dec x y := {
  | left _ => x :: merge l1 (y :: l2)
  | right _ => y :: merge (x :: l1) l2
  }.
Proof.
  lia.
Qed.

(*|
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`.

.. note::

  In Equations, `=>` and `:=` for clauses are mostly interchangeable, so pick
  the one you prefer or mix the two as you like.

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Decidable equality for <code class="coq highlight">nat</code></summary>

..
|*)

(*|
Define a Boolean equality test using Equations.
|*)
Equations eq_nat (n m : nat) : bool :=
  eq_nat n m := REPLACE_ME.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^
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.
Extraction merge.

(*|
^^^^^^^^^^^^^^^^^^^^
Reasoning principles
^^^^^^^^^^^^^^^^^^^^

Equations actually proves more stuff for us when defining new functions.
For instance it gives us useful functional induction principles.
|*)

Lemma merge_In x l1 l2 :
  In x (merge l1 l2) <-> In x l1 \/ In x l2.
Proof.
  eapply merge_elim.
  all: firstorder congruence.
Qed.

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

.. note::

  There is no question mark here because there is nothing to prove (like
  termination above).

..
|*)

Equations neg (b : bool) : bool :=
  neg true := false ;
  neg false := true.

(*|
See all the things it generated about `neg`.
|*)

Search 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`.
|*)

About neg_elim.

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

Lemma neg_inv :
  forall b,
    neg (neg b) = b.
Proof.
  intros [].
  - simp neg. reflexivity.
  - simp neg. reflexivity.
Abort.

(*|
.. caution::

  The tactic is called `simp` and not `simpl`.

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

Lemma neg_inv :
  forall b,
    neg (neg b) = b.
Proof.
  Transparent neg. (* To tell Rocq it's ok to unfold it. *)
  (* Without it [cbn] below does nothing. *)
  intros []. all: cbn. 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`).
|*)

Lemma neg_inv :
  forall b,
    neg (neg b) = b.
Proof.
  intro b. pattern b, (neg b).
  apply neg_elim.
  - simp neg. reflexivity.
  - 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.
|*)

Lemma neg_inv :
  forall b,
    neg (neg b) = b.
Proof.
  intros b.
  funelim (neg b).
  all: reflexivity.
Qed.

(*|
Equations syntax is quite permissive and allows us to use notations.
|*)

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

Equations app {A} (l l' : list A) : list A := {
  [] +++ l' := l' ;
  (a :: l) +++ l' := a :: (l +++ l')
}
where "x +++ y" := (app x y).

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
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.
|*)

Lemma app_ind :
  forall A (P : list A -> list A -> list A -> Prop),
    (forall l', P [] l' l') ->
    (forall a l l', P l l' (l +++ l') -> P (a :: l) l' (a :: (l +++ l'))) ->
    forall l l', P l l' (l +++ l').
Proof.
  intros A P hnil hcons l l'.
  induction l as [| a l ih] in l' |- *.
  - apply hnil.
  - eapply hcons. eapply ih.
Qed.

(*|
The one Equations generated is very similar.
|*)

About app_elim.

(*| Once again we apply it using `funelim`. |*)

Lemma app_assoc {A} (x y z : list A) :
  x +++ y +++ z = (x +++ y) +++ z.
Proof.
  funelim (x +++ y).
  - auto.
  - simp app. rewrite H. (* [H] is the induction hypothesis. *)
    reflexivity.
Qed.

Lemma app_nil_r {A} (l : list A) :
 l +++ [] = l.
Proof.
  funelim (l +++ []).
  - reflexivity.
  - simp app. rewrite H. reflexivity.
Qed.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Specification of <code class="coq highlight">eq_nat</code></summary>

..
|*)

(*|
Prove the following two lemmas specifying your `eq_nat` using `funelim`.
|*)

Lemma eq_nat_eq {n m} :
  eq_nat n m = true -> n = m.
Proof.
Admitted.

Lemma neq_nat_neq {n m} :
  eq_nat n m = false -> n <> m.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^^^
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`.
|*)

Equations filter {A} (l : list A) (p : A -> bool) : list A :=
  filter [] p := [] ;
  filter (a :: l) p with p a => {
  | true => a :: filter l p ;
  | false => filter l p
  }.

(*|
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`.
|*)

Lemma filter_true {A} (l : list A) :
  filter l (fun x => true) = l.
Proof.
  funelim (filter l (fun _ => true)).
  - (* [l = []] *) reflexivity.
  - (* [l = (a :: l)] and [(fun x => true) a = true] *)
    rewrite H. reflexivity.
  - (* [l = (a :: l)] and [(fun x => true) a = false] *)
    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.

.. warning::

  Some editors (like VsCoq Legacy) don't tell you about obligations so be
  careful to check that you don't have unresolved obligations. The easiest
  way is to always use `Equations?`.

..

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

Equations equal (n m : nat) : { n = m } + { n <> m } :=
  equal O O := left eq_refl ;
  equal (S n) (S m) with equal n m := {
    equal (S n) (S ?(n)) (left eq_refl) := left eq_refl ;
    equal (S n) (S m) (right p) := right _
  } ;
  equal x y := right _.

(*|
You can also extract programs written with Equations and it looks reasonable.
|*)
Extraction equal.

(*|
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.

  Equations split_two {A : Type} (l : list A) : list (A * A) by wf (length l) lt :=
    split_two [] := [] ;
    split_two [a] := [] ;
    split_two (a :: b :: l) := (a, b) :: split_two 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.
|*)

  Next Obligation.
    cbn. lia.
  Qed.

End SplitTwo.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Convoy pattern</summary>

..
|*)

(*|
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`?
|*)
Lemma eq_dec :
  forall (n m : nat), { n = m } + { n <> m }.
Proof.
  intros n m.
  destruct (eq_nat n m) eqn: e.
  - left. apply eq_nat_eq. assumption.
  - right. apply neq_nat_neq. assumption.
Qed.

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

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^
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.
|*)

Print head.

(*|
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.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Head and tail of vectors</summary>

..
|*)

(*|
.. important::

  This exercise has you redo exactly what is in the lecture notes.
  Try to forget about the answer for a minute and come up with the answer
  yourself.

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.

(*|
.. raw:: html

   </details>

..
|*)

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

Fail Fixpoint zip {A B n} (v : vec A n) (v' : vec B n) : vec (A * B) n :=
  match v, v' with
  | vnil, vnil => vnil
  | vcons a v, vcons b v' => vcons (a, b) (zip v v')
  end.

(*|
Thankfully, Equations knows how to do it!
|*)

Equations zip {A B n} (v : vec A n) (v' : vec B n) : vec (A * B) n :=
  zip vnil vnil := vnil ;
  zip (vcons a v) (vcons b v') := vcons (a, b) (zip v v').

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

Print zip.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: <code class="coq highlight">zip</code> by hand</summary>

..
|*)

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

.. tip::

  Your `match` on the first vector will need to return a function that
  expects the other vector as argument.

  You may also use `hd` and `tl` on the second vector.

..
|*)

Fixpoint zip' {A B n} (v : vec A n) (w : vec B n) : vec (A * B) n :=
  REPLACE_ME.

(*|
.. raw:: html

   </details>

..
|*)

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

Equations vnth {A n} (v : vec A n) (x : fin n) : A :=
  vnth (vcons a v) fin0 := a ;
  vnth (vcons a v) (finS x) := vnth v x.

(*|
We now have tools to reason about such dependent types.
The `dependent elimination` tactic is like `destruct` but it takes the index
into account!
|*)

Lemma vec_expand A n (v : vec A (S n)) :
  v = vcons (head v) (tail v).
Proof.
  dependent elimination 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`.

.. tip::

  Equations will typically output a warning telling you
  the command to write.

..
|*)

Derive Signature NoConfusion NoConfusionHom for fin.
Derive NoConfusion for vec.

Lemma zip_vnth A B n (v : vec A n) (v' : vec B n) (x : fin n) :
  vnth (zip v v') x = (vnth v x, vnth v' x).
Proof.
  funelim (vnth v x). (* Notice how both v and x are destructed at once. *)
  - dependent elimination v'.
    simp zip vnth. reflexivity.
  - dependent elimination v'.
    simp zip vnth. (* Sometimes [simp] will also solve the goal. *)
Qed.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Repeat</summary>

..
|*)

(*|
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`.
|*)

Equations repeat {A} (a : A) (n : nat) : vec A n :=
  repeat a n := REPLACE_ME.

Lemma repeat_ind :
  REPLACE_ME.
Proof.
Admitted.

Lemma vnth_repeat A (a : A) n m :
  vnth (repeat a n) m = a.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Map</summary>

..
|*)

(*|
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`.
|*)

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Reversing a vector</summary>

..
|*)

(*|
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`.

.. tip::

  You can use underscores `_` to tell Equations to try and solve a missing
  goal automatically; if it doesn't solve it, it will produce an obligation to
  solve interactively.
  This works a bit like `refine`.
  Alternatively use `Equations?` to directly open proof mode.

..

.. note::

  We give you the `transport` operation which basically gives you `rewrite` in
  proof terms. More on this in the equality lecture.

..
|*)

Definition transport {A} {P : A -> Type} {u v} (e : u = v) : P u -> P v :=
  match e with
  | eq_refl => fun x => x
  end.

Fail Equations rev_acc {A n m} (v : vec A n) (acc : vec A m) : vec A (n + m) :=
  rev_acc vnil acc := acc ;
  rev_acc (vcons a v) acc := rev_acc v (vcons a acc).

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Vectors as subset types</summary>

..
|*)

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

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^^^^^^^^^^
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…
|*)

Check test. (* The type has been computed for us! *)

(*|
We cannot write terms that are ill-typed in STLC, such as applying `tstar` to
itself.
|*)

Fail Definition test' : term vnil _ :=
  tapp tstar tstar.

(*|
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:
|*)

Equations extend {n E A} (ρ : valuation (n := n) E) (a : interp_type A) : valuation (vcons A E) :=
  extend ρ a fin0 := a ;
  extend ρ a (finS x) := ρ x.

(*|
We are now ready to interpret terms!
|*)

Equations interp {n E A} (t : term (n := n) E A) (rho : valuation E) : interp_type A :=
  interp (tvar x) rho := rho x ;
  interp  tstar rho := tt ;
  interp (tlam A (B := B) b) rho := fun x => interp b (extend rho x) ;
  interp (tapp u v) rho := (interp u rho) (interp v rho).

(*|
We can test on a few examples and see them get normalised.
|*)

Eval compute in interp (test tunit tunit) rho0.

Eval compute in interp (tapp (test _ _) (test tunit tunit)) rho0.

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Normal forms</summary>

..
|*)

(*|
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`.

.. tip::

  It might be useful to first show that there is no stuck term in the
  empty environment.

..
|*)

Inductive normal {n} (E : env n) : type -> Type :=
| nstar : normal E tunit
| nlam (A : type) B (b : normal (vcons A E) B) : normal E (A ~> B)
| nstuck A (s : stuck E A) :> normal E A

with stuck {n} (E : env n) : type -> Type :=
| svar (x : fin n) : stuck E (vnth E x)
| sapp A B (f : stuck E (A ~> B)) (u : normal E A) : stuck E B.

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

Derive NoConfusion for type.

Lemma lam_inv :
  REPLACE_ME.
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
^^^^^^^^^^^^^^^^^^
Advanced exercises
^^^^^^^^^^^^^^^^^^

The following exercises are more advanced.
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Vectors and subset types are equivalent</summary>

..
|*)

(*|
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.

Lemma ilist_eq :
  forall A n (l l' : ilist A n),
    proj1_sig l = proj1_sig l' ->
    l = l'.
Proof.
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
}.

Lemma transportK :
  forall A (u : A) (e : u = u) (P : A -> Type) (t : P u),
    transport e t = t.
Proof.
Admitted.

Lemma transport_vcons :
  forall A n m e e' a (v : vec A n),
    transport e (vcons a v) = vcons a (n := m) (transport e' v).
Proof.
Admitted.

Lemma equiv_ilist :
  forall A n,
    equiv (vec A n) (ilist A n).
Proof.
Admitted.

(*|
.. raw:: html

   </details>

..
|*)

(*|
.. raw:: html

   <details class="exercise"><summary>Exercise: Normalisation by evaluation</summary>

..
|*)

(*|
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) }.

Equations? xren {n m E F} A (r : @ren n m E F) : ren (vcons A E) (vcons A F) :=
  xren A ⟨ r ⟩ := ⟨ fun x => _ ⟩.
Proof.
  - dependent elimination x.
    + apply fin0.
    + apply finS, r, x.
  - dependent elimination x.
    + cbn. simp vnth. reflexivity.
    + cbn. simp vnth.
Defined.

Equations idren {n E} : ren (n := n) E E :=
  idren := ⟨ fun x => x ⟩.

Equations? rencomp {n m k E F G} (r : @ren n m E F) (r' : ren (m := k) F G) : ren E G :=
  rencomp ⟨ r | h ⟩ ⟨ r' | h' ⟩ := ⟨ fun x => r' (r x) ⟩.
Proof.
  rewrite h, h'. reflexivity.
Defined.

Equations weak {n E A} : ren (n := n) E (vcons A E) :=
  weak := ⟨ fun x => finS x ⟩.

Equations nren {A n m E F} (r : @ren n m E F) (s : normal E A) : normal F A by struct s := {
  nren r nstar := nstar ;
  nren r (nlam A b) := nlam A (nren (xren _ r) b) ;
  nren r (nstuck s) := sren r s
}
where sren {A n m E F} (r : @ren n m E F) (s : stuck E A) : stuck F A by struct s := {
  sren ⟨ r | h ⟩ (svar x) := transport _ (svar (r x)) ;
  sren r (sapp f u) := sapp (sren r f) (nren r u)
}.

Equations sem {n} (E : env n) (A : type) : Type :=
  sem E tunit := normal E tunit ;
  sem E (A ~> B) := forall m F (r : ren (m := m) E F), sem F A -> sem F B.

(*|
Semantic valuation:
|*)

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

Equations semren {n m E F A} (r : @ren n m E F) (s : sem E A) : sem F A :=
  semren r s := REPLACE_ME.

Equations renval {n m k E F G} (rho : @sval n m E F) (r : ren (m := k) F G) : sval E G :=
  renval rho r x := REPLACE_ME.

Equations sextend {n m A} {E : env n} {F : env m} (rho : sval E F) (a : sem F A) : sval (vcons A E) F :=
  sextend rho a x := REPLACE_ME.

Equations eval {n m A} {E : env n} {F : env m} (t : term E A) (rho : sval E F) : sem F A :=
  eval t rho := REPLACE_ME.

Equations reify {n A} {E : env n} (s : sem E A) : normal E A := {
  reify (A := tunit) s := s ;
  reify (A := A ~> B) f := nlam A (reify (f _ _ weak (reflect (svar fin0))))
}
where reflect {n A} {E : env n} (s : stuck E A) : sem E A := {
  reflect (A := tunit) s := nstuck s ;
  reflect (A := A ~> B) s := fun m G r a => reflect (sapp (sren r s) (reify a))
}.

Equations idval {n E} : sval (n := n) E E :=
  idval x := REPLACE_ME.

Equations nbe {n E A} (t : @term n E A) : normal E A :=
  nbe t := reify (eval t idval).

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

(*|
.. raw:: html

   </details>

..
|*)
