src/Pure/meta_simplifier.ML
changeset 12603 7d2bca103101
parent 12285 6490fc7b3eed
child 12779 c5739c1431ab
equal deleted inserted replaced
12602:6984018a98e3 12603:7d2bca103101
    15 signature META_SIMPLIFIER =
    15 signature META_SIMPLIFIER =
    16 sig
    16 sig
    17   include BASIC_META_SIMPLIFIER
    17   include BASIC_META_SIMPLIFIER
    18   exception SIMPLIFIER of string * thm
    18   exception SIMPLIFIER of string * thm
    19   type meta_simpset
    19   type meta_simpset
    20   val dest_mss		: meta_simpset ->
    20   val dest_mss          : meta_simpset ->
    21     {simps: thm list, congs: thm list, procs: (string * cterm list) list}
    21     {simps: thm list, congs: thm list, procs: (string * cterm list) list}
    22   val empty_mss         : meta_simpset
    22   val empty_mss         : meta_simpset
    23   val clear_mss		: meta_simpset -> meta_simpset
    23   val clear_mss         : meta_simpset -> meta_simpset
    24   val merge_mss		: meta_simpset * meta_simpset -> meta_simpset
    24   val merge_mss         : meta_simpset * meta_simpset -> meta_simpset
    25   val add_simps         : meta_simpset * thm list -> meta_simpset
    25   val add_simps         : meta_simpset * thm list -> meta_simpset
    26   val del_simps         : meta_simpset * thm list -> meta_simpset
    26   val del_simps         : meta_simpset * thm list -> meta_simpset
    27   val mss_of            : thm list -> meta_simpset
    27   val mss_of            : thm list -> meta_simpset
    28   val add_congs         : meta_simpset * thm list -> meta_simpset
    28   val add_congs         : meta_simpset * thm list -> meta_simpset
    29   val del_congs         : meta_simpset * thm list -> meta_simpset
    29   val del_congs         : meta_simpset * thm list -> meta_simpset
    30   val add_simprocs	: meta_simpset *
    30   val add_simprocs      : meta_simpset *
    31     (string * cterm list * (Sign.sg -> thm list -> term -> thm option) * stamp) list
    31     (string * cterm list * (Sign.sg -> thm list -> term -> thm option) * stamp) list
    32       -> meta_simpset
    32       -> meta_simpset
    33   val del_simprocs	: meta_simpset *
    33   val del_simprocs      : meta_simpset *
    34     (string * cterm list * (Sign.sg -> thm list -> term -> thm option) * stamp) list
    34     (string * cterm list * (Sign.sg -> thm list -> term -> thm option) * stamp) list
    35       -> meta_simpset
    35       -> meta_simpset
    36   val add_prems         : meta_simpset * thm list -> meta_simpset
    36   val add_prems         : meta_simpset * thm list -> meta_simpset
    37   val prems_of_mss      : meta_simpset -> thm list
    37   val prems_of_mss      : meta_simpset -> thm list
    38   val set_mk_rews       : meta_simpset * (thm -> thm list) -> meta_simpset
    38   val set_mk_rews       : meta_simpset * (thm -> thm list) -> meta_simpset
    62 
    62 
    63 exception SIMPLIFIER of string * thm;
    63 exception SIMPLIFIER of string * thm;
    64 
    64 
    65 val simp_depth = ref 0;
    65 val simp_depth = ref 0;
    66 
    66 
    67 fun println a = tracing (replicate_string (! simp_depth) " " ^ a);
    67 local
       
    68 
       
    69 fun println a =
       
    70   tracing ((case ! simp_depth of 0 => "" | n => "[" ^ string_of_int n ^ "]") ^ a);
    68 
    71 
    69 fun prnt warn a = if warn then warning a else println a;
    72 fun prnt warn a = if warn then warning a else println a;
    70 
    73 fun prtm warn a sign t = prnt warn (a ^ "\n" ^ Sign.string_of_term sign t);
    71 fun prtm warn a sign t =
    74 fun prctm warn a t = prnt warn (a ^ "\n" ^ Display.string_of_cterm t);
    72   (prnt warn a; prnt warn (Sign.string_of_term sign t));
    75 
    73 
    76 in
    74 fun prctm warn a t =
    77 
    75   (prnt warn a; prnt warn (Display.string_of_cterm t));
    78 fun prthm warn a = prctm warn a o Thm.cprop_of;
    76 
       
    77 fun prthm warn a thm =
       
    78   let val {sign, prop, ...} = rep_thm thm
       
    79   in prtm warn a sign prop end;
       
    80 
    79 
    81 val trace_simp = ref false;
    80 val trace_simp = ref false;
    82 val debug_simp = ref false;
    81 val debug_simp = ref false;
    83 
    82 
    84 fun trace warn a = if !trace_simp then prnt warn a else ();
    83 fun trace warn a = if !trace_simp then prnt warn a else ();
    90 
    89 
    91 fun trace_thm warn a thm =
    90 fun trace_thm warn a thm =
    92   let val {sign, prop, ...} = rep_thm thm
    91   let val {sign, prop, ...} = rep_thm thm
    93   in trace_term warn a sign prop end;
    92   in trace_term warn a sign prop end;
    94 
    93 
       
    94 end;
    95 
    95 
    96 
    96 
    97 (** meta simp sets **)
    97 (** meta simp sets **)
    98 
    98 
    99 (* basic components *)
    99 (* basic components *)
   102 (* thm: the rewrite rule
   102 (* thm: the rewrite rule
   103    lhs: the left-hand side
   103    lhs: the left-hand side
   104    elhs: the etac-contracted lhs.
   104    elhs: the etac-contracted lhs.
   105    fo:  use first-order matching
   105    fo:  use first-order matching
   106    perm: the rewrite rule is permutative
   106    perm: the rewrite rule is permutative
   107 Reamrks:
   107 Remarks:
   108   - elhs is used for matching,
   108   - elhs is used for matching,
   109     lhs only for preservation of bound variable names.
   109     lhs only for preservation of bound variable names.
   110   - fo is set iff
   110   - fo is set iff
   111     either elhs is first-order (no Var is applied),
   111     either elhs is first-order (no Var is applied),
   112            in which case fo-matching is complete,
   112            in which case fo-matching is complete,
   118  {name: string, proc: Sign.sg -> thm list -> term -> thm option, lhs: cterm, id: stamp};
   118  {name: string, proc: Sign.sg -> thm list -> term -> thm option, lhs: cterm, id: stamp};
   119 
   119 
   120 fun eq_rrule ({thm = thm1, ...}: rrule, {thm = thm2, ...}: rrule) =
   120 fun eq_rrule ({thm = thm1, ...}: rrule, {thm = thm2, ...}: rrule) =
   121   #prop (rep_thm thm1) aconv #prop (rep_thm thm2);
   121   #prop (rep_thm thm1) aconv #prop (rep_thm thm2);
   122 
   122 
   123 fun eq_cong ({thm = thm1, ...}: cong, {thm = thm2, ...}: cong) = 
   123 fun eq_cong ({thm = thm1, ...}: cong, {thm = thm2, ...}: cong) =
   124   #prop (rep_thm thm1) aconv #prop (rep_thm thm2);
   124   #prop (rep_thm thm1) aconv #prop (rep_thm thm2);
   125 
   125 
   126 fun eq_prem (thm1, thm2) =
   126 fun eq_prem (thm1, thm2) =
   127   #prop (rep_thm thm1) aconv #prop (rep_thm thm2);
   127   #prop (rep_thm thm1) aconv #prop (rep_thm thm2);
   128 
   128 
   179 fun clear_mss (Mss {mk_rews, termless, ...}) =
   179 fun clear_mss (Mss {mk_rews, termless, ...}) =
   180   mk_mss (Net.empty, ([], []), Net.empty, [], [], mk_rews, termless,0);
   180   mk_mss (Net.empty, ([], []), Net.empty, [], [], mk_rews, termless,0);
   181 
   181 
   182 fun incr_depth(Mss{rules,congs,procs,bounds,prems,mk_rews,termless,depth}) =
   182 fun incr_depth(Mss{rules,congs,procs,bounds,prems,mk_rews,termless,depth}) =
   183   mk_mss (rules, congs, procs, bounds, prems, mk_rews, termless, depth+1)
   183   mk_mss (rules, congs, procs, bounds, prems, mk_rews, termless, depth+1)
   184  
   184 
   185 
   185 
   186 
   186 
   187 (** simpset operations **)
   187 (** simpset operations **)
   188 
   188 
   189 (* term variables *)
   189 (* term variables *)
   202      |> partition_eq eq_snd
   202      |> partition_eq eq_snd
   203      |> map (fn ps => (#1 (#1 (hd ps)), map (#2 o #1) ps))
   203      |> map (fn ps => (#1 (#1 (hd ps)), map (#2 o #1) ps))
   204      |> Library.sort_wrt #1};
   204      |> Library.sort_wrt #1};
   205 
   205 
   206 
   206 
   207 (* merge_mss *)	      (*NOTE: ignores mk_rews, termless and depth of 2nd mss*)
   207 (* merge_mss *)       (*NOTE: ignores mk_rews, termless and depth of 2nd mss*)
   208 
   208 
   209 fun merge_mss
   209 fun merge_mss
   210  (Mss {rules = rules1, congs = (congs1,weak1), procs = procs1,
   210  (Mss {rules = rules1, congs = (congs1,weak1), procs = procs1,
   211        bounds = bounds1, prems = prems1, mk_rews, termless, depth},
   211        bounds = bounds1, prems = prems1, mk_rews, termless, depth},
   212   Mss {rules = rules2, congs = (congs2,weak2), procs = procs2,
   212   Mss {rules = rules2, congs = (congs2,weak2), procs = procs2,
   428   let val {sign, t, ...} = rep_cterm lhs
   428   let val {sign, t, ...} = rep_cterm lhs
   429   in (trace_term false ("Adding simplification procedure " ^ quote name ^ " for")
   429   in (trace_term false ("Adding simplification procedure " ^ quote name ^ " for")
   430       sign t;
   430       sign t;
   431     mk_mss (rules, congs,
   431     mk_mss (rules, congs,
   432       Net.insert_term ((t, mk_simproc (name, proc, lhs, id)), procs, eq_simproc)
   432       Net.insert_term ((t, mk_simproc (name, proc, lhs, id)), procs, eq_simproc)
   433         handle Net.INSERT => 
   433         handle Net.INSERT =>
   434 	    (warning ("Ignoring duplicate simplification procedure \"" 
   434             (warning ("Ignoring duplicate simplification procedure \""
   435 	              ^ name ^ "\""); 
   435                       ^ name ^ "\"");
   436 	     procs),
   436              procs),
   437         bounds, prems, mk_rews, termless,depth))
   437         bounds, prems, mk_rews, termless,depth))
   438   end;
   438   end;
   439 
   439 
   440 fun add_simproc (mss, (name, lhss, proc, id)) =
   440 fun add_simproc (mss, (name, lhss, proc, id)) =
   441   foldl add_proc (mss, map (fn lhs => (name, lhs, proc, id)) lhss);
   441   foldl add_proc (mss, map (fn lhs => (name, lhs, proc, id)) lhss);
   447 
   447 
   448 fun del_proc (mss as Mss {rules,congs,procs,bounds,prems,mk_rews,termless,depth},
   448 fun del_proc (mss as Mss {rules,congs,procs,bounds,prems,mk_rews,termless,depth},
   449     (name, lhs, proc, id)) =
   449     (name, lhs, proc, id)) =
   450   mk_mss (rules, congs,
   450   mk_mss (rules, congs,
   451     Net.delete_term ((term_of lhs, mk_simproc (name, proc, lhs, id)), procs, eq_simproc)
   451     Net.delete_term ((term_of lhs, mk_simproc (name, proc, lhs, id)), procs, eq_simproc)
   452       handle Net.DELETE => 
   452       handle Net.DELETE =>
   453 	  (warning ("Simplification procedure \"" ^ name ^
   453           (warning ("Simplification procedure \"" ^ name ^
   454 		       "\" not in simpset"); procs),
   454                        "\" not in simpset"); procs),
   455       bounds, prems, mk_rews, termless, depth);
   455       bounds, prems, mk_rews, termless, depth);
   456 
   456 
   457 fun del_simproc (mss, (name, lhss, proc, id)) =
   457 fun del_simproc (mss, (name, lhss, proc, id)) =
   458   foldl del_proc (mss, map (fn lhs => (name, lhs, proc, id)) lhss);
   458   foldl del_proc (mss, map (fn lhs => (name, lhs, proc, id)) lhss);
   459 
   459 
   628       | rews (rrule :: rrules) =
   628       | rews (rrule :: rrules) =
   629           let val opt = rew rrule handle Pattern.MATCH => None
   629           let val opt = rew rrule handle Pattern.MATCH => None
   630           in case opt of None => rews rrules | some => some end;
   630           in case opt of None => rews rrules | some => some end;
   631 
   631 
   632     fun sort_rrules rrs = let
   632     fun sort_rrules rrs = let
   633       fun is_simple({thm, ...}:rrule) = case #prop (rep_thm thm) of 
   633       fun is_simple({thm, ...}:rrule) = case #prop (rep_thm thm) of
   634                                       Const("==",_) $ _ $ _ => true
   634                                       Const("==",_) $ _ $ _ => true
   635                                       | _                   => false 
   635                                       | _                   => false
   636       fun sort []        (re1,re2) = re1 @ re2
   636       fun sort []        (re1,re2) = re1 @ re2
   637         | sort (rr::rrs) (re1,re2) = if is_simple rr 
   637         | sort (rr::rrs) (re1,re2) = if is_simple rr
   638                                      then sort rrs (rr::re1,re2)
   638                                      then sort rrs (rr::re1,re2)
   639                                      else sort rrs (re1,rr::re2)
   639                                      else sort rrs (re1,rr::re2)
   640     in sort rrs ([],[]) end
   640     in sort rrs ([],[]) end
   641 
   641 
   642     fun proc_rews ([]:simproc list) = None
   642     fun proc_rews ([]:simproc list) = None
   821           end
   821           end
   822 
   822 
   823         fun rebuild None = (case rewritec (prover, sign, maxidx) mss
   823         fun rebuild None = (case rewritec (prover, sign, maxidx) mss
   824             (mk_implies (prem1, conc)) of
   824             (mk_implies (prem1, conc)) of
   825               None => None
   825               None => None
   826             | Some (thm, _) => 
   826             | Some (thm, _) =>
   827                 let val (prem, conc) = Drule.dest_implies (rhs_of thm)
   827                 let val (prem, conc) = Drule.dest_implies (rhs_of thm)
   828                 in (case mut_impc (prems, prem, conc, mss) of
   828                 in (case mut_impc (prems, prem, conc, mss) of
   829                     None => Some (None, thm)
   829                     None => Some (None, thm)
   830                   | Some (x, thm') => Some (x, transitive thm thm'))
   830                   | Some (x, thm') => Some (x, transitive thm thm'))
   831                 end handle TERM _ => Some (None, thm))
   831                 end handle TERM _ => Some (None, thm))