added the new command inductive_cases to derive simplification equations for inductive predicates; added binding simps for general simplification equation
authorbulwahn
Wed Jul 07 08:25:21 2010 +0200 (2010-07-07)
changeset 37734489ac1ecb9f1
parent 37733 bf6c1216db43
child 37735 26e673df3fd0
added the new command inductive_cases to derive simplification equations for inductive predicates; added binding simps for general simplification equation
etc/isar-keywords.el
src/HOL/Tools/inductive.ML
src/HOL/Tools/inductive_set.ML
     1.1 --- a/etc/isar-keywords.el	Tue Jul 06 08:08:35 2010 -0700
     1.2 +++ b/etc/isar-keywords.el	Wed Jul 07 08:25:21 2010 +0200
     1.3 @@ -120,6 +120,7 @@
     1.4      "inductive"
     1.5      "inductive_cases"
     1.6      "inductive_set"
     1.7 +    "inductive_simps"
     1.8      "init_toplevel"
     1.9      "instance"
    1.10      "instantiation"
    1.11 @@ -550,7 +551,8 @@
    1.12      "use"))
    1.13  
    1.14  (defconst isar-keywords-theory-script
    1.15 -  '("inductive_cases"))
    1.16 +  '("inductive_cases"
    1.17 +    "inductive_simps"))
    1.18  
    1.19  (defconst isar-keywords-theory-goal
    1.20    '("ax_specification"
     2.1 --- a/src/HOL/Tools/inductive.ML	Tue Jul 06 08:08:35 2010 -0700
     2.2 +++ b/src/HOL/Tools/inductive.ML	Wed Jul 07 08:25:21 2010 +0200
     2.3 @@ -22,7 +22,7 @@
     2.4  sig
     2.5    type inductive_result =
     2.6      {preds: term list, elims: thm list, raw_induct: thm,
     2.7 -     induct: thm, inducts: thm list, intrs: thm list}
     2.8 +     induct: thm, inducts: thm list, intrs: thm list, eqs: thm list}
     2.9    val morph_result: morphism -> inductive_result -> inductive_result
    2.10    type inductive_info = {names: string list, coind: bool} * inductive_result
    2.11    val the_inductive: Proof.context -> string -> inductive_info
    2.12 @@ -73,7 +73,7 @@
    2.13      local_theory -> inductive_result * local_theory
    2.14    val declare_rules: binding -> bool -> bool -> string list -> term list ->
    2.15      thm list -> binding list -> Attrib.src list list -> (thm * string list * int) list ->
    2.16 -    thm -> local_theory -> thm list * thm list * thm * thm list * local_theory
    2.17 +    thm list -> thm -> local_theory -> thm list * thm list * thm list * thm * thm list * local_theory
    2.18    val add_ind_def: add_ind_def
    2.19    val gen_add_inductive_i: add_ind_def -> inductive_flags ->
    2.20      ((binding * typ) * mixfix) list -> (string * typ) list -> (Attrib.binding * term) list ->
    2.21 @@ -120,16 +120,16 @@
    2.22  
    2.23  type inductive_result =
    2.24    {preds: term list, elims: thm list, raw_induct: thm,
    2.25 -   induct: thm, inducts: thm list, intrs: thm list};
    2.26 +   induct: thm, inducts: thm list, intrs: thm list, eqs: thm list};
    2.27  
    2.28 -fun morph_result phi {preds, elims, raw_induct: thm, induct, inducts, intrs} =
    2.29 +fun morph_result phi {preds, elims, raw_induct: thm, induct, inducts, intrs, eqs} =
    2.30    let
    2.31      val term = Morphism.term phi;
    2.32      val thm = Morphism.thm phi;
    2.33      val fact = Morphism.fact phi;
    2.34    in
    2.35     {preds = map term preds, elims = fact elims, raw_induct = thm raw_induct,
    2.36 -    induct = thm induct, inducts = fact inducts, intrs = fact intrs}
    2.37 +    induct = thm induct, inducts = fact inducts, intrs = fact intrs, eqs = fact eqs}
    2.38    end;
    2.39  
    2.40  type inductive_info =
    2.41 @@ -244,6 +244,9 @@
    2.42    | mk_names a 1 = [a]
    2.43    | mk_names a n = map (fn i => a ^ string_of_int i) (1 upto n);
    2.44  
    2.45 +fun select_disj 1 1 = []
    2.46 +  | select_disj _ 1 = [rtac disjI1]
    2.47 +  | select_disj n i = (rtac disjI2)::(select_disj (n - 1) (i - 1));
    2.48  
    2.49  
    2.50  (** process rules **)
    2.51 @@ -347,10 +350,6 @@
    2.52        (mono RS (fp_def RS
    2.53          (if coind then @{thm def_gfp_unfold} else @{thm def_lfp_unfold})));
    2.54  
    2.55 -    fun select_disj 1 1 = []
    2.56 -      | select_disj _ 1 = [rtac disjI1]
    2.57 -      | select_disj n i = (rtac disjI2)::(select_disj (n - 1) (i - 1));
    2.58 -
    2.59      val rules = [refl, TrueI, notFalseI, exI, conjI];
    2.60  
    2.61      val intrs = map_index (fn (i, intr) =>
    2.62 @@ -361,7 +360,6 @@
    2.63          (*Not ares_tac, since refl must be tried before any equality assumptions;
    2.64            backtracking may occur if the premises have extra variables!*)
    2.65          DEPTH_SOLVE_1 (resolve_tac rules 1 APPEND assume_tac 1)])
    2.66 -       |> rulify
    2.67         |> singleton (ProofContext.export ctxt ctxt')) intr_ts
    2.68  
    2.69    in (intrs, unfold) end;
    2.70 @@ -408,14 +406,78 @@
    2.71               REPEAT (FIRSTGOAL (eresolve_tac rules2)),
    2.72               EVERY (map (fn prem =>
    2.73                 DEPTH_SOLVE_1 (ares_tac [rewrite_rule rec_preds_defs prem, conjI] 1)) (tl prems))])
    2.74 -          |> rulify
    2.75            |> singleton (ProofContext.export ctxt'' ctxt'''),
    2.76           map #2 c_intrs, length Ts)
    2.77        end
    2.78  
    2.79     in map prove_elim cs end;
    2.80  
    2.81 +(* prove simplification equations *)
    2.82  
    2.83 +fun prove_eqs quiet_mode cs params intr_ts intrs elims ctxt ctxt'' =
    2.84 +  let
    2.85 +    val _ = clean_message quiet_mode "  Proving the simplification rules ...";
    2.86 +    
    2.87 +    fun dest_intr r =
    2.88 +      (the (dest_predicate cs params (HOLogic.dest_Trueprop (Logic.strip_assums_concl r))),
    2.89 +       Logic.strip_assums_hyp r, Logic.strip_params r);
    2.90 +    val intr_ts' = map dest_intr intr_ts;
    2.91 +    fun prove_eq c elim =
    2.92 +      let
    2.93 +        val Ts = arg_types_of (length params) c;
    2.94 +        val (anames, ctxt') = Variable.variant_fixes (mk_names "a" (length Ts)) ctxt;
    2.95 +        val frees = map Free (anames ~~ Ts);
    2.96 +        val c_intrs = filter (equal c o #1 o #1 o #1) (intr_ts' ~~ intrs);
    2.97 +        fun mk_intr_conj (((_, _, us, _), ts, params'), _) =
    2.98 +          let
    2.99 +            fun list_ex ([], t) = t
   2.100 +              | list_ex ((a,T)::vars, t) =
   2.101 +                 (HOLogic.exists_const T) $ (Abs(a, T, list_ex(vars,t)));
   2.102 +            val conjs = map2 (curry HOLogic.mk_eq) frees us @ (map HOLogic.dest_Trueprop ts)
   2.103 +          in
   2.104 +            list_ex (params', if null conjs then @{term True} else foldr1 HOLogic.mk_conj conjs)
   2.105 +          end;
   2.106 +        val lhs = list_comb (c, params @ frees)
   2.107 +        val rhs =
   2.108 +          if null c_intrs then @{term False} else foldr1 HOLogic.mk_disj (map mk_intr_conj c_intrs)
   2.109 +        val eq = HOLogic.mk_Trueprop (HOLogic.mk_eq (lhs, rhs))
   2.110 +        fun prove_intr1 (i, _) = Subgoal.FOCUS_PREMS (fn {params, prems, ...} =>
   2.111 +            let
   2.112 +              val (prems', last_prem) = split_last prems
   2.113 +            in
   2.114 +              EVERY1 (select_disj (length c_intrs) (i + 1))
   2.115 +              THEN EVERY (replicate (length params) (rtac @{thm exI} 1))
   2.116 +              THEN EVERY (map (fn prem => (rtac @{thm conjI} 1 THEN rtac prem 1)) prems')
   2.117 +              THEN rtac last_prem 1
   2.118 +            end) ctxt' 1
   2.119 +        fun prove_intr2 (((_, _, us, _), ts, params'), intr) =
   2.120 +          EVERY (replicate (length params') (etac @{thm exE} 1))
   2.121 +          THEN EVERY (replicate (length ts + length us - 1) (etac @{thm conjE} 1))
   2.122 +          THEN Subgoal.FOCUS_PREMS (fn {params, prems, ...} =>
   2.123 +            let
   2.124 +              val (eqs, prems') = chop (length us) prems
   2.125 +              val rew_thms = map (fn th => th RS @{thm eq_reflection}) eqs
   2.126 +            in
   2.127 +              rewrite_goal_tac rew_thms 1
   2.128 +              THEN rtac intr 1
   2.129 +              THEN (EVERY (map (fn p => rtac p 1) prems'))              
   2.130 +            end) ctxt' 1 
   2.131 +      in
   2.132 +        Skip_Proof.prove ctxt' [] [] eq (fn {...} =>
   2.133 +          rtac @{thm iffI} 1 THEN etac (#1 elim) 1
   2.134 +          THEN EVERY (map_index prove_intr1 c_intrs)
   2.135 +          THEN (if null c_intrs then etac @{thm FalseE} 1 else
   2.136 +            let val (c_intrs', last_c_intr) = split_last c_intrs in
   2.137 +              EVERY (map (fn ci => etac @{thm disjE} 1 THEN prove_intr2 ci) c_intrs')
   2.138 +              THEN prove_intr2 last_c_intr
   2.139 +            end))
   2.140 +        |> rulify
   2.141 +        |> singleton (ProofContext.export ctxt' ctxt'')
   2.142 +      end;  
   2.143 +  in
   2.144 +    map2 prove_eq cs elims
   2.145 +  end;
   2.146 +  
   2.147  (* derivation of simplified elimination rules *)
   2.148  
   2.149  local
   2.150 @@ -455,7 +517,6 @@
   2.151  
   2.152  end;
   2.153  
   2.154 -
   2.155  (* inductive_cases *)
   2.156  
   2.157  fun gen_inductive_cases prep_att prep_prop args lthy =
   2.158 @@ -483,7 +544,37 @@
   2.159          in Method.erule 0 rules end))
   2.160      "dynamic case analysis on predicates";
   2.161  
   2.162 +(* derivation of simplified equation *)
   2.163  
   2.164 +fun mk_simp_eq ctxt prop =
   2.165 +  let
   2.166 +    val (c, args) = strip_comb (HOLogic.dest_Trueprop prop)
   2.167 +    val ctxt' = Variable.auto_fixes prop ctxt
   2.168 +    val cname = fst (dest_Const c)
   2.169 +    val info = the_inductive ctxt cname
   2.170 +    val eq = nth (#eqs (snd info)) (find_index (fn c => c = cname) (#names (fst info)))
   2.171 +    val (_, args') = strip_comb (fst (HOLogic.dest_eq (HOLogic.dest_Trueprop (Thm.prop_of eq))))
   2.172 +    val certify = cterm_of (ProofContext.theory_of ctxt)
   2.173 +  in
   2.174 +    cterm_instantiate (map (pairself certify) (args' ~~ args)) eq
   2.175 +    |> Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv
   2.176 +      (Simplifier.full_rewrite (simpset_of ctxt))))
   2.177 +    |> singleton (Variable.export ctxt' ctxt)
   2.178 +  end
   2.179 +
   2.180 +(* inductive simps *)
   2.181 +
   2.182 +fun gen_inductive_simps prep_att prep_prop args lthy =
   2.183 +  let
   2.184 +    val thy = ProofContext.theory_of lthy;
   2.185 +    val facts = args |> map (fn ((a, atts), props) =>
   2.186 +      ((a, map (prep_att thy) atts),
   2.187 +        map (Thm.no_attributes o single o mk_simp_eq lthy o prep_prop lthy) props));
   2.188 +  in lthy |> Local_Theory.notes facts |>> map snd end;
   2.189 +
   2.190 +val inductive_simps = gen_inductive_simps Attrib.intern_src Syntax.read_prop;
   2.191 +val inductive_simps_i = gen_inductive_simps (K I) Syntax.check_prop;
   2.192 +    
   2.193  (* prove induction rule *)
   2.194  
   2.195  fun prove_indrule quiet_mode cs argTs bs xs rec_const params intr_ts mono
   2.196 @@ -697,7 +788,7 @@
   2.197    end;
   2.198  
   2.199  fun declare_rules rec_binding coind no_ind cnames
   2.200 -    preds intrs intr_bindings intr_atts elims raw_induct lthy =
   2.201 +    preds intrs intr_bindings intr_atts elims eqs raw_induct lthy =
   2.202    let
   2.203      val rec_name = Binding.name_of rec_binding;
   2.204      fun rec_qualified qualified = Binding.qualify qualified rec_name;
   2.205 @@ -737,18 +828,23 @@
   2.206          ((rec_qualified true (Binding.name (coind_prefix coind ^ "induct")),
   2.207            map (Attrib.internal o K) (#2 induct)), [rulify (#1 induct)]);
   2.208  
   2.209 -    val (inducts, lthy3) =
   2.210 -      if no_ind orelse coind then ([], lthy2)
   2.211 +    val (eqs', lthy3) = lthy2 |> 
   2.212 +      fold_map (fn (name, eq) => Local_Theory.note
   2.213 +          ((Binding.qualify true (Long_Name.base_name name) (Binding.name "simps"), []), [eq])
   2.214 +          #> apfst (hd o snd))
   2.215 +        (if null eqs then [] else (cnames ~~ eqs))
   2.216 +    val (inducts, lthy4) =
   2.217 +      if no_ind orelse coind then ([], lthy3)
   2.218        else
   2.219 -        let val inducts = cnames ~~ Project_Rule.projects lthy2 (1 upto length cnames) induct' in
   2.220 -          lthy2 |>
   2.221 +        let val inducts = cnames ~~ Project_Rule.projects lthy3 (1 upto length cnames) induct' in
   2.222 +          lthy3 |>
   2.223            Local_Theory.notes [((rec_qualified true (Binding.name "inducts"), []),
   2.224              inducts |> map (fn (name, th) => ([th],
   2.225                [Attrib.internal (K ind_case_names),
   2.226                 Attrib.internal (K (Rule_Cases.consumes 1)),
   2.227                 Attrib.internal (K (Induct.induct_pred name))])))] |>> snd o hd
   2.228          end;
   2.229 -  in (intrs', elims', induct', inducts, lthy3) end;
   2.230 +  in (intrs', elims', eqs', induct', inducts, lthy4) end;
   2.231  
   2.232  type inductive_flags =
   2.233    {quiet_mode: bool, verbose: bool, alt_name: binding, coind: bool,
   2.234 @@ -794,17 +890,23 @@
   2.235         else
   2.236           prove_indrule quiet_mode cs argTs bs xs rec_const params intr_ts mono fp_def
   2.237             rec_preds_defs lthy2 lthy1);
   2.238 +    val eqs =
   2.239 +      if no_elim then [] else prove_eqs quiet_mode cs params intr_ts intrs elims lthy2 lthy1
   2.240  
   2.241 -    val (intrs', elims', induct, inducts, lthy3) = declare_rules rec_name coind no_ind
   2.242 -      cnames preds intrs intr_names intr_atts elims raw_induct lthy1;
   2.243 +    val elims' = map (fn (th, ns, i) => (rulify th, ns, i)) elims
   2.244 +    val intrs' = map rulify intrs
   2.245 +
   2.246 +    val (intrs'', elims'', eqs', induct, inducts, lthy3) = declare_rules rec_name coind no_ind
   2.247 +      cnames preds intrs' intr_names intr_atts elims' eqs raw_induct lthy1;
   2.248  
   2.249      val result =
   2.250        {preds = preds,
   2.251 -       intrs = intrs',
   2.252 -       elims = elims',
   2.253 +       intrs = intrs'',
   2.254 +       elims = elims'',
   2.255         raw_induct = rulify raw_induct,
   2.256         induct = induct,
   2.257 -       inducts = inducts};
   2.258 +       inducts = inducts,
   2.259 +       eqs = eqs'};
   2.260  
   2.261      val lthy4 = lthy3
   2.262        |> Local_Theory.declaration false (fn phi =>
   2.263 @@ -993,4 +1095,9 @@
   2.264      "create simplified instances of elimination rules (improper)" Keyword.thy_script
   2.265      (Parse.and_list1 Parse_Spec.specs >> (snd oo inductive_cases));
   2.266  
   2.267 +val _ =
   2.268 +  Outer_Syntax.local_theory "inductive_simps"
   2.269 +    "create simplification rules for inductive predicates" Keyword.thy_script
   2.270 +    (Parse.and_list1 Parse_Spec.specs >> (snd oo inductive_simps));
   2.271 +
   2.272  end;
     3.1 --- a/src/HOL/Tools/inductive_set.ML	Tue Jul 06 08:08:35 2010 -0700
     3.2 +++ b/src/HOL/Tools/inductive_set.ML	Wed Jul 07 08:25:21 2010 +0200
     3.3 @@ -520,16 +520,17 @@
     3.4      val cnames = map (Local_Theory.full_name lthy3 o #1) cnames_syn;  (* FIXME *)
     3.5      val (intr_names, intr_atts) = split_list (map fst intros);
     3.6      val raw_induct' = to_set [] (Context.Proof lthy3) raw_induct;
     3.7 -    val (intrs', elims', induct, inducts, lthy4) =
     3.8 +    val eqs = [] (* TODO: define equations *)
     3.9 +    val (intrs', elims', eqs', induct, inducts, lthy4) =
    3.10        Inductive.declare_rules rec_name coind no_ind cnames (map fst defs)
    3.11          (map (to_set [] (Context.Proof lthy3)) intrs) intr_names intr_atts
    3.12          (map (fn th => (to_set [] (Context.Proof lthy3) th,
    3.13             map fst (fst (Rule_Cases.get th)),
    3.14             Rule_Cases.get_constraints th)) elims)
    3.15 -        raw_induct' lthy3;
    3.16 +        eqs raw_induct' lthy3;
    3.17    in
    3.18      ({intrs = intrs', elims = elims', induct = induct, inducts = inducts,
    3.19 -      raw_induct = raw_induct', preds = map fst defs},
    3.20 +      raw_induct = raw_induct', preds = map fst defs, eqs = eqs'},
    3.21       lthy4)
    3.22    end;
    3.23