src/Provers/simplifier.ML
author wenzelm
Thu Jan 16 14:53:37 1997 +0100 (1997-01-16 ago)
changeset 2509 0a7169d89b7a
parent 2503 7590fd5ce3c7
child 2521 b7dd670cfe3a
permissions -rw-r--r--
added termless parameter;
added simplification procedures;
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
wenzelm@2509
    14
infix 4 addsimps addeqcongs addsimprocs delsimprocs addsolver delsimps
wenzelm@2509
    15
  setsolver setloop setmksimps settermless setsubgoaler;
clasohm@0
    16
clasohm@0
    17
signature SIMPLIFIER =
clasohm@0
    18
sig
wenzelm@2509
    19
  type simproc
wenzelm@2509
    20
  val mk_simproc: string -> cterm list -> (Sign.sg -> term -> thm option) -> simproc
wenzelm@2509
    21
  val name_of_simproc: simproc -> string
wenzelm@2509
    22
  val conv_prover: (term * term -> term) -> thm -> (thm -> thm)
wenzelm@2509
    23
    -> tactic -> (int -> tactic) -> Sign.sg -> term -> term -> thm	(* FIXME move?, rename? *)
clasohm@0
    24
  type simpset
wenzelm@2503
    25
  val empty_ss: simpset
wenzelm@2509
    26
  val rep_ss: simpset -> {simps: thm list, procs: string list, congs: thm list}
wenzelm@2503
    27
  val prems_of_ss: simpset -> thm list
wenzelm@2503
    28
  val setloop: simpset * (int -> tactic) -> simpset
wenzelm@2503
    29
  val setsolver: simpset * (thm list -> int -> tactic) -> simpset
wenzelm@2503
    30
  val addsolver: simpset * (thm list -> int -> tactic) -> simpset
wenzelm@2503
    31
  val setsubgoaler: simpset * (simpset -> int -> tactic) -> simpset
wenzelm@2503
    32
  val setmksimps: simpset * (thm -> thm list) -> simpset
wenzelm@2509
    33
  val settermless: simpset * (term * term -> bool) -> simpset
clasohm@0
    34
  val addsimps: simpset * thm list -> simpset
nipkow@88
    35
  val delsimps: simpset * thm list -> simpset
wenzelm@2509
    36
  val addsimprocs: simpset * simproc list -> simpset
wenzelm@2509
    37
  val delsimprocs: simpset * simproc list -> simpset
wenzelm@2503
    38
  val addeqcongs: simpset * thm list -> simpset
clasohm@0
    39
  val merge_ss: simpset * simpset -> simpset
clasohm@1243
    40
  val simpset: simpset ref
clasohm@1243
    41
  val Addsimps: thm list -> unit
clasohm@1243
    42
  val Delsimps: thm list -> unit
wenzelm@2509
    43
  val Addsimprocs: simproc list -> unit
wenzelm@2509
    44
  val Delsimprocs: simproc list -> unit
wenzelm@2503
    45
  val          simp_tac: simpset -> int -> tactic
wenzelm@2503
    46
  val      asm_simp_tac: simpset -> int -> tactic
wenzelm@2503
    47
  val     full_simp_tac: simpset -> int -> tactic
wenzelm@2503
    48
  val asm_full_simp_tac: simpset -> int -> tactic
wenzelm@2503
    49
  val          Simp_tac: int -> tactic
oheimb@1676
    50
  val      Asm_simp_tac: int -> tactic
oheimb@1676
    51
  val     Full_simp_tac: int -> tactic
clasohm@1243
    52
  val Asm_full_simp_tac: int -> tactic
clasohm@0
    53
end;
clasohm@0
    54
wenzelm@2503
    55
wenzelm@2503
    56
structure Simplifier: SIMPLIFIER =
clasohm@0
    57
struct
clasohm@0
    58
wenzelm@2509
    59
wenzelm@2509
    60
(** simplification procedures **)
wenzelm@2509
    61
