src/HOL/Tools/inductive_package.ML
changeset 12180 91c9f661b183
parent 12172 5e81c9d539f8
child 12259 3949e7aba298
equal deleted inserted replaced
12179:5b427479cc14 12180:91c9f661b183
    46   val inductive_cases: ((bstring * Args.src list) * string list) * Comment.text
    46   val inductive_cases: ((bstring * Args.src list) * string list) * Comment.text
    47     -> theory -> theory
    47     -> theory -> theory
    48   val inductive_cases_i: ((bstring * theory attribute list) * term list) * Comment.text
    48   val inductive_cases_i: ((bstring * theory attribute list) * term list) * Comment.text
    49     -> theory -> theory
    49     -> theory -> theory
    50   val add_inductive_i: bool -> bool -> bstring -> bool -> bool -> bool -> term list ->
    50   val add_inductive_i: bool -> bool -> bstring -> bool -> bool -> bool -> term list ->
    51     ((bstring * term) * theory attribute list) list ->
    51     ((bstring * term) * theory attribute list) list -> thm list -> theory -> theory *
    52       thm list -> thm list -> theory -> theory *
       
    53       {defs: thm list, elims: thm list, raw_induct: thm, induct: thm,
    52       {defs: thm list, elims: thm list, raw_induct: thm, induct: thm,
    54        intrs: thm list, mk_cases: string -> thm, mono: thm, unfold: thm}
    53        intrs: thm list, mk_cases: string -> thm, mono: thm, unfold: thm}
    55   val add_inductive: bool -> bool -> string list ->
    54   val add_inductive: bool -> bool -> string list ->
    56     ((bstring * string) * Args.src list) list -> (xstring * Args.src list) list ->
    55     ((bstring * string) * Args.src list) list -> (xstring * Args.src list) list ->
    57       (xstring * Args.src list) list -> theory -> theory *
    56     theory -> theory *
    58       {defs: thm list, elims: thm list, raw_induct: thm, induct: thm,
    57       {defs: thm list, elims: thm list, raw_induct: thm, induct: thm,
    59        intrs: thm list, mk_cases: string -> thm, mono: thm, unfold: thm}
    58        intrs: thm list, mk_cases: string -> thm, mono: thm, unfold: thm}
    60   val setup: (theory -> theory) list
    59   val setup: (theory -> theory) list
    61 end;
    60 end;
    62 
    61 
   483     (fn _ => [rtac monoI 1, REPEAT (ares_tac (flat (map mk_mono monos) @ get_monos thy) 1)]));
   482     (fn _ => [rtac monoI 1, REPEAT (ares_tac (flat (map mk_mono monos) @ get_monos thy) 1)]));
   484 
   483 
   485 
   484 
   486 (* prove introduction rules *)
   485 (* prove introduction rules *)
   487 
   486 
   488 fun prove_intrs coind mono fp_def intr_ts con_defs rec_sets_defs thy =
   487 fun prove_intrs coind mono fp_def intr_ts rec_sets_defs thy =
   489   let
   488   let
   490     val _ = clean_message "  Proving the introduction rules ...";
   489     val _ = clean_message "  Proving the introduction rules ...";
   491 
   490 
   492     val unfold = standard (mono RS (fp_def RS
   491     val unfold = standard (mono RS (fp_def RS
   493       (if coind then def_gfp_unfold else def_lfp_unfold)));
   492       (if coind then def_gfp_unfold else def_lfp_unfold)));
   506        EVERY1 (select_disj (length intr_ts) i),
   505        EVERY1 (select_disj (length intr_ts) i),
   507        (*Not ares_tac, since refl must be tried before any equality assumptions;
   506        (*Not ares_tac, since refl must be tried before any equality assumptions;
   508          backtracking may occur if the premises have extra variables!*)
   507          backtracking may occur if the premises have extra variables!*)
   509        DEPTH_SOLVE_1 (resolve_tac [refl, exI, conjI] 1 APPEND assume_tac 1),
   508        DEPTH_SOLVE_1 (resolve_tac [refl, exI, conjI] 1 APPEND assume_tac 1),
   510        (*Now solve the equations like Inl 0 = Inl ?b2*)
   509        (*Now solve the equations like Inl 0 = Inl ?b2*)
   511        rewrite_goals_tac con_defs,
       
   512        REPEAT (rtac refl 1)])
   510        REPEAT (rtac refl 1)])
   513       |> rulify) (1 upto (length intr_ts) ~~ intr_ts)
   511       |> rulify) (1 upto (length intr_ts) ~~ intr_ts)
   514 
   512 
   515   in (intrs, unfold) end;
   513   in (intrs, unfold) end;
   516 
   514 
   536         |> RuleCases.name cases)
   534         |> RuleCases.name cases)
   537   end;
   535   end;
   538 
   536 
   539 
   537 
   540 (* derivation of simplified elimination rules *)
   538 (* derivation of simplified elimination rules *)
   541 
       
   542 (*Applies freeness of the given constructors, which *must* be unfolded by
       
   543   the given defs.  Cannot simply use the local con_defs because con_defs=[]
       
   544   for inference systems. (??) *)
       
   545 
   539 
   546 local
   540 local
   547 
   541 
   548 (*cprop should have the form t:Si where Si is an inductive set*)
   542 (*cprop should have the form t:Si where Si is an inductive set*)
   549 val mk_cases_err = "mk_cases: proposition not of form \"t : S_i\"";
   543 val mk_cases_err = "mk_cases: proposition not of form \"t : S_i\"";
   690 fun cond_declare_consts declare_consts cs paramTs cnames =
   684 fun cond_declare_consts declare_consts cs paramTs cnames =
   691   if declare_consts then
   685   if declare_consts then
   692     Theory.add_consts_i (map (fn (c, n) => (n, paramTs ---> fastype_of c, NoSyn)) (cs ~~ cnames))
   686     Theory.add_consts_i (map (fn (c, n) => (n, paramTs ---> fastype_of c, NoSyn)) (cs ~~ cnames))
   693   else I;
   687   else I;
   694 
   688 
   695 fun mk_ind_def declare_consts alt_name coind cs intr_ts monos con_defs thy
   689 fun mk_ind_def declare_consts alt_name coind cs intr_ts monos thy
   696       params paramTs cTs cnames =
   690       params paramTs cTs cnames =
   697   let
   691   let
   698     val sumT = fold_bal (fn (T, U) => Type ("+", [T, U])) cTs;
   692     val sumT = fold_bal (fn (T, U) => Type ("+", [T, U])) cTs;
   699     val setT = HOLogic.mk_setT sumT;
   693     val setT = HOLogic.mk_setT sumT;
   700 
   694 
   753     val mono = prove_mono setT fp_fun monos thy'
   747     val mono = prove_mono setT fp_fun monos thy'
   754 
   748 
   755   in (thy', mono, fp_def, rec_sets_defs, rec_const, sumT) end;
   749   in (thy', mono, fp_def, rec_sets_defs, rec_const, sumT) end;
   756 
   750 
   757 fun add_ind_def verbose declare_consts alt_name coind no_elim no_ind cs
   751 fun add_ind_def verbose declare_consts alt_name coind no_elim no_ind cs
   758     intros monos con_defs thy params paramTs cTs cnames induct_cases =
   752     intros monos thy params paramTs cTs cnames induct_cases =
   759   let
   753   let
   760     val _ =
   754     val _ =
   761       if verbose then message ("Proofs for " ^ coind_prefix coind ^ "inductive set(s) " ^
   755       if verbose then message ("Proofs for " ^ coind_prefix coind ^ "inductive set(s) " ^
   762         commas_quote cnames) else ();
   756         commas_quote cnames) else ();
   763 
   757 
   764     val ((intr_names, intr_ts), intr_atts) = apfst split_list (split_list intros);
   758     val ((intr_names, intr_ts), intr_atts) = apfst split_list (split_list intros);
   765 
   759 
   766     val (thy1, mono, fp_def, rec_sets_defs, rec_const, sumT) =
   760     val (thy1, mono, fp_def, rec_sets_defs, rec_const, sumT) =
   767       mk_ind_def declare_consts alt_name coind cs intr_ts monos con_defs thy
   761       mk_ind_def declare_consts alt_name coind cs intr_ts monos thy
   768         params paramTs cTs cnames;
   762         params paramTs cTs cnames;
   769 
   763 
   770     val (intrs, unfold) = prove_intrs coind mono fp_def intr_ts con_defs
   764     val (intrs, unfold) = prove_intrs coind mono fp_def intr_ts rec_sets_defs thy1;
   771       rec_sets_defs thy1;
       
   772     val elims = if no_elim then [] else
   765     val elims = if no_elim then [] else
   773       prove_elims cs cTs params intr_ts intr_names unfold rec_sets_defs thy1;
   766       prove_elims cs cTs params intr_ts intr_names unfold rec_sets_defs thy1;
   774     val raw_induct = if no_ind then Drule.asm_rl else
   767     val raw_induct = if no_ind then Drule.asm_rl else
   775       if coind then standard (rule_by_tactic
   768       if coind then standard (rule_by_tactic
   776         (rewrite_tac [mk_meta_eq vimage_Un] THEN
   769         (rewrite_tac [mk_meta_eq vimage_Un] THEN
   810 fun try_term f msg sign t =
   803 fun try_term f msg sign t =
   811   (case Library.try f t of
   804   (case Library.try f t of
   812     Some x => x
   805     Some x => x
   813   | None => error (msg ^ Sign.string_of_term sign t));
   806   | None => error (msg ^ Sign.string_of_term sign t));
   814 
   807 
   815 fun add_inductive_i verbose declare_consts alt_name coind no_elim no_ind cs
   808 fun add_inductive_i verbose declare_consts alt_name coind no_elim no_ind cs pre_intros monos thy =
   816     pre_intros monos con_defs thy =
       
   817   let
   809   let
   818     val _ = Theory.requires thy "Inductive" (coind_prefix coind ^ "inductive definitions");
   810     val _ = Theory.requires thy "Inductive" (coind_prefix coind ^ "inductive definitions");
   819     val sign = Theory.sign_of thy;
   811     val sign = Theory.sign_of thy;
   820 
   812 
   821     (*parameters should agree for all mutually recursive components*)
   813     (*parameters should agree for all mutually recursive components*)
   835     val intros = map (check_rule save_sign cs) pre_intros;
   827     val intros = map (check_rule save_sign cs) pre_intros;
   836     val induct_cases = map (#1 o #1) intros;
   828     val induct_cases = map (#1 o #1) intros;
   837 
   829 
   838     val (thy1, result as {elims, induct, ...}) =
   830     val (thy1, result as {elims, induct, ...}) =
   839       add_ind_def verbose declare_consts alt_name coind no_elim no_ind cs intros monos
   831       add_ind_def verbose declare_consts alt_name coind no_elim no_ind cs intros monos
   840         con_defs thy params paramTs cTs cnames induct_cases;
   832         thy params paramTs cTs cnames induct_cases;
   841     val thy2 = thy1
   833     val thy2 = thy1
   842       |> put_inductives full_cnames ({names = full_cnames, coind = coind}, result)
   834       |> put_inductives full_cnames ({names = full_cnames, coind = coind}, result)
   843       |> add_cases_induct no_elim (no_ind orelse coind orelse length cs > 1)
   835       |> add_cases_induct no_elim (no_ind orelse coind orelse length cs > 1)
   844           full_cnames elims induct;
   836           full_cnames elims induct;
   845   in (thy2, result) end;
   837   in (thy2, result) end;
   846 
   838 
   847 fun add_inductive verbose coind c_strings intro_srcs raw_monos raw_con_defs thy =
   839 fun add_inductive verbose coind c_strings intro_srcs raw_monos thy =
   848   let
   840   let
   849     val sign = Theory.sign_of thy;
   841     val sign = Theory.sign_of thy;
   850     val cs = map (term_of o Thm.read_cterm sign o rpair HOLogic.termT) c_strings;
   842     val cs = map (term_of o Thm.read_cterm sign o rpair HOLogic.termT) c_strings;
   851 
   843 
   852     val intr_names = map (fst o fst) intro_srcs;
   844     val intr_names = map (fst o fst) intro_srcs;
   854       handle ERROR => error ("The error(s) above occurred for " ^ s);
   846       handle ERROR => error ("The error(s) above occurred for " ^ s);
   855     val intr_ts = map (Thm.term_of o read_rule o snd o fst) intro_srcs;
   847     val intr_ts = map (Thm.term_of o read_rule o snd o fst) intro_srcs;
   856     val intr_atts = map (map (Attrib.global_attribute thy) o snd) intro_srcs;
   848     val intr_atts = map (map (Attrib.global_attribute thy) o snd) intro_srcs;
   857     val (cs', intr_ts') = unify_consts sign cs intr_ts;
   849     val (cs', intr_ts') = unify_consts sign cs intr_ts;
   858 
   850 
   859     val (thy', (monos, con_defs)) = thy
   851     val (thy', monos) = thy |> IsarThy.apply_theorems raw_monos;
   860       |> IsarThy.apply_theorems raw_monos
       
   861       |>>> IsarThy.apply_theorems raw_con_defs;
       
   862   in
   852   in
   863     add_inductive_i verbose false "" coind false false cs'
   853     add_inductive_i verbose false "" coind false false cs'
   864       ((intr_names ~~ intr_ts') ~~ intr_atts) monos con_defs thy'
   854       ((intr_names ~~ intr_ts') ~~ intr_atts) monos thy'
   865   end;
   855   end;
   866 
   856 
   867 
   857 
   868 
   858 
   869 (** package setup **)
   859 (** package setup **)
   879 
   869 
   880 (* outer syntax *)
   870 (* outer syntax *)
   881 
   871 
   882 local structure P = OuterParse and K = OuterSyntax.Keyword in
   872 local structure P = OuterParse and K = OuterSyntax.Keyword in
   883 
   873 
   884 fun mk_ind coind (((sets, intrs), monos), con_defs) =
   874 fun mk_ind coind ((sets, intrs), monos) =
   885   #1 o add_inductive true coind sets (map P.triple_swap intrs) monos con_defs;
   875   #1 o add_inductive true coind sets (map P.triple_swap intrs) monos;
   886 
   876 
   887 fun ind_decl coind =
   877 fun ind_decl coind =
   888   (Scan.repeat1 P.term --| P.marg_comment) --
   878   (Scan.repeat1 P.term --| P.marg_comment) --
   889   (P.$$$ "intros" |--
   879   (P.$$$ "intros" |--
   890     P.!!! (Scan.repeat1 (P.opt_thm_name ":" -- P.prop --| P.marg_comment))) --
   880     P.!!! (Scan.repeat1 (P.opt_thm_name ":" -- P.prop --| P.marg_comment))) --
   891   Scan.optional (P.$$$ "monos" |-- P.!!! P.xthms1 --| P.marg_comment) [] --
   881   Scan.optional (P.$$$ "monos" |-- P.!!! P.xthms1 --| P.marg_comment) []
   892   Scan.optional (P.$$$ "con_defs" |-- P.!!! P.xthms1 --| P.marg_comment) []
       
   893   >> (Toplevel.theory o mk_ind coind);
   882   >> (Toplevel.theory o mk_ind coind);
   894 
   883 
   895 val inductiveP =
   884 val inductiveP =
   896   OuterSyntax.command "inductive" "define inductive sets" K.thy_decl (ind_decl false);
   885   OuterSyntax.command "inductive" "define inductive sets" K.thy_decl (ind_decl false);
   897 
   886 
   905 
   894 
   906 val inductive_casesP =
   895 val inductive_casesP =
   907   OuterSyntax.command "inductive_cases"
   896   OuterSyntax.command "inductive_cases"
   908     "create simplified instances of elimination rules (improper)" K.thy_script ind_cases;
   897     "create simplified instances of elimination rules (improper)" K.thy_script ind_cases;
   909 
   898 
   910 val _ = OuterSyntax.add_keywords ["intros", "monos", "con_defs"];
   899 val _ = OuterSyntax.add_keywords ["intros", "monos"];
   911 val _ = OuterSyntax.add_parsers [inductiveP, coinductiveP, inductive_casesP];
   900 val _ = OuterSyntax.add_parsers [inductiveP, coinductiveP, inductive_casesP];
   912 
   901 
   913 end;
   902 end;
   914 
   903 
   915 end;
   904 end;