src/Provers/simplifier.ML
author wenzelm
Wed Jul 23 11:03:54 1997 +0200 (1997-07-23 ago)
changeset 3557 9546f8185c43
parent 3551 7c013a617813
child 3577 9715b6e3ec5f
permissions -rw-r--r--
added simplification meta rules;
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
nipkow@1
     5
Generic simplifier, suitable for most logics.
nipkow@1
     6
*)
clasohm@1260
     7
wenzelm@3551
     8
infix 4
wenzelm@3551
     9
  setsubgoaler setloop addloop setSSolver addSSolver setSolver
wenzelm@3551
    10
  addSolver setmksimps addsimps delsimps addeqcongs deleqcongs
wenzelm@3551
    11
  settermless addsimprocs delsimprocs;
oheimb@2567
    12
clasohm@0
    13
clasohm@0
    14
signature SIMPLIFIER =
clasohm@0
    15
sig
wenzelm@2509
    16
  type simproc
wenzelm@2509
    17
  val mk_simproc: string -> cterm list -> (Sign.sg -> term -> thm option) -> simproc
wenzelm@2509
    18
  val conv_prover: (term * term -> term) -> thm -> (thm -> thm)
wenzelm@3557
    19
    -> tactic -> (int -> tactic) -> Sign.sg -> term -> term -> thm
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
oheimb@2629
    29
  val setsubgoaler: simpset *  (simpset -> int -> tactic) -> simpset
oheimb@2629
    30
  val setloop:      simpset *             (int -> tactic) -> simpset
oheimb@2629
    31
  val addloop:      simpset *             (int -> tactic) -> simpset
oheimb@2629
    32
  val setSSolver:   simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    33
  val addSSolver:   simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    34
  val setSolver:    simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    35
  val addSolver:    simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    36
  val setmksimps:  simpset * (thm -> thm list) -> simpset
wenzelm@2509
    37
  val settermless: simpset * (term * term -> bool) -> simpset
oheimb@2629
    38
  val addsimps:    simpset * thm list -> simpset
oheimb@2629
    39
  val delsimps:    simpset * thm list -> simpset
oheimb@2629
    40
  val addeqcongs:  simpset * thm list -> simpset
oheimb@2629
    41
  val deleqcongs:  simpset * thm list -> simpset
wenzelm@2509
    42
  val addsimprocs: simpset * simproc list -> simpset
wenzelm@2509
    43
  val delsimprocs: simpset * simproc list -> simpset
oheimb@2629
    44
  val merge_ss:    simpset * simpset -> simpset
oheimb@2629
    45
  val prems_of_ss: simpset -> thm list
oheimb@2629
    46
  val simpset:     simpset ref
clasohm@1243
    47
  val Addsimps: thm list -> unit
clasohm@1243
    48
  val Delsimps: thm list -> unit
wenzelm@2509
    49
  val Addsimprocs: simproc list -> unit
wenzelm@2509
    50
  val Delsimprocs: simproc list -> unit
oheimb@2629
    51
  val               simp_tac: simpset -> int -> tactic
oheimb@2629
    52
  val           asm_simp_tac: simpset -> int -> tactic
oheimb@2629
    53
  val          full_simp_tac: simpset -> int -> tactic
oheimb@2629
    54
  val      asm_full_simp_tac: simpset -> int -> tactic
oheimb@2629
    55
  val safe_asm_full_simp_tac: simpset -> int -> tactic
oheimb@2629
    56
  val               Simp_tac:            int -> tactic
oheimb@2629
    57
  val           Asm_simp_tac:            int -> tactic
oheimb@2629
    58
  val          Full_simp_tac:            int -> tactic
oheimb@2629
    59
  val      Asm_full_simp_tac:            int -> tactic
wenzelm@3557
    60
  val          simplify: simpset -> thm -> thm
wenzelm@3557
    61
  val      asm_simplify: simpset -> thm -> thm
wenzelm@3557
    62
  val     full_simplify: simpset -> thm -> thm
wenzelm@3557
    63
  val asm_full_simplify: simpset -> thm -> thm
clasohm@0
    64
end;
clasohm@0
    65
wenzelm@2503
    66
wenzelm@2503
    67
structure Simplifier: SIMPLIFIER =
clasohm@0
    68
struct
clasohm@0
    69
wenzelm@2509
    70
wenzelm@2509
    71
(** simplification procedures **)
wenzelm@2509
    72
wenzelm@2509
    73
(* datatype simproc *)
wenzelm@2509
    74
wenzelm@2509
    75
datatype simproc =
wenzelm@3551
    76
  Simproc of string * cterm list * (Sign.sg -> term -> thm option) * stamp;
wenzelm@2509
    77
wenzelm@3557
    78
