src/Provers/simplifier.ML
author oheimb
Sat Feb 15 16:14:35 1997 +0100 (1997-02-15 ago)
changeset 2629 b442786d4469
parent 2567 7a28e02e10b7
child 2645 9d3a3e62bf34
permissions -rw-r--r--
added deleqcongs, richer rep_ss
split solver in safe and unsafe parts (finish_tac, unsafe_finish_tac)
added safe_asm_full_simp_tac, setSSolver, addSSolver
renamed setsolver to setSolver, addsolver to addSolver
clasohm@1243
     1
(*  Title:      Provers/simplifier.ML
nipkow@1
     2
    ID:         $Id$
nipkow@1
     3
    Author:     Tobias Nipkow
nipkow@1
     4
    Copyright   1993  TU Munich
nipkow@1
     5
nipkow@1
     6
Generic simplifier, suitable for most logics.
wenzelm@2503
     7
wenzelm@2503
     8
TODO:
wenzelm@2503
     9
  - stamps to identify funs / tacs
wenzelm@2503
    10
  - merge: fail if incompatible funs
wenzelm@2509
    11
  - improve merge
nipkow@1
    12
*)
clasohm@1260
    13
oheimb@2629
    14
infix 4 setsubgoaler setloop addloop setSSolver addSSolver setSolver addSolver 
oheimb@2629
    15
        setmksimps addsimps delsimps addeqcongs deleqcongs
oheimb@2567
    16
	settermless addsimprocs delsimprocs;
oheimb@2567
    17
clasohm@0
    18
clasohm@0
    19
signature SIMPLIFIER =
clasohm@0
    20
sig
wenzelm@2509
    21
  type simproc
wenzelm@2509
    22
  val mk_simproc: string -> cterm list -> (Sign.sg -> term -> thm option) -> simproc
wenzelm@2509
    23
  val name_of_simproc: simproc -> string
wenzelm@2509
    24
  val conv_prover: (term * term -> term) -> thm -> (thm -> thm)
wenzelm@2509
    25
    -> tactic -> (int -> tactic) -> Sign.sg -> term -> term -> thm	(* FIXME move?, rename? *)
clasohm@0
    26
  type simpset
wenzelm@2503
    27
  val empty_ss: simpset
oheimb@2629
    28
  val rep_ss: simpset -> {simps: thm list, procs: string list, congs: thm list,
oheimb@2629
    29
			  subgoal_tac:        simpset -> int -> tactic,
oheimb@2629
    30
			  loop_tac:                      int -> tactic,
oheimb@2629
    31
			         finish_tac: thm list -> int -> tactic,
oheimb@2629
    32
			  unsafe_finish_tac: thm list -> int -> tactic}
oheimb@2629
    33
  val setsubgoaler: simpset *  (simpset -> int -> tactic) -> simpset
oheimb@2629
    34
  val setloop:      simpset *             (int -> tactic) -> simpset
oheimb@2629
    35
  val addloop:      simpset *             (int -> tactic) -> simpset
oheimb@2629
    36
  val setSSolver:   simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    37
  val addSSolver:   simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    38
  val setSolver:    simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    39
  val addSolver:    simpset * (thm list -> int -> tactic) -> simpset
oheimb@2629
    40
  val setmksimps:  simpset * (thm -> thm list) -> simpset
wenzelm@2509
    41
  val settermless: simpset * (term * term -> bool) -> simpset
oheimb@2629
    42
  val addsimps:    simpset * thm list -> simpset
oheimb@2629
    43
  val delsimps:    simpset * thm list -> simpset
oheimb@2629
    44
  val addeqcongs:  simpset * thm list -> simpset
oheimb@2629
    45
  val deleqcongs:  simpset * thm list -> simpset
wenzelm@2509
    46
  val addsimprocs: simpset * simproc list -> simpset
wenzelm@2509
    47
  val delsimprocs: simpset * simproc list -> simpset
oheimb@2629
    48
  val merge_ss:    simpset * simpset -> simpset
oheimb@2629
    49
  val prems_of_ss: simpset -> thm list
oheimb@2629
    50
  val simpset:     simpset ref
clasohm@1243
    51
  val Addsimps: thm list -> unit
clasohm@1243
    52
  val Delsimps: thm list -> unit
