src/Provers/simplifier.ML
author wenzelm
Thu Dec 04 14:11:37 1997 +0100 (1997-12-04 ago)
changeset 4366 4d84cdb0df42
parent 4290 902ee0883861
child 4612 26764de50c74
permissions -rw-r--r--
added print_simpset;
clasohm@1243
     1
(*  Title:      Provers/simplifier.ML
nipkow@1
     2
    ID:         $Id$
wenzelm@3557
     3
    Author:     Tobias Nipkow and Markus Wenzel, TU Muenchen
nipkow@1
     4
wenzelm@3577
     5
Generic simplifier, suitable for most logics.  See also Pure/thm.ML
wenzelm@3577
     6
for the actual meta level rewriting engine.
nipkow@1
     7
*)
clasohm@1260
     8
wenzelm@3551
     9
infix 4
wenzelm@3551
    10
  setsubgoaler setloop addloop setSSolver addSSolver setSolver
wenzelm@3551
    11
  addSolver setmksimps addsimps delsimps addeqcongs deleqcongs
wenzelm@3551
    12
  settermless addsimprocs delsimprocs;
oheimb@2567
    13
clasohm@0
    14
clasohm@0
    15
signature SIMPLIFIER =
clasohm@0
    16
sig
wenzelm@2509
    17
  type simproc
wenzelm@3577
    18
  val mk_simproc: string -> cterm list
wenzelm@3577
    19
    -> (Sign.sg -> thm list -> term -> thm option) -> simproc
clasohm@0
    20
  type simpset
wenzelm@2503
    21
  val empty_ss: simpset
wenzelm@3551
    22
  val rep_ss: simpset ->
wenzelm@3551
    23
   {mss: meta_simpset,
wenzelm@3551
    24
    subgoal_tac:        simpset -> int -> tactic,
wenzelm@3551
    25
    loop_tac:                      int -> tactic,
wenzelm@3551
    26
           finish_tac: thm list -> int -> tactic,
wenzelm@3551
    27
    unsafe_finish_tac: thm list -> int -> tactic};
wenzelm@3551
    28
  val print_ss: simpset -> unit
wenzelm@4366
    29
  val print_simpset: theory -> unit
oheimb@2629
    30
  val setsubgoaler: simpset *  (simpset -> int -> tactic) -> simpset
oheimb@2629
    31
  val setloop:      simpset *             (int -> tactic) -> simpset
oheimb@2629
    32
  val addloop:      simpset *             (int -> tactic) -> simpset
oheimb@2629
    33
  val setSSolver:   simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    34
  val addSSolver:   simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    35
  val setSolver:    simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    36
  val addSolver:    simpset * (thm list -> int -> tactic) -> simpset
wenzelm@3577
    37
  val setmksimps:   simpset * (thm -> thm list) -> simpset
wenzelm@3577
    38
  val settermless:  simpset * (term * term -> bool) -> simpset
wenzelm@3577
    39
  val addsimps:     simpset * thm list -> simpset
wenzelm@3577
    40
  val delsimps:     simpset * thm list -> simpset
wenzelm@3577
    41
  val addeqcongs:   simpset * thm list -> simpset
wenzelm@3577
    42
  val deleqcongs:   simpset * thm list -> simpset
wenzelm@3577
    43
  val addsimprocs:  simpset * simproc list -> simpset
wenzelm@3577
    44
  val delsimprocs:  simpset * simproc list -> simpset
wenzelm@3577
    45
  val merge_ss:     simpset * simpset -> simpset
wenzelm@3577
    46
  val prems_of_ss:  simpset -> thm list
wenzelm@4080
    47
wenzelm@4124
    48
  val simpset_thy_data: string * (object * (object -> object) *
wenzelm@4259
    49
    (object * object -> object) * (Sign.sg -> object -> unit))
wenzelm@4080
    50
  val simpset_ref_of_sg: Sign.sg -> simpset ref
wenzelm@4080
    51
  val simpset_ref_of: theory -> simpset ref
wenzelm@4080
    52
  val simpset_of_sg: Sign.sg -> simpset
wenzelm@4080
    53
  val simpset_of: theory -> simpset
wenzelm@4080
    54
  val SIMPSET: (simpset -> tactic) -> tactic
wenzelm@4080
    55
  val SIMPSET': (simpset -> 'a -> tactic) -> 'a -> tactic
wenzelm@4080
    56
  val simpset: unit -> simpset
wenzelm@4080
    57
  val simpset_ref: unit -> simpset ref