fun mk_simproc name lhss proc =
wenzelm@3557
    79
  Simproc (name, map (Thm.cterm_fun Logic.varify) lhss, proc, stamp ());
wenzelm@3557
    80
wenzelm@3551
    81
fun rep_simproc (Simproc args) = args;
wenzelm@2509
    82
wenzelm@2509
    83
wenzelm@2509
    84
(* generic conversion prover *)		(* FIXME move?, rename? *)
wenzelm@2509
    85
wenzelm@2509
    86
fun conv_prover mk_eqv eqv_refl mk_meta_eq expand_tac norm_tac sg t u =
wenzelm@2509
    87
  let
wenzelm@2509
    88
    val X = Free (gensym "X.", fastype_of t);
wenzelm@2509
    89
    val goal = Logic.mk_implies (mk_eqv (X, t), mk_eqv (X, u));
wenzelm@2509
    90
    val pre_result =
wenzelm@2509
    91
      prove_goalw_cterm [] (cterm_of sg goal)   (*goal: X=t ==> X=u*)
wenzelm@2509
    92
        (fn prems => [
wenzelm@2509
    93
          expand_tac,				(*expand u*)
wenzelm@2509
    94
          ALLGOALS (cut_facts_tac prems),
wenzelm@2509
    95
          ALLGOALS norm_tac]);			(*normalize both t and u*)
wenzelm@2509
    96
  in
wenzelm@2509
    97
    mk_meta_eq (eqv_refl RS pre_result)         (*final result: t==u*)
wenzelm@2509
    98
  end
wenzelm@2509
    99
  handle ERROR => error ("The error(s) above occurred while trying to prove " ^
wenzelm@2509
   100
    (string_of_cterm (cterm_of sg (mk_eqv (t, u)))));
wenzelm@2509
   101
wenzelm@2509
   102
wenzelm@2509
   103
wenzelm@2503
   104
(** simplification sets **)
wenzelm@2503
   105
wenzelm@2503
   106
(* type simpset *)
wenzelm@2503
   107
clasohm@0
   108
datatype simpset =
wenzelm@2503
   109
  Simpset of {
wenzelm@2503
   110
    mss: meta_simpset,
oheimb@2629
   111
    subgoal_tac:        simpset -> int -> tactic,
oheimb@2629
   112
    loop_tac:                      int -> tactic,
oheimb@2629
   113
           finish_tac: thm list -> int -> tactic,
oheimb@2629
   114
    unsafe_finish_tac: thm list -> int -> tactic};
wenzelm@2503
   115
wenzelm@3551
   116
fun make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac) =
wenzelm@3551
   117
  Simpset {mss = mss, subgoal_tac = subgoal_tac, loop_tac = loop_tac,
oheimb@2629
   118
    finish_tac = finish_tac, unsafe_finish_tac = unsafe_finish_tac};
clasohm@0
   119
clasohm@0
   120
val empty_ss =
wenzelm@3551
   121
  make_ss (Thm.empty_mss, K (K no_tac), K no_tac, K (K no_tac), K (K no_tac));
wenzelm@3551
   122
wenzelm@3551
   123
fun rep_ss (Simpset args) = args;
wenzelm@3551
   124
fun prems_of_ss (Simpset {mss, ...}) = Thm.prems_of_mss mss;
wenzelm@3551
   125
wenzelm@3551
   126
wenzelm@3551
   127
(* print simpsets *)
wenzelm@2503
   128
wenzelm@3551
   129
fun print_ss ss =
wenzelm@3551
   130
  let
wenzelm@3551
   131
    val Simpset {mss, ...} = ss;
wenzelm@3551
   132
    val {simps, procs, congs} = Thm.dest_mss mss;
wenzelm@2503
   133
wenzelm@3551
   134
    val pretty_thms = map Display.pretty_thm;
wenzelm@3551
   135
    fun pretty_proc (name, lhss) =
wenzelm@3551
   136
      Pretty.big_list (name ^ ":") (map Display.pretty_cterm lhss);
wenzelm@3551
   137
  in
wenzelm@3551
   138
    Pretty.writeln (Pretty.big_list "simplification rules:" (pretty_thms simps));
wenzelm@3551
   139
    Pretty.writeln (Pretty.big_list "simplification procedures:" (map pretty_proc procs));
wenzelm@3551
   140
    Pretty.writeln (Pretty.big_list "congruences:" (pretty_thms congs))
wenzelm@3551
   141
  end;
wenzelm@2503
   142
wenzelm@2503
   143
wenzelm@2503
   144
(* extend simpsets *)
wenzelm@2503
   145
wenzelm@3551
   146