wenzelm@2509
    53
  val Addsimprocs: simproc list -> unit
wenzelm@2509
    54
  val Delsimprocs: simproc list -> unit
oheimb@2629
    55
  val               simp_tac: simpset -> int -> tactic
oheimb@2629
    56
  val           asm_simp_tac: simpset -> int -> tactic
oheimb@2629
    57
  val          full_simp_tac: simpset -> int -> tactic
oheimb@2629
    58
  val      asm_full_simp_tac: simpset -> int -> tactic
oheimb@2629
    59
  val safe_asm_full_simp_tac: simpset -> int -> tactic
oheimb@2629
    60
  val               Simp_tac:            int -> tactic
oheimb@2629
    61
  val           Asm_simp_tac:            int -> tactic
oheimb@2629
    62
  val          Full_simp_tac:            int -> tactic
oheimb@2629
    63
  val      Asm_full_simp_tac:            int -> tactic
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@2509
    76
  Simproc of {
wenzelm@2509
    77
    name: string,
wenzelm@2509
    78
    procs: (Sign.sg * term * (Sign.sg -> term -> thm option) * stamp) list}
wenzelm@2509
    79
wenzelm@2509
    80
(* FIXME stamps!? *)
wenzelm@2509
    81
fun eq_simproc (Simproc {name = name1, ...}, Simproc {name = name2, ...}) =
wenzelm@2509
    82
  (name1 = name2);
wenzelm@2509
    83
wenzelm@2509
    84
fun mk_simproc name lhss proc =
wenzelm@2509
    85
  let
wenzelm@2509
    86
    fun mk_proc lhs =
wenzelm@2509
    87
      (#sign (Thm.rep_cterm lhs), Logic.varify (term_of lhs), proc, stamp ());
wenzelm@2509
    88
  in
wenzelm@2509
    89
    Simproc {name = name, procs = map mk_proc lhss}
wenzelm@2509
    90
  end;
wenzelm@2509
    91
wenzelm@2509
    92
fun name_of_simproc (Simproc {name, ...}) = name;
wenzelm@2509
    93
wenzelm@2509
    94
wenzelm@2509
    95
(* generic conversion prover *)		(* FIXME move?, rename? *)
wenzelm@2509
    96
wenzelm@2509
    97
fun conv_prover mk_eqv eqv_refl mk_meta_eq expand_tac norm_tac sg t u =
wenzelm@2509
    98
  let
wenzelm@2509
    99
    val X = Free (gensym "X.", fastype_of t);
wenzelm@2509
   100
    val goal = Logic.mk_implies (mk_eqv (X, t), mk_eqv (X, u));
wenzelm@2509
   101
    val pre_result =
wenzelm@2509
   102
      prove_goalw_cterm [] (cterm_of sg goal)   (*goal: X=t ==> X=u*)
wenzelm@2509
   103
        (fn prems => [
wenzelm@2509
   104
          expand_tac,				(*expand u*)
wenzelm@2509
   105
          ALLGOALS (cut_facts_tac prems),
wenzelm@2509
   106
          ALLGOALS norm_tac]);			(*normalize both t and u*)
wenzelm@2509
   107
  in
wenzelm@2509
   108
    mk_meta_eq (eqv_refl RS pre_result)         (*final result: t==u*)
wenzelm@2509
   109
  end
wenzelm@2509
   110
  handle ERROR => error ("The error(s) above occurred while trying to prove " ^
wenzelm@2509
   111
    (string_of_cterm (cterm_of sg (mk_eqv (t, u)))));
wenzelm@2509
   112
wenzelm@2509
   113
wenzelm@2509
   114
wenzelm@2503
   115
(** simplification sets **)
wenzelm@2503
   116
wenzelm@2503
   117
(* type simpset *)
wenzelm@2503
   118
clasohm@0
   119
datatype simpset =
wenzelm@2503
   120
  Simpset of {
wenzelm@2503
   121
    mss: meta_simpset,
wenzelm@2503
   122
    simps: thm list,
wenzelm@2509
   123
    procs: simproc list,
wenzelm@2503
   124
    congs: thm list,
oheimb@2629
   125
    subgoal_tac:        simpset -> int -> tactic,
oheimb@2629
   126
    loop_tac:                      int -> tactic,
oheimb@2629
   127
           finish_tac: thm list -> int -> tactic,
oheimb@2629
   128
    unsafe_finish_tac: thm list -> int -> tactic};
wenzelm@2503
   129
oheimb@2629
   130
fun make_ss (mss, simps, procs, congs, 
oheimb@2629
   131
	     subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac) =
wenzelm@2509
   132
  Simpset {mss = mss, simps = simps, procs = procs, congs = congs,
oheimb@2629
   133
    subgoal_tac = subgoal_tac, loop_tac = loop_tac,
oheimb@2629
   134
    finish_tac = finish_tac, unsafe_finish_tac = unsafe_finish_tac};
clasohm@0
   135
clasohm@0
   136
val empty_ss =
oheimb@2629
   137
  make_ss (Thm.empty_mss, [], [], [], 
oheimb@2629
   138
	   K (K no_tac), K no_tac, K (K no_tac), K (K no_tac));
wenzelm@2503
   139
oheimb@2629
   140
fun rep_ss (Simpset {simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   141
		     finish_tac, unsafe_finish_tac, ...}) =
oheimb@2629
   142
  {simps = simps, procs = map name_of_simproc procs, congs = congs,
oheimb@2629
   143
   subgoal_tac = subgoal_tac, loop_tac = loop_tac,
oheimb@2629
   144
   finish_tac = finish_tac, unsafe_finish_tac = unsafe_finish_tac};
wenzelm@2503
   145
wenzelm@2503
   146
fun prems_of_ss (Simpset {mss, ...}) = Thm.prems_of_mss mss;
wenzelm@2503
   147
wenzelm@2503
   148
wenzelm@2503
   149
(* extend simpsets *)
wenzelm@2503
   150
oheimb@2629
   151
fun (Simpset {mss, simps, procs, congs, subgoal_tac = _, loop_tac, 
oheimb@2629
   152
	      finish_tac, unsafe_finish_tac}) setsubgoaler subgoal_tac =
oheimb@2629
   153
  make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   154
	   finish_tac, unsafe_finish_tac);