clasohm@1243
    58
  val Addsimps: thm list -> unit
clasohm@1243
    59
  val Delsimps: thm list -> unit
wenzelm@2509
    60
  val Addsimprocs: simproc list -> unit
wenzelm@2509
    61
  val Delsimprocs: simproc list -> unit
wenzelm@4080
    62
oheimb@2629
    63
  val               simp_tac: simpset -> int -> tactic
oheimb@2629
    64
  val           asm_simp_tac: simpset -> int -> tactic
oheimb@2629
    65
  val          full_simp_tac: simpset -> int -> tactic
oheimb@2629
    66
  val      asm_full_simp_tac: simpset -> int -> tactic
oheimb@2629
    67
  val safe_asm_full_simp_tac: simpset -> int -> tactic
oheimb@2629
    68
  val               Simp_tac:            int -> tactic
oheimb@2629
    69
  val           Asm_simp_tac:            int -> tactic
oheimb@2629
    70
  val          Full_simp_tac:            int -> tactic
oheimb@2629
    71
  val      Asm_full_simp_tac:            int -> tactic
wenzelm@3557
    72
  val          simplify: simpset -> thm -> thm
wenzelm@3557
    73
  val      asm_simplify: simpset -> thm -> thm
wenzelm@3557
    74
  val     full_simplify: simpset -> thm -> thm
wenzelm@3557
    75
  val asm_full_simplify: simpset -> thm -> thm
clasohm@0
    76
end;
clasohm@0
    77
wenzelm@2503
    78
wenzelm@2503
    79
structure Simplifier: SIMPLIFIER =
clasohm@0
    80
struct
clasohm@0
    81
wenzelm@2509
    82
wenzelm@2509
    83
(** simplification procedures **)
wenzelm@2509
    84
wenzelm@2509
    85
(* datatype simproc *)
wenzelm@2509
    86
wenzelm@2509
    87
datatype simproc =
wenzelm@3577
    88
  Simproc of string * cterm list * (Sign.sg -> thm list -> term -> thm option) * stamp;
wenzelm@2509
    89
wenzelm@3557
    90
fun mk_simproc name lhss proc =
wenzelm@3557
    91
  Simproc (name, map (Thm.cterm_fun Logic.varify) lhss, proc, stamp ());
wenzelm@3557
    92
wenzelm@3551
    93
fun rep_simproc (Simproc args) = args;
wenzelm@2509
    94
wenzelm@2509
    95
wenzelm@2509
    96
wenzelm@2503
    97
(** simplification sets **)
wenzelm@2503
    98
wenzelm@2503
    99
(* type simpset *)
wenzelm@2503
   100
clasohm@0
   101
datatype simpset =
wenzelm@2503
   102
  Simpset of {
wenzelm@2503
   103
    mss: meta_simpset,
oheimb@2629
   104
    subgoal_tac:        simpset -> int -> tactic,
oheimb@2629
   105
    loop_tac:                      int -> tactic,
oheimb@2629
   106
           finish_tac: thm list -> int -> tactic,
oheimb@2629
   107
    unsafe_finish_tac: thm list -> int -> tactic};
wenzelm@2503
   108
wenzelm@3551
   109
fun make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac) =
wenzelm@3551
   110
  Simpset {mss = mss, subgoal_tac = subgoal_tac, loop_tac = loop_tac,
oheimb@2629
   111
    finish_tac = finish_tac, unsafe_finish_tac = unsafe_finish_tac};
clasohm@0
   112
clasohm@0
   113
val empty_ss =
wenzelm@3551
   114
  make_ss (Thm.empty_mss, K (K no_tac), K no_tac, K (K no_tac), K (K no_tac));
wenzelm@3551
   115
wenzelm@3551
   116
fun rep_ss (Simpset args) = args;
wenzelm@3551
   117
fun prems_of_ss (Simpset {mss, ...}) = Thm.prems_of_mss mss;
wenzelm@3551
   118
wenzelm@3551
   119
wenzelm@3551
   120
(* print simpsets *)
wenzelm@2503
   121
wenzelm@3551
   122
fun print_ss ss =
wenzelm@3551
   123
  let
wenzelm@3551
   124
    val Simpset {mss, ...} = ss;
wenzelm@3551
   125
    val {simps, procs, congs} = Thm.dest_mss mss;
wenzelm@2503
   126
wenzelm@3551
   127
    val pretty_thms = map Display.pretty_thm;
wenzelm@3551
   128
    fun pretty_proc (name, lhss) =
