src/HOL/Tools/SMT/z3_proof_reconstruction.ML
author boehmes
Wed Dec 15 10:12:44 2010 +0100 (2010-12-15)
changeset 41127 2ea84c8535c6
parent 40681 872b08416fb4
child 41130 130771a48c70
permissions -rw-r--r--
re-implemented eta-expansion, lambda-lifting, and explicit application on terms (exploiting the control over the term structure);
abolished SMT interface concept in favor of solver classes (now also the translation configuration is stored in the context);
proof reconstruction is now expected to return a theorem stating False (and hence needs to discharge all hypothetical definitions);
built-in functions carry additionally their arity and their most general type;
slightly generalized the definition of fun_app
boehmes@36898
     1
(*  Title:      HOL/Tools/SMT/z3_proof_reconstruction.ML
boehmes@36898
     2
    Author:     Sascha Boehme, TU Muenchen
boehmes@36898
     3
boehmes@36898
     4
Proof reconstruction for proofs found by Z3.
boehmes@36898
     5
*)
boehmes@36898
     6
boehmes@36898
     7
signature Z3_PROOF_RECONSTRUCTION =
boehmes@36898
     8
sig
boehmes@36899
     9
  val add_z3_rule: thm -> Context.generic -> Context.generic
boehmes@40162
    10
  val reconstruct: Proof.context -> SMT_Translate.recon -> string list ->
boehmes@41127
    11
    int list * thm
boehmes@36898
    12
  val setup: theory -> theory
boehmes@36898
    13
end
boehmes@36898
    14
boehmes@36898
    15
structure Z3_Proof_Reconstruction: Z3_PROOF_RECONSTRUCTION =
boehmes@36898
    16
struct
boehmes@36898
    17
boehmes@36898
    18
structure P = Z3_Proof_Parser
boehmes@36898
    19
structure T = Z3_Proof_Tools
boehmes@36898
    20
structure L = Z3_Proof_Literals
boehmes@40662
    21
structure M = Z3_Proof_Methods
boehmes@36898
    22
boehmes@40424
    23
fun z3_exn msg = raise SMT_Failure.SMT (SMT_Failure.Other_Failure
boehmes@40162
    24
  ("Z3 proof reconstruction: " ^ msg))
boehmes@36898
    25
boehmes@36898
    26
boehmes@36898
    27
boehmes@36898
    28
(** net of schematic rules **)
boehmes@36898
    29
boehmes@36898
    30
val z3_ruleN = "z3_rule"
boehmes@36898
    31
boehmes@36898
    32
local
boehmes@36898
    33
  val description = "declaration of Z3 proof rules"
boehmes@36898
    34
boehmes@36898
    35
  val eq = Thm.eq_thm
boehmes@36898
    36
boehmes@36898
    37
  structure Z3_Rules = Generic_Data
boehmes@36898
    38
  (
boehmes@36898
    39
    type T = thm Net.net
boehmes@36898
    40
    val empty = Net.empty
boehmes@36898
    41
    val extend = I
boehmes@36898
    42
    val merge = Net.merge eq
boehmes@36898
    43
  )
boehmes@36898
    44
