decidable.v 5.54 KB
Newer Older
1 2 3 4 5
(* Copyright (c) 2012, Robbert Krebbers. *)
(* This file is distributed under the terms of the BSD license. *)
(** This file collects theorems, definitions, tactics, related to propositions
with a decidable equality. Such propositions are collected by the [Decision]
type class. *)
6 7
Require Export base tactics.

Robbert Krebbers's avatar
Robbert Krebbers committed
8 9
Hint Extern 200 (Decision _) => progress (lazy beta) : typeclass_instances.

10 11
Lemma dec_stable `{Decision P} : ¬¬P  P.
Proof. firstorder. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
12

13 14 15 16 17 18 19 20 21
(** We introduce [decide_rel] to avoid inefficienct computation due to eager
evaluation of propositions by [vm_compute]. This inefficiency occurs if
[(x = y) := (f x = f y)] as [decide (x = y)] evaluates to [decide (f x = f y)]
which then might lead to evaluation of [f x] and [f y]. Using [decide_rel]
we hide [f] under a lambda abstraction to avoid this unnecessary evaluation. *)
Definition decide_rel {A B} (R : A  B  Prop) {dec :  x y, Decision (R x y)}
  (x : A) (y : B) : Decision (R x y) := dec x y.
Lemma decide_rel_correct {A B} (R : A  B  Prop) `{ x y, Decision (R x y)}
  (x : A) (y : B) : decide_rel R x y = decide (R x y).
22
Proof. done. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
23

24
(** The tactic [case_decide] performs case analysis on an arbitrary occurrence
25
of [decide] or [decide_rel] in the conclusion or hypotheses. *)
26
Ltac case_decide :=
Robbert Krebbers's avatar
Robbert Krebbers committed
27
  match goal with
28 29
  | H : context [@decide ?P ?dec] |- _ =>
    destruct (@decide P dec)
30
  | H : context [@decide_rel _ _ ?R ?x ?y ?dec] |- _ =>
31 32 33
    destruct (@decide_rel _ _ R x y dec)
  | |- context [@decide ?P ?dec] =>
    destruct (@decide P dec)
34
  | |- context [@decide_rel _ _ ?R ?x ?y ?dec] =>
35
    destruct (@decide_rel _ _ R x y dec)
Robbert Krebbers's avatar
Robbert Krebbers committed
36 37
  end.

38 39
(** The tactic [solve_decision] uses Coq's [decide equality] tactic together
with instance resolution to automatically generate decision procedures. *)
Robbert Krebbers's avatar
Robbert Krebbers committed
40 41
Ltac solve_trivial_decision :=
  match goal with
42 43
  | |- Decision (?P) => apply _
  | |- sumbool ?P (¬?P) => change (Decision P); apply _
Robbert Krebbers's avatar
Robbert Krebbers committed
44
  end.
45 46 47
Ltac solve_decision := intros; first
  [ solve_trivial_decision
  | unfold Decision; decide equality; solve_trivial_decision ].
Robbert Krebbers's avatar
Robbert Krebbers committed
48

49 50 51
(** We can convert decidable propositions to booleans. *)
Definition bool_decide (P : Prop) {dec : Decision P} : bool :=
  if dec then true else false.
Robbert Krebbers's avatar
Robbert Krebbers committed
52 53

Lemma bool_decide_unpack (P : Prop) {dec : Decision P} : bool_decide P  P.
54
Proof. unfold bool_decide. by destruct dec. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
55
Lemma bool_decide_pack (P : Prop) {dec : Decision P} : P  bool_decide P.
56
Proof. unfold bool_decide. by destruct dec. Qed.
Robbert Krebbers's avatar
Robbert Krebbers committed
57

58 59 60 61 62
(** * Decidable Sigma types *)
(** Leibniz equality on Sigma types requires the equipped proofs to be
equal as Coq does not support proof irrelevance. For decidable we
propositions we define the type [dsig P] whose Leibniz equality is proof
irrelevant. That is [∀ x y : dsig P, x = y ↔ `x = `y]. *)
63 64 65 66 67 68
Definition dsig `(P : A  Prop) `{ x : A, Decision (P x)} :=
  { x | bool_decide (P x) }.