wenzelm@3551
   129
      Pretty.big_list (name ^ ":") (map Display.pretty_cterm lhss);
wenzelm@3551
   130
  in
wenzelm@3551
   131
    Pretty.writeln (Pretty.big_list "simplification rules:" (pretty_thms simps));
wenzelm@3551
   132
    Pretty.writeln (Pretty.big_list "simplification procedures:" (map pretty_proc procs));
wenzelm@3551
   133
    Pretty.writeln (Pretty.big_list "congruences:" (pretty_thms congs))
wenzelm@3551
   134
  end;
wenzelm@2503
   135
wenzelm@2503
   136
wenzelm@2503
   137
(* extend simpsets *)
wenzelm@2503
   138
wenzelm@3551
   139
fun (Simpset {mss, subgoal_tac = _, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   140
    setsubgoaler subgoal_tac =
wenzelm@3551
   141
  make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
oheimb@2629
   142
wenzelm@3551
   143
fun (Simpset {mss, subgoal_tac, loop_tac = _, finish_tac, unsafe_finish_tac})
wenzelm@3551
   144
    setloop loop_tac =
wenzelm@3551
   145
  make_ss (mss, subgoal_tac, DETERM o loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   146
wenzelm@3551
   147
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   148
    addloop tac =
wenzelm@3551
   149
  make_ss (mss, subgoal_tac, loop_tac ORELSE' (DETERM o tac), finish_tac, unsafe_finish_tac);
oheimb@2567
   150
wenzelm@3551
   151
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac = _, unsafe_finish_tac})
wenzelm@3551
   152
    setSSolver finish_tac =
wenzelm@3551
   153
  make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   154
wenzelm@3551
   155
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   156
    addSSolver tac =
wenzelm@3551
   157
  make_ss (mss, subgoal_tac, loop_tac, fn hyps => finish_tac hyps ORELSE' tac hyps,
wenzelm@3551
   158
    unsafe_finish_tac);
wenzelm@2503
   159
wenzelm@3551
   160
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac = _})
wenzelm@3551
   161
    setSolver unsafe_finish_tac =
wenzelm@3551
   162
  make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   163
wenzelm@3551
   164
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   165
    addSolver tac =