boehmes@36898
    45
  val prep = `Thm.prop_of o Simplifier.rewrite_rule [L.rewrite_true]
boehmes@36898
    46
boehmes@36898
    47
  fun ins thm net = Net.insert_term eq (prep thm) net handle Net.INSERT => net
boehmes@36898
    48
  fun del thm net = Net.delete_term eq (prep thm) net handle Net.DELETE => net
boehmes@36898
    49
boehmes@36898
    50
  val add = Thm.declaration_attribute (Z3_Rules.map o ins)
boehmes@36898
    51
  val del = Thm.declaration_attribute (Z3_Rules.map o del)
boehmes@36898
    52
in
boehmes@36898
    53
boehmes@36899
    54
val add_z3_rule = Z3_Rules.map o ins
boehmes@36898
    55
boehmes@36898
    56
fun by_schematic_rule ctxt ct =
boehmes@36898
    57
  the (T.net_instance (Z3_Rules.get (Context.Proof ctxt)) ct)
boehmes@36898
    58
boehmes@36898
    59
val z3_rules_setup =
boehmes@36898
    60
  Attrib.setup (Binding.name z3_ruleN) (Attrib.add_del add del) description #>
wenzelm@39557
    61
  Global_Theory.add_thms_dynamic (Binding.name z3_ruleN, Net.content o Z3_Rules.get)
boehmes@36898
    62
boehmes@36898
    63
end
boehmes@36898
    64
boehmes@36898
    65
boehmes@36898
    66
boehmes@36898
    67
(** proof tools **)
boehmes@36898
    68
boehmes@36898
    69
fun named ctxt name prover ct =
boehmes@40424
    70
  let val _ = SMT_Config.trace_msg ctxt I ("Z3: trying " ^ name ^ " ...")
boehmes@36898
    71
  in prover ct end
boehmes@36898
    72
boehmes@36898
    73
fun NAMED ctxt name tac i st =
boehmes@40424
    74
  let val _ = SMT_Config.trace_msg ctxt I ("Z3: trying " ^ name ^ " ...")
boehmes@36898
    75
  in tac i st end
boehmes@36898
    76
boehmes@36898
    77
fun pretty_goal ctxt thms t =
boehmes@36898
    78
  [Pretty.block [Pretty.str "proposition: ", Syntax.pretty_term ctxt t]]
boehmes@36898
    79
  |> not (null thms) ? cons (Pretty.big_list "assumptions:"
boehmes@36898
    80
       (map (Display.pretty_thm ctxt) thms))
boehmes@36898
    81
boehmes@36898
    82
fun try_apply ctxt thms =
boehmes@36898
    83
  let
boehmes@36898
    84
    fun try_apply_err ct = Pretty.string_of (Pretty.chunks [
boehmes@36898
    85
      Pretty.big_list ("Z3 found a proof," ^
boehmes@36898
    86
        " but proof reconstruction failed at the following subgoal:")
boehmes@36898
    87
        (pretty_goal ctxt thms (Thm.term_of ct)),
boehmes@36898
    88
      Pretty.str ("Adding a rule to the lemma group " ^ quote z3_ruleN ^
boehmes@36898
    89
        " might solve this problem.")])
boehmes@36898
    90
boehmes@36898
    91
    fun apply [] ct = error (try_apply_err ct)
boehmes@36898
    92
      | apply (prover :: provers) ct =
boehmes@36898
    93
          (case try prover ct of
boehmes@40424
    94
            SOME thm => (SMT_Config.trace_msg ctxt I "Z3: succeeded"; thm)
boehmes@36898
    95
          | NONE => apply provers ct)
boehmes@36898
    96
boehmes@36898
    97
  in apply o cons (named ctxt "schematic rules" (by_schematic_rule ctxt)) end
boehmes@36898
    98
boehmes@36899
    99
local
boehmes@36899
   100
  val rewr_if =
boehmes@36899
   101
    @{lemma "(if P then Q1 else Q2) = ((P --> Q1) & (~P --> Q2))" by simp}
boehmes@36899
   102
in
boehmes@36899
   103
val simp_fast_tac =
boehmes@36899
   104
  Simplifier.simp_tac (HOL_ss addsimps [rewr_if])
boehmes@36899
   105
  THEN_ALL_NEW Classical.fast_tac HOL_cs
boehmes@36899
   106
end
boehmes@36899
   107
boehmes@36898
   108
boehmes@36898
   109
boehmes@36898
   110
(** theorems and proofs **)
boehmes@36898
   111
boehmes@36898
   112
(* theorem incarnations *)
boehmes@36898
   113
boehmes@36898
   114
datatype theorem =
boehmes@36898
   115
  Thm of thm | (* theorem without special features *)
boehmes@36898
   116
  MetaEq of thm | (* meta equality "t == s" *)
boehmes@36898
   117
  Literals of thm * L.littab
boehmes@36898
   118
    (* "P1 & ... & Pn" and table of all literals P1, ..., Pn *)
boehmes@36898
   119
boehmes@36898
   120
fun thm_of (Thm thm) = thm
boehmes@36898
   121
  | thm_of (MetaEq thm) = thm COMP @{thm meta_eq_to_obj_eq}
boehmes@36898
   122
  | thm_of (Literals (thm, _)) = thm
boehmes@36898
   123
boehmes@36898
   124
fun meta_eq_of (MetaEq thm) = thm
boehmes@36898
   125
  | meta_eq_of p = mk_meta_eq (thm_of p)
boehmes@36898
   126
boehmes@36898
   127
fun literals_of (Literals (_, lits)) = lits
boehmes@36898
   128
  | literals_of p = L.make_littab [thm_of p]
boehmes@36898
   129
boehmes@36898
   130
boehmes@36898
   131
(* proof representation *)
boehmes@36898
   132
boehmes@36898
   133
datatype proof = Unproved of P.proof_step | Proved of theorem
boehmes@36898
   134
boehmes@36898
   135
boehmes@36898
   136
boehmes@36898
   137
(** core proof rules **)
boehmes@36898
   138
boehmes@36898
   139
(* assumption *)
boehmes@36898
   140
boehmes@36898
   141
local
boehmes@36898
   142
  val remove_trigger = @{lemma "trigger t p == p"
boehmes@36898
   143
    by (rule eq_reflection, rule trigger_def)}
boehmes@36898
   144
boehmes@40664
   145
  val remove_weight = @{lemma "weight w p == p"
boehmes@40664
   146
    by (rule eq_reflection, rule weight_def)}
boehmes@40664
   147
boehmes@40664
   148
  val prep_rules = [@{thm Let_def}, remove_trigger, remove_weight,
boehmes@40664
   149
    L.rewrite_true]
boehmes@36898
   150
boehmes@36898
   151
  fun rewrite_conv ctxt eqs = Simplifier.full_rewrite
boehmes@36898
   152
    (Simplifier.context ctxt Simplifier.empty_ss addsimps eqs)
boehmes@36898
   153
boehmes@40164
   154
  fun rewrites f ctxt eqs = map (f (Conv.fconv_rule (rewrite_conv ctxt eqs)))
boehmes@36898
   155
boehmes@40164
   156
  fun burrow_snd_option f (i, thm) = Option.map (pair i) (f thm)
boehmes@36898
   157
  fun lookup_assm ctxt assms ct =
boehmes@40164
   158
    (case T.net_instance' burrow_snd_option assms ct of
boehmes@40164
   159
      SOME ithm => ithm
boehmes@36898
   160
    | _ => z3_exn ("not asserted: " ^
boehmes@36898
   161
        quote (Syntax.string_of_term ctxt (Thm.term_of ct))))
boehmes@36898
   162
in
boehmes@41127
   163
fun prepare_assms ctxt rewrite_rules assms =
boehmes@36898
   164
  let
boehmes@41127
   165
    val eqs = rewrites I ctxt [L.rewrite_true] rewrite_rules
boehmes@40164
   166
    val assms' =
boehmes@41127
   167
      assms
boehmes@41127
   168
      |> rewrites apsnd ctxt (union Thm.eq_thm eqs prep_rules)
boehmes@41127
   169
      |> map (apsnd (Conv.fconv_rule Thm.eta_conversion))
boehmes@41127
   170
  in (eqs, T.thm_net_of snd assms') end
boehmes@36898
   171
boehmes@41127
   172
fun asserted ctxt (eqs, assms) ct =
boehmes@41127
   173
  let val revert_conv = rewrite_conv ctxt eqs then_conv Thm.eta_conversion
boehmes@40164
   174
  in Thm (T.with_conv revert_conv (snd o lookup_assm ctxt assms) ct) end
boehmes@40164
   175
boehmes@40164
   176
fun find_assm ctxt (unfolds, assms) ct =
boehmes@40164
   177
  fst (lookup_assm ctxt assms (Thm.rhs_of (rewrite_conv ctxt unfolds ct)))
boehmes@36898
   178
end
boehmes@36898
   179
boehmes@36898
   180
boehmes@36898
   181
boehmes@36898
   182
(* P = Q ==> P ==> Q   or   P --> Q ==> P ==> Q *)
boehmes@36898
   183
local
boehmes@36898
   184
  val meta_iffD1 = @{lemma "P == Q ==> P ==> (Q::bool)" by simp}
boehmes@36898
   185
  val meta_iffD1_c = T.precompose2 Thm.dest_binop meta_iffD1
boehmes@36898
   186
boehmes@36898
   187
  val iffD1_c = T.precompose2 (Thm.dest_binop o Thm.dest_arg) @{thm iffD1}
boehmes@36898
   188
  val mp_c = T.precompose2 (Thm.dest_binop o Thm.dest_arg) @{thm mp}
boehmes@36898
   189
in
boehmes@36898
   190
fun mp (MetaEq thm) p = Thm (Thm.implies_elim (T.compose meta_iffD1_c thm) p)
boehmes@36898
   191
  | mp p_q p = 
boehmes@36898
   192
      let
boehmes@36898
   193
        val pq = thm_of p_q
boehmes@36898
   194
        val thm = T.compose iffD1_c pq handle THM _ => T.compose mp_c pq
boehmes@36898
   195
      in Thm (Thm.implies_elim thm p) end
boehmes@36898
   196
end
boehmes@36898
   197
boehmes@36898
   198
boehmes@36898
   199
boehmes@36898
   200
(* and_elim:     P1 & ... & Pn ==> Pi *)
boehmes@36898
   201
(* not_or_elim:  ~(P1 | ... | Pn) ==> ~Pi *)
boehmes@36898
   202
local
boehmes@36898
   203
  fun is_sublit conj t = L.exists_lit conj (fn u => u aconv t)
boehmes@36898
   204
boehmes@36898
   205
  fun derive conj t lits idx ptab =
boehmes@36898
   206
    let
boehmes@36898
   207
      val lit = the (L.get_first_lit (is_sublit conj t) lits)
boehmes@36898
   208
      val ls = L.explode conj false false [t] lit
boehmes@36898
   209
      val lits' = fold L.insert_lit ls (L.delete_lit lit lits)
boehmes@36898
   210
boehmes@36898
   211
      fun upd (Proved thm) = Proved (Literals (thm_of thm, lits'))
boehmes@36898
   212
        | upd p = p
boehmes@36898
   213
    in (the (L.lookup_lit lits' t), Inttab.map_entry idx upd ptab) end
boehmes@36898
   214
boehmes@36898
   215
  fun lit_elim conj (p, idx) ct ptab =
boehmes@36898
   216
    let val lits = literals_of p
boehmes@36898
   217
    in
boehmes@36898
   218
      (case L.lookup_lit lits (T.term_of ct) of
boehmes@36898
   219
        SOME lit => (Thm lit, ptab)
boehmes@36898
   220
      | NONE => apfst Thm (derive conj (T.term_of ct) lits idx ptab))
boehmes@36898
   221
    end
boehmes@36898
   222
in
boehmes@36898
   223
val and_elim = lit_elim true
boehmes@36898
   224
val not_or_elim = lit_elim false
boehmes@36898
   225
end
boehmes@36898
   226
boehmes@36898
   227
boehmes@36898
   228
boehmes@36898
   229
(* P1, ..., Pn |- False ==> |- ~P1 | ... | ~Pn *)
boehmes@36898
   230
local
boehmes@36898
   231
  fun step lit thm =
boehmes@36898
   232
    Thm.implies_elim (Thm.implies_intr (Thm.cprop_of lit) thm) lit
boehmes@36898
   233
  val explode_disj = L.explode false false false
boehmes@36898
   234
  fun intro hyps thm th = fold step (explode_disj hyps th) thm
boehmes@36898
   235
boehmes@36898
   236
  fun dest_ccontr ct = [Thm.dest_arg (Thm.dest_arg (Thm.dest_arg1 ct))]
boehmes@36898
   237
  val ccontr = T.precompose dest_ccontr @{thm ccontr}
boehmes@36898
   238
in
boehmes@36898
   239
fun lemma thm ct =
boehmes@36898
   240
  let
boehmes@40579
   241
    val cu = L.negate (Thm.dest_arg ct)
boehmes@36898
   242
    val hyps = map_filter (try HOLogic.dest_Trueprop) (#hyps (Thm.rep_thm thm))
boehmes@36898
   243
  in Thm (T.compose ccontr (T.under_assumption (intro hyps thm) cu)) end
boehmes@36898
   244
end
boehmes@36898
   245
boehmes@36898
   246
boehmes@36898
   247
boehmes@36898
   248
(* \/{P1, ..., Pn, Q1, ..., Qn}, ~P1, ..., ~Pn ==> \/{Q1, ..., Qn} *)
boehmes@36898
   249
local
boehmes@36898
   250
  val explode_disj = L.explode false true false
boehmes@36898
   251
  val join_disj = L.join false
boehmes@36898
   252
  fun unit thm thms th =
boehmes@40579
   253
    let val t = @{const Not} $ T.prop_of thm and ts = map T.prop_of thms
boehmes@36898
   254
    in join_disj (L.make_littab (thms @ explode_disj ts th)) t end
boehmes@36898
   255
boehmes@36898
   256
  fun dest_arg2 ct = Thm.dest_arg (Thm.dest_arg ct)
boehmes@36898
   257
  fun dest ct = pairself dest_arg2 (Thm.dest_binop ct)
boehmes@36898
   258
  val contrapos = T.precompose2 dest @{lemma "(~P ==> ~Q) ==> Q ==> P" by fast}
boehmes@36898
   259
in
boehmes@36898
   260
fun unit_resolution thm thms ct =
boehmes@40579
   261
  L.negate (Thm.dest_arg ct)
boehmes@36898
   262
  |> T.under_assumption (unit thm thms)
boehmes@36898
   263
  |> Thm o T.discharge thm o T.compose contrapos
boehmes@36898
   264
end
boehmes@36898
   265
boehmes@36898
   266
boehmes@36898
   267
boehmes@36898
   268
(* P ==> P == True   or   P ==> P == False *)
boehmes@36898
   269
local
boehmes@36898
   270
  val iff1 = @{lemma "P ==> P == (~ False)" by simp}
boehmes@36898
   271
  val iff2 = @{lemma "~P ==> P == False" by simp}
boehmes@36898
   272
in
boehmes@36898
   273
fun iff_true thm = MetaEq (thm COMP iff1)
boehmes@36898
   274
fun iff_false thm = MetaEq (thm COMP iff2)
boehmes@36898
   275
end
boehmes@36898
   276
boehmes@36898
   277
boehmes@36898
   278
boehmes@36898
   279
(* distributivity of | over & *)
boehmes@36898
   280
fun distributivity ctxt = Thm o try_apply ctxt [] [
boehmes@36899
   281
  named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
boehmes@36898
   282
    (* FIXME: not very well tested *)
boehmes@36898
   283
boehmes@36898
   284
boehmes@36898
   285
boehmes@36898
   286
(* Tseitin-like axioms *)
boehmes@36898
   287
boehmes@36898
   288
local
boehmes@36898
   289
  val disjI1 = @{lemma "(P ==> Q) ==> ~P | Q" by fast}
boehmes@36898
   290
  val disjI2 = @{lemma "(~P ==> Q) ==> P | Q" by fast}
boehmes@36898
   291
  val disjI3 = @{lemma "(~Q ==> P) ==> P | Q" by fast}
boehmes@36898
   292
  val disjI4 = @{lemma "(Q ==> P) ==> P | ~Q" by fast}
boehmes@36898
   293
boehmes@36898
   294
  fun prove' conj1 conj2 ct2 thm =
boehmes@36898
   295
    let val lits = L.true_thm :: L.explode conj1 true (conj1 <> conj2) [] thm
boehmes@36898
   296
    in L.join conj2 (L.make_littab lits) (Thm.term_of ct2) end
boehmes@36898
   297
boehmes@36898
   298
  fun prove rule (ct1, conj1) (ct2, conj2) =
boehmes@36898
   299
    T.under_assumption (prove' conj1 conj2 ct2) ct1 COMP rule
boehmes@36898
   300
boehmes@36898
   301
  fun prove_def_axiom ct =
boehmes@36898
   302
    let val (ct1, ct2) = Thm.dest_binop (Thm.dest_arg ct)
boehmes@36898
   303
    in
boehmes@36898
   304
      (case Thm.term_of ct1 of
boehmes@40579
   305
        @{const Not} $ (@{const HOL.conj} $ _ $ _) =>
boehmes@36898
   306
          prove disjI1 (Thm.dest_arg ct1, true) (ct2, true)
boehmes@40579
   307
      | @{const HOL.conj} $ _ $ _ =>
boehmes@40579
   308
          prove disjI3 (L.negate ct2, false) (ct1, true)
boehmes@40579
   309
      | @{const Not} $ (@{const HOL.disj} $ _ $ _) =>
boehmes@40579
   310
          prove disjI3 (L.negate ct2, false) (ct1, false)
boehmes@40579
   311
      | @{const HOL.disj} $ _ $ _ =>
boehmes@40579
   312
          prove disjI2 (L.negate ct1, false) (ct2, true)
boehmes@40681
   313
      | Const (@{const_name distinct}, _) $ _ =>
boehmes@36898
   314
          let
boehmes@36898
   315
            fun dis_conv cv = Conv.arg_conv (Conv.arg1_conv cv)
boehmes@36898
   316
            fun prv cu =
boehmes@36898
   317
              let val (cu1, cu2) = Thm.dest_binop (Thm.dest_arg cu)
boehmes@36898
   318
              in prove disjI4 (Thm.dest_arg cu2, true) (cu1, true) end
boehmes@36898
   319
          in T.with_conv (dis_conv T.unfold_distinct_conv) prv ct end
boehmes@40681
   320
      | @{const Not} $ (Const (@{const_name distinct}, _) $ _) =>
boehmes@36898
   321
          let
boehmes@36898
   322
            fun dis_conv cv = Conv.arg_conv (Conv.arg1_conv (Conv.arg_conv cv))
boehmes@36898
   323
            fun prv cu =
boehmes@36898
   324
              let val (cu1, cu2) = Thm.dest_binop (Thm.dest_arg cu)
boehmes@36898
   325
              in prove disjI1 (Thm.dest_arg cu1, true) (cu2, true) end
boehmes@36898
   326
          in T.with_conv (dis_conv T.unfold_distinct_conv) prv ct end
boehmes@36898
   327
      | _ => raise CTERM ("prove_def_axiom", [ct]))
boehmes@36898
   328
    end
boehmes@36898
   329
in
boehmes@36898
   330
fun def_axiom ctxt = Thm o try_apply ctxt [] [
boehmes@36898
   331
  named ctxt "conj/disj/distinct" prove_def_axiom,
boehmes@36899
   332
  T.by_abstraction (true, false) ctxt [] (fn ctxt' =>
boehmes@36899
   333
    named ctxt' "simp+fast" (T.by_tac simp_fast_tac))]
boehmes@36898
   334
end
boehmes@36898
   335
boehmes@36898
   336
boehmes@36898
   337
boehmes@36898
   338
(* local definitions *)
boehmes@36898
   339
local
boehmes@36898
   340
  val intro_rules = [
boehmes@36898
   341
    @{lemma "n == P ==> (~n | P) & (n | ~P)" by simp},
boehmes@36898
   342
    @{lemma "n == (if P then s else t) ==> (~P | n = s) & (P | n = t)"
boehmes@36898
   343
      by simp},
boehmes@36898
   344
    @{lemma "n == P ==> n = P" by (rule meta_eq_to_obj_eq)} ]
boehmes@36898
   345
boehmes@36898
   346
  val apply_rules = [
boehmes@36898
   347
    @{lemma "(~n | P) & (n | ~P) ==> P == n" by (atomize(full)) fast},
boehmes@36898
   348
    @{lemma "(~P | n = s) & (P | n = t) ==> (if P then s else t) == n"
boehmes@36898
   349
      by (atomize(full)) fastsimp} ]
boehmes@36898
   350
boehmes@36898
   351
  val inst_rule = T.match_instantiate Thm.dest_arg
boehmes@36898
   352
boehmes@36898
   353
  fun apply_rule ct =
boehmes@36898
   354
    (case get_first (try (inst_rule ct)) intro_rules of
boehmes@36898
   355
      SOME thm => thm
boehmes@36898
   356
    | NONE => raise CTERM ("intro_def", [ct]))
boehmes@36898
   357
in
boehmes@36898
   358
fun intro_def ct = T.make_hyp_def (apply_rule ct) #>> Thm
boehmes@36898
   359
boehmes@36898
   360
fun apply_def thm =
boehmes@36898
   361
  get_first (try (fn rule => MetaEq (thm COMP rule))) apply_rules
boehmes@36898
   362
  |> the_default (Thm thm)
boehmes@36898
   363
end
boehmes@36898
   364
boehmes@36898
   365
boehmes@36898
   366
boehmes@36898
   367
(* negation normal form *)
boehmes@36898
   368
boehmes@36898
   369
local
boehmes@36898
   370
  val quant_rules1 = ([
boehmes@36898
   371
    @{lemma "(!!x. P x == Q) ==> ALL x. P x == Q" by simp},
boehmes@36898
   372
    @{lemma "(!!x. P x == Q) ==> EX x. P x == Q" by simp}], [
boehmes@36898
   373
    @{lemma "(!!x. P x == Q x) ==> ALL x. P x == ALL x. Q x" by simp},
boehmes@36898
   374
    @{lemma "(!!x. P x == Q x) ==> EX x. P x == EX x. Q x" by simp}])
boehmes@36898
   375
boehmes@36898
   376
  val quant_rules2 = ([
boehmes@36898
   377
    @{lemma "(!!x. ~P x == Q) ==> ~(ALL x. P x) == Q" by simp},
boehmes@36898
   378
    @{lemma "(!!x. ~P x == Q) ==> ~(EX x. P x) == Q" by simp}], [
boehmes@36898
   379
    @{lemma "(!!x. ~P x == Q x) ==> ~(ALL x. P x) == EX x. Q x" by simp},
boehmes@36898
   380
    @{lemma "(!!x. ~P x == Q x) ==> ~(EX x. P x) == ALL x. Q x" by simp}])
boehmes@36898
   381
boehmes@36898
   382
  fun nnf_quant_tac thm (qs as (qs1, qs2)) i st = (
boehmes@36898
   383
    Tactic.rtac thm ORELSE'
boehmes@36898
   384
    (Tactic.match_tac qs1 THEN' nnf_quant_tac thm qs) ORELSE'
boehmes@36898
   385
    (Tactic.match_tac qs2 THEN' nnf_quant_tac thm qs)) i st
boehmes@36898
   386
boehmes@36898
   387
  fun nnf_quant vars qs p ct =
boehmes@36898
   388
    T.as_meta_eq ct
boehmes@36898
   389
    |> T.by_tac (nnf_quant_tac (T.varify vars (meta_eq_of p)) qs)
boehmes@36898
   390
boehmes@36898
   391
  fun prove_nnf ctxt = try_apply ctxt [] [
boehmes@36899
   392
    named ctxt "conj/disj" L.prove_conj_disj_eq,
boehmes@36899
   393
    T.by_abstraction (true, false) ctxt [] (fn ctxt' =>
boehmes@36899
   394
      named ctxt' "simp+fast" (T.by_tac simp_fast_tac))]
boehmes@36898
   395
in
boehmes@36898
   396
fun nnf ctxt vars ps ct =
boehmes@36898
   397
  (case T.term_of ct of
boehmes@36898
   398
    _ $ (l as Const _ $ Abs _) $ (r as Const _ $ Abs _) =>
boehmes@36898
   399
      if l aconv r
boehmes@36898
   400
      then MetaEq (Thm.reflexive (Thm.dest_arg (Thm.dest_arg ct)))
boehmes@36898
   401
      else MetaEq (nnf_quant vars quant_rules1 (hd ps) ct)
boehmes@40579
   402
  | _ $ (@{const Not} $ (Const _ $ Abs _)) $ (Const _ $ Abs _) =>
boehmes@36898
   403
      MetaEq (nnf_quant vars quant_rules2 (hd ps) ct)
boehmes@36898
   404
  | _ =>
boehmes@36898
   405
      let
boehmes@36898
   406
        val nnf_rewr_conv = Conv.arg_conv (Conv.arg_conv
boehmes@36898
   407
          (T.unfold_eqs ctxt (map (Thm.symmetric o meta_eq_of) ps)))
boehmes@36898
   408
      in Thm (T.with_conv nnf_rewr_conv (prove_nnf ctxt) ct) end)
boehmes@36898
   409
end
boehmes@36898
   410
boehmes@36898
   411
boehmes@36898
   412
boehmes@36898
   413
(** equality proof rules **)
boehmes@36898
   414
boehmes@36898
   415
(* |- t = t *)
boehmes@36898
   416
fun refl ct = MetaEq (Thm.reflexive (Thm.dest_arg (Thm.dest_arg ct)))
boehmes@36898
   417
boehmes@36898
   418
boehmes@36898
   419
boehmes@36898
   420
(* s = t ==> t = s *)
boehmes@36898
   421
local
boehmes@36898
   422
  val symm_rule = @{lemma "s = t ==> t == s" by simp}
boehmes@36898
   423
in
boehmes@36898
   424
fun symm (MetaEq thm) = MetaEq (Thm.symmetric thm)
boehmes@36898
   425
  | symm p = MetaEq (thm_of p COMP symm_rule)
boehmes@36898
   426
end
boehmes@36898
   427
boehmes@36898
   428
boehmes@36898
   429
boehmes@36898
   430
(* s = t ==> t = u ==> s = u *)
boehmes@36898
   431
local
boehmes@36898
   432
  val trans1 = @{lemma "s == t ==> t =  u ==> s == u" by simp}
boehmes@36898
   433
  val trans2 = @{lemma "s =  t ==> t == u ==> s == u" by simp}
boehmes@36898
   434
  val trans3 = @{lemma "s =  t ==> t =  u ==> s == u" by simp}
boehmes@36898
   435
in
boehmes@36898
   436
fun trans (MetaEq thm1) (MetaEq thm2) = MetaEq (Thm.transitive thm1 thm2)
boehmes@36898
   437
  | trans (MetaEq thm) q = MetaEq (thm_of q COMP (thm COMP trans1))
boehmes@36898
   438
  | trans p (MetaEq thm) = MetaEq (thm COMP (thm_of p COMP trans2))
boehmes@36898
   439
  | trans p q = MetaEq (thm_of q COMP (thm_of p COMP trans3))
boehmes@36898
   440
end
boehmes@36898
   441
boehmes@36898
   442
boehmes@36898
   443
boehmes@36898
   444
(* t1 = s1 ==> ... ==> tn = sn ==> f t1 ... tn = f s1 .. sn
boehmes@36898
   445
   (reflexive antecendents are droppped) *)
boehmes@36898
   446
local
boehmes@36898
   447
  exception MONO
boehmes@36898
   448
boehmes@36898
   449
  fun prove_refl (ct, _) = Thm.reflexive ct
boehmes@36898
   450
  fun prove_comb f g cp =
boehmes@36898
   451
    let val ((ct1, ct2), (cu1, cu2)) = pairself Thm.dest_comb cp
boehmes@36898
   452
    in Thm.combination (f (ct1, cu1)) (g (ct2, cu2)) end
boehmes@36898
   453
  fun prove_arg f = prove_comb prove_refl f
boehmes@36898
   454
boehmes@36898
   455
  fun prove f cp = prove_comb (prove f) f cp handle CTERM _ => prove_refl cp
boehmes@36898
   456
boehmes@36898
   457
  fun prove_nary is_comb f =
boehmes@36898
   458
    let
boehmes@36898
   459
      fun prove (cp as (ct, _)) = f cp handle MONO =>
boehmes@36898
   460
        if is_comb (Thm.term_of ct)
boehmes@36898
   461
        then prove_comb (prove_arg prove) prove cp
boehmes@36898
   462
        else prove_refl cp
boehmes@36898
   463
    in prove end
boehmes@36898
   464
boehmes@36898
   465
  fun prove_list f n cp =
boehmes@36898
   466
    if n = 0 then prove_refl cp
boehmes@36898
   467
    else prove_comb (prove_arg f) (prove_list f (n-1)) cp
boehmes@36898
   468
boehmes@36898
   469
  fun with_length f (cp as (cl, _)) =
boehmes@36898
   470
    f (length (HOLogic.dest_list (Thm.term_of cl))) cp
boehmes@36898
   471
boehmes@36898
   472
  fun prove_distinct f = prove_arg (with_length (prove_list f))
boehmes@36898
   473
boehmes@36898
   474
  fun prove_eq exn lookup cp =
boehmes@36898
   475
    (case lookup (Logic.mk_equals (pairself Thm.term_of cp)) of
boehmes@36898
   476
      SOME eq => eq
boehmes@36898
   477
    | NONE => if exn then raise MONO else prove_refl cp)
boehmes@36898
   478
  
boehmes@36898
   479
  val prove_eq_exn = prove_eq true
boehmes@36898
   480
  and prove_eq_safe = prove_eq false
boehmes@36898
   481
boehmes@36898
   482
  fun mono f (cp as (cl, _)) =
boehmes@36898
   483
    (case Term.head_of (Thm.term_of cl) of
boehmes@40579
   484
      @{const HOL.conj} => prove_nary L.is_conj (prove_eq_exn f)
boehmes@40579
   485
    | @{const HOL.disj} => prove_nary L.is_disj (prove_eq_exn f)
boehmes@40681
   486
    | Const (@{const_name distinct}, _) => prove_distinct (prove_eq_safe f)
boehmes@36898
   487
    | _ => prove (prove_eq_safe f)) cp
boehmes@36898
   488
in
boehmes@36898
   489
fun monotonicity eqs ct =
boehmes@36898
   490
  let
boehmes@40680
   491
    fun and_symmetric (t, thm) = [(t, thm), (t, Thm.symmetric thm)]
boehmes@40680
   492
    val teqs = maps (and_symmetric o `Thm.prop_of o meta_eq_of) eqs
