src/HOL/Tools/induct_method.ML
changeset 9299 c5cda71de65d
parent 9230 17ae63f82ad8
child 9313 b5a29408dc39
equal deleted inserted replaced
9298:7d9b562a750b 9299:c5cda71de65d
    24   val cases_set_local: string -> Proof.context attribute
    24   val cases_set_local: string -> Proof.context attribute
    25   val induct_type_global: string -> theory attribute
    25   val induct_type_global: string -> theory attribute
    26   val induct_set_global: string -> theory attribute
    26   val induct_set_global: string -> theory attribute
    27   val induct_type_local: string -> Proof.context attribute
    27   val induct_type_local: string -> Proof.context attribute
    28   val induct_set_local: string -> Proof.context attribute
    28   val induct_set_local: string -> Proof.context attribute
    29   val con_elim_tac: simpset -> tactic
    29   val simp_case_tac: bool -> simpset -> int -> tactic
    30   val con_elim_solved_tac: simpset -> tactic
       
    31   val setup: (theory -> theory) list
    30   val setup: (theory -> theory) list
    32 end;
    31 end;
    33 
    32 
    34 structure InductMethod: INDUCT_METHOD =
    33 structure InductMethod: INDUCT_METHOD =
    35 struct
    34 struct
   166 
   165 
   167 val elim_rls = [asm_rl, FalseE, refl_thin, conjE, exE, Pair_inject];
   166 val elim_rls = [asm_rl, FalseE, refl_thin, conjE, exE, Pair_inject];
   168 
   167 
   169 val elim_tac = REPEAT o Tactic.eresolve_tac elim_rls;
   168 val elim_tac = REPEAT o Tactic.eresolve_tac elim_rls;
   170 
   169 
   171 fun simp_case_tac ss = 
       
   172   EVERY' [elim_tac, asm_full_simp_tac ss, elim_tac, REPEAT o bound_hyp_subst_tac];
       
   173 
       
   174 in
   170 in
   175 
   171 
   176 fun con_elim_tac ss = ALLGOALS (simp_case_tac ss) THEN prune_params_tac;
   172 fun simp_case_tac solved ss i =
   177 
   173   EVERY' [elim_tac, asm_full_simp_tac ss, elim_tac, REPEAT o bound_hyp_subst_tac] i
   178 fun con_elim_solved_tac ss =
   174   THEN_MAYBE (if solved then no_tac else all_tac);
   179   ALLGOALS (fn i => TRY (simp_case_tac ss i THEN_MAYBE no_tac)) THEN prune_params_tac;
       
   180 
   175 
   181 end;
   176 end;
   182 
   177 
   183 
   178 
   184 
   179 
   199 fun cases_var thm =
   194 fun cases_var thm =
   200   (case try (hd o vars_of o hd o Logic.strip_assums_hyp o Library.last_elem o Thm.prems_of) thm of
   195   (case try (hd o vars_of o hd o Logic.strip_assums_hyp o Library.last_elem o Thm.prems_of) thm of
   201     None => raise THM ("Malformed cases rule", 0, [thm])
   196     None => raise THM ("Malformed cases rule", 0, [thm])
   202   | Some x => x);
   197   | Some x => x);
   203 
   198 
   204 fun simplify_cases ctxt =
   199 fun simplified_cases ctxt cases thm =
   205   Tactic.rule_by_tactic (con_elim_solved_tac (Simplifier.get_local_simpset ctxt));
   200   let
   206 
   201     val nprems = Thm.nprems_of thm;
   207 fun cases_tac (ctxt, (simplified, args)) facts =
   202     val opt_cases =
       
   203       Library.replicate (nprems - Int.min (nprems, length cases)) None @
       
   204       map Some (Library.take (nprems, cases));
       
   205 
       
   206     val tac = simp_case_tac true (Simplifier.get_local_simpset ctxt);
       
   207     fun simp ((i, c), (th, cs)) =
       
   208       (case try (Tactic.rule_by_tactic (tac i)) th of
       
   209         None => (th, None :: cs)
       
   210       | Some th' => (th', c :: cs));
       
   211 
       
   212     val (thm', opt_cases') = foldr simp (1 upto Thm.nprems_of thm ~~ opt_cases, (thm, []));
       
   213   in (thm', mapfilter I opt_cases') end;
       
   214 
       
   215 fun cases_tac (ctxt, ((simplified, opaque), args)) facts =
   208   let
   216   let
   209     val sg = ProofContext.sign_of ctxt;
   217     val sg = ProofContext.sign_of ctxt;
   210     val cert = Thm.cterm_of sg;
   218     val cert = Thm.cterm_of sg;
   211 
   219 
   212     fun inst_rule t thm =
   220     fun inst_rule t thm =
   213       Drule.cterm_instantiate [(cert (cases_var thm), cert t)] thm;
   221       Drule.cterm_instantiate [(cert (cases_var thm), cert t)] thm;
   214 
       
   215     val cond_simp = if simplified then simplify_cases ctxt else I;
       
   216 
   222 
   217     fun find_cases th =
   223     fun find_cases th =
   218       NetRules.may_unify (#2 (get_cases ctxt))
   224       NetRules.may_unify (#2 (get_cases ctxt))
   219         (Logic.strip_assums_concl (#prop (Thm.rep_thm th)));
   225         (Logic.strip_assums_concl (#prop (Thm.rep_thm th)));
   220 
   226 
   227               None => error ("No cases rule for type: " ^ quote name)
   233               None => error ("No cases rule for type: " ^ quote name)
   228             | Some thm => [(inst_rule t thm, RuleCases.get thm)])
   234             | Some thm => [(inst_rule t thm, RuleCases.get thm)])
   229           end
   235           end
   230       | ((None, None), th :: _) => map (RuleCases.add o #2) (find_cases th)
   236       | ((None, None), th :: _) => map (RuleCases.add o #2) (find_cases th)
   231       | ((Some t, None), th :: _) =>
   237       | ((Some t, None), th :: _) =>
   232           (case find_cases th of	(*may instantiate first rule only!*)
   238           (case find_cases th of        (*may instantiate first rule only!*)
   233             (_, thm) :: _ => [(inst_rule t thm, RuleCases.get thm)]
   239             (_, thm) :: _ => [(inst_rule t thm, RuleCases.get thm)]
   234           | [] => [])
   240           | [] => [])
   235       | ((None, Some thm), _) => [RuleCases.add thm]
   241       | ((None, Some thm), _) => [RuleCases.add thm]
   236       | ((Some t, Some thm), _) => [(inst_rule t thm, RuleCases.get thm)]);
   242       | ((Some t, Some thm), _) => [(inst_rule t thm, RuleCases.get thm)]);
   237 
   243 
       
   244     val cond_simp = if simplified then simplified_cases ctxt else rpair;
       
   245 
   238     fun prep_rule (thm, cases) =
   246     fun prep_rule (thm, cases) =
   239       Seq.map (rpair cases o cond_simp) (Method.multi_resolves facts [thm]);
   247       Seq.map (cond_simp cases) (Method.multi_resolves facts [thm]);
   240   in Method.resolveq_cases_tac (Seq.flat (Seq.map prep_rule (Seq.of_list rules))) end;
   248   in Method.resolveq_cases_tac opaque (Seq.flat (Seq.map prep_rule (Seq.of_list rules))) end;
   241 
   249 
   242 in
   250 in
   243 
   251 
   244 val cases_meth = Method.METHOD_CASES o (HEADGOAL oo cases_tac);
   252 val cases_meth = Method.METHOD_CASES o (HEADGOAL oo cases_tac);
   245 
   253 
   294         | [] => error "No rule given"
   302         | [] => error "No rule given"
   295         | bads => error ("Incompatible rules for " ^ commas_quote (map #1 bads)))
   303         | bads => error ("Incompatible rules for " ^ commas_quote (map #1 bads)))
   296       end;
   304       end;
   297 
   305 
   298 
   306 
   299 fun induct_tac (ctxt, (stripped, args)) facts =
   307 fun induct_tac (ctxt, ((stripped, opaque), args)) facts =
   300   let
   308   let
   301     val sg = ProofContext.sign_of ctxt;
   309     val sg = ProofContext.sign_of ctxt;
   302     val cert = Thm.cterm_of sg;
   310     val cert = Thm.cterm_of sg;
   303 
   311 
   304     fun prep_var (x, Some t) = Some (cert x, cert t)
   312     fun prep_var (x, Some t) = Some (cert x, cert t)
   328           let val thms = map (induct_rule ctxt o last_elem o mapfilter I) insts
   336           let val thms = map (induct_rule ctxt o last_elem o mapfilter I) insts
   329             handle Library.LIST _ => error "Unable to figure out type induction rule"
   337             handle Library.LIST _ => error "Unable to figure out type induction rule"
   330           in [(inst_rule insts (join_rules thms), RuleCases.get (#2 (hd thms)))] end
   338           in [(inst_rule insts (join_rules thms), RuleCases.get (#2 (hd thms)))] end
   331       | (([], None), th :: _) => map (RuleCases.add o #2) (find_induct th)
   339       | (([], None), th :: _) => map (RuleCases.add o #2) (find_induct th)
   332       | ((insts, None), th :: _) =>
   340       | ((insts, None), th :: _) =>
   333           (case find_induct th of	(*may instantiate first rule only!*)
   341           (case find_induct th of       (*may instantiate first rule only!*)
   334 	    (_, thm) :: _ => [(inst_rule insts thm, RuleCases.get thm)]
   342             (_, thm) :: _ => [(inst_rule insts thm, RuleCases.get thm)]
   335           | [] => [])
   343           | [] => [])
   336       | (([], Some thm), _) => [RuleCases.add thm]
   344       | (([], Some thm), _) => [RuleCases.add thm]
   337       | ((insts, Some thm), _) => [(inst_rule insts thm, RuleCases.get thm)]);
   345       | ((insts, Some thm), _) => [(inst_rule insts thm, RuleCases.get thm)]);
   338 
   346 
   339     fun prep_rule (thm, cases) =
   347     fun prep_rule (thm, cases) =
   340       Seq.map (rpair cases) (Method.multi_resolves facts [thm]);
   348       Seq.map (rpair cases) (Method.multi_resolves facts [thm]);
   341     val tac = Method.resolveq_cases_tac (Seq.flat (Seq.map prep_rule (Seq.of_list rules)));
   349     val tac = Method.resolveq_cases_tac opaque (Seq.flat (Seq.map prep_rule (Seq.of_list rules)));
   342   in
   350   in
   343     if stripped then tac THEN_ALL_NEW_CASES (REPEAT o Tactic.match_tac [impI, allI, ballI])
   351     if stripped then tac THEN_ALL_NEW_CASES (REPEAT o Tactic.match_tac [impI, allI, ballI])
   344     else tac
   352     else tac
   345   end;
   353   end;
   346 
   354 
   357 val casesN = "cases";
   365 val casesN = "cases";
   358 val inductN = "induct";
   366 val inductN = "induct";
   359 
   367 
   360 val simplifiedN = "simplified";
   368 val simplifiedN = "simplified";
   361 val strippedN = "stripped";
   369 val strippedN = "stripped";
       
   370 val opaqN = "opaque";
   362 
   371 
   363 val typeN = "type";
   372 val typeN = "type";
   364 val setN = "set";
   373 val setN = "set";
   365 val ruleN = "rule";
   374 val ruleN = "rule";
   366 
   375 
   411 fun mode name =
   420 fun mode name =
   412   Scan.lift (Scan.optional (Args.parens (Args.$$$ name) >> K true) false);
   421   Scan.lift (Scan.optional (Args.parens (Args.$$$ name) >> K true) false);
   413 
   422 
   414 in
   423 in
   415 
   424 
   416 val cases_args = Method.syntax (mode simplifiedN -- (Scan.option term -- Scan.option cases_rule));
   425 val cases_args = Method.syntax
       
   426   (mode simplifiedN -- mode opaqN -- (Scan.option term -- Scan.option cases_rule));
       
   427 
   417 val induct_args = Method.syntax
   428 val induct_args = Method.syntax
   418   (mode strippedN -- (Args.and_list (Scan.repeat term_dummy) -- Scan.option induct_rule));
   429   (mode strippedN -- mode opaqN -- (Args.and_list (Scan.repeat term_dummy) -- Scan.option induct_rule));
   419 
   430 
   420 end;
   431 end;
   421 
   432 
   422 
   433 
   423 
   434