src/HOL/Tools/inductive.ML
changeset 42361 23f352990944
parent 42358 b47d41d9f4b5
child 42364 8c674b3b8e44
equal deleted inserted replaced
42360:da8817d01e7c 42361:23f352990944
   147 val get_inductives = InductiveData.get o Context.Proof;
   147 val get_inductives = InductiveData.get o Context.Proof;
   148 
   148 
   149 fun print_inductives ctxt =
   149 fun print_inductives ctxt =
   150   let
   150   let
   151     val (tab, monos) = get_inductives ctxt;
   151     val (tab, monos) = get_inductives ctxt;
   152     val space = Consts.space_of (ProofContext.consts_of ctxt);
   152     val space = Consts.space_of (Proof_Context.consts_of ctxt);
   153   in
   153   in
   154     [Pretty.strs ("(co)inductives:" :: map #1 (Name_Space.extern_table ctxt (space, tab))),
   154     [Pretty.strs ("(co)inductives:" :: map #1 (Name_Space.extern_table ctxt (space, tab))),
   155      Pretty.big_list "monotonicity rules:" (map (Display.pretty_thm ctxt) monos)]
   155      Pretty.big_list "monotonicity rules:" (map (Display.pretty_thm ctxt) monos)]
   156     |> Pretty.chunks |> Pretty.writeln
   156     |> Pretty.chunks |> Pretty.writeln
   157   end;
   157   end;
   292     val params' = Term.variant_frees rule (Logic.strip_params rule);
   292     val params' = Term.variant_frees rule (Logic.strip_params rule);
   293     val frees = rev (map Free params');
   293     val frees = rev (map Free params');
   294     val concl = subst_bounds (frees, Logic.strip_assums_concl rule);
   294     val concl = subst_bounds (frees, Logic.strip_assums_concl rule);
   295     val prems = map (curry subst_bounds frees) (Logic.strip_assums_hyp rule);
   295     val prems = map (curry subst_bounds frees) (Logic.strip_assums_hyp rule);
   296     val rule' = Logic.list_implies (prems, concl);
   296     val rule' = Logic.list_implies (prems, concl);
   297     val aprems = map (atomize_term (ProofContext.theory_of ctxt)) prems;
   297     val aprems = map (atomize_term (Proof_Context.theory_of ctxt)) prems;
   298     val arule = list_all_free (params', Logic.list_implies (aprems, concl));
   298     val arule = list_all_free (params', Logic.list_implies (aprems, concl));
   299 
   299 
   300     fun check_ind err t = case dest_predicate cs params t of
   300     fun check_ind err t = case dest_predicate cs params t of
   301         NONE => err (bad_app ^
   301         NONE => err (bad_app ^
   302           commas (map (Syntax.string_of_term ctxt) params))
   302           commas (map (Syntax.string_of_term ctxt) params))
   373         rtac (unfold RS iffD2) 1,
   373         rtac (unfold RS iffD2) 1,
   374         EVERY1 (select_disj (length intr_ts) (i + 1)),
   374         EVERY1 (select_disj (length intr_ts) (i + 1)),
   375         (*Not ares_tac, since refl must be tried before any equality assumptions;
   375         (*Not ares_tac, since refl must be tried before any equality assumptions;
   376           backtracking may occur if the premises have extra variables!*)
   376           backtracking may occur if the premises have extra variables!*)
   377         DEPTH_SOLVE_1 (resolve_tac rules 1 APPEND assume_tac 1)])
   377         DEPTH_SOLVE_1 (resolve_tac rules 1 APPEND assume_tac 1)])
   378        |> singleton (ProofContext.export ctxt ctxt')) intr_ts
   378        |> singleton (Proof_Context.export ctxt ctxt')) intr_ts
   379 
   379 
   380   in (intrs, unfold) end;
   380   in (intrs, unfold) end;
   381 
   381 
   382 
   382 
   383 (* prove elimination rules *)
   383 (* prove elimination rules *)
   419              dtac (unfold RS iffD1) 1,
   419              dtac (unfold RS iffD1) 1,
   420              REPEAT (FIRSTGOAL (eresolve_tac rules1)),
   420              REPEAT (FIRSTGOAL (eresolve_tac rules1)),
   421              REPEAT (FIRSTGOAL (eresolve_tac rules2)),
   421              REPEAT (FIRSTGOAL (eresolve_tac rules2)),
   422              EVERY (map (fn prem =>
   422              EVERY (map (fn prem =>
   423                DEPTH_SOLVE_1 (ares_tac [rewrite_rule rec_preds_defs prem, conjI] 1)) (tl prems))])
   423                DEPTH_SOLVE_1 (ares_tac [rewrite_rule rec_preds_defs prem, conjI] 1)) (tl prems))])
   424           |> singleton (ProofContext.export ctxt'' ctxt'''),
   424           |> singleton (Proof_Context.export ctxt'' ctxt'''),
   425          map #2 c_intrs, length Ts)
   425          map #2 c_intrs, length Ts)
   426       end
   426       end
   427 
   427 
   428    in map prove_elim cs end;
   428    in map prove_elim cs end;
   429 
   429 
   485             let val (c_intrs', last_c_intr) = split_last c_intrs in
   485             let val (c_intrs', last_c_intr) = split_last c_intrs in
   486               EVERY (map (fn ci => etac @{thm disjE} 1 THEN prove_intr2 ci) c_intrs')
   486               EVERY (map (fn ci => etac @{thm disjE} 1 THEN prove_intr2 ci) c_intrs')
   487               THEN prove_intr2 last_c_intr
   487               THEN prove_intr2 last_c_intr
   488             end))
   488             end))
   489         |> rulify
   489         |> rulify
   490         |> singleton (ProofContext.export ctxt' ctxt'')
   490         |> singleton (Proof_Context.export ctxt' ctxt'')
   491       end;  
   491       end;  
   492   in
   492   in
   493     map2 prove_eq cs elims
   493     map2 prove_eq cs elims
   494   end;
   494   end;
   495   
   495   
   508 
   508 
   509 in
   509 in
   510 
   510 
   511 fun mk_cases ctxt prop =
   511 fun mk_cases ctxt prop =
   512   let
   512   let
   513     val thy = ProofContext.theory_of ctxt;
   513     val thy = Proof_Context.theory_of ctxt;
   514     val ss = simpset_of ctxt;
   514     val ss = simpset_of ctxt;
   515 
   515 
   516     fun err msg =
   516     fun err msg =
   517       error (Pretty.string_of (Pretty.block
   517       error (Pretty.string_of (Pretty.block
   518         [Pretty.str msg, Pretty.fbrk, Syntax.pretty_term ctxt prop]));
   518         [Pretty.str msg, Pretty.fbrk, Syntax.pretty_term ctxt prop]));
   534 
   534 
   535 (* inductive_cases *)
   535 (* inductive_cases *)
   536 
   536 
   537 fun gen_inductive_cases prep_att prep_prop args lthy =
   537 fun gen_inductive_cases prep_att prep_prop args lthy =
   538   let
   538   let
   539     val thy = ProofContext.theory_of lthy;
   539     val thy = Proof_Context.theory_of lthy;
   540     val facts = args |> Par_List.map (fn ((a, atts), props) =>
   540     val facts = args |> Par_List.map (fn ((a, atts), props) =>
   541       ((a, map (prep_att thy) atts),
   541       ((a, map (prep_att thy) atts),
   542         Par_List.map (Thm.no_attributes o single o mk_cases lthy o prep_prop lthy) props));
   542         Par_List.map (Thm.no_attributes o single o mk_cases lthy o prep_prop lthy) props));
   543   in lthy |> Local_Theory.notes facts |>> map snd end;
   543   in lthy |> Local_Theory.notes facts |>> map snd end;
   544 
   544 
   553       (fn (raw_props, fixes) => fn ctxt =>
   553       (fn (raw_props, fixes) => fn ctxt =>
   554         let
   554         let
   555           val (_, ctxt') = Variable.add_fixes fixes ctxt;
   555           val (_, ctxt') = Variable.add_fixes fixes ctxt;
   556           val props = Syntax.read_props ctxt' raw_props;
   556           val props = Syntax.read_props ctxt' raw_props;
   557           val ctxt'' = fold Variable.declare_term props ctxt';
   557           val ctxt'' = fold Variable.declare_term props ctxt';
   558           val rules = ProofContext.export ctxt'' ctxt (map (mk_cases ctxt'') props)
   558           val rules = Proof_Context.export ctxt'' ctxt (map (mk_cases ctxt'') props)
   559         in Method.erule 0 rules end))
   559         in Method.erule 0 rules end))
   560     "dynamic case analysis on predicates";
   560     "dynamic case analysis on predicates";
   561 
   561 
   562 (* derivation of simplified equation *)
   562 (* derivation of simplified equation *)
   563 
   563 
   564 fun mk_simp_eq ctxt prop =
   564 fun mk_simp_eq ctxt prop =
   565   let
   565   let
   566     val thy = ProofContext.theory_of ctxt
   566     val thy = Proof_Context.theory_of ctxt
   567     val ctxt' = Variable.auto_fixes prop ctxt
   567     val ctxt' = Variable.auto_fixes prop ctxt
   568     val lhs_of = fst o HOLogic.dest_eq o HOLogic.dest_Trueprop o Thm.prop_of
   568     val lhs_of = fst o HOLogic.dest_eq o HOLogic.dest_Trueprop o Thm.prop_of
   569     val substs = Item_Net.retrieve (Equation_Data.get (Context.Proof ctxt)) (HOLogic.dest_Trueprop prop) 
   569     val substs = Item_Net.retrieve (Equation_Data.get (Context.Proof ctxt)) (HOLogic.dest_Trueprop prop) 
   570       |> map_filter
   570       |> map_filter
   571         (fn eq => SOME (Pattern.match thy (lhs_of eq, HOLogic.dest_Trueprop prop)
   571         (fn eq => SOME (Pattern.match thy (lhs_of eq, HOLogic.dest_Trueprop prop)
   586 
   586 
   587 (* inductive simps *)
   587 (* inductive simps *)
   588 
   588 
   589 fun gen_inductive_simps prep_att prep_prop args lthy =
   589 fun gen_inductive_simps prep_att prep_prop args lthy =
   590   let
   590   let
   591     val thy = ProofContext.theory_of lthy;
   591     val thy = Proof_Context.theory_of lthy;
   592     val facts = args |> map (fn ((a, atts), props) =>
   592     val facts = args |> map (fn ((a, atts), props) =>
   593       ((a, map (prep_att thy) atts),
   593       ((a, map (prep_att thy) atts),
   594         map (Thm.no_attributes o single o mk_simp_eq lthy o prep_prop lthy) props));
   594         map (Thm.no_attributes o single o mk_simp_eq lthy o prep_prop lthy) props));
   595   in lthy |> Local_Theory.notes facts |>> map snd end;
   595   in lthy |> Local_Theory.notes facts |>> map snd end;
   596 
   596 
   601 
   601 
   602 fun prove_indrule quiet_mode cs argTs bs xs rec_const params intr_ts mono
   602 fun prove_indrule quiet_mode cs argTs bs xs rec_const params intr_ts mono
   603     fp_def rec_preds_defs ctxt ctxt''' =
   603     fp_def rec_preds_defs ctxt ctxt''' =
   604   let
   604   let
   605     val _ = clean_message quiet_mode "  Proving the induction rule ...";
   605     val _ = clean_message quiet_mode "  Proving the induction rule ...";
   606     val thy = ProofContext.theory_of ctxt;
   606     val thy = Proof_Context.theory_of ctxt;
   607 
   607 
   608     (* predicates for induction rule *)
   608     (* predicates for induction rule *)
   609 
   609 
   610     val (pnames, ctxt') = Variable.variant_fixes (mk_names "P" (length cs)) ctxt;
   610     val (pnames, ctxt') = Variable.variant_fixes (mk_names "P" (length cs)) ctxt;
   611     val preds = map2 (curry Free) pnames
   611     val preds = map2 (curry Free) pnames
   700             REPEAT (eresolve_tac [@{thm le_funE}, @{thm le_boolE}] 1),
   700             REPEAT (eresolve_tac [@{thm le_funE}, @{thm le_boolE}] 1),
   701             atac 1,
   701             atac 1,
   702             rewrite_goals_tac simp_thms',
   702             rewrite_goals_tac simp_thms',
   703             atac 1])])
   703             atac 1])])
   704 
   704 
   705   in singleton (ProofContext.export ctxt'' ctxt''') (induct RS lemma) end;
   705   in singleton (Proof_Context.export ctxt'' ctxt''') (induct RS lemma) end;
   706 
   706 
   707 
   707 
   708 
   708 
   709 (** specification of (co)inductive predicates **)
   709 (** specification of (co)inductive predicates **)
   710 
   710 
   777          ((Binding.empty, [Attrib.internal (K Nitpick_Unfolds.add)]),
   777          ((Binding.empty, [Attrib.internal (K Nitpick_Unfolds.add)]),
   778          fold_rev lambda params
   778          fold_rev lambda params
   779            (Const (fp_name, (predT --> predT) --> predT) $ fp_fun)))
   779            (Const (fp_name, (predT --> predT) --> predT) $ fp_fun)))
   780       ||> Local_Theory.restore_naming lthy;
   780       ||> Local_Theory.restore_naming lthy;
   781     val fp_def' = Simplifier.rewrite (HOL_basic_ss addsimps [fp_def])
   781     val fp_def' = Simplifier.rewrite (HOL_basic_ss addsimps [fp_def])
   782       (cterm_of (ProofContext.theory_of lthy') (list_comb (rec_const, params)));
   782       (cterm_of (Proof_Context.theory_of lthy') (list_comb (rec_const, params)));
   783     val specs =
   783     val specs =
   784       if length cs < 2 then []
   784       if length cs < 2 then []
   785       else
   785       else
   786         map_index (fn (i, (name_mx, c)) =>
   786         map_index (fn (i, (name_mx, c)) =>
   787           let
   787           let
   799 
   799 
   800     val (_, lthy''') = Variable.add_fixes (map (fst o dest_Free) params) lthy'';
   800     val (_, lthy''') = Variable.add_fixes (map (fst o dest_Free) params) lthy'';
   801     val mono = prove_mono quiet_mode skip_mono fork_mono predT fp_fun monos lthy''';
   801     val mono = prove_mono quiet_mode skip_mono fork_mono predT fp_fun monos lthy''';
   802     val (_, lthy'''') =
   802     val (_, lthy'''') =
   803       Local_Theory.note (apfst Binding.conceal Attrib.empty_binding,
   803       Local_Theory.note (apfst Binding.conceal Attrib.empty_binding,
   804         ProofContext.export lthy''' lthy'' [mono]) lthy'';
   804         Proof_Context.export lthy''' lthy'' [mono]) lthy'';
   805 
   805 
   806   in (lthy'''', lthy''', rec_name, mono, fp_def', map (#2 o #2) consts_defs,
   806   in (lthy'''', lthy''', rec_name, mono, fp_def', map (#2 o #2) consts_defs,
   807     list_comb (rec_const, params), preds, argTs, bs, xs)
   807     list_comb (rec_const, params), preds, argTs, bs, xs)
   808   end;
   808   end;
   809 
   809 
   901         prove_elims quiet_mode cs params intr_ts (map Binding.name_of intr_names)
   901         prove_elims quiet_mode cs params intr_ts (map Binding.name_of intr_names)
   902           unfold rec_preds_defs lthy2 lthy1;
   902           unfold rec_preds_defs lthy2 lthy1;
   903     val raw_induct = zero_var_indexes
   903     val raw_induct = zero_var_indexes
   904       (if no_ind then Drule.asm_rl
   904       (if no_ind then Drule.asm_rl
   905        else if coind then
   905        else if coind then
   906          singleton (ProofContext.export lthy2 lthy1)
   906          singleton (Proof_Context.export lthy2 lthy1)
   907            (rotate_prems ~1 (Object_Logic.rulify
   907            (rotate_prems ~1 (Object_Logic.rulify
   908              (fold_rule rec_preds_defs
   908              (fold_rule rec_preds_defs
   909                (rewrite_rule simp_thms'''
   909                (rewrite_rule simp_thms'''
   910                 (mono RS (fp_def RS @{thm def_coinduct}))))))
   910                 (mono RS (fp_def RS @{thm def_coinduct}))))))
   911        else
   911        else
   940 
   940 
   941 fun gen_add_inductive_i mk_def
   941 fun gen_add_inductive_i mk_def
   942     (flags as {quiet_mode, verbose, alt_name, coind, no_elim, no_ind, skip_mono, fork_mono})
   942     (flags as {quiet_mode, verbose, alt_name, coind, no_elim, no_ind, skip_mono, fork_mono})
   943     cnames_syn pnames spec monos lthy =
   943     cnames_syn pnames spec monos lthy =
   944   let
   944   let
   945     val thy = ProofContext.theory_of lthy;
   945     val thy = Proof_Context.theory_of lthy;
   946     val _ = Theory.requires thy "Inductive" (coind_prefix coind ^ "inductive definitions");
   946     val _ = Theory.requires thy "Inductive" (coind_prefix coind ^ "inductive definitions");
   947 
   947 
   948 
   948 
   949     (* abbrevs *)
   949     (* abbrevs *)
   950 
   950 
   977     val ps = map Free pnames;
   977     val ps = map Free pnames;
   978 
   978 
   979     val (_, ctxt2) = lthy |> Variable.add_fixes (map (Binding.name_of o fst o fst) cnames_syn');
   979     val (_, ctxt2) = lthy |> Variable.add_fixes (map (Binding.name_of o fst o fst) cnames_syn');
   980     val _ = map (fn abbr => Local_Defs.fixed_abbrev abbr ctxt2) abbrevs;
   980     val _ = map (fn abbr => Local_Defs.fixed_abbrev abbr ctxt2) abbrevs;
   981     val ctxt3 = ctxt2 |> fold (snd oo Local_Defs.fixed_abbrev) abbrevs;
   981     val ctxt3 = ctxt2 |> fold (snd oo Local_Defs.fixed_abbrev) abbrevs;
   982     val expand = Assumption.export_term ctxt3 lthy #> ProofContext.cert_term lthy;
   982     val expand = Assumption.export_term ctxt3 lthy #> Proof_Context.cert_term lthy;
   983 
   983 
   984     fun close_rule r = list_all_free (rev (fold_aterms
   984     fun close_rule r = list_all_free (rev (fold_aterms
   985       (fn t as Free (v as (s, _)) =>
   985       (fn t as Free (v as (s, _)) =>
   986           if Variable.is_fixed ctxt1 s orelse
   986           if Variable.is_fixed ctxt1 s orelse
   987             member (op =) ps t then I else insert (op =) v
   987             member (op =) ps t then I else insert (op =) v
   996   end;
   996   end;
   997 
   997 
   998 fun gen_add_inductive mk_def verbose coind cnames_syn pnames_syn intro_srcs raw_monos int lthy =
   998 fun gen_add_inductive mk_def verbose coind cnames_syn pnames_syn intro_srcs raw_monos int lthy =
   999   let
   999   let
  1000     val ((vars, intrs), _) = lthy
  1000     val ((vars, intrs), _) = lthy
  1001       |> ProofContext.set_mode ProofContext.mode_abbrev
  1001       |> Proof_Context.set_mode Proof_Context.mode_abbrev
  1002       |> Specification.read_spec (cnames_syn @ pnames_syn) intro_srcs;
  1002       |> Specification.read_spec (cnames_syn @ pnames_syn) intro_srcs;
  1003     val (cs, ps) = chop (length cnames_syn) vars;
  1003     val (cs, ps) = chop (length cnames_syn) vars;
  1004     val monos = Attrib.eval_thms lthy raw_monos;
  1004     val monos = Attrib.eval_thms lthy raw_monos;
  1005     val flags = {quiet_mode = false, verbose = verbose, alt_name = Binding.empty,
  1005     val flags = {quiet_mode = false, verbose = verbose, alt_name = Binding.empty,
  1006       coind = coind, no_elim = false, no_ind = false, skip_mono = false, fork_mono = not int};
  1006       coind = coind, no_elim = false, no_ind = false, skip_mono = false, fork_mono = not int};
  1018     val ctxt' = thy
  1018     val ctxt' = thy
  1019       |> Named_Target.theory_init
  1019       |> Named_Target.theory_init
  1020       |> add_inductive_i flags cnames_syn pnames pre_intros monos |> snd
  1020       |> add_inductive_i flags cnames_syn pnames pre_intros monos |> snd
  1021       |> Local_Theory.exit;
  1021       |> Local_Theory.exit;
  1022     val info = #2 (the_inductive ctxt' name);
  1022     val info = #2 (the_inductive ctxt' name);
  1023   in (info, ProofContext.theory_of ctxt') end;
  1023   in (info, Proof_Context.theory_of ctxt') end;
  1024 
  1024 
  1025 
  1025 
  1026 (* read off arities of inductive predicates from raw induction rule *)
  1026 (* read off arities of inductive predicates from raw induction rule *)
  1027 fun arities_of induct =
  1027 fun arities_of induct =
  1028   map (fn (_ $ t $ u) =>
  1028   map (fn (_ $ t $ u) =>