Exercise session 4 — Modelling and automation — Solutions

Authors:

Yannick Forster

Théo Winterhalter

Files:
Set Default Goal Selector "!".

Set Default Goal Selector "!".

(* From the lecture: *)

From Stdlib Require Import Lia List ZArith.
Import ListNotations.

Record prod' (A B : Type) := mkpair {
  fst' : A ;
  snd' : B
}.

Arguments mkpair {A B}.

Definition to_prod {A B} (p : prod' A B) : A * B :=
  match p with
  | mkpair a b => (a, b)
  end.

Arguments fst' {A B}.
Arguments snd' {A B}.

Definition to_prod_alt3 {A B} (p : prod' A B) : A * B :=
  (fst' p, snd' p).

Exercise: Projections

Show that to_prod and to_prod_alt3 produce the same result.


forall (A B : Type) (p : prod' A B), to_prod p = to_prod_alt3 p

forall (A B : Type) (p : prod' A B), to_prod p = to_prod_alt3 p
A, B: Type
p: prod' A B

to_prod p = to_prod_alt3 p
A, B: Type
a: A
b: B

to_prod {| fst' := a; snd' := b |} = to_prod_alt3 {| fst' := a; snd' := b |}
reflexivity. Qed. (* From the lecture: *) Record monoid := { m_ty : Type ; m_ne : m_ty ; m_op : m_ty -> m_ty -> m_ty ; m_l_ne : forall x, m_op m_ne x = x ; m_r_ne : forall x, m_op x m_ne = x ; m_assoc : forall x y z, m_op (m_op x y) z = m_op x (m_op y z) }. Notation "a ** b" := (m_op _ a b) (at level 11, left associativity).

forall (M : monoid) (x y : m_ty M), x ** m_ne M ** y = x ** y

forall (M : monoid) (x y : m_ty M), x ** m_ne M ** y = x ** y
M: monoid
x, y: m_ty M

x ** m_ne M ** y = x ** y

More complicated than necessary of course

  
M: monoid
x, y: m_ty M

x ** (m_ne M ** y) = x ** y
M: monoid
x, y: m_ty M

x ** y = x ** y
reflexivity. Qed.

Exercise: Groups as records

Define a record for groups, building on the record for monoids. Then show that monoid_fact also holds in groups.

monoid_fact : forall (M : monoid) (x y : m_ty M), x ** m_ne M ** y = x ** y
Record group := { g_mon : monoid ; g_inv : forall x : g_mon.(m_ty), exists y, x ** y = g_mon.(m_ne) /\ y ** x = g_mon.(m_ne) }.

forall (G : group) (x y : m_ty (g_mon G)), x ** m_ne (g_mon G) ** y = x ** y

forall (G : group) (x y : m_ty (g_mon G)), x ** m_ne (g_mon G) ** y = x ** y
G: group
x, y: m_ty (g_mon G)

x ** m_ne (g_mon G) ** y = x ** y
apply monoid_fact. Qed.

Exercise: Lists form a monoid

Show that lists form a monoid using ++ as operation. How does monoid_fact translate to lists? Note that, unlike ** or +, ++ associates to the right, meaning x ++ y ++ z stands for x ++ (y ++ z).

A: Type

monoid
A: Type

monoid
A: Type

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

forall x : list A, [] ++ x = x
A: Type
x: list A

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

x = x
reflexivity.
A: Type

forall x : list A, x ++ [] = x
A: Type
x: list A

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

x = x
reflexivity.
A: Type

forall 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
x, y, z: list A

(x ++ y) ++ z = (x ++ y) ++ z
reflexivity. Defined.

forall (A : Type) (x y : list A), (x ++ []) ++ y = x ++ y

forall (A : Type) (x y : list A), (x ++ []) ++ y = x ++ y
A: Type
x, y: list A

(x ++ []) ++ y = x ++ y
apply monoid_fact with (M := list_monoid A). Qed. (* From the lecture: *) Class Monoid (A : Type) (neu : A) (op : A -> A -> A) := { mon_left_neutral : forall x, op neu x = x ; mon_right_neutral : forall x, op x neu = x ; mon_assoc : forall x y z, op (op x y) z = op x (op y z) }.

Monoid nat 0 Init.Nat.add

Monoid nat 0 Init.Nat.add

forall x : nat, 0 + x = x

forall x : nat, x + 0 = x

forall x y z : nat, x + y + z = x + (y + z)

forall x : nat, 0 + x = x
x: nat

0 + x = x
reflexivity.

forall x : nat, x + 0 = x
x: nat

x + 0 = x
lia.

forall x y z : nat, x + y + z = x + (y + z)
x, y, z: nat

x + y + z = x + (y + z)
lia. Qed.

forall (M : Type) (neu : M) (op : M -> M -> M), Monoid M neu op -> forall k n m : M, op (op (op k n) m) neu = op k (op n m)

forall (M : Type) (neu : M) (op : M -> M -> M), Monoid M neu op -> forall k n m : M, op (op (op k n) m) neu = op k (op n m)
M: Type
neu: M
op: M -> M -> M
H: Monoid M neu op
k, n, m: M

op (op (op k n) m) neu = op k (op n m)
M: Type
neu: M
op: M -> M -> M
H: Monoid M neu op
k, n, m: M

op (op k n) m = op k (op n m)
M: Type
neu: M
op: M -> M -> M
H: Monoid M neu op
k, n, m: M

op k (op n m) = op k (op n m)
reflexivity. Qed.

Exercise: Product instance

Complete the product instance.


forall (A B : Type) (na : A) (nb : B) (opa : A -> A -> A) (opb : B -> B -> B), Monoid A na opa -> Monoid B nb opb -> Monoid (A * B) (na, nb) (fun '(xa, xb) '(ya, yb) => (opa xa ya, opb xb yb))

forall (A B : Type) (na : A) (nb : B) (opa : A -> A -> A) (opb : B -> B -> B), Monoid A na opa -> Monoid B nb opb -> Monoid (A * B) (na, nb) (fun '(xa, xb) '(ya, yb) => (opa xa ya, opb xb yb))
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb

Monoid (A * B) (na, nb) (fun '(xa, xb) '(ya, yb) => (opa xa ya, opb xb yb))
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb

forall x : A * B, (let '(ya, yb) := x in (opa na ya, opb nb yb)) = x
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
forall x : A * B, (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) (na, nb) = x
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
forall x y z : A * B, (let '(xa, xb) := (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) y in fun '(ya, yb) => (opa xa ya, opb xb yb)) z = (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) ((let '(xa, xb) := y in fun '(ya, yb) => (opa xa ya, opb xb yb)) z)
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb

forall x : A * B, (let '(ya, yb) := x in (opa na ya, opb nb yb)) = x
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
a: A
b: B

(opa na a, opb nb b) = (a, b)
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
a: A
b: B

(a, opb nb b) = (a, b)
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
a: A
b: B

(a, b) = (a, b)
reflexivity.
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb

forall x : A * B, (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) (na, nb) = x
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
a: A
b: B

(opa a na, opb b nb) = (a, b)
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
a: A
b: B

(a, opb b nb) = (a, b)
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
a: A
b: B

(a, b) = (a, b)
reflexivity.
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb

forall x y z : A * B, (let '(xa, xb) := (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) y in fun '(ya, yb) => (opa xa ya, opb xb yb)) z = (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) ((let '(xa, xb) := y in fun '(ya, yb) => (opa xa ya, opb xb yb)) z)
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
xa: A
xb: B
ya: A
yb: B
za: A
zb: B

(opa (opa xa ya) za, opb (opb xb yb) zb) = (opa xa (opa ya za), opb xb (opb yb zb))
A, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opb
xa: A
xb: B
ya: A
yb: B
za: A
zb: B

(opa xa (opa ya za), opb xb (opb yb zb)) = (opa xa (opa ya za), opb xb (opb yb zb))
reflexivity. Qed.

Exercise: Monoid instance for lists

Define an instance for lists and apply test_monoid to it. Then check that Rocq can now find a monoid structure on list bool * nat * list nat.

test_monoid : forall (M : Type) (neu : M) (op : M -> M -> M), Monoid M neu op -> forall k n m : M, op (op (op k n) m) neu = op k (op n m)

forall A : Type, Monoid (list A) [] (app (A:=A))

forall A : Type, Monoid (list A) [] (app (A:=A))
A: Type

Monoid (list A) [] (app (A:=A))
A: Type

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

forall x : list A, [] ++ x = x
A: Type
x: list A

[] ++ x = x
reflexivity.
A: Type

forall x : list A, x ++ [] = x
A: Type
x: list A

x ++ [] = x
apply app_nil_r.
A: Type

forall 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
x, y, z: list A

(x ++ y) ++ z = (x ++ y) ++ z
reflexivity. Qed.

forall (A : Type) (k n m : list A), ((k ++ n) ++ m) ++ [] = k ++ n ++ m

forall (A : Type) (k n m : list A), ((k ++ n) ++ m) ++ [] = k ++ n ++ m
A: Type
k, n, m: list A

((k ++ n) ++ m) ++ [] = k ++ n ++ m
A: Type
k, n, m: list A

Monoid (list A) [] (app (A:=A))
exact _. Qed. Definition bar : Monoid (list bool * nat * list nat) _ _ := _. (* From the lecture: *) Class Eq A := { eqb : A -> A -> bool ; eqb_iff : forall x y, eqb x y = true <-> x = y }. Fixpoint memb {A} `{Eq A} (x : A) (l : list A) : bool := match l with | [] => false | y :: l => eqb x y || memb x l end.

Exercise: Specification of memb

Give memb a specification using the In predicate and show it correct with respect to it.

memb : ?A -> list ?A -> bool where ?A : [ |- Type] ?H : [ |- Eq ?A]

forall (A : Type) (H : Eq A) (x : A) (l : list A), memb x l = true <-> In x l

forall (A : Type) (H : Eq A) (x : A) (l : list A), memb x l = true <-> In x l
A: Type
hA: Eq A
x: A
l: list A

memb x l = true <-> In x l
A: Type
hA: Eq A
x: A

memb x [] = true <-> In x []
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
memb x (a :: l) = true <-> In x (a :: l)
A: Type
hA: Eq A
x: A

memb x [] = true <-> In x []
A: Type
hA: Eq A
x: A

false = true <-> False
A: Type
hA: Eq A
x: A

false = true -> False
A: Type
hA: Eq A
x: A
False -> false = true
A: Type
hA: Eq A
x: A

false = true -> False
discriminate.
A: Type
hA: Eq A
x: A

False -> false = true
intros [].
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l

memb x (a :: l) = true <-> In x (a :: l)
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l

(eqb x a || memb x l)%bool = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = true

(true || memb x l)%bool = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
(false || memb x l)%bool = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = true

(true || memb x l)%bool = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = true

true = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: x = a

true = true <-> a = x \/ In x l
A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l

true = true <-> a = a \/ In a l
A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l

true = true -> a = a \/ In a l
A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l
a = a \/ In a l -> true = true
A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l

true = true -> a = a \/ In a l
A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l
H: true = true

a = a \/ In a l
A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l
H: true = true

a = a
reflexivity.
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false

(false || memb x l)%bool = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false

memb x l = true <-> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false

memb x l = true -> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
a = x \/ In x l -> memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false

memb x l = true -> a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
H: memb x l = true

a = x \/ In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
H: memb x l = true

In x l
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
H: memb x l = true

memb x l = true
assumption.
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false

a = x \/ In x l -> memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
bot: a = x

memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
h: In x l
memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
bot: a = x

memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
bot: x = a

memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
bot: eqb x a = true

memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: true = false
bot: eqb x a = true

memb x l = true
discriminate.
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
h: In x l

memb x l = true
A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = false
h: In x l

In x l
assumption. Qed.

Exercise: Groups as a class

Define a class of groups and show uniqueness of neutral and inverse for all groups.

Apply this result to a group of your choosing (you will have to provide an instance). To apply a lemma, sometimes apply is not enough. In this case you can use eapply which is more permissive. It creates existential variables (starting with a question mark) corresponding to values it couldn't guess. They are typically resolved as you prove the various goals.

Can you show that every group forms a monoid (again, provide a generic instance)?

Class Group A (ne : A) (op : A -> A -> A) := {
  group_left_neutral : forall x, op ne x = x ;
  group_right_neutral : forall x, op x ne = x ;
  group_assoc : forall x y z, op (op x y) z = op x (op y z) ;
  group_inv : forall x, exists y, op x y = ne /\ op y x = ne
}.


forall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> forall ne' : G, (forall x : G, op ne' x = x) -> (forall x : G, op x ne' = x) -> ne = ne'

forall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> forall ne' : G, (forall x : G, op ne' x = x) -> (forall x : G, op x ne' = x) -> ne = ne'
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
ne': G
hl: forall x : G, op ne' x = x
hr: forall x : G, op x ne' = x

ne = ne'
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
ne': G
hl: op ne' ne = ne
hr: forall x : G, op x ne' = x

ne = ne'
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
ne': G
hl: ne' = ne
hr: forall x : G, op x ne' = x

ne = ne'
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
hr: forall x : G, op x ne = x

ne = ne
reflexivity. Qed.

forall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> forall a b c : G, op a b = ne -> op b a = ne -> op a c = ne -> op c a = ne -> b = c

forall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> forall a b c : G, op a b = ne -> op b a = ne -> op a c = ne -> op c a = ne -> b = c
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
a, b, c: G
hbr: op a b = ne
hbl: op b a = ne
hcr: op a c = ne
hcl: op c a = ne

b = c
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
a, b, c: G
hbr: op c (op a b) = op c ne
hbl: op b a = ne
hcr: op a c = ne
hcl: op c a = ne

b = c
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
a, b, c: G
hbr: op (op c a) b = op c ne
hbl: op b a = ne
hcr: op a c = ne
hcl: op c a = ne

b = c
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
a, b, c: G
hbr: op ne b = op c ne
hbl: op b a = ne
hcr: op a c = ne
hcl: op c a = ne

b = c
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
a, b, c: G
hbr: b = op c ne
hbl: op b a = ne
hcr: op a c = ne
hcl: op c a = ne

b = c
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
a, b, c: G
hbr: b = c
hbl: op b a = ne
hcr: op a c = ne
hcl: op c a = ne

b = c
assumption. Qed.

Group Z 0%Z Z.add

Group Z 0%Z Z.add

forall x : Z, (0 + x)%Z = x

forall x : Z, (x + 0)%Z = x

forall x y z : Z, (x + y + z)%Z = (x + (y + z))%Z

forall x : Z, exists y : Z, (x + y)%Z = 0%Z /\ (y + x)%Z = 0%Z

forall x : Z, (0 + x)%Z = x
x: Z

(0 + x)%Z = x
lia.

forall x : Z, (x + 0)%Z = x
x: Z

(x + 0)%Z = x
lia.

forall x y z : Z, (x + y + z)%Z = (x + (y + z))%Z
x, y, z: Z

(x + y + z)%Z = (x + (y + z))%Z
lia.

forall x : Z, exists y : Z, (x + y)%Z = 0%Z /\ (y + x)%Z = 0%Z
x: Z

exists y : Z, (x + y)%Z = 0%Z /\ (y + x)%Z = 0%Z
x: Z

(x + - x)%Z = 0%Z /\ (- x + x)%Z = 0%Z
lia. Qed.

forall z : Z, (forall i : Z, (z + i)%Z = i) -> (forall i : Z, (i + z)%Z = i) -> z = 0%Z

forall z : Z, (forall i : Z, (z + i)%Z = i) -> (forall i : Z, (i + z)%Z = i) -> z = 0%Z
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i

z = 0%Z
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i

0%Z = z
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i

Group Z 0%Z ?op
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i
forall x : Z, ?op z x = x
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i
forall x : Z, ?op x z = x
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i

forall x : Z, (z + x)%Z = x
z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i
forall x : Z, (x + z)%Z = x
all: assumption. Qed.

forall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> Monoid G ne op

forall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> Monoid G ne op
G: Type
ne: G
op: G -> G -> G
H: Group G ne op

Monoid G ne op
G: Type
ne: G
op: G -> G -> G
H: Group G ne op

forall x : G, op ne x = x
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
forall x : G, op x ne = x
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
forall x y z : G, op (op x y) z = op x (op y z)
G: Type
ne: G
op: G -> G -> G
H: Group G ne op

forall x : G, op ne x = x
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
x: G

op ne x = x
apply group_left_neutral.
G: Type
ne: G
op: G -> G -> G
H: Group G ne op

forall x : G, op x ne = x
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
x: G

op x ne = x
apply group_right_neutral.
G: Type
ne: G
op: G -> G -> G
H: Group G ne op

forall x y z : G, op (op x y) z = op x (op y z)
G: Type
ne: G
op: G -> G -> G
H: Group G ne op
x, y, z: G

op (op x y) z = op x (op y z)
apply group_assoc. Qed. (* From the lecture: *)

forall (A : Type) (x : A) (l : list A), In x (x :: l)

forall (A : Type) (x : A) (l : list A), In x (x :: l)
A: Type
x: A
l: list A

In x (x :: l)
A: Type
x: A
l: list A

x = x \/ In x l
auto. Qed.

forall (A : Type) (x y : A) (l : list A), In x l -> In x (y :: l)

forall (A : Type) (x y : A) (l : list A), In x l -> In x (y :: l)
A: Type
x, y: A
l: list A
h: In x l

In x (y :: l)
A: Type
x, y: A
l: list A
h: In x l

y = x \/ In x l
auto. Qed. Create HintDb indb. #[export] Hint Resolve In_hd : indb. #[export] Hint Resolve In_hd : core.

Exercise: Extending the hint database

Expand the database so that auto with indb is enough to solve the following goals.

Recall the following lemmas from the lecture.

In_hd : forall (A : Type) (x : A) (l : list A), In x (x :: l)
In_tl : forall (A : Type) (x y : A) (l : list A), In x l -> In x (y :: l)
#[export] Hint Resolve In_tl : indb.

forall (A : Type) (x a b c d : A) (l : list A), In x l -> In x (a :: b :: c :: d :: l)

forall (A : Type) (x a b c d : A) (l : list A), In x l -> In x (a :: b :: c :: d :: l)
auto with indb. Qed.

forall (A : Type) (x a b c d : A) (l : list A), In x (a :: b :: x :: c :: d :: l)

forall (A : Type) (x a b c d : A) (l : list A), In x (a :: b :: x :: c :: d :: l)
auto with indb. Qed.

Exercise: Membership in concatenations

Show that In x l implies In x (l ++ r) and that In x r implies In x (l ++ r).

Now add both lemmas to indb. For the first time, we are introducing a choice for auto: presented with the goal In x (l ++ r) it has to choose whether to go left or right. It has no way to know in advance which one is better so it will pick one and backtrack if it doesn't work.

Use it to solve the following two goals.


forall (A : Type) (x : A) (l r : list A), In x l -> In x (l ++ r)

forall (A : Type) (x : A) (l r : list A), In x l -> In x (l ++ r)
A: Type
x: A
l, r: list A
h: In x l

In x (l ++ r)
A: Type
x: A
r: list A
h: In x []

In x ([] ++ r)
A: Type
x, y: A
l, r: list A
h: In x (y :: l)
ih: forall r : list A, In x l -> In x (l ++ r)
In x ((y :: l) ++ r)
A: Type
x: A
r: list A
h: In x []

In x ([] ++ r)
A: Type
x: A
r: list A
h: False

In x ([] ++ r)
contradiction.
A: Type
x, y: A
l, r: list A
h: In x (y :: l)
ih: forall r : list A, In x l -> In x (l ++ r)

In x ((y :: l) ++ r)
A: Type
x, y: A
l, r: list A
h: In x (y :: l)
ih: forall r : list A, In x l -> In x (l ++ r)

y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: y = x \/ In x l
ih: forall r : list A, In x l -> In x (l ++ r)

y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: y = x
ih: forall r : list A, In x l -> In x (l ++ r)

y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: In x l
ih: forall r : list A, In x l -> In x (l ++ r)
y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: y = x
ih: forall r : list A, In x l -> In x (l ++ r)

y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: y = x
ih: forall r : list A, In x l -> In x (l ++ r)

y = x
assumption.
A: Type
x, y: A
l, r: list A
h: In x l
ih: forall r : list A, In x l -> In x (l ++ r)

y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: In x l
ih: forall r : list A, In x l -> In x (l ++ r)

In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: In x l
ih: forall r : list A, In x l -> In x (l ++ r)

In x l
assumption. Qed.

forall (A : Type) (x : A) (l r : list A), In x r -> In x (l ++ r)

forall (A : Type) (x : A) (l r : list A), In x r -> In x (l ++ r)
A: Type
x: A
l, r: list A
h: In x r

In x (l ++ r)
A: Type
x: A
r: list A
h: In x r

In x ([] ++ r)
A: Type
x, y: A
l, r: list A
h: In x r
ih: forall r : list A, In x r -> In x (l ++ r)
In x ((y :: l) ++ r)
A: Type
x: A
r: list A
h: In x r

In x ([] ++ r)
A: Type
x: A
r: list A
h: In x r

In x r
assumption.
A: Type
x, y: A
l, r: list A
h: In x r
ih: forall r : list A, In x r -> In x (l ++ r)

In x ((y :: l) ++ r)
A: Type
x, y: A
l, r: list A
h: In x r
ih: forall r : list A, In x r -> In x (l ++ r)

y = x \/ In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: In x r
ih: forall r : list A, In x r -> In x (l ++ r)

In x (l ++ r)
A: Type
x, y: A
l, r: list A
h: In x r
ih: forall r : list A, In x r -> In x (l ++ r)

In x r
assumption. Qed. #[export] Hint Resolve In_app_l : indb. #[export] Hint Resolve In_app_r : indb.

forall (A : Type) (x a b c d : A) (l l' : list A), In x l -> In x ([a; b; c] ++ l' ++ d :: l)

forall (A : Type) (x a b c d : A) (l l' : list A), In x l -> In x ([a; b; c] ++ l' ++ d :: l)
auto with indb. Qed.

forall (A : Type) (x a b c d : A) (l l' : list A), In x l -> In x (l ++ [a; b; c] ++ l' ++ [d])

forall (A : Type) (x a b c d : A) (l l' : list A), In x l -> In x (l ++ [a; b; c] ++ l' ++ [d])
auto with indb. Qed.

Exercise: Equal elements

What if the element in my list is not syntactically what I'm looking for but only equal to it?

Prove a lemma for this particular case and add a hint for it. It should solve the following goal.


forall (A : Type) (x y : A) (l : list A), x = y -> In x (y :: l)

forall (A : Type) (x y : A) (l : list A), x = y -> In x (y :: l)
A: Type
x, y: A
l: list A
e: x = y

In x (y :: l)
A: Type
x, y: A
l: list A
e: x = y

y = x \/ In x l
auto. Qed. #[export] Hint Resolve In_hd_eq : indb.

forall (A : Type) (x y a b c d : A) (l l' : list A), x = y -> In x ([a; b; c] ++ l' ++ d :: y :: l)

forall (A : Type) (x y a b c d : A) (l l' : list A), x = y -> In x ([a; b; c] ++ l' ++ d :: y :: l)
auto with indb. Qed. (* From the lecture: *) Axiom DNE : forall P : Prop, ~~ P -> P. From Stdlib Require Import Classical.

Exercise: The arith database

The equality in the exercise "Equal elements" is not always going to be an assumption in the context. But it could be handled by some more automation. There is for instance the arith database that can deal with arithmetic.

You can give two (or more) databases to auto. Check that it indeed succeeds in the following goal with arith but not without.


forall (a b c d : nat) (l l' : list nat), In (a + b) ([b; c] ++ l' ++ d :: b + a :: l)

forall (a b c d : nat) (l l' : list nat), In (a + b) ([b; c] ++ l' ++ d :: b + a :: l)

forall (a b c d : nat) (l l' : list nat), In (a + b) ([b; c] ++ l' ++ d :: b + a :: l)
auto with indb arith. Qed.

Exercise: Limits of arith

Sadly, it has its limits: check that it isn't sufficient for the following goal even though you should be able to prove it (do it).


forall (a b c d : nat) (l l' : list nat), In (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)

forall (a b c d : nat) (l l' : list nat), In (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)
a, b, c, d: nat
l, l': list nat

In (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)
a, b, c, d: nat
l, l': list nat

In (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)
a, b, c, d: nat
l, l': list nat

In (a + b + c) (l' ++ d :: c + 0 + a + b :: l)
a, b, c, d: nat
l, l': list nat

In (a + b + c) (d :: c + 0 + a + b :: l)
a, b, c, d: nat
l, l': list nat

In (a + b + c) (c + 0 + a + b :: l)
a, b, c, d: nat
l, l': list nat

a + b + c = c + 0 + a + b
lia. Qed.

Exercise: Using lia in auto (advanced)

There is a way to use lia with auto actually. For this we have to provide a different kind of hint. Using the command Hint Extern we can tell Rocq what tactic to try when encountering a goal of the form n = m where n, m : nat.

Below what we do is say that when the goal is of the shape @eq nat _ _ then we apply lia. We add this to indb. The 3 is something called cost. auto is actually cost-based and each action it takes has a cost attached to it. auto will start by picking the actions with the lowest cost when it has a choice. When it runs out of money, it gives up.

Check that you can solve the previous goal using auto with indb. Can you also make it so that the other goal works?

#[export] Hint Extern 3 (@eq nat _ _) => lia : indb.


forall (a b c d : nat) (l l' : list nat), In (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)

forall (a b c d : nat) (l l' : list nat), In (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)
auto with indb. Qed. #[export] Hint Extern 3 (@eq Z _ _) => lia : indb.

forall (a b c d : Z) (l l' : list Z), In (a + b + c)%Z ([a; b; c] ++ l' ++ d :: (c + d + 0 + a - d + b)%Z :: l)

forall (a b c d : Z) (l l' : list Z), In (a + b + c)%Z ([a; b; c] ++ l' ++ d :: (c + d + 0 + a - d + b)%Z :: l)
auto with indb. Qed.

Exercise: Existential variables

Solve the following goal without using any lemma or variable in the context explicitly.


forall (A : Type) (x : A) (l l' : list A), exists y : A, In y (l ++ x :: l')

forall (A : Type) (x : A) (l l' : list A), exists y : A, In y (l ++ x :: l')
A: Type
x: A
l, l': list A

exists y : A, In y (l ++ x :: l')
A: Type
x: A
l, l': list A

In ?y (l ++ x :: l')
auto with indb. Qed.

Exercise: eauto

Solve the following goal.


forall (A : Type) (P : A -> A -> Prop) (Q : A -> Prop), (forall x : A, exists y : A, P x y) -> (forall x y : A, P x y -> Q x) -> forall x : A, Q x

forall (A : Type) (P : A -> A -> Prop) (Q : A -> Prop), (forall x : A, exists y : A, P x y) -> (forall x y : A, P x y -> Q x) -> forall x : A, Q x
A: Type
P: A -> A -> Prop
Q: A -> Prop
h1: forall x : A, exists y : A, P x y
h2: forall x y : A, P x y -> Q x
x: A

Q x
A: Type
P: A -> A -> Prop
Q: A -> Prop
h2: forall x y : A, P x y -> Q x
x, y: A
h1: P x y

Q x
eauto. Qed.

Exercise: Logical equivalences (advanced)

Another interesting feature of Rocq is the ability to rewrite on other things rather than just equality.

For instance, we can use rewrite for logical equivalences. Let us go through it step by step.

To begin, prove the following logical equivalences.


forall A : Prop, A /\ A <-> A

forall A : Prop, A /\ A <-> A
A: Prop

A /\ A <-> A
A: Prop

A /\ A -> A
A: Prop
A -> A /\ A
A: Prop

A /\ A -> A
A: Prop
H, H0: A

A
auto.
A: Prop

A -> A /\ A
auto. Qed.

forall A : Prop, A \/ A <-> A

forall A : Prop, A \/ A <-> A
A: Prop

A \/ A <-> A
A: Prop

A \/ A -> A
A: Prop
A -> A \/ A
A: Prop

A \/ A -> A
A: Prop
H: A

A
A: Prop
H: A
A
all: auto.
A: Prop

A -> A \/ A
auto. Qed.

forall A B : Prop, A /\ B <-> B /\ A

forall A B : Prop, A /\ B <-> B /\ A
A, B: Prop

A /\ B <-> B /\ A
A, B: Prop

A /\ B -> B /\ A
A, B: Prop
B /\ A -> A /\ B
all: intros [] ; auto. Qed.

forall A B : Prop, A \/ B <-> B \/ A

forall A B : Prop, A \/ B <-> B \/ A
A, B: Prop

A \/ B <-> B \/ A
A, B: Prop

A \/ B -> B \/ A
A, B: Prop
B \/ A -> A \/ B
all: intros [] ; auto. Qed.

forall A B C : Prop, (A /\ B) /\ C <-> A /\ B /\ C

forall A B C : Prop, (A /\ B) /\ C <-> A /\ B /\ C
A, B, C: Prop

(A /\ B) /\ C <-> A /\ B /\ C
A, B, C: Prop

(A /\ B) /\ C -> A /\ B /\ C
A, B, C: Prop
A /\ B /\ C -> (A /\ B) /\ C
A, B, C: Prop

(A /\ B) /\ C -> A /\ B /\ C
A, B, C: Prop
H: A
H0: B
H1: C

A /\ B /\ C
auto.
A, B, C: Prop

A /\ B /\ C -> (A /\ B) /\ C
A, B, C: Prop
H: A
H0: B
H1: C

(A /\ B) /\ C
auto. Qed.

Exercise: Rewriting with equivalences (advanced)

Now you can solve the following goals just by using rewrite on equivalences. No more need for split!

Note that you can also use reflexivity, symmetry and transitivity on those. Under the hood, this is using class resolution to find the proper instances. For iff (logical equivalence) they are already registered so we can freely use them.


forall A B C D : Prop, A /\ (B /\ B) /\ (C -> D) /\ (C -> D) <-> A /\ B /\ (C -> D)

forall A B C D : Prop, A /\ (B /\ B) /\ (C -> D) /\ (C -> D) <-> A /\ B /\ (C -> D)
A, B, C, D: Prop

A /\ (B /\ B) /\ (C -> D) /\ (C -> D) <-> A /\ B /\ (C -> D)
A, B, C, D: Prop

A /\ B /\ (C -> D) <-> A /\ B /\ (C -> D)
reflexivity. Qed.

forall A B : Prop, B /\ A /\ B \/ A /\ B <-> B /\ A

forall A B : Prop, B /\ A /\ B \/ A /\ B <-> B /\ A
A, B: Prop

B /\ A /\ B \/ A /\ B <-> B /\ A
A, B: Prop

B /\ B /\ A \/ B /\ A <-> B /\ A
A, B: Prop

(B /\ B) /\ A \/ B /\ A <-> B /\ A
A, B: Prop

B /\ A \/ B /\ A <-> B /\ A
A, B: Prop

B /\ A <-> B /\ A
reflexivity. Qed.

Exercise: Set equality on lists (advanced)

Ok, this is getting old. We're going to switch to another relation which isn't already registered in the standard library. First we're going to introduce a relation on lists that relates two lists if they have the same elements (regardless of how many times they appear), i.e., if they represent the same set.

Complete the following definition.

Definition list_set_eq {A} (u v : list A) : Prop :=
  forall x, In x u <-> In x v.

Notation "u ~ v" := (list_set_eq u v) (at level 70).

We first need to show that the relation is reflexive, symmetric and transitive. We do so by instantiating the right classes so that we can use the corresponding tactics (as for iff).

Check it works with the provided goal.

From Stdlib Require Import Setoid.


forall A : Type, Reflexive list_set_eq

forall A : Type, Reflexive list_set_eq
A: Type

Reflexive list_set_eq
A: Type
l: list A

l ~ l
A: Type
l: list A
x: A

In x l <-> In x l
reflexivity. Qed.

forall A : Type, Symmetric list_set_eq

forall A : Type, Symmetric list_set_eq
A: Type

Symmetric list_set_eq
A: Type
u, v: list A
h: u ~ v

v ~ u
A: Type
u, v: list A
h: u ~ v
x: A

In x v <-> In x u
A: Type
u, v: list A
h: u ~ v
x: A

In x u <-> In x v
apply h. Qed.

forall A : Type, Transitive list_set_eq

forall A : Type, Transitive list_set_eq
A: Type

Transitive list_set_eq
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w

u ~ w
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: A

In x u <-> In x w
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: A

In x u <-> ?y
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: A
?y <-> In x w
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: A

In x u <-> ?y
eapply h1.
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: A

In x v <-> In x w
apply h2. Qed.

forall (A : Type) (u v w : list A), v ~ u -> (u ~ u -> v ~ w) -> u ~ w

forall (A : Type) (u v w : list A), v ~ u -> (u ~ u -> v ~ w) -> u ~ w
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w

u ~ w
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w

u ~ ?y
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w
?y ~ w
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w

u ~ ?y
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w

?y ~ u
eassumption.
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w

v ~ w
A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w

u ~ u
reflexivity. Qed.

Exercise: Rewriting with set equality (advanced)

We will use the following command to register this relation to use with rewrite. Rocq will find the instances of equivalence relation we provided above. Otherwise we could provide them manually. Look up the documentation if you want to do that: https://rocq-prover.org/doc/master/refman/addendum/generalized-rewriting.html

On the left of the colon we give the list of parameters, here there is only one which is the type of values. We call it A and we can refer to it after the colon. The next argument is the type of elements we compare with the relation: list A. Then we give the relation itself: list_set_eq. Finally we give a name to the setoid relation. This is for Rocq's internal use.

Prove the following goal using rewrite. This is just transitivity again but this is to show you how it works on a simple example.

Add Parametric Relation A : (list A) list_set_eq as list_set_rel.


forall (A : Type) (u v w : list A), u ~ v -> v ~ w -> u ~ w

forall (A : Type) (u v w : list A), u ~ v -> v ~ w -> u ~ w
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w

u ~ w
A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w

v ~ w
assumption. Qed.

Prove that u ++ v ~ v ++ u.


forall (A : Type) (l r : list A) (x : A), In x (l ++ r) -> In x l \/ In x r

forall (A : Type) (l r : list A) (x : A), In x (l ++ r) -> In x l \/ In x r
A: Type
l, r: list A
x: A
h: In x (l ++ r)

In x l \/ In x r
A: Type
r: list A
x: A
h: In x ([] ++ r)

In x [] \/ In x r
A: Type
a: A
l, r: list A
x: A
h: In x ((a :: l) ++ r)
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r
In x (a :: l) \/ In x r
A: Type
r: list A
x: A
h: In x ([] ++ r)

In x [] \/ In x r
A: Type
r: list A
x: A
h: In x r

False \/ In x r
auto.
A: Type
a: A
l, r: list A
x: A
h: In x ((a :: l) ++ r)
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r

In x (a :: l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: a = x \/ In x (l ++ r)
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r

(a = x \/ In x l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: a = x
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r

(a = x \/ In x l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: In x (l ++ r)
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r
(a = x \/ In x l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: a = x
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r

(a = x \/ In x l) \/ In x r
eauto with indb.
A: Type
a: A
l, r: list A
x: A
h: In x (l ++ r)
ih: forall r : list A, In x (l ++ r) -> In x l \/ In x r

(a = x \/ In x l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: In x (l ++ r)
ih: In x l \/ In x r

(a = x \/ In x l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: In x (l ++ r)
H: In x l

(a = x \/ In x l) \/ In x r
A: Type
a: A
l, r: list A
x: A
h: In x (l ++ r)
H: In x r
(a = x \/ In x l) \/ In x r
all: auto with indb. Qed.

forall (A : Type) (u v : list A), u ++ v ~ v ++ u

forall (A : Type) (u v : list A), u ++ v ~ v ++ u
A: Type
u, v: list A

u ++ v ~ v ++ u
A: Type
u, v: list A
x: A

In x (u ++ v) <-> In x (v ++ u)
A: Type
u, v: list A
x: A

In x (u ++ v) -> In x (v ++ u)
A: Type
u, v: list A
x: A
In x (v ++ u) -> In x (u ++ v)
A: Type
u, v: list A
x: A
h: In x u \/ In x v

In x (v ++ u)
A: Type
u, v: list A
x: A
h: In x v \/ In x u
In x (u ++ v)
A: Type
u, v: list A
x: A
H: In x u

In x (v ++ u)
A: Type
u, v: list A
x: A
H: In x v
In x (v ++ u)
A: Type
u, v: list A
x: A
H: In x v
In x (u ++ v)
A: Type
u, v: list A
x: A
H: In x u
In x (u ++ v)
all: auto with indb. Qed.

Exercise: Morphisms (advanced)

In order to rewrite this relation inside, e.g., In, we have to first show that In is invariant under ~. In other words, that u ~ v implies In x u <-> In x v. We can use the following command to declare it. This will in turn let us rewrite inside In.

Prove that we indeed have a morphism. Prove the given goals using rewrite.

A: Type
x: A

forall x0 y : list A, x0 ~ y -> In x x0 <-> In x y
A: Type
x: A

forall x0 y : list A, x0 ~ y -> In x x0 <-> In x y
A: Type
x: A
u, v: list A
e: u ~ v

In x u <-> In x v
apply e. Qed.

forall (A : Type) (x : A) (u v : list A), In x (u ++ v) -> In x (v ++ u)

forall (A : Type) (x : A) (u v : list A), In x (u ++ v) -> In x (v ++ u)
A: Type
x: A
u, v: list A
h: In x (u ++ v)

In x (v ++ u)
A: Type
x: A
u, v: list A
h: In x (u ++ v)

In x (u ++ v)
assumption. Qed.

forall (A : Type) (x a b c : A) (u v : list A), In x (u ++ [a; b; c] ++ x :: v)

forall (A : Type) (x a b c : A) (u v : list A), In x (u ++ [a; b; c] ++ x :: v)
A: Type
x, a, b, c: A
u, v: list A

In x (u ++ [a; b; c] ++ x :: v)
A: Type
x, a, b, c: A
u, v: list A

In x (([a; b; c] ++ x :: v) ++ u)
A: Type
x, a, b, c: A
u, v: list A

In x ([a; b; c] ++ (x :: v) ++ u)
A: Type
x, a, b, c: A
u, v: list A

In x (((x :: v) ++ u) ++ [a; b; c])
A: Type
x, a, b, c: A
u, v: list A

In x ((x :: v) ++ u ++ [a; b; c])
A: Type
x, a, b, c: A
u, v: list A

x = x \/ In x (v ++ u ++ [a; b; c])
auto. Qed.

Look up the Forall predicate. Show that it is a morphism for list_set_eq. Proceed to solve the following goal.


forall (A : Type) (P : A -> Prop) (l : list A), Forall P l <-> (forall x : A, In x l -> P x)

forall (A : Type) (P : A -> Prop) (l : list A), Forall P l <-> (forall x : A, In x l -> P x)
A: Type
P: A -> Prop
l: list A

Forall P l <-> (forall x : A, In x l -> P x)
A: Type
P: A -> Prop

Forall P [] <-> (forall x : A, In x [] -> P x)
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
Forall P (x :: l) <-> (forall x0 : A, In x0 (x :: l) -> P x0)
A: Type
P: A -> Prop

Forall P [] <-> (forall x : A, In x [] -> P x)
A: Type
P: A -> Prop

Forall P [] -> forall x : A, In x [] -> P x
A: Type
P: A -> Prop
(forall x : A, In x [] -> P x) -> Forall P []
A: Type
P: A -> Prop

Forall P [] -> forall x : A, In x [] -> P x
A: Type
P: A -> Prop

Forall P [] -> forall x : A, False -> P x
intros _ _ [].
A: Type
P: A -> Prop

(forall x : A, In x [] -> P x) -> Forall P []
A: Type
P: A -> Prop

Forall P []
constructor.
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)

Forall P (x :: l) <-> (forall x0 : A, In x0 (x :: l) -> P x0)
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)

Forall P (x :: l) -> forall x0 : A, In x0 (x :: l) -> P x0
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
(forall x0 : A, In x0 (x :: l) -> P x0) -> Forall P (x :: l)
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)

Forall P (x :: l) -> forall x0 : A, In x0 (x :: l) -> P x0
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
ha: In a (x :: l)

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
ha: In a (x :: l)
x0: A
l0: list A
H1: P x
H2: Forall P l
H: x0 = x
H0: l0 = l

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
ha: In a (x :: l)
H1: P x
H2: Forall P l

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
ha: x = a \/ In a l
H1: P x
H2: Forall P l

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
e: x = a
H1: P x
H2: Forall P l

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
hl: In a l
H1: P x
H2: Forall P l
P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
e: x = a
H1: P x
H2: Forall P l

P a
A: Type
P: A -> Prop
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
a: A
h: Forall P (a :: l)
H1: P a
H2: Forall P l

P a
assumption.
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
hl: In a l
H1: P x
H2: Forall P l

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
hl: In a l
H1: P x
H2: Forall P l

Forall P l
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: Forall P (x :: l)
a: A
hl: In a l
H1: P x
H2: Forall P l
In a l
all: assumption.
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)

(forall x0 : A, In x0 (x :: l) -> P x0) -> Forall P (x :: l)
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0

Forall P (x :: l)
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0

P x
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0
Forall P l
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0

P x
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0

In x (x :: l)
auto with indb.
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0

Forall P l
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0

forall x0 : A, In x0 l -> P x0
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0
a: A
ha: In a l

P a
A: Type
P: A -> Prop
x: A
l: list A
ih: Forall P l <-> (forall x : A, In x l -> P x)
h: forall x0 : A, In x0 (x :: l) -> P x0
a: A
ha: In a l

In a (x :: l)
auto with indb. Qed.

forall (A : Type) (P : A -> Prop) (u v : list A), u ~ v -> Forall P u -> Forall P v

forall (A : Type) (P : A -> Prop) (u v : list A), u ~ v -> Forall P u -> Forall P v
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: Forall P u

Forall P v
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: forall x : A, In x u -> P x

forall x : A, In x v -> P x
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: forall x : A, In x u -> P x
x: A
hx: In x v

P x
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: forall x : A, In x u -> P x
x: A
hx: In x u

P x
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: forall x : A, In x u -> P x
x: A
hx: In x u

In x u
assumption. Qed.
A: Type
P: A -> Prop

forall x y : list A, x ~ y -> Forall P x <-> Forall P y
A: Type
P: A -> Prop

forall x y : list A, x ~ y -> Forall P x <-> Forall P y
A: Type
P: A -> Prop
u, v: list A
e: u ~ v

Forall P u <-> Forall P v
A: Type
P: A -> Prop
u, v: list A
e: u ~ v

Forall P u -> Forall P v
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
Forall P v -> Forall P u
A: Type
P: A -> Prop
u, v: list A
e: u ~ v

u ~ v
A: Type
P: A -> Prop
u, v: list A
e: u ~ v
v ~ u
A: Type
P: A -> Prop
u, v: list A
e: u ~ v

u ~ v
auto.
A: Type
P: A -> Prop
u, v: list A
e: u ~ v

v ~ u
A: Type
P: A -> Prop
u, v: list A
e: u ~ v

u ~ v
auto. Qed.

forall u v w : list nat, let P := fun n : nat => exists m : nat, n = 2 * m in Forall P (w ++ u ++ v) -> Forall P (u ++ v ++ w)

forall u v w : list nat, let P := fun n : nat => exists m : nat, n = 2 * m in Forall P (w ++ u ++ v) -> Forall P (u ++ v ++ w)
u, v, w: list nat
P:= fun n : nat => exists m : nat, n = 2 * m: nat -> Prop
h: Forall P (w ++ u ++ v)

Forall P (u ++ v ++ w)
u, v, w: list nat
P:= fun n : nat => exists m : nat, n = 2 * m: nat -> Prop
h: Forall P (w ++ u ++ v)

Forall P ((v ++ w) ++ u)
u, v, w: list nat
P:= fun n : nat => exists m : nat, n = 2 * m: nat -> Prop
h: Forall P (w ++ u ++ v)

Forall P (v ++ w ++ u)
u, v, w: list nat
P:= fun n : nat => exists m : nat, n = 2 * m: nat -> Prop
h: Forall P (w ++ u ++ v)

Forall P ((w ++ u) ++ v)
u, v, w: list nat
P:= fun n : nat => exists m : nat, n = 2 * m: nat -> Prop
h: Forall P (w ++ u ++ v)

Forall P (w ++ u ++ v)
assumption. Qed.

Exercise: Backtracking

For each of the following scripts, predict without running Rocq whether it succeeds, and which goal remains or which witness is chosen. Then check your answer, using Show Proof to see the witness.

The try are only there so that the file compiles whatever the answer.


exists b : bool, negb b = true

exists b : bool, negb b = true
try (unshelve eexists ; constructor). Abort.

exists n : nat, n = 1

exists n : nat, n = 1
try (unshelve eexists ; constructor). Abort.

True \/ (False -> False)

True \/ (False -> False)
x: False

False
Abort.

True \/ (False -> False)

True \/ (False -> False)

True

True
Abort.

(False -> False) \/ True

(False -> False) \/ True
try (constructor ; exact I). Abort.

Answers:

  1. It succeeds with b := false: constructor first picks true, but then true = false cannot be proven by constructor, so it backtracks.

  2. It succeeds with n := 1: 0 = 1 fails, so constructor picks S ?m instead, and proving S ?m = 1 with eq_refl instantiates ?m := 0.

  3. Only the goal False remains, with x : False: intro x fails on True, so constructor backtracks and picks the right disjunct.

  4. The goal True remains: constructor picks the left disjunct, and backtracking does not go back across sentences (.), so intro x just fails and try hides the failure.

  5. It succeeds with or_intror I: exact I fails on False -> False, so constructor backtracks to the right disjunct.

    (* From the lecture: *)
    
    Inductive mult4 : nat -> Prop :=
    | mult4_0 : mult4 0
    | mult4_plus n : mult4 n -> mult4 (4 + n).
    
    Inductive not_mult4 : nat -> Prop :=
    | not_mult4_1 : not_mult4 1
    | not_mult4_2 : not_mult4 2
    | not_mult4_3 : not_mult4 3
    | not_mult4_plus n : not_mult4 n -> not_mult4 (4 + n).

Exercise: Tacticals

Prove each of the following goals with a single sentence, that is one tactic expression ending with a single . after Proof.. Combine ;, [ ... | ... ], .., try, solve, repeat and do.


mult4 12 /\ not_mult4 7 /\ mult4 0 /\ not_mult4 10

mult4 12 /\ not_mult4 7 /\ mult4 0 /\ not_mult4 10
repeat split ; repeat constructor. Qed.

forall n : nat, not_mult4 n -> not_mult4 (8 + n)

forall n : nat, not_mult4 n -> not_mult4 (8 + n)
intros n h ; do 2 apply not_mult4_plus ; exact h. Qed.

forall n : nat, n < 3 -> not_mult4 (n + 1)

forall n : nat, n < 3 -> not_mult4 (n + 1)
intros n h ; destruct n as [| [| [| n]]] ; [ constructor .. | exfalso ; lia ]. Qed.

forall n : nat, mult4 n -> mult4 (n + 4)

forall n : nat, mult4 n -> mult4 (n + 4)
intros n h ; induction h ; [ constructor ; constructor | simpl ; constructor ; assumption ]. Qed. Ltac split_or_apply := match goal with | |- ?A /\ ?B => split | h : ?B -> ?A |- ?A => apply h (* Here we match on any hypothesis *) (* The name [h] is of our choosing, it's going to apply to hypothesis [H : nat -> bool] for instance. *) end. Ltac my_assumption := match goal with | H : ?A |- ?A => apply H end.

Exercise: Repeated split

Define a tactic splits to perform split repeatedly on goals of the shape A * B but not on any other kinds of goals (for instance it should not solve True).

For instance, on (nat * bool) * (unit * bool) it should yield 4 subgoals.

Ltac splits :=
  lazymatch goal with
  | |- ?A * ?B => split ; splits
  | _ => idtac
  end.

Try it on these goals.


nat * bool

nat * bool

nat

bool
Abort.

nat * (bool * unit) * (unit * nat * bool) * unit

nat * (bool * unit) * (unit * nat * bool) * unit

nat

bool

unit

unit

nat

bool

unit
Abort.

Exercise: Clearing before induction

Prove the following by induction on n. In particular, don't use lia: we want you to use the induction hypothesis.


forall n : nat, n mod 14 = 7 -> n - n = 0

forall n : nat, n mod 14 = 7 -> n - n = 0
n: nat
hn: n mod 14 = 7

n - n = 0
n: nat

n - n = 0

0 - 0 = 0
n: nat
IHn: n - n = 0
S n - S n = 0

0 - 0 = 0
reflexivity.
n: nat
IHn: n - n = 0

S n - S n = 0
n: nat
IHn: n - n = 0

n - n = 0
eauto. Qed. Ltac handle_hyp h := lazymatch type of h with | (?A * ?B)%type => destruct h | nat => induction h | _ => idtac end.

Exercise: Forward reasoning

A very useful tactic that should be part of the standard library, but is not, is the fwd tactic. Given H : P -> Q, fwd H will yield two goals:

  • one where P must be proven

  • and one where H has been replaced by H : Q

Note that there shouldn't be anything else appearing in the goal.

Define such a tactic.

Ltac fwd h :=
  match type of h with
  | ?P -> _ =>
    let h' := fresh in
    assert (h' : P) ; [| specialize (h h') ; clear h' ]
  end.

Try on the following goal. Do not use apply, only intros, fwd and assumption.


forall P Q R : Type, (P -> Q -> R) -> (P -> Q) -> P -> R

forall P Q R : Type, (P -> Q -> R) -> (P -> Q) -> P -> R
P, Q, R: Type
h1: P -> Q -> R
h2: P -> Q
h3: P

R
P, Q, R: Type
h1: P -> Q -> R
h2: P -> Q
h3: P

P
P, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: P
R
P, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: P

R
P, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: P

P
P, Q, R: Type
h1: Q -> R
h2: Q
h3: P
R
P, Q, R: Type
h1: Q -> R
h2: Q
h3: P

R
P, Q, R: Type
h1: Q -> R
h2: Q
h3: P

Q
P, Q, R: Type
h1: R
h2: Q
h3: P
R
P, Q, R: Type
h1: R
h2: Q
h3: P

R
assumption. Qed.

Exercise: Forward reasoning with a tactic (harder)

Try to generalise the code for fwd so that you can also provide a tactic. If H : P -> Q then forward_gen H tac will also apply tac to try and solve the goal P first.

Ltac forward_gen h tac :=
  match type of h with
  | ?P -> _ =>
    let h' := fresh in
    assert (h' : P) ; [ tac | specialize (h h') ; clear h' ]
  end.

Once forward_gen is defined, we define handy notations: Tactic Notation "forward" constr(H) := forward_gen H ltac:(idtac). and Tactic Notation "forward" constr(H) "by" tactic(tac) := forward_gen H tac.

Tactic Notation "forward" constr(H) := forward_gen H ltac:(idtac).
Tactic Notation "forward" constr(H) "by" tactic(tac) := forward_gen H tac.


forall P Q R : Type, (P -> Q -> R) -> (P -> Q) -> P -> R

forall P Q R : Type, (P -> Q -> R) -> (P -> Q) -> P -> R
P, Q, R: Type
h1: P -> Q -> R
h2: P -> Q
h3: P

R
P, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: P

R
P, Q, R: Type
h1: R
h2: Q
h3: P

R
assumption. Qed.

Exercise: A tauto tactic

Write a tactic my_tauto that solves the following goals. You can start from the following, and expand it: Ltac my_tauto := lazymatch goal with | |- True => constructor end.

Ltac my_tauto :=
  lazymatch goal with
  | h : ?P |- ?P => exact h

  | |- True => constructor
  | |- _ /\ _ => split ; my_tauto
  | |- _ -> _ => intro ; my_tauto

  | h : False |- _ => destruct h
  | h : _ /\ _ |- _ => destruct h ; my_tauto
  | h : _ \/ _ |- _ => destruct h ; my_tauto

  | h1 : ?P -> ?Q, h2 : ?P |- _ => specialize (h1 h2) ; my_tauto

  | |- _ \/ _ => (left ; my_tauto) || (right ; my_tauto)
  end.

Section Tauto.

  Variables (P Q R : Prop).

  
P, Q, R: Prop

P -> True /\ True
P, Q, R: Prop

P -> True /\ True
my_tauto. Qed.
P, Q, R: Prop

P -> P
P, Q, R: Prop

P -> P
my_tauto. Qed.
P, Q, R: Prop

P -> (P -> R) -> R
P, Q, R: Prop

P -> (P -> R) -> R
my_tauto. Qed.
P, Q, R: Prop

False \/ True
P, Q, R: Prop

False \/ True
my_tauto. Qed.
P, Q, R: Prop

(P \/ Q \/ False) /\ (P -> Q) -> True /\ (R \/ Q)
P, Q, R: Prop

(P \/ Q \/ False) /\ (P -> Q) -> True /\ (R \/ Q)
my_tauto. Qed. End Tauto. (* From the lecture: *) Require Import MetaRocqPrelude. Axiom LEM : forall (P : Prop), P \/ ~ P. Axiom funext : forall A B (f g : A -> B), (forall x, f x = g x) -> f = g.

(fun n : nat => n + 0) = (fun n : nat => n)

(fun n : nat => n + 0) = (fun n : nat => n)

forall x : nat, x + 0 = x
x: nat

x + 0 = x
x: nat

x = x
reflexivity. Qed.

Exercise: Print Assumptions

Define a Rocq function assumptions : global_env × term -> list kername such that Compute assumptions ($quote_rec f) returns the list of assumptions (axioms) that f depends on, including recursively.

Note: You cannot convince Rocq that it is terminating, so we'll deactivate termination checking. That's ok when meta-programming.

Unset Guard Checking.
Fixpoint assms (env : global_env) (t : term) {struct t} : list kername :=
  match t with
  | tConst c u =>
      match lookup_constant env c with
      | Some body =>
          match body.(cst_body) with
          | None => [c]
          | Some c => assms env c
          end
      | _ => []
      end
  | tRel _ | tVar _ | tSort _ | tInd _ _ | tConstruct _ _ _ | tInt _ | tFloat _ | tString _ => []
  | tEvar ev args => flat_map (assms env) args
  | tCast t kind v => assms env t ++ assms env v
  | tProd na ty body => assms env ty ++ assms env body
  | tLambda na ty body => assms env ty ++ assms env body
  | tLetIn na def def_ty body => assms env def ++ assms env def_ty ++ assms env body
  | tApp f args => assms env f ++ flat_map (assms env) args
  | tCase ci type_info discr branches =>
      assms env discr ++ flat_map (fun b => assms env b.(bbody)) branches
  | tProj proj t => assms env t
  | tFix mfix idx => flat_map (fun d => assms env d.(dbody)) mfix
  | tCoFix mfix idx => flat_map (fun d => assms env d.(dbody)) mfix
  | tArray u arr def ty => flat_map (assms env) arr ++ assms env def ++ assms env ty
  end.
Set Guard Checking.

Definition assumptions p :=
  assms p.1 p.2.

= [] : list kername
Fetching opaque proofs from disk for Corelib.Init.Peano
= [(MPfile ["tp4c"], "funext")] : list kername
Definition bar_ax : nat := let x := foo_ax in 139.
= [(MPfile ["tp4c"], "funext")] : list kername
Module test.
P: Prop

~ ~ P -> P
P: Prop

~ ~ P -> P
tauto. Qed. End test.
Fetching opaque proofs from disk for Stdlib.Logic.Classical_Prop
= [(MPfile ["Classical_Prop"; "Logic"; "Stdlib"], "classic")] : list kername
Definition more_deps := (bar_ax, test.DNE, LEM).
= [(MPfile ["tp4c"], "funext"); (MPfile ["Classical_Prop"; "Logic"; "Stdlib"], "classic"); (MPfile ["tp4c"], "LEM")] : list kername

Exercise: Folding multiply-add

Define a function which replaces any subterm of the form a * b + c with muladd a b c defined below.

Definition muladd a b c :=
  a * b + c.

#[bypass_check(guard)] Fixpoint fold_muladd (t : term) : term :=
  match t with
  | tApp p ([ tApp m [ a ; b ] ; c ] as args) =>
      if (p == $quote plus) && (m == $quote mult)
      then tApp ($quote muladd) [ fold_muladd a ; fold_muladd b ; fold_muladd c ]
      else tApp (fold_muladd p) (map fold_muladd args)
  | tApp f args => tApp (fold_muladd f) (map fold_muladd args)
  | tRel n => tRel n
  | tVar id => tVar id
  | tEvar ev args => tEvar ev (map fold_muladd args)
  | tSort s => tSort s
  | tCast t kind v => tCast (fold_muladd t) kind (fold_muladd v)
  | tProd na ty body => tProd na (fold_muladd ty) (fold_muladd body)
  | tLambda na ty body => tLambda na (fold_muladd ty) (fold_muladd body)
  | tLetIn na def def_ty body => tLetIn na (fold_muladd def) (fold_muladd def_ty) (fold_muladd body)
  | tConst c u => tConst c u
  | tInd ind u => tInd ind u
  | tConstruct ind idx u => tConstruct ind idx u
  | tCase ind p discr brs =>
      let p' := map_predicate id fold_muladd fold_muladd p in
      let brs' := map_branches fold_muladd brs in
      tCase ind p' (fold_muladd discr) brs'
  | tProj proj t => tProj proj (fold_muladd t)
  | tFix mfix idx => tFix (map (map_def fold_muladd fold_muladd) mfix) idx
  | tCoFix mfix idx => tCoFix (map (map_def fold_muladd fold_muladd) mfix) idx
  | tInt i => tInt i
  | tFloat f => tFloat f
  | tString s => tString s
  | tArray u arr def ty => tArray u (map fold_muladd arr) (fold_muladd def) (fold_muladd ty)
  end.

Test it with the following.

muladd 3 2 5 : nat
1 + muladd 3 2 5 : nat
muladd (muladd 9 2 0) (1 + muladd 3 2 5) 1 + muladd 3 2 5 : nat

Exercise: Folding multiply-add with transform

Now that you suffered through the definition of fold_muladd, define it again using transform. transform takes h : tm_handler and transforms t : term into another term. The handler is typically of the form fun t k => ... where t is the subterm to inspect/transform and k is a continuation. Calling k on a subterm (or on t itself) gives control back to transform which will decompose the subterm once, and then call the handler again on the subsequent subterms.

Definition muladd_handler : tm_handler :=
  fun t k =>
    match t with
    | tApp p [ tApp m [ a ; b ] ; c ] =>
      if (p == $quote plus) && (m == $quote mult)
      then k (tApp ($quote muladd) [ a ; b ; c ])
      else k t
    | _ => k t
    end.

Definition fold_muladd_alt :=
  transform muladd_handler.

muladd 3 2 5 : nat
1 + muladd 3 2 5 : nat
muladd (muladd 9 2 0) (1 + muladd 3 2 5) 1 + muladd 3 2 5 : nat

If you want, you can also do the same for assumptions by using tm_fold which is similar but implements a fold instead.

Definition assum_fold (env : global_env) : fold_handler (list kername) :=
  fun t a k =>
    match t with
    | tConst c u =>
        match lookup_constant env c with
        | Some body =>
            match body.(cst_body) with
            | None => c :: a
            | Some c => k a c
            end
        | _ => []
        end
    | _ => k a t
    end.

Definition assumptions_alt p : list kername :=
  tm_fold (assum_fold p.1) [] p.2.

= [] : list kername
= [(MPfile ["tp4c"], "funext")] : list kername
= [(MPfile ["tp4c"], "funext")] : list kername
= [(MPfile ["Classical_Prop"; "Logic"; "Stdlib"], "classic")] : list kername

Exercise: Reification

Write a command reify that turns a Rocq expression of type nat into an expression of the following datatype. Expressions that do not start with + or * are reified as constants.

Inductive arith :=
| aPlus : arith -> arith -> arith
| aTimes : arith -> arith -> arith
| aConst : nat -> arith.

#[bypass_check(guard)] Fixpoint reify (t : term) : term :=
  match t with
  | tApp c [ u ; v ] =>
      if c == $quote plus then tApp ($quote aPlus) [ reify u ; reify v ]
      else if c == $quote mult then tApp ($quote aTimes) [ reify u ; reify v ]
      else tApp ($quote aConst) [t]
  | _n => tApp ($quote aConst) [t]
  end.


4 * (9 + 12) + (3 + 1 * 7) = 2

4 * (9 + 12) + (3 + 1 * 7) = 2
a:= aPlus (aTimes (aConst 4) (aPlus (aConst 9) (aConst 12))) (aPlus (aConst 3) (aTimes (aConst 1) (aConst 7))): arith

4 * (9 + 12) + (3 + 1 * 7) = 2
Abort.

Exercise: Instantiating axioms (advanced)

Write a meta-program that takes a definition potentially using an axiom and a proof of said axiom to produce a new definition, equal to the original one except that uses of the axiom are replaced by the proof.

The axiom to be replaced is going to be given as a kername, like those collected by assumptions. You don't actually have to verify that the constant is indeed an axiom.

Definition instantiate_axiom (ax : kername) (prf : term) : term -> term :=
  transform (fun t k =>
    match t with
    | tConst c u =>
      if eq_constant ax c then prf
      else k t
    | _ => k t
    end
  ).

Axiom mystery : nat.

Definition what :=
  mystery * 3.

= 30 : nat

Exercise: Removing axioms (advanced)

A slightly harder version would be to turn a definition using axioms to one assuming these axioms with an implication.

For instance, for the foo_ax defined above which uses funext, we would expect something of the following type: (forall A B (f g : A -> B), (forall x, f x = g x) -> f = g) -> (fun n => n + 0) = (fun n => n)

You can also use a variant of transform called transform_nb which also tracks the number of introduced variables (to know how much to lift by).

Definition replace_const_lift c u :=
  transform_nb (fun nb t k =>
    match t with
    | tConst c' ui =>
      if eq_constant c c' then (lift0 nb u)
      else k nb t
    | _ => k nb t
    end
  ) 0.

Definition unaxiom (p : global_env * term) : term :=
  let axs := assumptions p in
  fold_left (fun t ax =>
    match lookup_constant p.1 ax with
    | Some body =>
      let ty := body.(cst_type) in
      tLam "ax" ty (replace_const_lift ax (tRel 0) t)
    | None => t (* Something wrong, so we just let go *)
    end
  ) axs p.2.

= fun ax : nat => ax * 3 : nat -> nat
Axiom unknown : bool. Axiom random : nat -> nat. Definition test f := if unknown then what else random (f 9).
= fun (ax : nat -> nat) (_ : nat) (ax0 : bool) (f : nat -> nat) => if ax0 then what else ax (f 9) : (nat -> nat) -> nat -> bool -> (nat -> nat) -> nat

Exercise: Deriving (hard)

We promised MetaRocq could be used to derive automatically certain things. Let's see how this can be done by automatically deriving update functions for a record.

We assume that there is no dependency between the fields, otherwise it's unclear what an update function should do.

This exercise is hard, so it makes sense to make some assumptions first such as the absence of parameters (like in triple below) or of local definitions (like in trap below). Don't hesitate to ask questions if you are stuck.

We'll start with a few record definitions, together with one example of an update function, don't hesitate to write your own and quote them to understand what you need to write.

Record point3D := {
  px : nat ;
  py : nat ;
  pz : nat
}.

Record Zalt := {
  num : nat ;
  positive : bool
}.

Record triple A B C := {
  p1 : A ;
  p2 : B ;
  p3 : C
}.

Record trap := {
  v1 : nat ;
  v2 := 10 ^ v1 ;
  v3 : nat
}.

We write an update for num by hand.

Definition upd_num (f : nat -> nat) (x : Zalt) :=
  match x with
  | Build_Zalt num positive => Build_Zalt (f num) positive
  end.

Now we can look at how it is quoted.

We use $Quote rather than $quote to unfold the constant upd_num when quoting it. Otherwise we would get some tConst which is not as informative.

Definition q_upd_num := $Quote upd_num.
q_upd_num = tLam "f" (tProd {| binder_name := nAnon; binder_relevance := Relevant |} (tInd {| inductive_mind := (MPfile ["Datatypes"; "Init"; "Corelib"], "nat"); inductive_ind := 0 |} []) (tInd {| inductive_mind := (MPfile ["Datatypes"; "Init"; "Corelib"], "nat"); inductive_ind := 0 |} [])) (tLam "x" (tInd {| inductive_mind := (MPfile ["tp4c"], "Zalt"); inductive_ind := 0 |} []) (tCase {| ci_ind := {| inductive_mind := (MPfile ["tp4c"], "Zalt"); inductive_ind := 0 |}; ci_npar := 0; ci_relevance := Relevant |} {| puinst := []; pparams := []; pcontext := [{| binder_name := nNamed "x"; binder_relevance := Relevant |}]; preturn := tInd {| inductive_mind := (MPfile ["tp4c"], "Zalt"); inductive_ind := 0 |} [] |} (tRel 0) [{| bcontext := [{| binder_name := nNamed "positive"; binder_relevance := Relevant |}; {| binder_name := nNamed "num"; binder_relevance := Relevant |}]; bbody := tApp (tConstruct {| inductive_mind := (MPfile ["tp4c"], "Zalt"); inductive_ind := 0 |} 0 []) [tApp (tRel 3) [tRel 1]; tRel 0] |}])) : term

Below is a meta-program that gives you the definition of an inductive.

Definition get_inductive {A} (ind : A) :=
  t <- tmQuote ind ;;
  match t with
  | tInd ind _ =>
    let kn := ind.(inductive_mind) in
    tmQuoteInductive kn
  | _ => tmFail "Not an inductive type"
  end.

We use it like this to define Zalt_def to inspect at our leisure.

MetaRocq Run (
  mib <- get_inductive Zalt ;;
  tmDefinition "Zalt_def" mib
).

This now contains the definition of Zalt.

You may compare the information you see in here with what appeared in q_upd_num. It might be useful to copy paste them to better compare.

Zalt_def = {| ind_finite := BiFinite; ind_npars := 0; ind_params := []; ind_bodies := [{| ind_name := "Zalt"; ind_indices := []; ind_sort := sType (Universe.make' Level.lzero); ind_type := tSort (sType (Universe.make' Level.lzero)); ind_kelim := IntoAny; ind_ctors := [{| cstr_name := "Build_Zalt"; cstr_args := [{| decl_name := {| binder_name := nNamed "positive"; binder_relevance := Relevant |}; decl_body := None; decl_type := tInd {| inductive_mind := (MPfile ["Datatypes"; "Init"; "Corelib"], "bool"); inductive_ind := 0 |} [] |}; {| decl_name := {| binder_name := nNamed "num"; binder_relevance := Relevant |}; decl_body := None; decl_type := tInd {| inductive_mind := (MPfile ["Datatypes"; "Init"; "Corelib"], "nat"); inductive_ind := 0 |} [] |}]; cstr_indices := []; cstr_type := tPro "num" (tInd {| inductive_mind := (MPfile ["Datatypes"; "Init"; "Corelib"], "nat"); inductive_ind := 0 |} []) (tPro "positive" (tInd {| inductive_mind := (MPfile ["Datatypes"; "Init"; "Corelib"], "bool"); inductive_ind := 0 |} []) (tRel 2)); cstr_arity := 2 |}]; ind_projs := []; ind_relevance := Relevant |}]; ind_universes := Monomorphic_ctx; ind_variance := None |} : mutual_inductive_body

To help you build the derive_updates meta-program, we'll give you some useful tools.

Also check out the following useful constructs:

  • tmMkDefinition takes a string and a term and produces a definition using that name (if fresh, otherwise it fails) and unquoting the given term.

  • tmFreshName takes a string and will return a new string that is fresh in the current environment, based on the given one (typically by adding a number at the end).

If you plan to handle parameters:

  • it_mkLambda_or_LetIn takes c : context and t : term and produces a new λ-abstraction with body t and quantifying over c. Basically it does the right thing by inserting as many tLam as necessary.

  • subst l 0 t will substitute the variables of t using the terms provided in l. For this exercise, you can provide garbage (just some random tRel k will suffice), what matters is the number of terms you provide. Providing 3 will reduce tRel 5 to tRel 2.

Handy concatenation notation.

Notation "a # b" := (String.append a b).

To debug we recommend you use the following in place of tmMkDefinition

Definition tmDebugDefinition na (t : term) :=
  t <- tmEval all t ;;
  tmDefinition na t.

mkr 3 2 will produce [ tRel 4 ; tRel 3 ; tRel 2 ]

Fixpoint mkr i off :=
  match i with
  | 0 => []
  | S i => tRel (off + i) :: mkr i off
  end.

Extract the name from aname or use d as default.

Definition get_name (a : aname) d :=
  match a.(binder_name) with
  | nNamed na => na
  | nAnon => d
  end.

Definition has_body (c : context_decl) :=
  match c.(decl_body) with
  | Some _ => true
  | None => false
  end.

Fixpoint mkargs_aux nargs n args i {struct i} :=
  match i, n with
  | 0, _ => []
  | S i, Some (S n) =>
    let l := mkargs_aux nargs (Some n) (tl args) i in
    if hd true args then l else tRel i :: l
  | S i, Some 0 =>
    let l := mkargs_aux nargs None (tl args) i in
    if hd true args then l else tApp (tRel (S nargs)) [ tRel i ] :: l
  | S i, None =>
    let l := mkargs_aux nargs None (tl args) i in
    if hd true args then l else tRel i :: l
  end.

Definition mkargs nargs n args :=
  let l := rev_map has_body args in
  mkargs_aux nargs n l nargs.

Definition from_arg ind npar params args cargs n (a : context_decl) :=
  match a.(decl_body) with
  | Some _ => None
  | None =>
    let nargs := List.length args in
    let ty := subst (mkr (nargs - S n) 0) 0 a.(decl_type) in
    let nparams := List.length params in
    let t :=
      it_mkLambda_or_LetIn params (
        tLam "f" (tImpl ty ty) (
          tLam "x" (mkApps (tInd ind []) (mkr nparams 1)) (
            tCase
              {| ci_ind := ind ; ci_npar := npar ; ci_relevance := Relevant |}
              {|
                puinst := [] ;
                pparams := mkr nparams 2 ;
                pcontext := [
                  {| binder_name := nNamed "x"; binder_relevance := Relevant |}
                ] ;
                preturn := mkApps (tInd ind []) (mkr nparams 3)
              |}
              (tRel 0)
              [
                {|
                  bcontext := args ;
                  bbody := tApp (tConstruct ind 0 []) (mkr nparams 5 ++ mkargs nargs (Some (nargs - S n)) cargs)
                |}
              ]
          )
        )
      )
    in
    Some (a.(decl_name), t)
  end.

Definition from_ctor ind npar params (b : constructor_body) :=
  let args := map decl_name b.(cstr_args) in
  mapi (from_arg ind npar params args b.(cstr_args)) b.(cstr_args).

Fixpoint def_list dn (l : list (option (aname * term))) :=
  match l with
  | Some (n, q) :: l =>
    na <- tmFreshName ("upd_" # get_name n dn) ;;
    tmMkDefinition na q ;;
    def_list dn l
  | None :: l => def_list dn l
  | [] => tmReturn tt
  end.

Fixpoint debug_def_list dn (l : list (option (aname * term))) :=
  match l with
  | Some (n, q) :: l =>
    na <- tmFreshName ("debug_" # get_name n dn) ;;
    tmDebugDefinition na q ;;
    debug_def_list dn l
  | None :: l => debug_def_list dn l
  | [] => tmReturn tt
  end.

Definition from_mind (def_list : ident -> list (option (aname * term)) -> TemplateMonad unit) ind mind :=
  match mind.(ind_finite) with
  | BiFinite =>
    match mind.(ind_bodies) with
    | [ oib ] =>
      match oib.(ind_ctors) with
      | [ cstr ] =>
        let upd_funs := from_ctor ind mind.(ind_npars) mind.(ind_params) cstr in
        let default_name := string_of_kername ind.(inductive_mind) in
        def_list default_name upd_funs
      | _ => tmFail "A record should have exactly one constructor"
      end
    | _ => tmFail "Expecting only one record (not mutually defined)"
    end
  | _ => tmFail "Not a record"
  end.

Definition get_inductive' {A} (ind : A) :=
  t <- tmQuote ind ;;
  match t with
  | tInd ind _ =>
    let kn := ind.(inductive_mind) in
    q <- tmQuoteInductive kn ;;
    tmReturn (ind, q)
  | _ => tmFail "Not an inductive type"
  end.

Definition derive_updates {A} (ind : A) : TemplateMonad unit :=
  '(ind, mib) <- get_inductive' ind ;;
  from_mind def_list ind mib.

Below, one of them should always fail.

MetaRocq Run (derive_updates point3D).
MetaRocq Run (derive_updates Zalt).
The command has indeed failed with message: Not a record
MetaRocq Run (derive_updates triple). MetaRocq Run (derive_updates trap).

Test that it works. If you manage to execute those lines, it's very likely that it does, but better safe than sorry.

= {| p1 := "hello"; p2 := 24; p3 := true |} : triple string nat bool
= {| v1 := 2; v3 := 35 |} : trap
From MetaRocq.Utils Require Import ReflectEq. Ltac intro_Prop := match goal with | |- forall P : Prop, _ => intro end.