oheimb@2629
   155
oheimb@2629
   156
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac = _, 
oheimb@2629
   157
	      finish_tac, unsafe_finish_tac}) setloop loop_tac =
oheimb@2629
   158
  make_ss (mss, simps, procs, congs, subgoal_tac, DETERM o loop_tac, 
oheimb@2629
   159
	   finish_tac, unsafe_finish_tac);
wenzelm@2503
   160
oheimb@2629
   161
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   162
	      finish_tac, unsafe_finish_tac}) addloop tac =
oheimb@2629
   163
  make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac ORELSE'(DETERM o tac),
oheimb@2629
   164
	   finish_tac, unsafe_finish_tac);
oheimb@2567
   165
oheimb@2629
   166
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac,
oheimb@2629
   167
	      finish_tac = _, unsafe_finish_tac}) setSSolver finish_tac =
oheimb@2629
   168
  make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   169
	   finish_tac, unsafe_finish_tac);
wenzelm@2503
   170
oheimb@2629
   171
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   172
	      finish_tac, unsafe_finish_tac}) addSSolver tac =
oheimb@2629
   173
  make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac,
oheimb@2629
   174
    fn hyps => finish_tac hyps ORELSE' tac hyps, unsafe_finish_tac);
wenzelm@2503
   175
oheimb@2629
   176
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac,
oheimb@2629
   177
	      finish_tac, unsafe_finish_tac = _}) setSolver unsafe_finish_tac =
oheimb@2629
   178
  make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   179
	   finish_tac, unsafe_finish_tac);
wenzelm@2503
   180
oheimb@2629
   181
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   182
	      finish_tac, unsafe_finish_tac}) addSolver tac =
oheimb@2629
   183
  make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac,
oheimb@2629
   184
    finish_tac, fn hyps => unsafe_finish_tac hyps ORELSE' tac hyps);
wenzelm@2503
   185
oheimb@2629
   186
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   187
	      finish_tac, unsafe_finish_tac}) setmksimps mk_simps =
oheimb@2629
   188
  make_ss (Thm.set_mk_rews (mss, mk_simps), simps, procs, congs,
oheimb@2629
   189
    subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
oheimb@2629
   190
oheimb@2629
   191
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   192
	      finish_tac, unsafe_finish_tac}) settermless termless =