boehmes@40680
   493
    val lookup = AList.lookup (op aconv) teqs
boehmes@36898
   494
    val cp = Thm.dest_binop (Thm.dest_arg ct)
boehmes@36898
   495
  in MetaEq (prove_eq_exn lookup cp handle MONO => mono lookup cp) end
boehmes@36898
   496
end
boehmes@36898
   497
boehmes@36898
   498
boehmes@36898
   499
boehmes@36898
   500
(* |- f a b = f b a (where f is equality) *)
boehmes@36898
   501
local
boehmes@36898
   502
  val rule = @{lemma "a = b == b = a" by (atomize(full)) (rule eq_commute)}
boehmes@36898
   503
in
boehmes@36898
   504
fun commutativity ct = MetaEq (T.match_instantiate I (T.as_meta_eq ct) rule)
boehmes@36898
   505
end
boehmes@36898
   506
boehmes@36898
   507
boehmes@36898
   508
boehmes@36898
   509
(** quantifier proof rules **)
boehmes@36898
   510
boehmes@36898
   511
(* P ?x = Q ?x ==> (ALL x. P x) = (ALL x. Q x)
boehmes@36898
   512
   P ?x = Q ?x ==> (EX x. P x) = (EX x. Q x)    *)
boehmes@36898
   513
