src/HOL/Tools/inductive_package.ML
changeset 26477 ecf06644f6cb
parent 26336 a0e2b706ce73
child 26534 a2cb4de2a1aa
equal deleted inserted replaced
26476:4e78281b3273 26477:ecf06644f6cb
    19   Pj, Pk are two of the predicates being defined in mutual recursion
    19   Pj, Pk are two of the predicates being defined in mutual recursion
    20 *)
    20 *)
    21 
    21 
    22 signature BASIC_INDUCTIVE_PACKAGE =
    22 signature BASIC_INDUCTIVE_PACKAGE =
    23 sig
    23 sig
    24   val quiet_mode: bool ref
       
    25   type inductive_result
    24   type inductive_result
    26   val morph_result: morphism -> inductive_result -> inductive_result
    25   val morph_result: morphism -> inductive_result -> inductive_result
    27   type inductive_info
    26   type inductive_info
    28   val the_inductive: Proof.context -> string -> inductive_info
    27   val the_inductive: Proof.context -> string -> inductive_info
    29   val print_inductives: Proof.context -> unit
    28   val print_inductives: Proof.context -> unit
    37   val inductive_cases: ((bstring * Attrib.src list) * string list) list ->
    36   val inductive_cases: ((bstring * Attrib.src list) * string list) list ->
    38     Proof.context -> thm list list * local_theory
    37     Proof.context -> thm list list * local_theory
    39   val inductive_cases_i: ((bstring * Attrib.src list) * term list) list ->
    38   val inductive_cases_i: ((bstring * Attrib.src list) * term list) list ->
    40     Proof.context -> thm list list * local_theory
    39     Proof.context -> thm list list * local_theory
    41   val add_inductive_i:
    40   val add_inductive_i:
    42     {verbose: bool, kind: string, alt_name: bstring, coind: bool, no_elim: bool, no_ind: bool} ->
    41     {quiet_mode: bool, verbose: bool, kind: string, alt_name: bstring,
       
    42       coind: bool, no_elim: bool, no_ind: bool} ->
    43     ((string * typ) * mixfix) list ->
    43     ((string * typ) * mixfix) list ->
    44     (string * typ) list -> ((bstring * Attrib.src list) * term) list -> thm list ->
    44     (string * typ) list -> ((bstring * Attrib.src list) * term) list -> thm list ->
    45       local_theory -> inductive_result * local_theory
    45       local_theory -> inductive_result * local_theory
    46   val add_inductive: bool -> bool -> (string * string option * mixfix) list ->
    46   val add_inductive: bool -> bool -> (string * string option * mixfix) list ->
    47     (string * string option * mixfix) list ->
    47     (string * string option * mixfix) list ->
    48     ((bstring * Attrib.src list) * string) list -> (Facts.ref * Attrib.src list) list ->
    48     ((bstring * Attrib.src list) * string) list -> (Facts.ref * Attrib.src list) list ->
    49     local_theory -> inductive_result * local_theory
    49     local_theory -> inductive_result * local_theory
    50   val add_inductive_global: string ->
    50   val add_inductive_global: string ->
    51     {verbose: bool, kind: string, alt_name: bstring, coind: bool, no_elim: bool, no_ind: bool} ->
    51     {quiet_mode: bool, verbose: bool, kind: string, alt_name: bstring,
       
    52       coind: bool, no_elim: bool, no_ind: bool} ->
    52     ((string * typ) * mixfix) list -> (string * typ) list ->
    53     ((string * typ) * mixfix) list -> (string * typ) list ->
    53     ((bstring * Attrib.src list) * term) list -> thm list -> theory -> inductive_result * theory
    54     ((bstring * Attrib.src list) * term) list -> thm list -> theory -> inductive_result * theory
    54   val arities_of: thm -> (string * int) list
    55   val arities_of: thm -> (string * int) list
    55   val params_of: thm -> term list
    56   val params_of: thm -> term list
    56   val partition_rules: thm -> thm list -> (string * thm list) list
    57   val partition_rules: thm -> thm list -> (string * thm list) list
    67   val declare_rules: string -> bstring -> bool -> bool -> string list ->
    68   val declare_rules: string -> bstring -> bool -> bool -> string list ->
    68     thm list -> bstring list -> Attrib.src list list -> (thm * string list) list ->
    69     thm list -> bstring list -> Attrib.src list list -> (thm * string list) list ->
    69     thm -> local_theory -> thm list * thm list * thm * local_theory
    70     thm -> local_theory -> thm list * thm list * thm * local_theory
    70   val add_ind_def: add_ind_def
    71   val add_ind_def: add_ind_def
    71   val gen_add_inductive_i: add_ind_def ->
    72   val gen_add_inductive_i: add_ind_def ->
    72     {verbose: bool, kind: string, alt_name: bstring, coind: bool, no_elim: bool, no_ind: bool} ->
    73     {quiet_mode: bool, verbose: bool, kind: string, alt_name: bstring,
       
    74       coind: bool, no_elim: bool, no_ind: bool} ->
    73     ((string * typ) * mixfix) list ->
    75     ((string * typ) * mixfix) list ->
    74     (string * typ) list -> ((bstring * Attrib.src list) * term) list -> thm list ->
    76     (string * typ) list -> ((bstring * Attrib.src list) * term) list -> thm list ->
    75       local_theory -> inductive_result * local_theory
    77       local_theory -> inductive_result * local_theory
    76   val gen_add_inductive: add_ind_def ->
    78   val gen_add_inductive: add_ind_def ->
    77     bool -> bool -> (string * string option * mixfix) list ->
    79     bool -> bool -> (string * string option * mixfix) list ->
   190 
   192 
   191 
   193 
   192 
   194 
   193 (** misc utilities **)
   195 (** misc utilities **)
   194 
   196 
   195 val quiet_mode = ref false;
   197 fun message quiet_mode s = if quiet_mode then () else writeln s;
   196 fun message s = if ! quiet_mode then () else writeln s;
   198 fun clean_message quiet_mode s = if ! quick_and_dirty then () else message quiet_mode s;
   197 fun clean_message s = if ! quick_and_dirty then () else message s;
       
   198 
   199 
   199 fun coind_prefix true = "co"
   200 fun coind_prefix true = "co"
   200   | coind_prefix false = "";
   201   | coind_prefix false = "";
   201 
   202 
   202 fun log (b:int) m n = if m >= n then 0 else 1 + log b (b * m) n;
   203 fun log (b:int) m n = if m >= n then 0 else 1 + log b (b * m) n;
   314 
   315 
   315 (** proofs for (co)inductive predicates **)
   316 (** proofs for (co)inductive predicates **)
   316 
   317 
   317 (* prove monotonicity -- NOT subject to quick_and_dirty! *)
   318 (* prove monotonicity -- NOT subject to quick_and_dirty! *)
   318 
   319 
   319 fun prove_mono predT fp_fun monos ctxt =
   320 fun prove_mono quiet_mode predT fp_fun monos ctxt =
   320  (message "  Proving monotonicity ...";
   321  (message quiet_mode "  Proving monotonicity ...";
   321   Goal.prove ctxt [] []   (*NO quick_and_dirty here!*)
   322   Goal.prove ctxt [] []   (*NO quick_and_dirty here!*)
   322     (HOLogic.mk_Trueprop
   323     (HOLogic.mk_Trueprop
   323       (Const (@{const_name Orderings.mono}, (predT --> predT) --> HOLogic.boolT) $ fp_fun))
   324       (Const (@{const_name Orderings.mono}, (predT --> predT) --> HOLogic.boolT) $ fp_fun))
   324     (fn _ => EVERY [rtac @{thm monoI} 1,
   325     (fn _ => EVERY [rtac @{thm monoI} 1,
   325       REPEAT (resolve_tac [le_funI, le_boolI'] 1),
   326       REPEAT (resolve_tac [le_funI, le_boolI'] 1),
   329          etac le_funE 1, dtac le_boolD 1])]));
   330          etac le_funE 1, dtac le_boolD 1])]));
   330 
   331 
   331 
   332 
   332 (* prove introduction rules *)
   333 (* prove introduction rules *)
   333 
   334 
   334 fun prove_intrs coind mono fp_def k params intr_ts rec_preds_defs ctxt =
   335 fun prove_intrs quiet_mode coind mono fp_def k params intr_ts rec_preds_defs ctxt =
   335   let
   336   let
   336     val _ = clean_message "  Proving the introduction rules ...";
   337     val _ = clean_message quiet_mode "  Proving the introduction rules ...";
   337 
   338 
   338     val unfold = funpow k (fn th => th RS fun_cong)
   339     val unfold = funpow k (fn th => th RS fun_cong)
   339       (mono RS (fp_def RS
   340       (mono RS (fp_def RS
   340         (if coind then def_gfp_unfold else def_lfp_unfold)));
   341         (if coind then def_gfp_unfold else def_lfp_unfold)));
   341 
   342 
   357   in (intrs, unfold) end;
   358   in (intrs, unfold) end;
   358 
   359 
   359 
   360 
   360 (* prove elimination rules *)
   361 (* prove elimination rules *)
   361 
   362 
   362 fun prove_elims cs params intr_ts intr_names unfold rec_preds_defs ctxt =
   363 fun prove_elims quiet_mode cs params intr_ts intr_names unfold rec_preds_defs ctxt =
   363   let
   364   let
   364     val _ = clean_message "  Proving the elimination rules ...";
   365     val _ = clean_message quiet_mode "  Proving the elimination rules ...";
   365 
   366 
   366     val ([pname], ctxt') = ctxt |>
   367     val ([pname], ctxt') = ctxt |>
   367       Variable.add_fixes (map (fst o dest_Free) params) |> snd |>
   368       Variable.add_fixes (map (fst o dest_Free) params) |> snd |>
   368       Variable.variant_fixes ["P"];
   369       Variable.variant_fixes ["P"];
   369     val P = HOLogic.mk_Trueprop (Free (pname, HOLogic.boolT));
   370     val P = HOLogic.mk_Trueprop (Free (pname, HOLogic.boolT));
   474 
   475 
   475 
   476 
   476 
   477 
   477 (* prove induction rule *)
   478 (* prove induction rule *)
   478 
   479 
   479 fun prove_indrule cs argTs bs xs rec_const params intr_ts mono
   480 fun prove_indrule quiet_mode cs argTs bs xs rec_const params intr_ts mono
   480     fp_def rec_preds_defs ctxt =
   481     fp_def rec_preds_defs ctxt =
   481   let
   482   let
   482     val _ = clean_message "  Proving the induction rule ...";
   483     val _ = clean_message quiet_mode "  Proving the induction rule ...";
   483     val thy = ProofContext.theory_of ctxt;
   484     val thy = ProofContext.theory_of ctxt;
   484 
   485 
   485     (* predicates for induction rule *)
   486     (* predicates for induction rule *)
   486 
   487 
   487     val (pnames, ctxt') = ctxt |>
   488     val (pnames, ctxt') = ctxt |>
   583 
   584 
   584 
   585 
   585 
   586 
   586 (** specification of (co)inductive predicates **)
   587 (** specification of (co)inductive predicates **)
   587 
   588 
   588 fun mk_ind_def alt_name coind cs intr_ts monos params cnames_syn ctxt =
   589 fun mk_ind_def quiet_mode alt_name coind cs intr_ts monos params cnames_syn ctxt =
   589   let
   590   let
   590     val fp_name = if coind then @{const_name Inductive.gfp} else @{const_name Inductive.lfp};
   591     val fp_name = if coind then @{const_name Inductive.gfp} else @{const_name Inductive.lfp};
   591 
   592 
   592     val argTs = fold (fn c => fn Ts => Ts @
   593     val argTs = fold (fn c => fn Ts => Ts @
   593       (List.drop (binder_types (fastype_of c), length params) \\ Ts)) cs [];
   594       (List.drop (binder_types (fastype_of c), length params) \\ Ts)) cs [];
   661               make_args argTs (xs ~~ Ts)))))
   662               make_args argTs (xs ~~ Ts)))))
   662         end) (cnames_syn ~~ cs);
   663         end) (cnames_syn ~~ cs);
   663     val (consts_defs, ctxt'') = fold_map (LocalTheory.define Thm.internalK) specs ctxt';
   664     val (consts_defs, ctxt'') = fold_map (LocalTheory.define Thm.internalK) specs ctxt';
   664     val preds = (case cs of [_] => [rec_const] | _ => map #1 consts_defs);
   665     val preds = (case cs of [_] => [rec_const] | _ => map #1 consts_defs);
   665 
   666 
   666     val mono = prove_mono predT fp_fun monos ctxt''
   667     val mono = prove_mono quiet_mode predT fp_fun monos ctxt''
   667 
   668 
   668   in (ctxt'', rec_name, mono, fp_def', map (#2 o #2) consts_defs,
   669   in (ctxt'', rec_name, mono, fp_def', map (#2 o #2) consts_defs,
   669     list_comb (rec_const, params), preds, argTs, bs, xs)
   670     list_comb (rec_const, params), preds, argTs, bs, xs)
   670   end;
   671   end;
   671 
   672 
   713              Attrib.internal (K (Induct.induct_pred name))])))] |> snd
   714              Attrib.internal (K (Induct.induct_pred name))])))] |> snd
   714       end
   715       end
   715   in (intrs', elims', induct', ctxt3) end;
   716   in (intrs', elims', induct', ctxt3) end;
   716 
   717 
   717 type add_ind_def =
   718 type add_ind_def =
   718   {verbose: bool, kind: string, alt_name: bstring, coind: bool, no_elim: bool, no_ind: bool} ->
   719   {quiet_mode: bool, verbose: bool, kind: string, alt_name: bstring,
       
   720     coind: bool, no_elim: bool, no_ind: bool} ->
   719   term list -> ((string * Attrib.src list) * term) list -> thm list ->
   721   term list -> ((string * Attrib.src list) * term) list -> thm list ->
   720   term list -> (string * mixfix) list ->
   722   term list -> (string * mixfix) list ->
   721   local_theory -> inductive_result * local_theory
   723   local_theory -> inductive_result * local_theory
   722 
   724 
   723 fun add_ind_def {verbose, kind, alt_name, coind, no_elim, no_ind}
   725 fun add_ind_def {quiet_mode, verbose, kind, alt_name, coind, no_elim, no_ind}
   724     cs intros monos params cnames_syn ctxt =
   726     cs intros monos params cnames_syn ctxt =
   725   let
   727   let
   726     val _ = null cnames_syn andalso error "No inductive predicates given";
   728     val _ = null cnames_syn andalso error "No inductive predicates given";
   727     val _ =
   729     val _ = message (quiet_mode andalso not verbose)
   728       if verbose then message ("Proofs for " ^ coind_prefix coind ^ "inductive predicate(s) " ^
   730       ("Proofs for " ^ coind_prefix coind ^ "inductive predicate(s) " ^
   729         commas_quote (map fst cnames_syn)) else ();
   731         commas_quote (map fst cnames_syn));
   730 
   732 
   731     val cnames = map (Sign.full_name (ProofContext.theory_of ctxt) o #1) cnames_syn;  (* FIXME *)
   733     val cnames = map (Sign.full_name (ProofContext.theory_of ctxt) o #1) cnames_syn;  (* FIXME *)
   732     val ((intr_names, intr_atts), intr_ts) =
   734     val ((intr_names, intr_atts), intr_ts) =
   733       apfst split_list (split_list (map (check_rule ctxt cs params) intros));
   735       apfst split_list (split_list (map (check_rule ctxt cs params) intros));
   734 
   736 
   735     val (ctxt1, rec_name, mono, fp_def, rec_preds_defs, rec_const, preds,
   737     val (ctxt1, rec_name, mono, fp_def, rec_preds_defs, rec_const, preds,
   736       argTs, bs, xs) = mk_ind_def alt_name coind cs intr_ts monos params cnames_syn ctxt;
   738       argTs, bs, xs) = mk_ind_def quiet_mode alt_name coind cs intr_ts monos params cnames_syn ctxt;
   737 
   739 
   738     val (intrs, unfold) = prove_intrs coind mono fp_def (length bs + length xs)
   740     val (intrs, unfold) = prove_intrs quiet_mode coind mono fp_def (length bs + length xs)
   739       params intr_ts rec_preds_defs ctxt1;
   741       params intr_ts rec_preds_defs ctxt1;
   740     val elims = if no_elim then [] else
   742     val elims = if no_elim then [] else
   741       prove_elims cs params intr_ts intr_names unfold rec_preds_defs ctxt1;
   743       prove_elims quiet_mode cs params intr_ts intr_names unfold rec_preds_defs ctxt1;
   742     val raw_induct = zero_var_indexes
   744     val raw_induct = zero_var_indexes
   743       (if no_ind then Drule.asm_rl else
   745       (if no_ind then Drule.asm_rl else
   744        if coind then
   746        if coind then
   745          singleton (ProofContext.export
   747          singleton (ProofContext.export
   746            (snd (Variable.add_fixes (map (fst o dest_Free) params) ctxt1)) ctxt1)
   748            (snd (Variable.add_fixes (map (fst o dest_Free) params) ctxt1)) ctxt1)
   747            (rotate_prems ~1 (ObjectLogic.rulify (rule_by_tactic
   749            (rotate_prems ~1 (ObjectLogic.rulify (rule_by_tactic
   748              (rewrite_tac [le_fun_def, le_bool_def, sup_fun_eq, sup_bool_eq] THEN
   750              (rewrite_tac [le_fun_def, le_bool_def, sup_fun_eq, sup_bool_eq] THEN
   749                fold_tac rec_preds_defs) (mono RS (fp_def RS def_coinduct)))))
   751                fold_tac rec_preds_defs) (mono RS (fp_def RS def_coinduct)))))
   750        else
   752        else
   751          prove_indrule cs argTs bs xs rec_const params intr_ts mono fp_def
   753          prove_indrule quiet_mode cs argTs bs xs rec_const params intr_ts mono fp_def
   752            rec_preds_defs ctxt1);
   754            rec_preds_defs ctxt1);
   753 
   755 
   754     val (intrs', elims', induct, ctxt2) = declare_rules kind rec_name coind no_ind
   756     val (intrs', elims', induct, ctxt2) = declare_rules kind rec_name coind no_ind
   755       cnames intrs intr_names intr_atts elims raw_induct ctxt1;
   757       cnames intrs intr_names intr_atts elims raw_induct ctxt1;
   756 
   758 
   769   in (result, ctxt3) end;
   771   in (result, ctxt3) end;
   770 
   772 
   771 
   773 
   772 (* external interfaces *)
   774 (* external interfaces *)
   773 
   775 
   774 fun gen_add_inductive_i mk_def (flags as {verbose, kind, alt_name, coind, no_elim, no_ind})
   776 fun gen_add_inductive_i mk_def
       
   777     (flags as {quiet_mode, verbose, kind, alt_name, coind, no_elim, no_ind})
   775     cnames_syn pnames spec monos lthy =
   778     cnames_syn pnames spec monos lthy =
   776   let
   779   let
   777     val thy = ProofContext.theory_of lthy;
   780     val thy = ProofContext.theory_of lthy;
   778     val _ = Theory.requires thy "Inductive" (coind_prefix coind ^ "inductive definitions");
   781     val _ = Theory.requires thy "Inductive" (coind_prefix coind ^ "inductive definitions");
   779 
   782 
   833       |> Specification.read_specification
   836       |> Specification.read_specification
   834           (cnames_syn @ pnames_syn) (map (fn (a, s) => [(a, [s])]) intro_srcs);
   837           (cnames_syn @ pnames_syn) (map (fn (a, s) => [(a, [s])]) intro_srcs);
   835     val (cs, ps) = chop (length cnames_syn) vars;
   838     val (cs, ps) = chop (length cnames_syn) vars;
   836     val intrs = map (apsnd the_single) specs;
   839     val intrs = map (apsnd the_single) specs;
   837     val monos = Attrib.eval_thms lthy raw_monos;
   840     val monos = Attrib.eval_thms lthy raw_monos;
   838     val flags = {verbose = verbose, kind = Thm.theoremK, alt_name = "",
   841     val flags = {quiet_mode = false, verbose = verbose, kind = Thm.theoremK, alt_name = "",
   839       coind = coind, no_elim = false, no_ind = false};
   842       coind = coind, no_elim = false, no_ind = false};
   840   in
   843   in
   841     lthy
   844     lthy
   842     |> LocalTheory.set_group (serial_string ())
   845     |> LocalTheory.set_group (serial_string ())
   843     |> gen_add_inductive_i mk_def flags cs (map fst ps) intrs monos
   846     |> gen_add_inductive_i mk_def flags cs (map fst ps) intrs monos