Definition proj2_dsig `{ x : A, Decision (P x)} (x : dsig P) : P (`x) :=
  bool_decide_unpack _ (proj2_sig x).
Definition dexist `{ x : A, Decision (P x)} (x : A) (p : P x) : dsig P :=
  xbool_decide_pack _ p.
Robbert Krebbers's avatar
Robbert Krebbers committed
69

70
Lemma dsig_eq {A} (P : A  Prop) {dec :  x, Decision (P x)}
71
  (x y : dsig P) : x = y  `x = `y.
Robbert Krebbers's avatar
Robbert Krebbers committed
72
Proof.
73 74 75 76 77
  split.
  * destruct x, y. apply proj1_sig_inj.
  * intro. destruct x as [x Hx], y as [y Hy].
    simpl in *. subst. f_equal.
    revert Hx Hy. case (bool_decide (P y)).
78 79
    + by intros [] [].
    + done.
Robbert Krebbers's avatar
Robbert Krebbers committed
80
Qed.
81

82 83 84 85 86
(** The following combinators are useful to create Decision proofs in
combination with the [refine] tactic. *)
Notation cast_if S := (if S then left _ else right _).
Notation cast_if_and S1 S2 := (if S1 then cast_if S2 else right _).
Notation cast_if_and3 S1 S2 S3 := (if S1 then cast_if_and S2 S3 else right _).
Robbert Krebbers's avatar
Robbert Krebbers committed
87 88
Notation cast_if_and4 S1 S2 S3 S4 :=
  (if S1 then cast_if_and3 S2 S3 S4 else right _).
89 90 91
Notation cast_if_or S1 S2 := (if S1 then left _ else cast_if S2).
Notation cast_if_not S := (if S then right _ else left _).

92 93
(** * Instances of Decision *)
(** Instances of [Decision] for operators of propositional logic. *)
94 95 96 97 98 99
Instance True_dec: Decision True := left I.
Instance False_dec: Decision False := right (False_rect False).

Section prop_dec.
  Context `(P_dec : Decision P) `(Q_dec : Decision Q).

100 101
  Global Instance not_dec: Decision (¬P).
  Proof. refine (cast_if_not P_dec); intuition. Defined.
102
  Global Instance and_dec: Decision (P  Q).
103
  Proof. refine (cast_if_and P_dec Q_dec); intuition. Defined.
104
  Global Instance or_dec: Decision (P  Q).
105
  Proof. refine (cast_if_or P_dec Q_dec); intuition. Defined.
106
  Global Instance impl_dec: Decision (P  Q).
107
  Proof. refine (if P_dec then cast_if Q_dec else left _); intuition. Defined.
108
End prop_dec.
109 110

(** Instances of [Decision] for common data types. *)
Robbert Krebbers's avatar
Robbert Krebbers committed
111 112
Instance bool_eq_dec (x y : bool) : Decision (x = y).
Proof. solve_decision. Defined.
113 114 115
Instance unit_eq_dec (x y : unit) : Decision (x = y).
Proof. refine (left _); by destruct x, y. Defined.
Instance prod_eq_dec `(A_dec :  x y : A, Decision (x = y))
Robbert Krebbers's avatar
Robbert Krebbers committed
116
  `(B_dec :  x y : B, Decision (x = y)) (x y : A * B) : Decision (x = y).
117 118 119 120 121
Proof.
  refine (cast_if_and (A_dec (fst x) (fst y)) (B_dec (snd x) (snd y)));
    abstract (destruct x, y; simpl in *; congruence).
Defined.
Instance sum_eq_dec `(A_dec :  x y : A, Decision (x = y))
Robbert Krebbers's avatar
Robbert Krebbers committed
122
  `(B_dec :  x y : B, Decision (x = y)) (x y : A + B) : Decision (x = y).
123
Proof. solve_decision. Defined.
Robbert Krebbers's avatar
Robbert Krebbers committed
124 125 126 127 128 129 130 131

Instance curry_dec `(P_dec :  (x : A) (y : B), Decision (P x y)) p :
    Decision (curry P p) :=
  match p as p return Decision (curry P p) with
  | (x,y) => P_dec x y
  end.
Instance uncurry_dec `(P_dec :  (p : A * B), Decision (P p)) x y :
  Decision (uncurry P x y) := P_dec (x,y).