local
boehmes@36898
   514
  val rules = [
boehmes@36898
   515
    @{lemma "(!!x. P x == Q x) ==> (ALL x. P x) == (ALL x. Q x)" by simp},
boehmes@36898
   516
    @{lemma "(!!x. P x == Q x) ==> (EX x. P x) == (EX x. Q x)" by simp}]
boehmes@36898
   517
in
boehmes@36898
   518
fun quant_intro vars p ct =
boehmes@36898
   519
  let
boehmes@36898
   520
    val thm = meta_eq_of p
boehmes@36898
   521
    val rules' = T.varify vars thm :: rules
boehmes@36898
   522
    val cu = T.as_meta_eq ct
boehmes@36898
   523
  in MetaEq (T.by_tac (REPEAT_ALL_NEW (Tactic.match_tac rules')) cu) end
boehmes@36898
   524
end
boehmes@36898
   525
boehmes@36898
   526
boehmes@36898
   527
boehmes@36898
   528
(* |- ((ALL x. P x) | Q) = (ALL x. P x | Q) *)
boehmes@36898
   529
fun pull_quant ctxt = Thm o try_apply ctxt [] [
boehmes@36898
   530
  named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
boehmes@36898
   531
    (* FIXME: not very well tested *)
boehmes@36898
   532
boehmes@36898
   533
boehmes@36898
   534
boehmes@36898
   535
(* |- (ALL x. P x & Q x) = ((ALL x. P x) & (ALL x. Q x)) *)
boehmes@36898
   536
fun push_quant ctxt = Thm o try_apply ctxt [] [
boehmes@36898
   537
  named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
boehmes@36898
   538
    (* FIXME: not very well tested *)
boehmes@36898
   539
boehmes@36898
   540
boehmes@36898
   541
boehmes@36898
   542
(* |- (ALL x1 ... xn y1 ... yn. P x1 ... xn) = (ALL x1 ... xn. P x1 ... xn) *)
boehmes@36898
   543
local
boehmes@36898
   544
  val elim_all = @{lemma "(ALL x. P) == P" by simp}
boehmes@36898
   545
  val elim_ex = @{lemma "(EX x. P) == P" by simp}
boehmes@36898
   546
boehmes@36898
   547
  fun elim_unused_conv ctxt =
boehmes@36898
   548
    Conv.params_conv ~1 (K (Conv.arg_conv (Conv.arg1_conv
wenzelm@36936
   549
      (Conv.rewrs_conv [elim_all, elim_ex])))) ctxt
boehmes@36898
   550
boehmes@36898
   551
  fun elim_unused_tac ctxt =
boehmes@36898
   552
    REPEAT_ALL_NEW (
boehmes@36898
   553
      Tactic.match_tac [@{thm refl}, @{thm iff_allI}, @{thm iff_exI}]
boehmes@36898
   554
      ORELSE' CONVERSION (elim_unused_conv ctxt))
boehmes@36898
   555
in
boehmes@36898
   556
fun elim_unused_vars ctxt = Thm o T.by_tac (elim_unused_tac ctxt)
boehmes@36898
   557
end
boehmes@36898
   558
boehmes@36898
   559
boehmes@36898
   560
boehmes@36898
   561
(* |- (ALL x1 ... xn. ~(x1 = t1 & ... xn = tn) | P x1 ... xn) = P t1 ... tn *)
boehmes@36898
   562
fun dest_eq_res ctxt = Thm o try_apply ctxt [] [
boehmes@36898
   563
  named ctxt "fast" (T.by_tac (Classical.fast_tac HOL_cs))]
boehmes@36898
   564
    (* FIXME: not very well tested *)
boehmes@36898
   565
boehmes@36898
   566
boehmes@36898
   567
boehmes@36898
   568
(* |- ~(ALL x1...xn. P x1...xn) | P a1...an *)
boehmes@36898
   569
local
boehmes@36898
   570
  val rule = @{lemma "~ P x | Q ==> ~(ALL x. P x) | Q" by fast}
boehmes@36898
   571
in
boehmes@36898
   572
val quant_inst = Thm o T.by_tac (
boehmes@36898
   573
  REPEAT_ALL_NEW (Tactic.match_tac [rule])
boehmes@36898
   574
  THEN' Tactic.rtac @{thm excluded_middle})
boehmes@36898
   575
end
boehmes@36898
   576
boehmes@36898
   577
boehmes@36898
   578
boehmes@36898
   579
(* c = SOME x. P x |- (EX x. P x) = P c
boehmes@36898
   580
   c = SOME x. ~ P x |- ~(ALL x. P x) = ~ P c *)
boehmes@36898
   581
local
boehmes@36898
   582
  val elim_ex = @{lemma "EX x. P == P" by simp}
boehmes@36898
   583
  val elim_all = @{lemma "~ (ALL x. P) == ~P" by simp}
boehmes@36898
   584
  val sk_ex = @{lemma "c == SOME x. P x ==> EX x. P x == P c"
boehmes@36898
   585
    by simp (intro eq_reflection some_eq_ex[symmetric])}
boehmes@36898
   586
  val sk_all = @{lemma "c == SOME x. ~ P x ==> ~(ALL x. P x) == ~ P c"
boehmes@36898
   587
    by (simp only: not_all) (intro eq_reflection some_eq_ex[symmetric])}
boehmes@36898
   588
  val sk_ex_rule = ((sk_ex, I), elim_ex)
boehmes@36898
   589
  and sk_all_rule = ((sk_all, Thm.dest_arg), elim_all)
boehmes@36898
   590
boehmes@36898
   591
  fun dest f sk_rule = 
boehmes@36898
   592
    Thm.dest_comb (f (Thm.dest_arg (Thm.dest_arg (Thm.cprop_of sk_rule))))
boehmes@36898
   593
  fun type_of f sk_rule = Thm.ctyp_of_term (snd (dest f sk_rule))
boehmes@36898
   594
  fun pair2 (a, b) (c, d) = [(a, c), (b, d)]
boehmes@36898
   595
  fun inst_sk (sk_rule, f) p c =
boehmes@36898
   596
    Thm.instantiate ([(type_of f sk_rule, Thm.ctyp_of_term c)], []) sk_rule
boehmes@36898
   597
    |> (fn sk' => Thm.instantiate ([], (pair2 (dest f sk') (p, c))) sk')
boehmes@36898
   598
    |> Conv.fconv_rule (Thm.beta_conversion true)
boehmes@36898
   599
boehmes@36898
   600
  fun kind (Const (@{const_name Ex}, _) $ _) = (sk_ex_rule, I, I)
boehmes@40579
   601
    | kind (@{const Not} $ (Const (@{const_name All}, _) $ _)) =
boehmes@40579
   602
        (sk_all_rule, Thm.dest_arg, L.negate)
boehmes@36898
   603
    | kind t = raise TERM ("skolemize", [t])
boehmes@36898
   604
boehmes@36898
   605
  fun dest_abs_type (Abs (_, T, _)) = T
boehmes@36898
   606
    | dest_abs_type t = raise TERM ("dest_abs_type", [t])
boehmes@36898
   607
boehmes@36898
   608
  fun bodies_of thy lhs rhs =
boehmes@36898
   609
    let
boehmes@36898
   610
      val (rule, dest, make) = kind (Thm.term_of lhs)
boehmes@36898
   611
boehmes@36898
   612
      fun dest_body idx cbs ct =
boehmes@36898
   613
        let
boehmes@36898
   614
          val cb = Thm.dest_arg (dest ct)
boehmes@36898
   615
          val T = dest_abs_type (Thm.term_of cb)
boehmes@36898
   616
          val cv = Thm.cterm_of thy (Var (("x", idx), T))
boehmes@36898
   617
          val cu = make (Drule.beta_conv cb cv)
boehmes@36898
   618
          val cbs' = (cv, cb) :: cbs
boehmes@36898
   619
        in
boehmes@36898
   620
          (snd (Thm.first_order_match (cu, rhs)), rev cbs')
boehmes@36898
   621
          handle Pattern.MATCH => dest_body (idx+1) cbs' cu
boehmes@36898
   622
        end
boehmes@36898
   623
    in (rule, dest_body 1 [] lhs) end
boehmes@36898
   624
boehmes@36898
   625
  fun transitive f thm = Thm.transitive thm (f (Thm.rhs_of thm))
boehmes@36898
   626
boehmes@36898
   627
  fun sk_step (rule, elim) (cv, mct, cb) ((is, thm), ctxt) =
boehmes@36898
   628
    (case mct of
boehmes@36898
   629
      SOME ct =>
boehmes@36898
   630
        ctxt
boehmes@36898
   631
        |> T.make_hyp_def (inst_sk rule (Thm.instantiate_cterm ([], is) cb) ct)
boehmes@36898
   632
        |>> pair ((cv, ct) :: is) o Thm.transitive thm
boehmes@36898
   633
    | NONE => ((is, transitive (Conv.rewr_conv elim) thm), ctxt))
boehmes@36898
   634
in
boehmes@36898
   635
fun skolemize ct ctxt =
boehmes@36898
   636
  let
boehmes@36898
   637
    val (lhs, rhs) = Thm.dest_binop (Thm.dest_arg ct)
boehmes@36898
   638
    val (rule, (ctab, cbs)) = bodies_of (ProofContext.theory_of ctxt) lhs rhs
boehmes@36898
   639
    fun lookup_var (cv, cb) = (cv, AList.lookup (op aconvc) ctab cv, cb)
boehmes@36898
   640
  in
boehmes@36898
   641
    (([], Thm.reflexive lhs), ctxt)
boehmes@36898
   642
    |> fold (sk_step rule) (map lookup_var cbs)
boehmes@36898
   643
    |>> MetaEq o snd
boehmes@36898
   644
  end
boehmes@36898
   645
end
boehmes@36898
   646
boehmes@36898
   647
boehmes@36898
   648
boehmes@36898
   649
(** theory proof rules **)
boehmes@36898
   650
boehmes@36898
   651
(* theory lemmas: linear arithmetic, arrays *)
boehmes@36898
   652
boehmes@36898
   653
fun th_lemma ctxt simpset thms = Thm o try_apply ctxt thms [
boehmes@36899
   654
  T.by_abstraction (false, true) ctxt thms (fn ctxt' => T.by_tac (
boehmes@36898
   655
    NAMED ctxt' "arith" (Arith_Data.arith_tac ctxt')
boehmes@36898
   656
    ORELSE' NAMED ctxt' "simp+arith" (Simplifier.simp_tac simpset THEN_ALL_NEW
boehmes@36898
   657
      Arith_Data.arith_tac ctxt')))]
boehmes@36898
   658
boehmes@36898
   659
boehmes@36898
   660
boehmes@36898
   661
(* rewriting: prove equalities:
boehmes@36898
   662
     * ACI of conjunction/disjunction
boehmes@36898
   663
     * contradiction, excluded middle
boehmes@36898
   664
     * logical rewriting rules (for negation, implication, equivalence,
boehmes@36898
   665
         distinct)
boehmes@36898
   666
     * normal forms for polynoms (integer/real arithmetic)
boehmes@36898
   667
     * quantifier elimination over linear arithmetic
boehmes@36898
   668
     * ... ? **)
boehmes@36898
   669
structure Z3_Simps = Named_Thms
boehmes@36898
   670
(
boehmes@36898
   671
  val name = "z3_simp"
boehmes@36898
   672
  val description = "simplification rules for Z3 proof reconstruction"
boehmes@36898
   673
)
boehmes@36898
   674
boehmes@36898
   675
local
boehmes@36898
   676
  fun spec_meta_eq_of thm =
boehmes@36898
   677
    (case try (fn th => th RS @{thm spec}) thm of
boehmes@36898
   678
      SOME thm' => spec_meta_eq_of thm'
boehmes@36898
   679
    | NONE => mk_meta_eq thm)
boehmes@36898
   680
boehmes@36898
   681
  fun prep (Thm thm) = spec_meta_eq_of thm
boehmes@36898
   682
    | prep (MetaEq thm) = thm
boehmes@36898
   683
    | prep (Literals (thm, _)) = spec_meta_eq_of thm
boehmes@36898
   684
boehmes@36898
   685
  fun unfold_conv ctxt ths =
boehmes@36898
   686
    Conv.arg_conv (Conv.binop_conv (T.unfold_eqs ctxt (map prep ths)))
boehmes@36898
   687
boehmes@36898
   688
  fun with_conv _ [] prv = prv
boehmes@36898
   689
    | with_conv ctxt ths prv = T.with_conv (unfold_conv ctxt ths) prv
boehmes@36898
   690
boehmes@36898
   691
  val unfold_conv =
boehmes@36898
   692
    Conv.arg_conv (Conv.binop_conv (Conv.try_conv T.unfold_distinct_conv))
boehmes@36898
   693
  val prove_conj_disj_eq = T.with_conv unfold_conv L.prove_conj_disj_eq
boehmes@40663
   694
boehmes@40663
   695
  fun assume_prems ctxt thm =
boehmes@40663
   696
    Assumption.add_assumes (Drule.cprems_of thm) ctxt
boehmes@40663
   697
    |>> (fn thms => fold Thm.elim_implies thms thm)
boehmes@36898
   698
in
boehmes@36898
   699
boehmes@40663
   700
fun rewrite simpset ths ct ctxt =
boehmes@40663
   701
  apfst Thm (assume_prems ctxt (with_conv ctxt ths (try_apply ctxt [] [
boehmes@40663
   702
    named ctxt "conj/disj/distinct" prove_conj_disj_eq,
boehmes@40663
   703
    T.by_abstraction (true, false) ctxt [] (fn ctxt' => T.by_tac (
boehmes@40663
   704
      NAMED ctxt' "simp (logic)" (Simplifier.simp_tac simpset)
boehmes@40663
   705
      THEN_ALL_NEW NAMED ctxt' "fast (logic)" (Classical.fast_tac HOL_cs))),
boehmes@40663
   706
    T.by_abstraction (false, true) ctxt [] (fn ctxt' => T.by_tac (
boehmes@40663
   707
      NAMED ctxt' "simp (theory)" (Simplifier.simp_tac simpset)
boehmes@40663
   708
      THEN_ALL_NEW (
boehmes@40663
   709
        NAMED ctxt' "fast (theory)" (Classical.fast_tac HOL_cs)
boehmes@40663
   710
        ORELSE' NAMED ctxt' "arith (theory)" (Arith_Data.arith_tac ctxt')))),
boehmes@40663
   711
    T.by_abstraction (true, true) ctxt [] (fn ctxt' => T.by_tac (
boehmes@40663
   712
      NAMED ctxt' "simp (full)" (Simplifier.simp_tac simpset)
boehmes@40663
   713
      THEN_ALL_NEW (
boehmes@40663
   714
        NAMED ctxt' "fast (full)" (Classical.fast_tac HOL_cs)
boehmes@40663
   715
        ORELSE' NAMED ctxt' "arith (full)" (Arith_Data.arith_tac ctxt')))),
boehmes@40663
   716
    named ctxt "injectivity" (M.prove_injectivity ctxt)]) ct))
boehmes@36898
   717
boehmes@36898
   718
end
boehmes@36898
   719
boehmes@36898
   720
boehmes@36898
   721
boehmes@36898
   722
(** proof reconstruction **)
boehmes@36898
   723
boehmes@36898
   724
(* tracing and checking *)
boehmes@36898
   725
boehmes@36898
   726
local
boehmes@36898
   727
  fun count_rules ptab =
boehmes@36898
   728
    let
boehmes@36898
   729
      fun count (_, Unproved _) (solved, total) = (solved, total + 1)
boehmes@36898
   730
        | count (_, Proved _) (solved, total) = (solved + 1, total + 1)
boehmes@36898
   731
    in Inttab.fold count ptab (0, 0) end
boehmes@36898
   732
boehmes@36898
   733
  fun header idx r (solved, total) = 
boehmes@36898
   734
    "Z3: #" ^ string_of_int idx ^ ": " ^ P.string_of_rule r ^ " (goal " ^
boehmes@36898
   735
    string_of_int (solved + 1) ^ " of " ^ string_of_int total ^ ")"
boehmes@36898
   736
boehmes@36898
   737
  fun check ctxt idx r ps ct p =
boehmes@36898
   738
    let val thm = thm_of p |> tap (Thm.join_proofs o single)
boehmes@36898
   739
    in
boehmes@36898
   740
      if (Thm.cprop_of thm) aconvc ct then ()
boehmes@36898
   741
      else z3_exn (Pretty.string_of (Pretty.big_list ("proof step failed: " ^
boehmes@36898
   742
        quote (P.string_of_rule r) ^ " (#" ^ string_of_int idx ^ ")")
boehmes@36898
   743
          (pretty_goal ctxt (map (thm_of o fst) ps) (Thm.prop_of thm) @
boehmes@36898
   744
           [Pretty.block [Pretty.str "expected: ",
boehmes@36898
   745
            Syntax.pretty_term ctxt (Thm.term_of ct)]])))
boehmes@36898
   746
    end
boehmes@36898
   747
in
boehmes@36898
   748
fun trace_rule idx prove r ps ct (cxp as (ctxt, ptab)) =
boehmes@36898
   749
  let
boehmes@40424
   750
    val _ = SMT_Config.trace_msg ctxt (header idx r o count_rules) ptab
boehmes@36899
   751
    val result as (p, (ctxt', _)) = prove r ps ct cxp
boehmes@40424
   752
    val _ = if not (Config.get ctxt' SMT_Config.trace) then ()
boehmes@36898
   753
      else check ctxt' idx r ps ct p
boehmes@36898
   754
  in result end
boehmes@36898
   755
end
boehmes@36898
   756
boehmes@36898
   757
boehmes@36898
   758
(* overall reconstruction procedure *)
boehmes@36898
   759
boehmes@40164
   760
local
boehmes@40164
   761
  fun not_supported r = raise Fail ("Z3: proof rule not implemented: " ^
boehmes@40164
   762
    quote (P.string_of_rule r))
boehmes@36898
   763
boehmes@40164
   764
  fun step assms simpset vars r ps ct (cxp as (cx, ptab)) =
boehmes@40164
   765
    (case (r, ps) of
boehmes@40164
   766
      (* core rules *)
boehmes@40164
   767
      (P.TrueAxiom, _) => (Thm L.true_thm, cxp)
boehmes@40164
   768
    | (P.Asserted, _) => (asserted cx assms ct, cxp)
boehmes@40164
   769
    | (P.Goal, _) => (asserted cx assms ct, cxp)
boehmes@40164
   770
    | (P.ModusPonens, [(p, _), (q, _)]) => (mp q (thm_of p), cxp)
boehmes@40164
   771
    | (P.ModusPonensOeq, [(p, _), (q, _)]) => (mp q (thm_of p), cxp)
boehmes@40164
   772
    | (P.AndElim, [(p, i)]) => and_elim (p, i) ct ptab ||> pair cx
boehmes@40164
   773
    | (P.NotOrElim, [(p, i)]) => not_or_elim (p, i) ct ptab ||> pair cx
boehmes@40164
   774
    | (P.Hypothesis, _) => (Thm (Thm.assume ct), cxp)
boehmes@40164
   775
    | (P.Lemma, [(p, _)]) => (lemma (thm_of p) ct, cxp)
boehmes@40164
   776
    | (P.UnitResolution, (p, _) :: ps) =>
boehmes@40164
   777
        (unit_resolution (thm_of p) (map (thm_of o fst) ps) ct, cxp)
boehmes@40164
   778
    | (P.IffTrue, [(p, _)]) => (iff_true (thm_of p), cxp)
boehmes@40164
   779
    | (P.IffFalse, [(p, _)]) => (iff_false (thm_of p), cxp)
boehmes@40164
   780
    | (P.Distributivity, _) => (distributivity cx ct, cxp)
boehmes@40164
   781
    | (P.DefAxiom, _) => (def_axiom cx ct, cxp)
boehmes@40164
   782
    | (P.IntroDef, _) => intro_def ct cx ||> rpair ptab
boehmes@40164
   783
    | (P.ApplyDef, [(p, _)]) => (apply_def (thm_of p), cxp)
boehmes@40164
   784
    | (P.IffOeq, [(p, _)]) => (p, cxp)
boehmes@40164
   785
    | (P.NnfPos, _) => (nnf cx vars (map fst ps) ct, cxp)
boehmes@40164
   786
    | (P.NnfNeg, _) => (nnf cx vars (map fst ps) ct, cxp)
boehmes@36898
   787
boehmes@40164
   788
      (* equality rules *)
boehmes@40164
   789
    | (P.Reflexivity, _) => (refl ct, cxp)
boehmes@40164
   790
    | (P.Symmetry, [(p, _)]) => (symm p, cxp)
boehmes@40164
   791
    | (P.Transitivity, [(p, _), (q, _)]) => (trans p q, cxp)
boehmes@40164
   792
    | (P.Monotonicity, _) => (monotonicity (map fst ps) ct, cxp)
boehmes@40164
   793
    | (P.Commutativity, _) => (commutativity ct, cxp)
boehmes@40164
   794
boehmes@40164
   795
      (* quantifier rules *)
boehmes@40164
   796
    | (P.QuantIntro, [(p, _)]) => (quant_intro vars p ct, cxp)
boehmes@40164
   797
    | (P.PullQuant, _) => (pull_quant cx ct, cxp)
boehmes@40164
   798
    | (P.PushQuant, _) => (push_quant cx ct, cxp)
boehmes@40164
   799
    | (P.ElimUnusedVars, _) => (elim_unused_vars cx ct, cxp)
boehmes@40164
   800
    | (P.DestEqRes, _) => (dest_eq_res cx ct, cxp)
boehmes@40164
   801
    | (P.QuantInst, _) => (quant_inst ct, cxp)
boehmes@40164
   802
    | (P.Skolemize, _) => skolemize ct cx ||> rpair ptab
boehmes@40164
   803
boehmes@40164
   804
      (* theory rules *)
boehmes@40516
   805
    | (P.ThLemma _, _) =>  (* FIXME: use arguments *)
boehmes@40164
   806
        (th_lemma cx simpset (map (thm_of o fst) ps) ct, cxp)
boehmes@40662
   807
    | (P.Rewrite, _) => rewrite simpset [] ct cx ||> rpair ptab
boehmes@40662
   808
    | (P.RewriteStar, ps) => rewrite simpset (map fst ps) ct cx ||> rpair ptab
boehmes@36898
   809
boehmes@40164
   810
    | (P.NnfStar, _) => not_supported r
boehmes@40164
   811
    | (P.CnfStar, _) => not_supported r
boehmes@40164
   812
    | (P.TransitivityStar, _) => not_supported r
boehmes@40164
   813
    | (P.PullQuantStar, _) => not_supported r
boehmes@36898
   814
boehmes@40164
   815
    | _ => raise Fail ("Z3: proof rule " ^ quote (P.string_of_rule r) ^
boehmes@40164
   816
       " has an unexpected number of arguments."))
boehmes@36898
   817
boehmes@40164
   818
  fun prove ctxt assms vars =
boehmes@40164
   819
    let
boehmes@40164
   820
      val simpset = T.make_simpset ctxt (Z3_Simps.get ctxt)
boehmes@40164
   821
 
boehmes@40164
   822
      fun conclude idx rule prop (ps, cxp) =
boehmes@40164
   823
        trace_rule idx (step assms simpset vars) rule ps prop cxp
boehmes@40164
   824
        |-> (fn p => apsnd (Inttab.update (idx, Proved p)) #> pair p)
boehmes@40164
   825
 
boehmes@40164
   826
      fun lookup idx (cxp as (_, ptab)) =
boehmes@40164
   827
        (case Inttab.lookup ptab idx of
boehmes@40164
   828
          SOME (Unproved (P.Proof_Step {rule, prems, prop})) =>
boehmes@40164
   829
            fold_map lookup prems cxp
boehmes@40164
   830
            |>> map2 rpair prems
boehmes@40164
   831
            |> conclude idx rule prop
boehmes@40164
   832
        | SOME (Proved p) => (p, cxp)
boehmes@40164
   833
        | NONE => z3_exn ("unknown proof id: " ^ quote (string_of_int idx)))
boehmes@40164
   834
 
boehmes@40164
   835
      fun result (p, (cx, _)) = (thm_of p, cx)
boehmes@40164
   836
    in
boehmes@40164
   837
      (fn idx => result o lookup idx o pair ctxt o Inttab.map (K Unproved))
boehmes@40164
   838
    end
boehmes@36898
   839
boehmes@41127
   840
  val disch_rules = map (pair false)
boehmes@41127
   841
    [@{thm allI}, @{thm refl}, @{thm reflexive}]
boehmes@41127
   842
boehmes@41127
   843
  fun disch_assm thm =
boehmes@41127
   844
    if Thm.nprems_of thm = 0 then Drule.flexflex_unique thm
boehmes@41127
   845
    else
boehmes@41127
   846
      (case Seq.pull (Thm.biresolution false disch_rules 1 thm) of
boehmes@41127
   847
        SOME (thm', _) => disch_assm thm'
boehmes@41127
   848
      | NONE => raise THM ("failed to discharge premise", 1, [thm]))
boehmes@41127
   849
boehmes@41127
   850
  fun discharge outer_ctxt (thm, inner_ctxt) =
boehmes@41127
   851
    thm
boehmes@41127
   852
    |> singleton (ProofContext.export inner_ctxt outer_ctxt)
boehmes@41127
   853
    |> tap (tracing o prefix "final goal: " o PolyML.makestring)
boehmes@41127
   854
    |> disch_assm    
boehmes@41127
   855
boehmes@40164
   856
  fun filter_assms ctxt assms ptab =
boehmes@40164
   857
    let
boehmes@40164
   858
      fun step r ct =
boehmes@40164
   859
        (case r of
boehmes@40164
   860
          P.Asserted => insert (op =) (find_assm ctxt assms ct)
boehmes@40164
   861
        | P.Goal => insert (op =) (find_assm ctxt assms ct)
boehmes@40164
   862
        | _ => I)
boehmes@36898
   863
boehmes@40164
   864
      fun lookup idx =
boehmes@40164
   865
        (case Inttab.lookup ptab idx of
boehmes@40164
   866
          SOME (P.Proof_Step {rule, prems, prop}) =>
boehmes@40164
   867
            fold lookup prems #> step rule prop
boehmes@40164
   868
        | NONE => z3_exn ("unknown proof id: " ^ quote (string_of_int idx)))
boehmes@40164
   869
    in lookup end
boehmes@40164
   870
in
boehmes@40164
   871
boehmes@41127
   872
fun reconstruct outer_ctxt recon output =
boehmes@40164
   873
  let
boehmes@41127
   874
    val {context=ctxt, typs, terms, rewrite_rules, assms} = recon
boehmes@41127
   875
    val (idx, (ptab, vars, ctxt')) = P.parse ctxt typs terms output
boehmes@41127
   876
    val assms' = prepare_assms ctxt' rewrite_rules assms
boehmes@36898
   877
  in
boehmes@41127
   878
    if Config.get ctxt' SMT_Config.filter_only_facts then
boehmes@41127
   879
      (filter_assms ctxt' assms' ptab idx [], @{thm TrueI})
boehmes@41127
   880
    else
boehmes@41127
   881
      prove ctxt' assms' vars idx ptab
boehmes@41127
   882
      |> discharge outer_ctxt
boehmes@41127
   883
      |> pair []
boehmes@36898
   884
  end
boehmes@36898
   885
boehmes@40164
   886
end
boehmes@36898
   887
boehmes@40164
   888
val setup = z3_rules_setup #> Z3_Simps.setup
boehmes@36898
   889
boehmes@36898
   890
end