src/Provers/splitter.ML
author wenzelm
Sat Dec 14 17:28:05 2013 +0100 (2013-12-14)
changeset 54742 7a86358a3c0b
parent 54216 c0c453ce70a7
child 56245 84fc7dfa3cd4
permissions -rw-r--r--
proper context for basic Simplifier operations: rewrite_rule, rewrite_goals_rule, rewrite_goals_tac etc.;
clarified tool context in some boundary cases;
     1 (*  Title:      Provers/splitter.ML
     2     Author:     Tobias Nipkow
     3     Copyright   1995  TU Munich
     4 
     5 Generic case-splitter, suitable for most logics.
     6 Deals with equalities of the form ?P(f args) = ...
     7 where "f args" must be a first-order term without duplicate variables.
     8 *)
     9 
    10 signature SPLITTER_DATA =
    11 sig
    12   val thy           : theory
    13   val mk_eq         : thm -> thm
    14   val meta_eq_to_iff: thm (* "x == y ==> x = y"                      *)
    15   val iffD          : thm (* "[| P = Q; Q |] ==> P"                  *)
    16   val disjE         : thm (* "[| P | Q; P ==> R; Q ==> R |] ==> R"   *)
    17   val conjE         : thm (* "[| P & Q; [| P; Q |] ==> R |] ==> R"   *)
    18   val exE           : thm (* "[| EX x. P x; !!x. P x ==> Q |] ==> Q" *)
    19   val contrapos     : thm (* "[| ~ Q; P ==> Q |] ==> ~ P"            *)
    20   val contrapos2    : thm (* "[| Q; ~ P ==> ~ Q |] ==> P"            *)
    21   val notnotD       : thm (* "~ ~ P ==> P"                           *)
    22 end
    23 
    24 signature SPLITTER =
    25 sig
    26   (* somewhat more internal functions *)
    27   val cmap_of_split_thms: thm list -> (string * (typ * term * thm * typ * int) list) list
    28   val split_posns: (string * (typ * term * thm * typ * int) list) list ->
    29     theory -> typ list -> term -> (thm * (typ * typ * int list) list * int list * typ * term) list
    30     (* first argument is a "cmap", returns a list of "split packs" *)
    31   (* the "real" interface, providing a number of tactics *)
    32   val split_tac       : thm list -> int -> tactic
    33   val split_inside_tac: thm list -> int -> tactic
    34   val split_asm_tac   : thm list -> int -> tactic
    35   val add_split: thm -> Proof.context -> Proof.context
    36   val del_split: thm -> Proof.context -> Proof.context
    37   val split_add: attribute
    38   val split_del: attribute
    39   val split_modifiers : Method.modifier parser list
    40   val setup: theory -> theory
    41 end;
    42 
    43 functor Splitter(Data: SPLITTER_DATA): SPLITTER =
    44 struct
    45 
    46 val Const (const_not, _) $ _ =
    47   Object_Logic.drop_judgment Data.thy
    48     (#1 (Logic.dest_implies (Thm.prop_of Data.notnotD)));
    49 
    50 val Const (const_or , _) $ _ $ _ =
    51   Object_Logic.drop_judgment Data.thy
    52     (#1 (Logic.dest_implies (Thm.prop_of Data.disjE)));
    53 
    54 val const_Trueprop = Object_Logic.judgment_name Data.thy;
    55 
    56 
    57 fun split_format_err () = error "Wrong format for split rule";
    58 
    59 fun split_thm_info thm = case concl_of (Data.mk_eq thm) of
    60      Const("==", _) $ (Var _ $ t) $ c => (case strip_comb t of
    61        (Const p, _) => (p, case c of (Const (s, _) $ _) => s = const_not | _ => false)
    62      | _ => split_format_err ())
    63    | _ => split_format_err ();
    64 
    65 fun cmap_of_split_thms thms =
    66 let
    67   val splits = map Data.mk_eq thms
    68   fun add_thm thm cmap =
    69     (case concl_of thm of _ $ (t as _ $ lhs) $ _ =>
    70        (case strip_comb lhs of (Const(a,aT),args) =>
    71           let val info = (aT,lhs,thm,fastype_of t,length args)
    72           in case AList.lookup (op =) cmap a of
    73                SOME infos => AList.update (op =) (a, info::infos) cmap
    74              | NONE => (a,[info])::cmap
    75           end
    76         | _ => split_format_err())
    77      | _ => split_format_err())
    78 in
    79   fold add_thm splits []
    80 end;
    81 
    82 val abss = fold (Term.abs o pair "");
    83 
    84 (* ------------------------------------------------------------------------- *)
    85 (* mk_case_split_tac                                                         *)
    86 (* ------------------------------------------------------------------------- *)
    87 
    88 fun mk_case_split_tac order =
    89 let
    90 
    91 (************************************************************
    92    Create lift-theorem "trlift" :
    93 
    94    [| !!x. Q x == R x; P(%x. R x) == C |] ==> P (%x. Q x) == C
    95 
    96 *************************************************************)
    97 
    98 val meta_iffD = Data.meta_eq_to_iff RS Data.iffD;  (* (P == Q) ==> Q ==> P *)
    99 
   100 val lift = Goal.prove_global Pure.thy ["P", "Q", "R"]
   101   [Syntax.read_prop_global Pure.thy "!!x :: 'b. Q(x) == R(x) :: 'c"]
   102   (Syntax.read_prop_global Pure.thy "P(%x. Q(x)) == P(%x. R(x))")
   103   (fn {context = ctxt, prems} => rewrite_goals_tac ctxt prems THEN rtac reflexive_thm 1)
   104 
   105 val _ $ _ $ (_ $ (_ $ abs_lift) $ _) = prop_of lift;
   106 
   107 val trlift = lift RS transitive_thm;
   108 
   109 
   110 (************************************************************************
   111    Set up term for instantiation of P in the lift-theorem
   112 
   113    t     : lefthand side of meta-equality in subgoal
   114            the lift theorem is applied to (see select)
   115    pos   : "path" leading to abstraction, coded as a list
   116    T     : type of body of P(...)
   117 *************************************************************************)
   118 
   119 fun mk_cntxt t pos T =
   120   let
   121     fun down [] t = (Bound 0, t)
   122       | down (p :: ps) t =
   123           let
   124             val (h, ts) = strip_comb t
   125             val (ts1, u :: ts2) = chop p ts
   126             val (u1, u2) = down ps u
   127           in
   128             (list_comb (incr_boundvars 1 h,
   129                map (incr_boundvars 1) ts1 @ u1 ::
   130                map (incr_boundvars 1) ts2),
   131              u2)
   132           end;
   133     val (u1, u2) = down (rev pos) t
   134   in (Abs ("", T, u1), u2) end;
   135 
   136 
   137 (************************************************************************
   138    Set up term for instantiation of P in the split-theorem
   139    P(...) == rhs
   140 
   141    t     : lefthand side of meta-equality in subgoal
   142            the split theorem is applied to (see select)
   143    T     : type of body of P(...)
   144    tt    : the term  Const(key,..) $ ...
   145 *************************************************************************)
   146 
   147 fun mk_cntxt_splitthm t tt T =
   148   let fun repl lev t =
   149     if Envir.aeconv(incr_boundvars lev tt, t) then Bound lev
   150     else case t of
   151         (Abs (v, T2, t)) => Abs (v, T2, repl (lev+1) t)
   152       | (Bound i) => Bound (if i>=lev then i+1 else i)
   153       | (t1 $ t2) => (repl lev t1) $ (repl lev t2)
   154       | t => t
   155   in Abs("", T, repl 0 t) end;
   156 
   157 
   158 (* add all loose bound variables in t to list is *)
   159 fun add_lbnos t is = add_loose_bnos (t, 0, is);
   160 
   161 (* check if the innermost abstraction that needs to be removed
   162    has a body of type T; otherwise the expansion thm will fail later on
   163 *)
   164 fun type_test (T, lbnos, apsns) =
   165   let val (_, U: typ, _) = nth apsns (foldl1 Int.min lbnos)
   166   in T = U end;
   167 
   168 (*************************************************************************
   169    Create a "split_pack".
   170 
   171    thm   : the relevant split-theorem, i.e. P(...) == rhs , where P(...)
   172            is of the form
   173            P( Const(key,...) $ t_1 $ ... $ t_n )      (e.g. key = "if")
   174    T     : type of P(...)
   175    T'    : type of term to be scanned
   176    n     : number of arguments expected by Const(key,...)
   177    ts    : list of arguments actually found
   178    apsns : list of tuples of the form (T,U,pos), one tuple for each
   179            abstraction that is encountered on the way to the position where
   180            Const(key, ...) $ ...  occurs, where
   181            T   : type of the variable bound by the abstraction
   182            U   : type of the abstraction's body
   183            pos : "path" leading to the body of the abstraction
   184    pos   : "path" leading to the position where Const(key, ...) $ ...  occurs.
   185    TB    : type of  Const(key,...) $ t_1 $ ... $ t_n
   186    t     : the term Const(key,...) $ t_1 $ ... $ t_n
   187 
   188    A split pack is a tuple of the form
   189    (thm, apsns, pos, TB, tt)
   190    Note : apsns is reversed, so that the outermost quantifier's position
   191           comes first ! If the terms in ts don't contain variables bound
   192           by other than meta-quantifiers, apsns is empty, because no further
   193           lifting is required before applying the split-theorem.
   194 ******************************************************************************)
   195 
   196 fun mk_split_pack (thm, T: typ, T', n, ts, apsns, pos, TB, t) =
   197   if n > length ts then []
   198   else let val lev = length apsns
   199            val lbnos = fold add_lbnos (take n ts) []
   200            val flbnos = filter (fn i => i < lev) lbnos
   201            val tt = incr_boundvars (~lev) t
   202        in if null flbnos then
   203             if T = T' then [(thm,[],pos,TB,tt)] else []
   204           else if type_test(T,flbnos,apsns) then [(thm, rev apsns,pos,TB,tt)]
   205                else []
   206        end;
   207 
   208 
   209 (****************************************************************************
   210    Recursively scans term for occurences of Const(key,...) $ ...
   211    Returns a list of "split-packs" (one for each occurence of Const(key,...) )
   212 
   213    cmap : association list of split-theorems that should be tried.
   214           The elements have the format (key,(thm,T,n)) , where
   215           key : the theorem's key constant ( Const(key,...) $ ... )
   216           thm : the theorem itself
   217           T   : type of P( Const(key,...) $ ... )
   218           n   : number of arguments expected by Const(key,...)
   219    Ts   : types of parameters
   220    t    : the term to be scanned
   221 ******************************************************************************)
   222 
   223 (* Simplified first-order matching;
   224    assumes that all Vars in the pattern are distinct;
   225    see Pure/pattern.ML for the full version;
   226 *)
   227 local
   228   exception MATCH
   229 in
   230   fun typ_match thy (tyenv, TU) = Sign.typ_match thy TU tyenv
   231     handle Type.TYPE_MATCH => raise MATCH;
   232 
   233   fun fomatch thy args =
   234     let
   235       fun mtch tyinsts = fn
   236           (Ts, Var(_,T), t) =>
   237             typ_match thy (tyinsts, (T, fastype_of1(Ts,t)))
   238         | (_, Free (a,T), Free (b,U)) =>
   239             if a=b then typ_match thy (tyinsts,(T,U)) else raise MATCH
   240         | (_, Const (a,T), Const (b,U)) =>
   241             if a=b then typ_match thy (tyinsts,(T,U)) else raise MATCH
   242         | (_, Bound i, Bound j) =>
   243             if i=j then tyinsts else raise MATCH
   244         | (Ts, Abs(_,T,t), Abs(_,U,u)) =>
   245             mtch (typ_match thy (tyinsts,(T,U))) (U::Ts,t,u)
   246         | (Ts, f$t, g$u) =>
   247             mtch (mtch tyinsts (Ts,f,g)) (Ts, t, u)
   248         | _ => raise MATCH
   249     in (mtch Vartab.empty args; true) handle MATCH => false end;
   250 end;
   251 
   252 fun split_posns (cmap : (string * (typ * term * thm * typ * int) list) list) thy Ts t =
   253   let
   254     val T' = fastype_of1 (Ts, t);
   255     fun posns Ts pos apsns (Abs (_, T, t)) =
   256           let val U = fastype_of1 (T::Ts,t)
   257           in posns (T::Ts) (0::pos) ((T, U, pos)::apsns) t end
   258       | posns Ts pos apsns t =
   259           let
   260             val (h, ts) = strip_comb t
   261             fun iter t (i, a) = (i+1, (posns Ts (i::pos) apsns t) @ a);
   262             val a =
   263               case h of
   264                 Const(c, cT) =>
   265                   let fun find [] = []
   266                         | find ((gcT, pat, thm, T, n)::tups) =
   267                             let val t2 = list_comb (h, take n ts) in
   268                               if Sign.typ_instance thy (cT, gcT) andalso fomatch thy (Ts, pat, t2)
   269                               then mk_split_pack(thm,T,T',n,ts,apsns,pos,type_of1(Ts,t2),t2)
   270                               else find tups
   271                             end
   272                   in find (these (AList.lookup (op =) cmap c)) end
   273               | _ => []
   274           in snd (fold iter ts (0, a)) end
   275   in posns Ts [] [] t end;
   276 
   277 fun shorter ((_,ps,pos,_,_), (_,qs,qos,_,_)) =
   278   prod_ord (int_ord o pairself length) (order o pairself length)
   279     ((ps, pos), (qs, qos));
   280 
   281 
   282 (************************************************************
   283    call split_posns with appropriate parameters
   284 *************************************************************)
   285 
   286 fun select cmap state i =
   287   let
   288     val thy = Thm.theory_of_thm state
   289     val goal = term_of (Thm.cprem_of state i);
   290     val Ts = rev (map #2 (Logic.strip_params goal));
   291     val _ $ t $ _ = Logic.strip_assums_concl goal;
   292   in (Ts, t, sort shorter (split_posns cmap thy Ts t)) end;
   293 
   294 fun exported_split_posns cmap thy Ts t =
   295   sort shorter (split_posns cmap thy Ts t);
   296 
   297 (*************************************************************
   298    instantiate lift theorem
   299 
   300    if t is of the form
   301    ... ( Const(...,...) $ Abs( .... ) ) ...
   302    then
   303    P = %a.  ... ( Const(...,...) $ a ) ...
   304    where a has type T --> U
   305 
   306    Ts      : types of parameters
   307    t       : lefthand side of meta-equality in subgoal
   308              the split theorem is applied to (see cmap)
   309    T,U,pos : see mk_split_pack
   310    state   : current proof state
   311    i       : no. of subgoal
   312 **************************************************************)
   313 
   314 fun inst_lift Ts t (T, U, pos) state i =
   315   let
   316     val cert = cterm_of (Thm.theory_of_thm state);
   317     val (cntxt, u) = mk_cntxt t pos (T --> U);
   318     val trlift' = Thm.lift_rule (Thm.cprem_of state i)
   319       (Thm.rename_boundvars abs_lift u trlift);
   320     val (P, _) = strip_comb (fst (Logic.dest_equals
   321       (Logic.strip_assums_concl (Thm.prop_of trlift'))));
   322   in cterm_instantiate [(cert P, cert (abss Ts cntxt))] trlift'
   323   end;
   324 
   325 
   326 (*************************************************************
   327    instantiate split theorem
   328 
   329    Ts    : types of parameters
   330    t     : lefthand side of meta-equality in subgoal
   331            the split theorem is applied to (see cmap)
   332    tt    : the term  Const(key,..) $ ...
   333    thm   : the split theorem
   334    TB    : type of body of P(...)
   335    state : current proof state
   336    i     : number of subgoal
   337 **************************************************************)
   338 
   339 fun inst_split Ts t tt thm TB state i =
   340   let
   341     val thm' = Thm.lift_rule (Thm.cprem_of state i) thm;
   342     val (P, _) = strip_comb (fst (Logic.dest_equals
   343       (Logic.strip_assums_concl (Thm.prop_of thm'))));
   344     val cert = cterm_of (Thm.theory_of_thm state);
   345     val cntxt = mk_cntxt_splitthm t tt TB;
   346   in cterm_instantiate [(cert P, cert (abss Ts cntxt))] thm'
   347   end;
   348 
   349 
   350 (*****************************************************************************
   351    The split-tactic
   352 
   353    splits : list of split-theorems to be tried
   354    i      : number of subgoal the tactic should be applied to
   355 *****************************************************************************)
   356 
   357 fun split_tac [] i = no_tac
   358   | split_tac splits i =
   359   let val cmap = cmap_of_split_thms splits
   360       fun lift_tac Ts t p st = compose_tac (false, inst_lift Ts t p st i, 2) i st
   361       fun lift_split_tac state =
   362             let val (Ts, t, splits) = select cmap state i
   363             in case splits of
   364                  [] => no_tac state
   365                | (thm, apsns, pos, TB, tt)::_ =>
   366                    (case apsns of
   367                       [] => compose_tac (false, inst_split Ts t tt thm TB state i, 0) i state
   368                     | p::_ => EVERY [lift_tac Ts t p,
   369                                      rtac reflexive_thm (i+1),
   370                                      lift_split_tac] state)
   371             end
   372   in COND (has_fewer_prems i) no_tac
   373           (rtac meta_iffD i THEN lift_split_tac)
   374   end;
   375 
   376 in (split_tac, exported_split_posns) end;  (* mk_case_split_tac *)
   377 
   378 
   379 val (split_tac, split_posns) = mk_case_split_tac int_ord;
   380 
   381 val (split_inside_tac, _) = mk_case_split_tac (rev_order o int_ord);
   382 
   383 
   384 (*****************************************************************************
   385    The split-tactic for premises
   386 
   387    splits : list of split-theorems to be tried
   388 ****************************************************************************)
   389 fun split_asm_tac [] = K no_tac
   390   | split_asm_tac splits =
   391 
   392   let val cname_list = map (fst o fst o split_thm_info) splits;
   393       fun tac (t,i) =
   394           let val n = find_index (exists_Const (member (op =) cname_list o #1))
   395                                  (Logic.strip_assums_hyp t);
   396               fun first_prem_is_disj (Const ("==>", _) $ (Const (c, _)
   397                     $ (Const (s, _) $ _ $ _ )) $ _ ) = c = const_Trueprop andalso s = const_or
   398               |   first_prem_is_disj (Const("all",_)$Abs(_,_,t)) =
   399                                         first_prem_is_disj t
   400               |   first_prem_is_disj _ = false;
   401       (* does not work properly if the split variable is bound by a quantifier *)
   402               fun flat_prems_tac i = SUBGOAL (fn (t,i) =>
   403                            (if first_prem_is_disj t
   404                             then EVERY[etac Data.disjE i,rotate_tac ~1 i,
   405                                        rotate_tac ~1  (i+1),
   406                                        flat_prems_tac (i+1)]
   407                             else all_tac)
   408                            THEN REPEAT (eresolve_tac [Data.conjE,Data.exE] i)
   409                            THEN REPEAT (dresolve_tac [Data.notnotD]   i)) i;
   410           in if n<0 then  no_tac  else (DETERM (EVERY'
   411                 [rotate_tac n, etac Data.contrapos2,
   412                  split_tac splits,
   413                  rotate_tac ~1, etac Data.contrapos, rotate_tac ~1,
   414                  flat_prems_tac] i))
   415           end;
   416   in SUBGOAL tac
   417   end;
   418 
   419 fun gen_split_tac [] = K no_tac
   420   | gen_split_tac (split::splits) =
   421       let val (_,asm) = split_thm_info split
   422       in (if asm then split_asm_tac else split_tac) [split] ORELSE'
   423          gen_split_tac splits
   424       end;
   425 
   426 
   427 (** declare split rules **)
   428 
   429 (* add_split / del_split *)
   430 
   431 fun string_of_typ (Type (s, Ts)) =
   432       (if null Ts then "" else enclose "(" ")" (commas (map string_of_typ Ts))) ^ s
   433   | string_of_typ _ = "_";
   434 
   435 fun split_name (name, T) asm = "split " ^
   436   (if asm then "asm " else "") ^ name ^ " :: " ^ string_of_typ T;
   437 
   438 fun add_split split ctxt =
   439   let
   440     val (name, asm) = split_thm_info split
   441     val tac = (if asm then split_asm_tac else split_tac) [split]
   442   in Simplifier.addloop (ctxt, (split_name name asm, K tac)) end;
   443 
   444 fun del_split split ctxt =
   445   let val (name, asm) = split_thm_info split
   446   in Simplifier.delloop (ctxt, split_name name asm) end;
   447 
   448 
   449 (* attributes *)
   450 
   451 val splitN = "split";
   452 
   453 val split_add = Simplifier.attrib add_split;
   454 val split_del = Simplifier.attrib del_split;
   455 
   456 
   457 (* methods *)
   458 
   459 val split_modifiers =
   460  [Args.$$$ splitN -- Args.colon >> K ((I, split_add): Method.modifier),
   461   Args.$$$ splitN -- Args.add -- Args.colon >> K (I, split_add),
   462   Args.$$$ splitN -- Args.del -- Args.colon >> K (I, split_del)];
   463 
   464 
   465 (* theory setup *)
   466 
   467 val setup =
   468   Attrib.setup @{binding split}
   469     (Attrib.add_del split_add split_del) "declare case split rule" #>
   470   Method.setup @{binding split}
   471     (Attrib.thms >> (fn ths => K (SIMPLE_METHOD' (CHANGED_PROP o gen_split_tac ths))))
   472     "apply case split rule";
   473 
   474 end;