fun (Simpset {mss, subgoal_tac = _, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   147
    setsubgoaler subgoal_tac =
wenzelm@3551
   148
  make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
oheimb@2629
   149
wenzelm@3551
   150
fun (Simpset {mss, subgoal_tac, loop_tac = _, finish_tac, unsafe_finish_tac})
wenzelm@3551
   151
    setloop loop_tac =
wenzelm@3551
   152
  make_ss (mss, subgoal_tac, DETERM o loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   153
wenzelm@3551
   154
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   155
    addloop tac =
wenzelm@3551
   156
  make_ss (mss, subgoal_tac, loop_tac ORELSE' (DETERM o tac), finish_tac, unsafe_finish_tac);
oheimb@2567
   157
wenzelm@3551
   158
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac = _, unsafe_finish_tac})
wenzelm@3551
   159
    setSSolver finish_tac =
wenzelm@3551
   160
  make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   161
wenzelm@3551
   162
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   163
    addSSolver tac =
wenzelm@3551
   164
  make_ss (mss, subgoal_tac, loop_tac, fn hyps => finish_tac hyps ORELSE' tac hyps,
wenzelm@3551
   165
    unsafe_finish_tac);
wenzelm@2503
   166
wenzelm@3551
   167
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac = _})
wenzelm@3551
   168
    setSolver unsafe_finish_tac =