wenzelm@2509
    62
(* datatype simproc *)
wenzelm@2509
    63
wenzelm@2509
    64
datatype simproc =
wenzelm@2509
    65
  Simproc of {
wenzelm@2509
    66
    name: string,
wenzelm@2509
    67
    procs: (Sign.sg * term * (Sign.sg -> term -> thm option) * stamp) list}
wenzelm@2509
    68
wenzelm@2509
    69
(* FIXME stamps!? *)
wenzelm@2509
    70
fun eq_simproc (Simproc {name = name1, ...}, Simproc {name = name2, ...}) =
wenzelm@2509
    71
  (name1 = name2);
wenzelm@2509
    72
wenzelm@2509
    73
fun mk_simproc name lhss proc =
wenzelm@2509
    74
  let
wenzelm@2509
    75
    fun mk_proc lhs =
wenzelm@2509
    76
      (#sign (Thm.rep_cterm lhs), Logic.varify (term_of lhs), proc, stamp ());
wenzelm@2509
    77
  in
wenzelm@2509
    78
    Simproc {name = name, procs = map mk_proc lhss}
wenzelm@2509
    79
  end;
wenzelm@2509
    80
wenzelm@2509
    81
fun name_of_simproc (Simproc {name, ...}) = name;
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,
wenzelm@2503
   111
    simps: thm list,
wenzelm@2509
   112
    procs: simproc list,
wenzelm@2503
   113
    congs: thm list,
wenzelm@2503
   114
    subgoal_tac: simpset -> int -> tactic,
wenzelm@2503
   115
    finish_tac: thm list -> int -> tactic,
wenzelm@2503
   116
    loop_tac: int -> tactic};
wenzelm@2503
   117
wenzelm@2509
   118
fun make_ss (mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac) =
wenzelm@2509
   119
  Simpset {mss = mss, simps = simps, procs = procs, congs = congs,
wenzelm@2503
   120
    subgoal_tac = subgoal_tac, finish_tac = finish_tac,
wenzelm@2503
   121
    loop_tac = loop_tac};
clasohm@0
   122
clasohm@0
   123
val empty_ss =
wenzelm@2509
   124
  make_ss (Thm.empty_mss, [], [], [], K (K no_tac), K (K no_tac), K no_tac);
wenzelm@2503
   125
wenzelm@2509
   126
fun rep_ss (Simpset {simps, procs, congs, ...}) =
wenzelm@2509
   127
  {simps = simps, procs = map name_of_simproc procs, congs = congs};
wenzelm@2503
   128
wenzelm@2503
   129
fun prems_of_ss (Simpset {mss, ...}) = Thm.prems_of_mss mss;
wenzelm@2503
   130
wenzelm@2503
   131
wenzelm@2503
   132
(* extend simpsets *)
wenzelm@2503
   133
wenzelm@2509
   134
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac = _})
wenzelm@2503
   135
    setloop loop_tac =
wenzelm@2509
   136
  make_ss (mss, simps, procs, congs, subgoal_tac, finish_tac, DETERM o loop_tac);
wenzelm@2503
   137
wenzelm@2509
   138
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac = _, loop_tac})
wenzelm@2503
   139
    setsolver finish_tac =
wenzelm@2509
   140
  make_ss (mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac);
wenzelm@2503
   141
wenzelm@2509
   142
fun (Simpset {mss, simps, procs, congs, subgoal_tac, loop_tac, finish_tac})
wenzelm@2503
   143
    addsolver tac =
wenzelm@2509
   144
  make_ss (mss, simps, procs, congs, subgoal_tac,
wenzelm@2503
   145
    fn hyps => finish_tac hyps ORELSE' tac hyps, loop_tac);
wenzelm@2503
   146
wenzelm@2509
   147
fun (Simpset {mss, simps, procs, congs, subgoal_tac = _, finish_tac, loop_tac})
wenzelm@2503
   148
    setsubgoaler subgoal_tac =
wenzelm@2509
   149
  make_ss (mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac);
wenzelm@2503
   150
wenzelm@2509
   151
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac})
wenzelm@2503
   152
    setmksimps mk_simps =