wenzelm@3551
   166
  make_ss (mss, subgoal_tac, loop_tac, finish_tac,
wenzelm@3551
   167
    fn hyps => unsafe_finish_tac hyps ORELSE' tac hyps);
wenzelm@2503
   168
wenzelm@3551
   169
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   170
    setmksimps mk_simps =
wenzelm@2645
   171
  make_ss (Thm.set_mk_rews (mss, map (Thm.strip_shyps o Drule.zero_var_indexes) o mk_simps),
oheimb@2629
   172
    subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   173
wenzelm@3551
   174
fun (Simpset {mss, subgoal_tac, loop_tac,  finish_tac, unsafe_finish_tac})
wenzelm@3551
   175
    settermless termless =
wenzelm@3551
   176
  make_ss (Thm.set_termless (mss, termless), subgoal_tac, loop_tac,
wenzelm@3551
   177
    finish_tac, unsafe_finish_tac);
wenzelm@3551
   178
wenzelm@3551
   179
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   180
    addsimps rews =
wenzelm@2503
   181
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@3551
   182
    make_ss (Thm.add_simps (mss, rews'), subgoal_tac, loop_tac,
wenzelm@3551
   183
      finish_tac, unsafe_finish_tac)
wenzelm@2503
   184
  end;
wenzelm@2503
   185
wenzelm@3551
   186
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   187
    delsimps rews =
wenzelm@2503
   188
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@3551
   189
    make_ss (Thm.del_simps (mss, rews'), subgoal_tac, loop_tac,
wenzelm@3551
   190
      finish_tac, unsafe_finish_tac)
wenzelm@2503
   191
  end;
wenzelm@2503
   192
wenzelm@3551
   193
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   194
    addeqcongs newcongs =
wenzelm@3551
   195
  make_ss (Thm.add_congs (mss, newcongs), subgoal_tac, loop_tac,
wenzelm@3551
   196
    finish_tac, unsafe_finish_tac);
wenzelm@2509
   197
wenzelm@3551
   198
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   199
    deleqcongs oldcongs =
wenzelm@3551
   200
  make_ss (Thm.del_congs (mss, oldcongs), subgoal_tac, loop_tac,
wenzelm@3551
   201
    finish_tac, unsafe_finish_tac);
oheimb@2629
   202
wenzelm@3551
   203
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   204
    addsimprocs simprocs =
wenzelm@3551
   205
  make_ss
wenzelm@3551
   206
    (Thm.add_simprocs (mss, map rep_simproc simprocs),
wenzelm@3551
   207
      subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   208
wenzelm@3551
   209
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   210
    delsimprocs simprocs =
wenzelm@3551
   211
  make_ss
wenzelm@3551
   212
    (Thm.del_simprocs (mss, map rep_simproc simprocs),
wenzelm@3551
   213
      subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   214
wenzelm@2503
   215
wenzelm@3551
   216
(* merge simpsets *)	(*NOTE: ignores tactics of 2nd simpset*)
wenzelm@2503
   217
wenzelm@3551
   218
fun merge_ss
wenzelm@3551
   219
   (Simpset {mss = mss1, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac},
wenzelm@3551
   220
    Simpset {mss = mss2, ...}) =
wenzelm@3551
   221
  make_ss (Thm.merge_mss (mss1, mss2),
wenzelm@3551
   222
    subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   223
wenzelm@2503
   224
wenzelm@3557
   225
wenzelm@4080
   226
(** simpset theory data **)
wenzelm@4080
   227
wenzelm@4080
   228
(* data kind simpset *)
wenzelm@4080
   229
wenzelm@4080
   230
val simpsetK = "simpset";
wenzelm@4080
   231
exception SimpsetData of simpset ref;
wenzelm@4080
   232
wenzelm@4080
   233
local
wenzelm@4080
   234
  val empty = SimpsetData (ref empty_ss);
clasohm@0
   235
wenzelm@4080
   236
  (*create new reference*)
wenzelm@4080
   237
  fun prep_ext (SimpsetData (ref ss)) = SimpsetData (ref ss);
wenzelm@4080
   238
wenzelm@4080
   239
  fun merge (SimpsetData (ref ss1), SimpsetData (ref ss2)) =
wenzelm@4080
   240
    SimpsetData (ref (merge_ss (ss1, ss2)));
wenzelm@4080
   241
wenzelm@4259
   242
  fun print (_: Sign.sg) (SimpsetData (ref ss)) = print_ss ss;
wenzelm@4080
   243
in
wenzelm@4080
   244
  val simpset_thy_data = (simpsetK, (empty, prep_ext, merge, print));
wenzelm@4080
   245
end;
wenzelm@4080
   246
wenzelm@4080
   247
wenzelm@4080
   248
(* access simpset *)
clasohm@0
   249
wenzelm@4366
   250
fun print_simpset thy = Display.print_data thy simpsetK;
wenzelm@4366
   251
wenzelm@4080
   252
fun simpset_ref_of_sg sg =
wenzelm@4080
   253
  (case Sign.get_data sg simpsetK of
wenzelm@4080
   254
    SimpsetData r => r
wenzelm@4080
   255
  | _ => sys_error "simpset_ref_of_sg")
wenzelm@4080
   256
wenzelm@4080
   257
val simpset_ref_of = simpset_ref_of_sg o sign_of;
wenzelm@4080
   258
val simpset_of_sg = ! o simpset_ref_of_sg;
wenzelm@4080
   259
val simpset_of = simpset_of_sg o sign_of;
wenzelm@4080
   260
wenzelm@4080
   261
fun SIMPSET tacf state = tacf (simpset_of_sg (sign_of_thm state)) state;
wenzelm@4080
   262
fun SIMPSET' tacf i state = tacf (simpset_of_sg (sign_of_thm state)) i state;
clasohm@0
   263
wenzelm@4080
   264
val simpset = simpset_of o Context.get_context;
wenzelm@4080
   265
val simpset_ref = simpset_ref_of_sg o sign_of o Context.get_context;
wenzelm@4080
   266
wenzelm@4080
   267
wenzelm@4080
   268
(* change simpset *)
wenzelm@4080
   269
wenzelm@4080
   270
fun change_simpset f x = simpset_ref () := (f (simpset (), x));
wenzelm@4080
   271
wenzelm@4080
   272
val Addsimps = change_simpset (op addsimps);
wenzelm@4080
   273
val Delsimps = change_simpset (op delsimps);
wenzelm@4080
   274
val Addsimprocs = change_simpset (op addsimprocs);
wenzelm@4080
   275
val Delsimprocs = change_simpset (op delsimprocs);
wenzelm@2509
   276
clasohm@0
   277
wenzelm@3557
   278
wenzelm@2503
   279
(** simplification tactics **)
clasohm@0
   280
wenzelm@3551
   281
fun NEWSUBGOALS tac tacf st0 =
wenzelm@3551
   282
  st0 |> (tac THEN (fn st1 => tacf (nprems_of st1 - nprems_of st0) st1));
nipkow@1
   283
wenzelm@3557
   284
fun solve_all_tac (subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac) mss =
wenzelm@3557
   285
  let
wenzelm@3557
   286
    val ss =
wenzelm@3557
   287
      make_ss (mss, subgoal_tac, loop_tac, unsafe_finish_tac, unsafe_finish_tac);
wenzelm@3557
   288
    val solve1_tac =
wenzelm@3557
   289
      NEWSUBGOALS (subgoal_tac ss 1) (fn n => if n < 0 then all_tac else no_tac);
wenzelm@3557
   290
  in DEPTH_SOLVE solve1_tac end;
wenzelm@3557
   291
wenzelm@3557
   292
oheimb@2629
   293
(*not totally safe: may instantiate unknowns that appear also in other subgoals*)
oheimb@2629
   294
fun basic_gen_simp_tac mode =
wenzelm@3551
   295
  fn (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac}) =>
wenzelm@3551
   296
    let
paulson@1512
   297
      fun simp_loop_tac i thm =
wenzelm@3557
   298
        (asm_rewrite_goal_tac mode
wenzelm@3557
   299
          (solve_all_tac (subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac)) mss i
wenzelm@3557
   300
        THEN (finish_tac (prems_of_mss mss) i ORELSE looper i)) thm
wenzelm@3551
   301
      and allsimp i n = EVERY (map (fn j => simp_loop_tac (i + j)) (n downto 0))
wenzelm@3551
   302
      and looper i = TRY (NEWSUBGOALS (loop_tac i) (allsimp i));
nipkow@217
   303
  in simp_loop_tac end;
clasohm@0
   304
wenzelm@3551
   305
fun gen_simp_tac mode (ss as Simpset {unsafe_finish_tac, ...}) =
wenzelm@3551
   306
  basic_gen_simp_tac mode (ss setSSolver unsafe_finish_tac);
wenzelm@3551
   307
oheimb@2629
   308
wenzelm@2503
   309
val          simp_tac = gen_simp_tac (false, false);
wenzelm@2503
   310
val      asm_simp_tac = gen_simp_tac (false, true);
wenzelm@2503
   311
val     full_simp_tac = gen_simp_tac (true,  false);
wenzelm@2503
   312
val asm_full_simp_tac = gen_simp_tac (true,  true);
clasohm@0
   313
oheimb@2629
   314
(*not totally safe: may instantiate unknowns that appear also in other subgoals*)
oheimb@2629
   315
val safe_asm_full_simp_tac = basic_gen_simp_tac (true, true);
oheimb@2629
   316
paulson@3728
   317
(** The abstraction over the proof state delays the dereferencing **)
paulson@3728
   318
wenzelm@4080
   319
fun          Simp_tac i st =          simp_tac (simpset ()) i st;
wenzelm@4080
   320
fun      Asm_simp_tac i st =      asm_simp_tac (simpset ()) i st;
wenzelm@4080
   321
fun     Full_simp_tac i st =     full_simp_tac (simpset ()) i st;
wenzelm@4080
   322
fun Asm_full_simp_tac i st = asm_full_simp_tac (simpset ()) i st;
nipkow@406
   323
wenzelm@3557
   324
wenzelm@3557
   325
wenzelm@3557
   326
(** simplification meta rules **)
wenzelm@3557
   327
wenzelm@3557
   328
fun simp mode (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac}) thm =
wenzelm@3557
   329
  let
wenzelm@3557
   330
    val tacf = solve_all_tac (subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@4271
   331
    fun prover m th = apsome fst (Seq.pull (tacf m th));
wenzelm@3557
   332
  in
wenzelm@3557
   333
    Drule.rewrite_thm mode prover mss thm
wenzelm@3557
   334
  end;
wenzelm@3557
   335
wenzelm@3557
   336
val          simplify = simp (false, false);
wenzelm@3557
   337
val      asm_simplify = simp (false, true);
wenzelm@3557
   338
val     full_simplify = simp (true, false);
wenzelm@3557
   339
val asm_full_simplify = simp (true, true);
wenzelm@3557
   340
wenzelm@3557
   341
clasohm@1243
   342
end;