wenzelm@2509
   193
  make_ss (Thm.set_termless (mss, termless), simps, procs, congs,
oheimb@2629
   194
    subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   195
oheimb@2629
   196
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   197
	      finish_tac, unsafe_finish_tac}) addsimps rews =
wenzelm@2503
   198
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@2521
   199
    make_ss (Thm.add_simps (mss, rews'), gen_union eq_thm (rews', simps),
oheimb@2629
   200
    procs, congs, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac)
wenzelm@2503
   201
  end;
wenzelm@2503
   202
oheimb@2629
   203
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   204
	      finish_tac, unsafe_finish_tac}) delsimps rews =
wenzelm@2503
   205
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
oheimb@2629
   206
    make_ss (Thm.del_simps (mss, rews'), foldl (gen_rem eq_thm) (simps, rews'),
oheimb@2629
   207
    procs, congs, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac)
wenzelm@2503
   208
  end;
wenzelm@2503
   209
oheimb@2629
   210
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   211
	      finish_tac, unsafe_finish_tac}) addeqcongs newcongs =
oheimb@2629
   212
  make_ss (Thm.add_congs (mss, newcongs), simps, procs, 
oheimb@2629
   213
  gen_union eq_thm (congs, newcongs), subgoal_tac, loop_tac, 
oheimb@2629
   214
  finish_tac, unsafe_finish_tac);
wenzelm@2509
   215
oheimb@2629
   216
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   217
	      finish_tac, unsafe_finish_tac}) deleqcongs oldcongs =
oheimb@2629
   218
  make_ss (Thm.del_congs (mss, oldcongs), simps, procs, 
oheimb@2629
   219
  foldl (gen_rem eq_thm) (congs, oldcongs), subgoal_tac, loop_tac, 
oheimb@2629
   220
  finish_tac, unsafe_finish_tac);
oheimb@2629
   221
oheimb@2629
   222
fun addsimproc ((Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   223
			  finish_tac, unsafe_finish_tac}),
