src/HOL/Tools/inductive_set.ML
changeset 56512 9276da80f7c3
parent 56245 84fc7dfa3cd4
child 57870 561680651364
equal deleted inserted replaced
56511:265816f87386 56512:9276da80f7c3
    23     (Attrib.binding * string) list -> (Facts.ref * Attrib.src list) list ->
    23     (Attrib.binding * string) list -> (Facts.ref * Attrib.src list) list ->
    24     local_theory -> Inductive.inductive_result * local_theory
    24     local_theory -> Inductive.inductive_result * local_theory
    25   val mono_add: attribute
    25   val mono_add: attribute
    26   val mono_del: attribute
    26   val mono_del: attribute
    27   val codegen_preproc: theory -> thm list -> thm list
    27   val codegen_preproc: theory -> thm list -> thm list
    28   val setup: theory -> theory
       
    29 end;
    28 end;
    30 
    29 
    31 structure Inductive_Set: INDUCTIVE_SET =
    30 structure Inductive_Set: INDUCTIVE_SET =
    32 struct
    31 struct
    33 
       
    34 (**** simplify {(x1, ..., xn). (x1, ..., xn) : S} to S ****)
       
    35 
       
    36 val collect_mem_simproc =
       
    37   Simplifier.simproc_global @{theory Set} "Collect_mem" ["Collect t"] (fn ctxt =>
       
    38     fn S as Const (@{const_name Collect}, Type ("fun", [_, T])) $ t =>
       
    39          let val (u, _, ps) = HOLogic.strip_psplits t
       
    40          in case u of
       
    41            (c as Const (@{const_name Set.member}, _)) $ q $ S' =>
       
    42              (case try (HOLogic.strip_ptuple ps) q of
       
    43                 NONE => NONE
       
    44               | SOME ts =>
       
    45                   if not (Term.is_open S') andalso
       
    46                     ts = map Bound (length ps downto 0)
       
    47                   then
       
    48                     let val simp =
       
    49                       full_simp_tac (put_simpset HOL_basic_ss ctxt
       
    50                         addsimps [@{thm split_paired_all}, @{thm split_conv}]) 1
       
    51                     in
       
    52                       SOME (Goal.prove ctxt [] []
       
    53                         (Const (@{const_name Pure.eq}, T --> T --> propT) $ S $ S')
       
    54                         (K (EVERY
       
    55                           [rtac eq_reflection 1, rtac @{thm subset_antisym} 1,
       
    56                            rtac subsetI 1, dtac CollectD 1, simp,
       
    57                            rtac subsetI 1, rtac CollectI 1, simp])))
       
    58                     end
       
    59                   else NONE)
       
    60          | _ => NONE
       
    61          end
       
    62      | _ => NONE);
       
    63 
    32 
    64 (***********************************************************************************)
    33 (***********************************************************************************)
    65 (* simplifies (%x y. (x, y) : S & P x y) to (%x y. (x, y) : S Int {(x, y). P x y}) *)
    34 (* simplifies (%x y. (x, y) : S & P x y) to (%x y. (x, y) : S Int {(x, y). P x y}) *)
    66 (* and        (%x y. (x, y) : S | P x y) to (%x y. (x, y) : S Un {(x, y). P x y})  *)
    35 (* and        (%x y. (x, y) : S | P x y) to (%x y. (x, y) : S Un {(x, y). P x y})  *)
    67 (* used for converting "strong" (co)induction rules                                *)
    36 (* used for converting "strong" (co)induction rules                                *)
   204 
   173 
   205 fun lookup_rule thy f rules = find_most_specific
   174 fun lookup_rule thy f rules = find_most_specific
   206   (swap #> Pattern.matches thy) (f #> fst) (op aconv) rules;
   175   (swap #> Pattern.matches thy) (f #> fst) (op aconv) rules;
   207 
   176 
   208 fun infer_arities thy arities (optf, t) fs = case strip_comb t of
   177 fun infer_arities thy arities (optf, t) fs = case strip_comb t of
   209     (Abs (s, T, u), []) => infer_arities thy arities (NONE, u) fs
   178     (Abs (_, _, u), []) => infer_arities thy arities (NONE, u) fs
   210   | (Abs _, _) => infer_arities thy arities (NONE, Envir.beta_norm t) fs
   179   | (Abs _, _) => infer_arities thy arities (NONE, Envir.beta_norm t) fs
   211   | (u, ts) => (case Option.map (lookup_arity thy arities) (name_type_of u) of
   180   | (u, ts) => (case Option.map (lookup_arity thy arities) (name_type_of u) of
   212       SOME (SOME (_, (arity, _))) =>
   181       SOME (SOME (_, (arity, _))) =>
   213         (fold (infer_arities thy arities) (arity ~~ List.take (ts, length arity)) fs
   182         (fold (infer_arities thy arities) (arity ~~ List.take (ts, length arity)) fs
   214            handle General.Subscript => error "infer_arities: bad term")
   183            handle General.Subscript => error "infer_arities: bad term")
   264                 HOLogic.Collect_const U $ HOLogic.mk_psplits fs' U
   233                 HOLogic.Collect_const U $ HOLogic.mk_psplits fs' U
   265                   HOLogic.boolT (Bound 0))))] arg_cong' RS sym)
   234                   HOLogic.boolT (Bound 0))))] arg_cong' RS sym)
   266           end)
   235           end)
   267   in
   236   in
   268     Simplifier.simplify (put_simpset HOL_basic_ss ctxt addsimps [mem_Collect_eq, @{thm split_conv}]
   237     Simplifier.simplify (put_simpset HOL_basic_ss ctxt addsimps [mem_Collect_eq, @{thm split_conv}]
   269       addsimprocs [collect_mem_simproc]) thm'' |>
   238       addsimprocs [@{simproc Collect_mem}]) thm'' |>
   270         zero_var_indexes |> eta_contract_thm (equal p)
   239         zero_var_indexes |> eta_contract_thm (equal p)
   271   end;
   240   end;
   272 
   241 
   273 
   242 
   274 (**** declare rules for converting predicates to sets ****)
   243 (**** declare rules for converting predicates to sets ****)
   395       end) fs;
   364       end) fs;
   396   in
   365   in
   397     thm |>
   366     thm |>
   398     Thm.instantiate ([], insts) |>
   367     Thm.instantiate ([], insts) |>
   399     Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimps to_set_simps
   368     Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimps to_set_simps
   400         addsimprocs [strong_ind_simproc pred_arities, collect_mem_simproc]) |>
   369         addsimprocs [strong_ind_simproc pred_arities, @{simproc Collect_mem}]) |>
   401     Rule_Cases.save thm
   370     Rule_Cases.save thm
   402   end;
   371   end;
   403 
   372 
   404 val to_set_att = Thm.rule_attribute o to_set;
   373 val to_set_att = Thm.rule_attribute o to_set;
   405 
   374 
   422         Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimprocs
   391         Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimprocs
   423           [to_pred_simproc (mem_Collect_eq :: @{thm split_conv} :: to_pred_simps)]) |>
   392           [to_pred_simproc (mem_Collect_eq :: @{thm split_conv} :: to_pred_simps)]) |>
   424         eta_contract_thm (is_pred pred_arities)
   393         eta_contract_thm (is_pred pred_arities)
   425       else thm
   394       else thm
   426   in map preproc end;
   395   in map preproc end;
   427 
       
   428 fun code_ind_att optmod = to_pred_att [];
       
   429 
   396 
   430 
   397 
   431 (**** definition of inductive sets ****)
   398 (**** definition of inductive sets ****)
   432 
   399 
   433 fun add_ind_set_def
   400 fun add_ind_set_def
   567 val mono_del = mono_att Inductive.mono_del;
   534 val mono_del = mono_att Inductive.mono_del;
   568 
   535 
   569 
   536 
   570 (** package setup **)
   537 (** package setup **)
   571 
   538 
   572 (* setup theory *)
   539 (* attributes *)
   573 
   540 
   574 val setup =
   541 val _ =
   575   Attrib.setup @{binding pred_set_conv} (Scan.succeed pred_set_conv_att)
   542   Theory.setup
   576     "declare rules for converting between predicate and set notation" #>
   543    (Attrib.setup @{binding pred_set_conv} (Scan.succeed pred_set_conv_att)
   577   Attrib.setup @{binding to_set} (Attrib.thms >> to_set_att)
   544       "declare rules for converting between predicate and set notation" #>
   578     "convert rule to set notation" #>
   545     Attrib.setup @{binding to_set} (Attrib.thms >> to_set_att)
   579   Attrib.setup @{binding to_pred} (Attrib.thms >> to_pred_att)
   546       "convert rule to set notation" #>
   580     "convert rule to predicate notation" #>
   547     Attrib.setup @{binding to_pred} (Attrib.thms >> to_pred_att)
   581   Attrib.setup @{binding mono_set} (Attrib.add_del mono_add mono_del)
   548       "convert rule to predicate notation" #>
   582     "declaration of monotonicity rule for set operators" #>
   549     Attrib.setup @{binding mono_set} (Attrib.add_del mono_add mono_del)
   583   map_theory_simpset (fn ctxt => ctxt addsimprocs [collect_mem_simproc]);
   550       "declare of monotonicity rule for set operators");
   584 
   551 
   585 
   552 
   586 (* outer syntax *)
   553 (* commands *)
   587 
   554 
   588 val ind_set_decl = Inductive.gen_ind_decl add_ind_set_def;
   555 val ind_set_decl = Inductive.gen_ind_decl add_ind_set_def;
   589 
   556 
   590 val _ =
   557 val _ =
   591   Outer_Syntax.local_theory @{command_spec "inductive_set"} "define inductive sets"
   558   Outer_Syntax.local_theory @{command_spec "inductive_set"} "define inductive sets"