wenzelm@2509
   153
  make_ss (Thm.set_mk_rews (mss, mk_simps), simps, procs, congs,
wenzelm@2503
   154
    subgoal_tac, finish_tac, loop_tac);
wenzelm@2503
   155
wenzelm@2509
   156
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac})
wenzelm@2509
   157
    settermless termless =
wenzelm@2509
   158
  make_ss (Thm.set_termless (mss, termless), simps, procs, congs,
wenzelm@2509
   159
    subgoal_tac, finish_tac, loop_tac);
wenzelm@2509
   160
wenzelm@2509
   161
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac})
wenzelm@2503
   162
    addsimps rews =
wenzelm@2503
   163
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@2503
   164
    make_ss (Thm.add_simps (mss, rews'), rews' @ simps,
wenzelm@2509
   165
      procs, congs, subgoal_tac, finish_tac, loop_tac)
wenzelm@2503
   166
  end;
wenzelm@2503
   167
wenzelm@2509
   168
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac})
wenzelm@2503
   169
    delsimps rews =
wenzelm@2503
   170
  let val rews' = flat (map (Thm.mk_rews_of_mss mss) rews) in
wenzelm@2503
   171
    make_ss (Thm.del_simps (mss, rews'),
wenzelm@2503
   172
      foldl (gen_rem eq_thm) (simps, rews'),
wenzelm@2509
   173
      procs, congs, subgoal_tac, finish_tac, loop_tac)
wenzelm@2503
   174
  end;
wenzelm@2503
   175
wenzelm@2509
   176
fun (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac})
wenzelm@2503
   177
    addeqcongs newcongs =
wenzelm@2503
   178
  make_ss (Thm.add_congs (mss, newcongs),
wenzelm@2509
   179
    simps, procs, newcongs @ congs, subgoal_tac, finish_tac, loop_tac);
wenzelm@2509
   180
wenzelm@2509
   181
fun addsimproc ((Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac}),
wenzelm@2509
   182
      simproc as Simproc {name = _, procs = procs'}) =
wenzelm@2509
   183
  make_ss (Thm.add_simprocs (mss, procs'),
wenzelm@2509
   184
    simps, gen_ins eq_simproc (simproc, procs),
wenzelm@2509
   185
    congs, subgoal_tac, finish_tac, loop_tac);
wenzelm@2509
   186
wenzelm@2509
   187
val op addsimprocs = foldl addsimproc;
wenzelm@2509
   188
wenzelm@2509
   189
fun delsimproc ((Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac}),
wenzelm@2509
   190
      simproc as Simproc {name = _, procs = procs'}) =
wenzelm@2509
   191
  make_ss (Thm.del_simprocs (mss, procs'),
wenzelm@2509
   192
    simps, gen_rem eq_simproc (procs, simproc),
wenzelm@2509
   193
    congs, subgoal_tac, finish_tac, loop_tac);
wenzelm@2509
   194
wenzelm@2509
   195
val op delsimprocs = foldl delsimproc;
wenzelm@2503
   196
wenzelm@2503
   197
wenzelm@2503
   198
(* merge simpsets *)
wenzelm@2503
   199
wenzelm@2509
   200
(*prefers first simpset (FIXME improve?)*)
wenzelm@2509
   201
fun merge_ss (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac},
wenzelm@2509
   202
    Simpset {simps = simps2, procs = procs2, congs = congs2, ...}) =
wenzelm@2503
   203
  let
wenzelm@2503
   204
    val simps' = gen_union eq_thm (simps, simps2);
wenzelm@2509
   205
    val procs' = gen_union eq_simproc (procs, procs2);
wenzelm@2503
   206
    val congs' = gen_union eq_thm (congs, congs2);
wenzelm@2503
   207
    val mss' = Thm.set_mk_rews (empty_mss, Thm.mk_rews_of_mss mss);
wenzelm@2503
   208
    val mss' = Thm.add_simps (mss', simps');
wenzelm@2503
   209
    val mss' = Thm.add_congs (mss', congs');
wenzelm@2503
   210
  in
wenzelm@2509
   211
    make_ss (mss', simps', procs', congs', subgoal_tac, finish_tac, loop_tac)
wenzelm@2503
   212
  end;
wenzelm@2503
   213
wenzelm@2503
   214
wenzelm@2503
   215
(* the current simpset *)
clasohm@0
   216
clasohm@1243
   217
val simpset = ref empty_ss;
clasohm@0
   218
wenzelm@2503
   219
fun Addsimps rews = (simpset := ! simpset addsimps rews);
wenzelm@2503
   220
fun Delsimps rews = (simpset := ! simpset delsimps rews);
clasohm@0
   221
wenzelm@2509
   222
fun Addsimprocs procs = (simpset := ! simpset addsimprocs procs);
wenzelm@2509
   223
fun Delsimprocs procs = (simpset := ! simpset delsimprocs procs);
wenzelm@2509
   224
clasohm@0
   225
clasohm@1243
   226
wenzelm@2503
   227
(** simplification tactics **)
clasohm@0
   228
nipkow@1
   229
fun NEWSUBGOALS tac tacf =
wenzelm@2503
   230
  STATE (fn state0 =>
wenzelm@2503
   231
    tac THEN STATE (fn state1 => tacf (nprems_of state1 - nprems_of state0)));
nipkow@1
   232
nipkow@217
   233
fun gen_simp_tac mode =
wenzelm@2509
   234
  fn (Simpset {mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac}) =>
clasohm@0
   235
  let fun solve_all_tac mss =
wenzelm@2509
   236
        let val ss =
wenzelm@2509
   237
              make_ss (mss, simps, procs, congs, subgoal_tac, finish_tac, loop_tac);
nipkow@1
   238
            val solve1_tac =
nipkow@1
   239
              NEWSUBGOALS (subgoal_tac ss 1)
nipkow@1
   240
                          (fn n => if n<0 then all_tac else no_tac)
nipkow@1
   241
        in DEPTH_SOLVE(solve1_tac) end
clasohm@0
   242
paulson@1512
   243
      fun simp_loop_tac i thm =
wenzelm@2503
   244
          (asm_rewrite_goal_tac mode solve_all_tac mss i THEN
wenzelm@2503
   245
           (finish_tac (prems_of_mss mss) i  ORELSE  looper i))  thm
nipkow@1
   246
      and allsimp i n = EVERY(map (fn j => simp_loop_tac (i+j)) (n downto 0))
nipkow@1
   247
      and looper i = TRY(NEWSUBGOALS (loop_tac i) (allsimp i))
nipkow@217
   248
  in simp_loop_tac end;
clasohm@0
   249
wenzelm@2503
   250
val          simp_tac = gen_simp_tac (false, false);
wenzelm@2503
   251
val      asm_simp_tac = gen_simp_tac (false, true);
wenzelm@2503
   252
val     full_simp_tac = gen_simp_tac (true,  false);
wenzelm@2503
   253
val asm_full_simp_tac = gen_simp_tac (true,  true);
clasohm@0
   254
wenzelm@2503
   255
fun          Simp_tac i =          simp_tac (! simpset) i;
wenzelm@2503
   256
fun      Asm_simp_tac i =      asm_simp_tac (! simpset) i;
wenzelm@2503
   257
fun     Full_simp_tac i =     full_simp_tac (! simpset) i;
wenzelm@2503
   258
fun Asm_full_simp_tac i = asm_full_simp_tac (! simpset) i;
nipkow@406
   259
clasohm@1243
   260
end;