Exercise session 4 — Modelling and automation — Solutions
- 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 pforall (A B : Type) (p : prod' A B), to_prod p = to_prod_alt3 pA, B: Type
p: prod' A Bto_prod p = to_prod_alt3 preflexivity. 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).A, B: Type
a: A
b: Bto_prod {| fst' := a; snd' := b |} = to_prod_alt3 {| fst' := a; snd' := b |}forall (M : monoid) (x y : m_ty M), x ** m_ne M ** y = x ** yforall (M : monoid) (x y : m_ty M), x ** m_ne M ** y = x ** yM: monoid
x, y: m_ty Mx ** m_ne M ** y = x ** y
More complicated than necessary of course
M: monoid
x, y: m_ty Mx ** (m_ne M ** y) = x ** yreflexivity. Qed.M: monoid
x, y: m_ty Mx ** y = x ** y
Exercise: Groups as records
Define a record for groups, building on the record for monoids.
Then show that monoid_fact also holds in groups.
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 ** yforall (G : group) (x y : m_ty (g_mon G)), x ** m_ne (g_mon G) ** y = x ** yapply monoid_fact. Qed.G: group
x, y: m_ty (g_mon G)x ** m_ne (g_mon G) ** y = x ** y
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: TypemonoidA: TypemonoidA: Typeforall x : list A, [] ++ x = xA: Typeforall x : list A, x ++ [] = xA: Typeforall x y z : list A, (x ++ y) ++ z = x ++ y ++ zA: Typeforall x : list A, [] ++ x = xA: Type
x: list A[] ++ x = xreflexivity.A: Type
x: list Ax = xA: Typeforall x : list A, x ++ [] = xA: Type
x: list Ax ++ [] = xreflexivity.A: Type
x: list Ax = xA: Typeforall x y z : list A, (x ++ y) ++ z = x ++ y ++ zA: Type
x, y, z: list A(x ++ y) ++ z = x ++ y ++ zreflexivity. Defined.A: Type
x, y, z: list A(x ++ y) ++ z = (x ++ y) ++ zforall (A : Type) (x y : list A), (x ++ []) ++ y = x ++ yforall (A : Type) (x y : list A), (x ++ []) ++ y = x ++ yapply 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) }.A: Type
x, y: list A(x ++ []) ++ y = x ++ yMonoid nat 0 Init.Nat.addMonoid nat 0 Init.Nat.addforall x : nat, 0 + x = xforall x : nat, x + 0 = xforall x y z : nat, x + y + z = x + (y + z)forall x : nat, 0 + x = xreflexivity.x: nat0 + x = xforall x : nat, x + 0 = xlia.x: natx + 0 = xforall x y z : nat, x + y + z = x + (y + z)lia. Qed.x, y, z: natx + y + z = x + (y + z)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: Mop (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: Mop (op k n) m = op k (op n m)reflexivity. Qed.M: Type
neu: M
op: M -> M -> M
H: Monoid M neu op
k, n, m: Mop k (op n m) = op k (op n m)
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 opbMonoid (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 opbforall x : A * B, (let '(ya, yb) := x in (opa na ya, opb nb yb)) = xA, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opbforall x : A * B, (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) (na, nb) = xA, B: Type
na: A
nb: B
opa: A -> A -> A
opb: B -> B -> B
MA: Monoid A na opa
MB: Monoid B nb opbforall 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 opbforall x : A * B, (let '(ya, yb) := x in (opa na ya, opb nb yb)) = xA, 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)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
a: A
b: B(a, 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 opbforall x : A * B, (let '(xa, xb) := x in fun '(ya, yb) => (opa xa ya, opb xb yb)) (na, nb) = xA, 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)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
a: A
b: B(a, 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 opbforall 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))reflexivity. Qed.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))
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.
forall A : Type, Monoid (list A) [] (app (A:=A))forall A : Type, Monoid (list A) [] (app (A:=A))A: TypeMonoid (list A) [] (app (A:=A))A: Typeforall x : list A, [] ++ x = xA: Typeforall x : list A, x ++ [] = xA: Typeforall x y z : list A, (x ++ y) ++ z = x ++ y ++ zA: Typeforall x : list A, [] ++ x = xreflexivity.A: Type
x: list A[] ++ x = xA: Typeforall x : list A, x ++ [] = xapply app_nil_r.A: Type
x: list Ax ++ [] = xA: Typeforall x y z : list A, (x ++ y) ++ z = x ++ y ++ zA: Type
x, y, z: list A(x ++ y) ++ z = x ++ y ++ zreflexivity. Qed.A: Type
x, y, z: list A(x ++ y) ++ z = (x ++ y) ++ zforall (A : Type) (k n m : list A), ((k ++ n) ++ m) ++ [] = k ++ n ++ mforall (A : Type) (k n m : list A), ((k ++ n) ++ m) ++ [] = k ++ n ++ mA: Type
k, n, m: list A((k ++ n) ++ m) ++ [] = k ++ n ++ mexact _. 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.A: Type
k, n, m: list AMonoid (list A) [] (app (A:=A))
Exercise: Specification of memb
Give memb a specification using the In predicate and show it correct with
respect to it.
forall (A : Type) (H : Eq A) (x : A) (l : list A), memb x l = true <-> In x lforall (A : Type) (H : Eq A) (x : A) (l : list A), memb x l = true <-> In x lA: Type
hA: Eq A
x: A
l: list Amemb x l = true <-> In x lA: Type
hA: Eq A
x: Amemb x [] = true <-> In x []A: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x lmemb x (a :: l) = true <-> In x (a :: l)A: Type
hA: Eq A
x: Amemb x [] = true <-> In x []A: Type
hA: Eq A
x: Afalse = true <-> FalseA: Type
hA: Eq A
x: Afalse = true -> FalseA: Type
hA: Eq A
x: AFalse -> false = truediscriminate.A: Type
hA: Eq A
x: Afalse = true -> Falseintros [].A: Type
hA: Eq A
x: AFalse -> false = trueA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x lmemb 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 lA: 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 lA: 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 lA: 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 lA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = truetrue = true <-> a = x \/ In x lA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: x = atrue = true <-> a = x \/ In x lA: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a ltrue = true <-> a = a \/ In a lA: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a ltrue = true -> a = a \/ In a lA: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a la = a \/ In a l -> true = trueA: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a ltrue = true -> a = a \/ In a lA: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l
H: true = truea = a \/ In a lreflexivity.A: Type
hA: Eq A
a: A
l: list A
ih: memb a l = true <-> In a l
H: true = truea = aA: 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 lA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = falsememb x l = true <-> a = x \/ In x lA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = falsememb x l = true -> a = x \/ In x lA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = falsea = x \/ In x l -> memb x l = trueA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = falsememb x l = true -> a = x \/ In x lA: 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 = truea = x \/ In x lA: 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 = trueIn x lassumption.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 = truememb x l = trueA: Type
hA: Eq A
x, a: A
l: list A
ih: memb x l = true <-> In x l
e: eqb x a = falsea = x \/ In x l -> memb x l = trueA: 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 = xmemb x l = trueA: 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 lmemb x l = trueA: 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 = xmemb x l = trueA: 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 = amemb x l = trueA: 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 = truememb x l = truediscriminate.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 = truememb x l = trueA: 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 lmemb x l = trueassumption. Qed.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 lIn x l
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' = xne = 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' = xne = 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' = xne = ne'reflexivity. Qed.G: Type
ne: G
op: G -> G -> G
H: Group G ne op
hr: forall x : G, op x ne = xne = neforall (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 = cforall (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 = cG: 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 = neb = cG: 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 = neb = cG: 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 = neb = cG: 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 = neb = cG: 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 = neb = cassumption. Qed.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 = neb = cGroup Z 0%Z Z.addGroup Z 0%Z Z.addforall x : Z, (0 + x)%Z = xforall x : Z, (x + 0)%Z = xforall x y z : Z, (x + y + z)%Z = (x + (y + z))%Zforall x : Z, exists y : Z, (x + y)%Z = 0%Z /\ (y + x)%Z = 0%Zforall x : Z, (0 + x)%Z = xlia.x: Z(0 + x)%Z = xforall x : Z, (x + 0)%Z = xlia.x: Z(x + 0)%Z = xforall x y z : Z, (x + y + z)%Z = (x + (y + z))%Zlia.x, y, z: Z(x + y + z)%Z = (x + (y + z))%Zforall x : Z, exists y : Z, (x + y)%Z = 0%Z /\ (y + x)%Z = 0%Zx: Zexists y : Z, (x + y)%Z = 0%Z /\ (y + x)%Z = 0%Zlia. Qed.x: Z(x + - x)%Z = 0%Z /\ (- x + x)%Z = 0%Zforall z : Z, (forall i : Z, (z + i)%Z = i) -> (forall i : Z, (i + z)%Z = i) -> z = 0%Zforall z : Z, (forall i : Z, (z + i)%Z = i) -> (forall i : Z, (i + z)%Z = i) -> z = 0%Zz: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = iz = 0%Zz: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = i0%Z = zz: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = iGroup Z 0%Z ?opz: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = iforall x : Z, ?op z x = xz: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = iforall x : Z, ?op x z = xall: assumption. Qed.z: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = iforall x : Z, (z + x)%Z = xz: Z
hl: forall i : Z, (z + i)%Z = i
hr: forall i : Z, (i + z)%Z = iforall x : Z, (x + z)%Z = xforall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> Monoid G ne opforall (G : Type) (ne : G) (op : G -> G -> G), Group G ne op -> Monoid G ne opG: Type
ne: G
op: G -> G -> G
H: Group G ne opMonoid G ne opG: Type
ne: G
op: G -> G -> G
H: Group G ne opforall x : G, op ne x = xG: Type
ne: G
op: G -> G -> G
H: Group G ne opforall x : G, op x ne = xG: Type
ne: G
op: G -> G -> G
H: Group G ne opforall 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 opforall x : G, op ne x = xapply group_left_neutral.G: Type
ne: G
op: G -> G -> G
H: Group G ne op
x: Gop ne x = xG: Type
ne: G
op: G -> G -> G
H: Group G ne opforall x : G, op x ne = xapply group_right_neutral.G: Type
ne: G
op: G -> G -> G
H: Group G ne op
x: Gop x ne = xG: Type
ne: G
op: G -> G -> G
H: Group G ne opforall x y z : G, op (op x y) z = op x (op y z)apply group_assoc. Qed. (* From the lecture: *)G: Type
ne: G
op: G -> G -> G
H: Group G ne op
x, y, z: Gop (op x y) z = op x (op y z)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 AIn x (x :: l)auto. Qed.A: Type
x: A
l: list Ax = x \/ In x lforall (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 lIn x (y :: l)auto. Qed. Create HintDb indb. #[export] Hint Resolve In_hd : indb. #[export] Hint Resolve In_hd : core.A: Type
x, y: A
l: list A
h: In x ly = x \/ In x l
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.
#[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)auto with indb. Qed.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 (a :: b :: x :: 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)
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 lIn 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)contradiction.A: Type
x: A
r: list A
h: FalseIn 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, 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)assumption.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 = xA: 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)assumption. Qed.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 lforall (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 rIn x (l ++ r)A: Type
x: A
r: list A
h: In x rIn 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 rIn x ([] ++ r)assumption.A: Type
x: A
r: list A
h: In x rIn x rA: 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)assumption. Qed. #[export] Hint Resolve In_app_l : indb. #[export] Hint Resolve In_app_r : indb.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 rforall (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 ([a; b; c] ++ l' ++ d :: l)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.forall (A : Type) (x a b c d : A) (l l' : list A), In x l -> In x (l ++ [a; b; c] ++ l' ++ [d])
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 = yIn x (y :: l)auto. Qed. #[export] Hint Resolve In_hd_eq : indb.A: Type
x, y: A
l: list A
e: x = yy = x \/ In x lforall (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.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)
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)auto with indb arith. Qed.forall (a b c d : nat) (l l' : list nat), In (a + b) ([b; c] ++ l' ++ d :: b + a :: l)
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 natIn (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)a, b, c, d: nat
l, l': list natIn (a + b + c) ([a; b; c] ++ l' ++ d :: c + 0 + a + b :: l)a, b, c, d: nat
l, l': list natIn (a + b + c) (l' ++ d :: c + 0 + a + b :: l)a, b, c, d: nat
l, l': list natIn (a + b + c) (d :: c + 0 + a + b :: l)a, b, c, d: nat
l, l': list natIn (a + b + c) (c + 0 + a + b :: l)lia. Qed.a, b, c, d: nat
l, l': list nata + b + c = c + 0 + a + b
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)auto with indb. Qed. #[export] Hint Extern 3 (@eq Z _ _) => 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 : 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.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)
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 Aexists y : A, In y (l ++ x :: l')auto with indb. Qed.A: Type
x: A
l, l': list AIn ?y (l ++ x :: l')
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 xforall (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 xA: 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: AQ xeauto. Qed.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 yQ x
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 <-> Aforall A : Prop, A /\ A <-> AA: PropA /\ A <-> AA: PropA /\ A -> AA: PropA -> A /\ AA: PropA /\ A -> Aauto.A: Prop
H, H0: AAauto. Qed.A: PropA -> A /\ Aforall A : Prop, A \/ A <-> Aforall A : Prop, A \/ A <-> AA: PropA \/ A <-> AA: PropA \/ A -> AA: PropA -> A \/ AA: PropA \/ A -> Aall: auto.A: Prop
H: AAA: Prop
H: AAauto. Qed.A: PropA -> A \/ Aforall A B : Prop, A /\ B <-> B /\ Aforall A B : Prop, A /\ B <-> B /\ AA, B: PropA /\ B <-> B /\ Aall: intros [] ; auto. Qed.A, B: PropA /\ B -> B /\ AA, B: PropB /\ A -> A /\ Bforall A B : Prop, A \/ B <-> B \/ Aforall A B : Prop, A \/ B <-> B \/ AA, B: PropA \/ B <-> B \/ Aall: intros [] ; auto. Qed.A, B: PropA \/ B -> B \/ AA, B: PropB \/ A -> A \/ Bforall A B C : Prop, (A /\ B) /\ C <-> A /\ B /\ Cforall A B C : Prop, (A /\ B) /\ C <-> A /\ B /\ CA, B, C: Prop(A /\ B) /\ C <-> A /\ B /\ CA, B, C: Prop(A /\ B) /\ C -> A /\ B /\ CA, B, C: PropA /\ B /\ C -> (A /\ B) /\ CA, B, C: Prop(A /\ B) /\ C -> A /\ B /\ Cauto.A, B, C: Prop
H: A
H0: B
H1: CA /\ B /\ CA, B, C: PropA /\ B /\ C -> (A /\ B) /\ Cauto. Qed.A, B, C: Prop
H: A
H0: B
H1: C(A /\ B) /\ C
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: PropA /\ (B /\ B) /\ (C -> D) /\ (C -> D) <-> A /\ B /\ (C -> D)reflexivity. Qed.A, B, C, D: PropA /\ B /\ (C -> D) <-> A /\ B /\ (C -> D)forall A B : Prop, B /\ A /\ B \/ A /\ B <-> B /\ Aforall A B : Prop, B /\ A /\ B \/ A /\ B <-> B /\ AA, B: PropB /\ A /\ B \/ A /\ B <-> B /\ AA, B: PropB /\ B /\ A \/ B /\ A <-> B /\ AA, B: Prop(B /\ B) /\ A \/ B /\ A <-> B /\ AA, B: PropB /\ A \/ B /\ A <-> B /\ Areflexivity. Qed.A, B: PropB /\ A <-> B /\ A
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_eqforall A : Type, Reflexive list_set_eqA: TypeReflexive list_set_eqA: Type
l: list Al ~ lreflexivity. Qed.A: Type
l: list A
x: AIn x l <-> In x lforall A : Type, Symmetric list_set_eqforall A : Type, Symmetric list_set_eqA: TypeSymmetric list_set_eqA: Type
u, v: list A
h: u ~ vv ~ uA: Type
u, v: list A
h: u ~ v
x: AIn x v <-> In x uapply h. Qed.A: Type
u, v: list A
h: u ~ v
x: AIn x u <-> In x vforall A : Type, Transitive list_set_eqforall A : Type, Transitive list_set_eqA: TypeTransitive list_set_eqA: Type
u, v, w: list A
h1: u ~ v
h2: v ~ wu ~ wA: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: AIn x u <-> In x wA: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: AIn x u <-> ?yA: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: A?y <-> In x weapply h1.A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: AIn x u <-> ?yapply h2. Qed.A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ w
x: AIn x v <-> In x wforall (A : Type) (u v w : list A), v ~ u -> (u ~ u -> v ~ w) -> u ~ wforall (A : Type) (u v w : list A), v ~ u -> (u ~ u -> v ~ w) -> u ~ wA: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ wu ~ wA: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ wu ~ ?yA: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w?y ~ wA: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ wu ~ ?yeassumption.A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ w?y ~ uA: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ wv ~ wreflexivity. Qed.A: Type
u, v, w: list A
h1: v ~ u
h2: u ~ u -> v ~ wu ~ u
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 ~ wforall (A : Type) (u v w : list A), u ~ v -> v ~ w -> u ~ wA: Type
u, v, w: list A
h1: u ~ v
h2: v ~ wu ~ wassumption. Qed.A: Type
u, v, w: list A
h1: u ~ v
h2: v ~ wv ~ w
Prove that u ++ v ~ v ++ u.
forall (A : Type) (l r : list A) (x : A), In x (l ++ r) -> In x l \/ In x rforall (A : Type) (l r : list A) (x : A), In x (l ++ r) -> In x l \/ In x rA: Type
l, r: list A
x: A
h: In x (l ++ r)In x l \/ In x rA: Type
r: list A
x: A
h: In x ([] ++ r)In x [] \/ In x rA: 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 rIn x (a :: l) \/ In x rA: Type
r: list A
x: A
h: In x ([] ++ r)In x [] \/ In x rauto.A: Type
r: list A
x: A
h: In x rFalse \/ In x rA: 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 rIn x (a :: l) \/ In x rA: 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 rA: 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 rA: 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 reauto with indb.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 rA: 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 rA: 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 rall: auto with indb. Qed.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 rA: 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 rforall (A : Type) (u v : list A), u ++ v ~ v ++ uforall (A : Type) (u v : list A), u ++ v ~ v ++ uA: Type
u, v: list Au ++ v ~ v ++ uA: Type
u, v: list A
x: AIn x (u ++ v) <-> In x (v ++ u)A: Type
u, v: list A
x: AIn x (u ++ v) -> In x (v ++ u)A: Type
u, v: list A
x: AIn x (v ++ u) -> In x (u ++ v)A: Type
u, v: list A
x: A
h: In x u \/ In x vIn x (v ++ u)A: Type
u, v: list A
x: A
h: In x v \/ In x uIn x (u ++ v)all: auto with indb. Qed.A: Type
u, v: list A
x: A
H: In x uIn x (v ++ u)A: Type
u, v: list A
x: A
H: In x vIn x (v ++ u)A: Type
u, v: list A
x: A
H: In x vIn x (u ++ v)A: Type
u, v: list A
x: A
H: In x uIn x (u ++ v)
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: Aforall x0 y : list A, x0 ~ y -> In x x0 <-> In x yA: Type
x: Aforall x0 y : list A, x0 ~ y -> In x x0 <-> In x yapply e. Qed.A: Type
x: A
u, v: list A
e: u ~ vIn x u <-> In x vforall (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)assumption. Qed.A: Type
x: A
u, v: list A
h: In x (u ++ v)In x (u ++ v)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 AIn x (u ++ [a; b; c] ++ x :: v)A: Type
x, a, b, c: A
u, v: list AIn x (([a; b; c] ++ x :: v) ++ u)A: Type
x, a, b, c: A
u, v: list AIn x ([a; b; c] ++ (x :: v) ++ u)A: Type
x, a, b, c: A
u, v: list AIn x (((x :: v) ++ u) ++ [a; b; c])A: Type
x, a, b, c: A
u, v: list AIn x ((x :: v) ++ u ++ [a; b; c])auto. Qed.A: Type
x, a, b, c: A
u, v: list Ax = x \/ In x (v ++ u ++ [a; b; c])
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 AForall P l <-> (forall x : A, In x l -> P x)A: Type
P: A -> PropForall 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 -> PropForall P [] <-> (forall x : A, In x [] -> P x)A: Type
P: A -> PropForall P [] -> forall x : A, In x [] -> P xA: Type
P: A -> Prop(forall x : A, In x [] -> P x) -> Forall P []A: Type
P: A -> PropForall P [] -> forall x : A, In x [] -> P xintros _ _ [].A: Type
P: A -> PropForall P [] -> forall x : A, False -> P xA: Type
P: A -> Prop(forall x : A, In x [] -> P x) -> Forall P []constructor.A: Type
P: A -> PropForall P []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 x0A: 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 x0A: 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 aA: 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 = lP aA: 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 lP aA: 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 lP aA: 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 lP aA: 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 lP aA: 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 lP aassumption.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 lP aA: 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 lP aall: 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 lForall P lA: 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 lIn a lA: 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 x0Forall 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 x0P xA: 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 x0Forall P lA: 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 x0P xauto 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 x0In x (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 x0Forall P lA: 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 x0forall x0 : A, In x0 l -> P x0A: 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 lP aauto with indb. Qed.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 lIn a (x :: l)forall (A : Type) (P : A -> Prop) (u v : list A), u ~ v -> Forall P u -> Forall P vforall (A : Type) (P : A -> Prop) (u v : list A), u ~ v -> Forall P u -> Forall P vA: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: Forall P uForall P vA: Type
P: A -> Prop
u, v: list A
e: u ~ v
h: forall x : A, In x u -> P xforall x : A, In x v -> P xA: 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 vP xA: 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 uP xassumption. Qed.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 uIn x uA: Type
P: A -> Propforall x y : list A, x ~ y -> Forall P x <-> Forall P yA: Type
P: A -> Propforall x y : list A, x ~ y -> Forall P x <-> Forall P yA: Type
P: A -> Prop
u, v: list A
e: u ~ vForall P u <-> Forall P vA: Type
P: A -> Prop
u, v: list A
e: u ~ vForall P u -> Forall P vA: Type
P: A -> Prop
u, v: list A
e: u ~ vForall P v -> Forall P uA: Type
P: A -> Prop
u, v: list A
e: u ~ vu ~ vA: Type
P: A -> Prop
u, v: list A
e: u ~ vv ~ uauto.A: Type
P: A -> Prop
u, v: list A
e: u ~ vu ~ vA: Type
P: A -> Prop
u, v: list A
e: u ~ vv ~ uauto. Qed.A: Type
P: A -> Prop
u, v: list A
e: u ~ vu ~ vforall 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)assumption. Qed.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)
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 = truetry (unshelve eexists ; constructor). Abort.exists b : bool, negb b = trueexists n : nat, n = 1try (unshelve eexists ; constructor). Abort.exists n : nat, n = 1True \/ (False -> False)True \/ (False -> False)Abort.x: FalseFalseTrue \/ (False -> False)True \/ (False -> False)TrueAbort.True(False -> False) \/ Truetry (constructor ; exact I). Abort.(False -> False) \/ True
Answers:
It succeeds with
b := false:constructorfirst pickstrue, but thentrue = falsecannot be proven byconstructor, so it backtracks.It succeeds with
n := 1:0 = 1fails, soconstructorpicksS ?minstead, and provingS ?m = 1witheq_reflinstantiates?m := 0.Only the goal
Falseremains, withx : False:intro xfails onTrue, soconstructorbacktracks and picks the right disjunct.The goal
Trueremains:constructorpicks the left disjunct, and backtracking does not go back across sentences (.), sointro xjust fails andtryhides the failure.It succeeds with
or_intror I:exact Ifails onFalse -> False, soconstructorbacktracks 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 10repeat split ; repeat constructor. Qed.mult4 12 /\ not_mult4 7 /\ mult4 0 /\ not_mult4 10forall n : nat, not_mult4 n -> not_mult4 (8 + n)intros n h ; do 2 apply not_mult4_plus ; exact h. Qed.forall n : nat, not_mult4 n -> not_mult4 (8 + n)forall n : nat, n < 3 -> not_mult4 (n + 1)intros n h ; destruct n as [| [| [| n]]] ; [ constructor .. | exfalso ; lia ]. Qed.forall n : nat, n < 3 -> not_mult4 (n + 1)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.forall n : nat, mult4 n -> mult4 (n + 4)
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 * boolnat * boolAbort.natboolnat * (bool * unit) * (unit * nat * bool) * unitnat * (bool * unit) * (unit * nat * bool) * unitAbort.natboolunitunitnatboolunit
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 = 0forall n : nat, n mod 14 = 7 -> n - n = 0n: nat
hn: n mod 14 = 7n - n = 0n: natn - n = 00 - 0 = 0n: nat
IHn: n - n = 0S n - S n = 0reflexivity.0 - 0 = 0n: nat
IHn: n - n = 0S n - S n = 0eauto. Qed. Ltac handle_hyp h := lazymatch type of h with | (?A * ?B)%type => destruct h | nat => induction h | _ => idtac end.n: nat
IHn: n - n = 0n - n = 0
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
Pmust be provenand one where
Hhas been replaced byH : 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 -> Rforall P Q R : Type, (P -> Q -> R) -> (P -> Q) -> P -> RP, Q, R: Type
h1: P -> Q -> R
h2: P -> Q
h3: PRP, Q, R: Type
h1: P -> Q -> R
h2: P -> Q
h3: PPP, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: PRP, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: PRP, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: PPP, Q, R: Type
h1: Q -> R
h2: Q
h3: PRP, Q, R: Type
h1: Q -> R
h2: Q
h3: PRP, Q, R: Type
h1: Q -> R
h2: Q
h3: PQP, Q, R: Type
h1: R
h2: Q
h3: PRassumption. Qed.P, Q, R: Type
h1: R
h2: Q
h3: PR
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 -> Rforall P Q R : Type, (P -> Q -> R) -> (P -> Q) -> P -> RP, Q, R: Type
h1: P -> Q -> R
h2: P -> Q
h3: PRP, Q, R: Type
h1: P -> Q -> R
h2: Q
h3: PRassumption. Qed.P, Q, R: Type
h1: R
h2: Q
h3: PR
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: PropP -> True /\ Truemy_tauto. Qed.P, Q, R: PropP -> True /\ TrueP, Q, R: PropP -> Pmy_tauto. Qed.P, Q, R: PropP -> PP, Q, R: PropP -> (P -> R) -> Rmy_tauto. Qed.P, Q, R: PropP -> (P -> R) -> RP, Q, R: PropFalse \/ Truemy_tauto. Qed.P, Q, R: PropFalse \/ TrueP, 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.P, Q, R: Prop(P \/ Q \/ False) /\ (P -> Q) -> True /\ (R \/ Q)(fun n : nat => n + 0) = (fun n : nat => n)(fun n : nat => n + 0) = (fun n : nat => n)forall x : nat, x + 0 = xx: natx + 0 = xreflexivity. Qed.x: natx = x
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.Definition bar_ax : nat := let x := foo_ax in 139.Module test.P: Prop~ ~ P -> Ptauto. Qed. End test.P: Prop~ ~ P -> PDefinition more_deps := (bar_ax, test.DNE, LEM).
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.
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.
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.
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) = 24 * (9 + 12) + (3 + 1 * 7) = 2Abort.a:= aPlus (aTimes (aConst 4) (aPlus (aConst 9) (aConst 12))) (aPlus (aConst 3) (aTimes (aConst 1) (aConst 7))): arith4 * (9 + 12) + (3 + 1 * 7) = 2
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.
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.Axiom unknown : bool. Axiom random : nat -> nat. Definition test f := if unknown then what else random (f 9).
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.
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.
To help you build the derive_updates meta-program, we'll give you some
useful tools.
Also check out the following useful constructs:
tmMkDefinitiontakes astringand atermand produces a definition using that name (if fresh, otherwise it fails) and unquoting the given term.tmFreshNametakes astringand 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_LetIntakesc : contextandt : termand produces a new λ-abstraction with bodytand quantifying overc. Basically it does the right thing by inserting as manytLamas necessary.subst l 0 twill substitute the variables oftusing the terms provided inl. For this exercise, you can provide garbage (just some randomtRel kwill suffice), what matters is the number of terms you provide. Providing3will reducetRel 5totRel 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).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.
From MetaRocq.Utils Require Import ReflectEq. Ltac intro_Prop := match goal with | |- forall P : Prop, _ => intro end.