wenzelm@3551
   169
  make_ss (mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   170
wenzelm@3551
   171
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   172
    addSolver tac =
wenzelm@3551
   173
  make_ss (mss, subgoal_tac, loop_tac, finish_tac,
wenzelm@3551
   174
    fn hyps => unsafe_finish_tac hyps ORELSE' tac hyps);
wenzelm@2503
   175
wenzelm@3551
   176
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   177
    setmksimps mk_simps =
wenzelm@2645
   178
  make_ss (Thm.set_mk_rews (mss, map (Thm.strip_shyps o Drule.zero_var_indexes) o mk_simps),
oheimb@2629
   179
    subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   180
wenzelm@3551
   181
fun (Simpset {mss, subgoal_tac, loop_tac,  finish_tac, unsafe_finish_tac})
wenzelm@3551
   182
    settermless termless =
wenzelm@3551
   183
  make_ss (Thm.set_termless (mss, termless), subgoal_tac, loop_tac,
wenzelm@3551
   184
    finish_tac, unsafe_finish_tac);
wenzelm@3551
   185
wenzelm@3551
   186
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   187
    addsimps rews =
wenzelm@2503
   188
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@3551
   189
    make_ss (Thm.add_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
    delsimps rews =
wenzelm@2503
   195
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@3551
   196
    make_ss (Thm.del_simps (mss, rews'), subgoal_tac, loop_tac,
wenzelm@3551
   197
      finish_tac, unsafe_finish_tac)
wenzelm@2503
   198
  end;
wenzelm@2503
   199
wenzelm@3551
   200
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   201
    addeqcongs newcongs =
wenzelm@3551
   202
  make_ss (Thm.add_congs (mss, newcongs), subgoal_tac, loop_tac,
wenzelm@3551
   203
    finish_tac, unsafe_finish_tac);
wenzelm@2509
   204
wenzelm@3551
   205
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   206
    deleqcongs oldcongs =
wenzelm@3551
   207
  make_ss (Thm.del_congs (mss, oldcongs), subgoal_tac, loop_tac,
wenzelm@3551
   208
    finish_tac, unsafe_finish_tac);
oheimb@2629
   209
wenzelm@3551
   210
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   211
    addsimprocs simprocs =
wenzelm@3551
   212
  make_ss
wenzelm@3551
   213
    (Thm.add_simprocs (mss, map rep_simproc simprocs),
wenzelm@3551
   214
      subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   215
wenzelm@3551
   216
fun (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac})
wenzelm@3551
   217
    delsimprocs simprocs =
wenzelm@3551
   218
  make_ss
wenzelm@3551
   219
    (Thm.del_simprocs (mss, map rep_simproc simprocs),
wenzelm@3551
   220
      subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   221
wenzelm@2503
   222
wenzelm@3551
   223
(* merge simpsets *)	(*NOTE: ignores tactics of 2nd simpset*)
wenzelm@2503
   224
wenzelm@3551
   225
fun merge_ss
wenzelm@3551
   226
   (Simpset {mss = mss1, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac},
wenzelm@3551
   227
    Simpset {mss = mss2, ...}) =
wenzelm@3551
   228
  make_ss (Thm.merge_mss (mss1, mss2),
wenzelm@3551
   229
    subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2503
   230
wenzelm@2503
   231
wenzelm@3557
   232
wenzelm@3557
   233
(** the current simpset **)
clasohm@0
   234
clasohm@1243
   235
val simpset = ref empty_ss;
clasohm@0
   236
wenzelm@2503
   237
fun Addsimps rews = (simpset := ! simpset addsimps rews);
wenzelm@2503
   238
fun Delsimps rews = (simpset := ! simpset delsimps rews);
clasohm@0
   239
wenzelm@2509
   240
fun Addsimprocs procs = (simpset := ! simpset addsimprocs procs);
wenzelm@2509
   241
fun Delsimprocs procs = (simpset := ! simpset delsimprocs procs);
wenzelm@2509
   242
clasohm@0
   243
wenzelm@3557
   244
wenzelm@2503
   245
(** simplification tactics **)
clasohm@0
   246
wenzelm@3551
   247
fun NEWSUBGOALS tac tacf st0 =
wenzelm@3551
   248
  st0 |> (tac THEN (fn st1 => tacf (nprems_of st1 - nprems_of st0) st1));
nipkow@1
   249
wenzelm@3557
   250
fun solve_all_tac (subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac) mss =
wenzelm@3557
   251
  let
wenzelm@3557
   252
    val ss =
wenzelm@3557
   253
      make_ss (mss, subgoal_tac, loop_tac, unsafe_finish_tac, unsafe_finish_tac);
wenzelm@3557
   254
    val solve1_tac =
wenzelm@3557
   255
      NEWSUBGOALS (subgoal_tac ss 1) (fn n => if n < 0 then all_tac else no_tac);
wenzelm@3557
   256
  in DEPTH_SOLVE solve1_tac end;
wenzelm@3557
   257
wenzelm@3557
   258
oheimb@2629
   259
(*not totally safe: may instantiate unknowns that appear also in other subgoals*)
oheimb@2629
   260
fun basic_gen_simp_tac mode =
wenzelm@3551
   261
  fn (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac}) =>
wenzelm@3551
   262
    let
paulson@1512
   263
      fun simp_loop_tac i thm =
wenzelm@3557
   264
        (asm_rewrite_goal_tac mode
wenzelm@3557
   265
          (solve_all_tac (subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac)) mss i
wenzelm@3557
   266
        THEN (finish_tac (prems_of_mss mss) i ORELSE looper i)) thm
wenzelm@3551
   267
      and allsimp i n = EVERY (map (fn j => simp_loop_tac (i + j)) (n downto 0))
wenzelm@3551
   268
      and looper i = TRY (NEWSUBGOALS (loop_tac i) (allsimp i));
nipkow@217
   269
  in simp_loop_tac end;
clasohm@0
   270
wenzelm@3551
   271
fun gen_simp_tac mode (ss as Simpset {unsafe_finish_tac, ...}) =
wenzelm@3551
   272
  basic_gen_simp_tac mode (ss setSSolver unsafe_finish_tac);
wenzelm@3551
   273
oheimb@2629
   274
wenzelm@2503
   275
val          simp_tac = gen_simp_tac (false, false);
wenzelm@2503
   276
val      asm_simp_tac = gen_simp_tac (false, true);
wenzelm@2503
   277
val     full_simp_tac = gen_simp_tac (true,  false);
wenzelm@2503
   278
val asm_full_simp_tac = gen_simp_tac (true,  true);
clasohm@0
   279
oheimb@2629
   280
(*not totally safe: may instantiate unknowns that appear also in other subgoals*)
oheimb@2629
   281
val safe_asm_full_simp_tac = basic_gen_simp_tac (true, true);
oheimb@2629
   282
wenzelm@2503
   283
fun          Simp_tac i =          simp_tac (! simpset) i;
wenzelm@2503
   284
fun      Asm_simp_tac i =      asm_simp_tac (! simpset) i;
wenzelm@2503
   285
fun     Full_simp_tac i =     full_simp_tac (! simpset) i;
wenzelm@2503
   286
fun Asm_full_simp_tac i = asm_full_simp_tac (! simpset) i;
nipkow@406
   287
wenzelm@3557
   288
wenzelm@3557
   289
wenzelm@3557
   290
(** simplification meta rules **)
wenzelm@3557
   291
wenzelm@3557
   292
fun simp mode (Simpset {mss, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac}) thm =
wenzelm@3557
   293
  let
wenzelm@3557
   294
    val tacf = solve_all_tac (subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@3557
   295
    fun prover m th = apsome fst (Sequence.pull (tacf m th));
wenzelm@3557
   296
  in
wenzelm@3557
   297
    Drule.rewrite_thm mode prover mss thm
wenzelm@3557
   298
  end;
wenzelm@3557
   299
wenzelm@3557
   300
val          simplify = simp (false, false);
wenzelm@3557
   301
val      asm_simplify = simp (false, true);
wenzelm@3557
   302
val     full_simplify = simp (true, false);
wenzelm@3557
   303
val asm_full_simplify = simp (true, true);
wenzelm@3557
   304
wenzelm@3557
   305
clasohm@1243
   306
end;