oheimb@2629
   224
			  simproc as Simproc {name = _, procs = procs'}) =
wenzelm@2509
   225
  make_ss (Thm.add_simprocs (mss, procs'),
wenzelm@2509
   226
    simps, gen_ins eq_simproc (simproc, procs),
oheimb@2629
   227
    congs, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   228
wenzelm@2509
   229
val op addsimprocs = foldl addsimproc;
wenzelm@2509
   230
oheimb@2629
   231
fun delsimproc ((Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   232
			  finish_tac, unsafe_finish_tac}),
oheimb@2629
   233
			  simproc as Simproc {name = _, procs = procs'}) =
wenzelm@2509
   234
  make_ss (Thm.del_simprocs (mss, procs'),
wenzelm@2509
   235
    simps, gen_rem eq_simproc (procs, simproc),
oheimb@2629
   236
    congs, subgoal_tac, loop_tac, finish_tac, unsafe_finish_tac);
wenzelm@2509
   237
wenzelm@2509
   238
val op delsimprocs = foldl delsimproc;
wenzelm@2503
   239
wenzelm@2503
   240
wenzelm@2503
   241
(* merge simpsets *)
wenzelm@2503
   242
wenzelm@2509
   243
(*prefers first simpset (FIXME improve?)*)
oheimb@2629
   244
fun merge_ss (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   245
		       finish_tac, unsafe_finish_tac},
wenzelm@2509
   246
    Simpset {simps = simps2, procs = procs2, congs = congs2, ...}) =
wenzelm@2503
   247
  let
wenzelm@2503
   248
    val simps' = gen_union eq_thm (simps, simps2);
wenzelm@2509
   249
    val procs' = gen_union eq_simproc (procs, procs2);
wenzelm@2503
   250
    val congs' = gen_union eq_thm (congs, congs2);
wenzelm@2503
   251
    val mss' = Thm.set_mk_rews (empty_mss, Thm.mk_rews_of_mss mss);
wenzelm@2503
   252
    val mss' = Thm.add_simps (mss', simps');
wenzelm@2503
   253
    val mss' = Thm.add_congs (mss', congs');
wenzelm@2503
   254
  in
oheimb@2629
   255
    make_ss (mss', simps', procs', congs', subgoal_tac, loop_tac, 
oheimb@2629
   256
	     finish_tac, unsafe_finish_tac)
wenzelm@2503
   257
  end;
wenzelm@2503
   258
wenzelm@2503
   259
wenzelm@2503
   260
(* the current simpset *)
clasohm@0
   261
clasohm@1243
   262
val simpset = ref empty_ss;
clasohm@0
   263
wenzelm@2503
   264
fun Addsimps rews = (simpset := ! simpset addsimps rews);
wenzelm@2503
   265
fun Delsimps rews = (simpset := ! simpset delsimps rews);
clasohm@0
   266
wenzelm@2509
   267
fun Addsimprocs procs = (simpset := ! simpset addsimprocs procs);
wenzelm@2509
   268
fun Delsimprocs procs = (simpset := ! simpset delsimprocs procs);
wenzelm@2509
   269
clasohm@0
   270
wenzelm@2503
   271
(** simplification tactics **)
clasohm@0
   272
nipkow@1
   273
fun NEWSUBGOALS tac tacf =
wenzelm@2503
   274
  STATE (fn state0 =>
wenzelm@2503
   275
    tac THEN STATE (fn state1 => tacf (nprems_of state1 - nprems_of state0)));
nipkow@1
   276
oheimb@2629
   277
(*not totally safe: may instantiate unknowns that appear also in other subgoals*)
oheimb@2629
   278
fun basic_gen_simp_tac mode =
oheimb@2629
   279
  fn (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, 
oheimb@2629
   280
	       finish_tac, unsafe_finish_tac}) =>
clasohm@0
   281
  let fun solve_all_tac mss =
wenzelm@2509
   282
        let val ss =
oheimb@2629
   283
              make_ss (mss, simps, procs, congs, subgoal_tac, loop_tac,
oheimb@2629
   284
		       unsafe_finish_tac, unsafe_finish_tac);
nipkow@1
   285
            val solve1_tac =
nipkow@1
   286
              NEWSUBGOALS (subgoal_tac ss 1)
nipkow@1
   287
                          (fn n => if n<0 then all_tac else no_tac)
nipkow@1
   288
        in DEPTH_SOLVE(solve1_tac) end
paulson@1512
   289
      fun simp_loop_tac i thm =
wenzelm@2503
   290
          (asm_rewrite_goal_tac mode solve_all_tac mss i THEN
wenzelm@2503
   291
           (finish_tac (prems_of_mss mss) i  ORELSE  looper i))  thm
nipkow@1
   292
      and allsimp i n = EVERY(map (fn j => simp_loop_tac (i+j)) (n downto 0))
nipkow@1
   293
      and looper i = TRY(NEWSUBGOALS (loop_tac i) (allsimp i))
nipkow@217
   294
  in simp_loop_tac end;
clasohm@0
   295
oheimb@2629
   296
fun gen_simp_tac mode ss = basic_gen_simp_tac mode 
oheimb@2629
   297
			   (ss setSSolver #unsafe_finish_tac (rep_ss ss));
oheimb@2629
   298
wenzelm@2503
   299
val          simp_tac = gen_simp_tac (false, false);
wenzelm@2503
   300
val      asm_simp_tac = gen_simp_tac (false, true);
wenzelm@2503
   301
val     full_simp_tac = gen_simp_tac (true,  false);
wenzelm@2503
   302
val asm_full_simp_tac = gen_simp_tac (true,  true);
clasohm@0
   303
oheimb@2629
   304
(*not totally safe: may instantiate unknowns that appear also in other subgoals*)
oheimb@2629
   305
val safe_asm_full_simp_tac = basic_gen_simp_tac (true, true);
oheimb@2629
   306
wenzelm@2503
   307
fun          Simp_tac i =          simp_tac (! simpset) i;
wenzelm@2503
   308
fun      Asm_simp_tac i =      asm_simp_tac (! simpset) i;
wenzelm@2503
   309
fun     Full_simp_tac i =     full_simp_tac (! simpset) i;
wenzelm@2503
   310
fun Asm_full_simp_tac i = asm_full_simp_tac (! simpset) i;
nipkow@406
   311
clasohm@1243
   312
end;