src/HOL/Tools/inductive_set.ML
changeset 67149 e61557884799
parent 63399 d1742d1b7f0f
child 67637 e6bcd14139fc
equal deleted inserted replaced
67148:d24dcac5eb4c 67149:e61557884799
    37 
    37 
    38 val anyt = Free ("t", TFree ("'t", []));
    38 val anyt = Free ("t", TFree ("'t", []));
    39 
    39 
    40 fun strong_ind_simproc tab =
    40 fun strong_ind_simproc tab =
    41   Simplifier.make_simproc @{context} "strong_ind"
    41   Simplifier.make_simproc @{context} "strong_ind"
    42    {lhss = [@{term "x::'a::{}"}],
    42    {lhss = [\<^term>\<open>x::'a::{}\<close>],
    43     proc = fn _ => fn ctxt => fn ct =>
    43     proc = fn _ => fn ctxt => fn ct =>
    44       let
    44       let
    45         fun close p t f =
    45         fun close p t f =
    46           let val vs = Term.add_vars t []
    46           let val vs = Term.add_vars t []
    47           in Thm.instantiate' [] (rev (map (SOME o Thm.cterm_of ctxt o Var) vs))
    47           in Thm.instantiate' [] (rev (map (SOME o Thm.cterm_of ctxt o Var) vs))
    48             (p (fold (Logic.all o Var) vs t) f)
    48             (p (fold (Logic.all o Var) vs t) f)
    49           end;
    49           end;
    50         fun mkop @{const_name HOL.conj} T x =
    50         fun mkop \<^const_name>\<open>HOL.conj\<close> T x =
    51               SOME (Const (@{const_name Lattices.inf}, T --> T --> T), x)
    51               SOME (Const (\<^const_name>\<open>Lattices.inf\<close>, T --> T --> T), x)
    52           | mkop @{const_name HOL.disj} T x =
    52           | mkop \<^const_name>\<open>HOL.disj\<close> T x =
    53               SOME (Const (@{const_name Lattices.sup}, T --> T --> T), x)
    53               SOME (Const (\<^const_name>\<open>Lattices.sup\<close>, T --> T --> T), x)
    54           | mkop _ _ _ = NONE;
    54           | mkop _ _ _ = NONE;
    55         fun mk_collect p T t =
    55         fun mk_collect p T t =
    56           let val U = HOLogic.dest_setT T
    56           let val U = HOLogic.dest_setT T
    57           in HOLogic.Collect_const U $
    57           in HOLogic.Collect_const U $
    58             HOLogic.mk_ptupleabs (HOLogic.flat_tuple_paths p) U HOLogic.boolT t
    58             HOLogic.mk_ptupleabs (HOLogic.flat_tuple_paths p) U HOLogic.boolT t
    59           end;
    59           end;
    60         fun decomp (Const (s, _) $ ((m as Const (@{const_name Set.member},
    60         fun decomp (Const (s, _) $ ((m as Const (\<^const_name>\<open>Set.member\<close>,
    61               Type (_, [_, Type (_, [T, _])]))) $ p $ S) $ u) =
    61               Type (_, [_, Type (_, [T, _])]))) $ p $ S) $ u) =
    62                 mkop s T (m, p, S, mk_collect p T (head_of u))
    62                 mkop s T (m, p, S, mk_collect p T (head_of u))
    63           | decomp (Const (s, _) $ u $ ((m as Const (@{const_name Set.member},
    63           | decomp (Const (s, _) $ u $ ((m as Const (\<^const_name>\<open>Set.member\<close>,
    64               Type (_, [_, Type (_, [T, _])]))) $ p $ S)) =
    64               Type (_, [_, Type (_, [T, _])]))) $ p $ S)) =
    65                 mkop s T (m, p, mk_collect p T (head_of u), S)
    65                 mkop s T (m, p, mk_collect p T (head_of u), S)
    66           | decomp _ = NONE;
    66           | decomp _ = NONE;
    67         val simp =
    67         val simp =
    68           full_simp_tac
    68           full_simp_tac
   239                   HOLogic.boolT (Bound 0))))] arg_cong' RS sym)
   239                   HOLogic.boolT (Bound 0))))] arg_cong' RS sym)
   240           end)
   240           end)
   241   in
   241   in
   242     Simplifier.simplify
   242     Simplifier.simplify
   243       (put_simpset HOL_basic_ss ctxt addsimps @{thms mem_Collect_eq case_prod_conv}
   243       (put_simpset HOL_basic_ss ctxt addsimps @{thms mem_Collect_eq case_prod_conv}
   244         addsimprocs [@{simproc Collect_mem}]) thm''
   244         addsimprocs [\<^simproc>\<open>Collect_mem\<close>]) thm''
   245       |> zero_var_indexes |> eta_contract_thm ctxt (equal p)
   245       |> zero_var_indexes |> eta_contract_thm ctxt (equal p)
   246   end;
   246   end;
   247 
   247 
   248 
   248 
   249 (**** declare rules for converting predicates to sets ****)
   249 (**** declare rules for converting predicates to sets ****)
   250 
   250 
   251 exception Malformed of string;
   251 exception Malformed of string;
   252 
   252 
   253 fun add context thm (tab as {to_set_simps, to_pred_simps, set_arities, pred_arities}) =
   253 fun add context thm (tab as {to_set_simps, to_pred_simps, set_arities, pred_arities}) =
   254   (case Thm.prop_of thm of
   254   (case Thm.prop_of thm of
   255     Const (@{const_name Trueprop}, _) $ (Const (@{const_name HOL.eq}, Type (_, [T, _])) $ lhs $ rhs) =>
   255     Const (\<^const_name>\<open>Trueprop\<close>, _) $ (Const (\<^const_name>\<open>HOL.eq\<close>, Type (_, [T, _])) $ lhs $ rhs) =>
   256       (case body_type T of
   256       (case body_type T of
   257          @{typ bool} =>
   257          \<^typ>\<open>bool\<close> =>
   258            let
   258            let
   259              val thy = Context.theory_of context;
   259              val thy = Context.theory_of context;
   260              val ctxt = Context.proof_of context;
   260              val ctxt = Context.proof_of context;
   261              fun factors_of t fs = case strip_abs_body t of
   261              fun factors_of t fs = case strip_abs_body t of
   262                  Const (@{const_name Set.member}, _) $ u $ S =>
   262                  Const (\<^const_name>\<open>Set.member\<close>, _) $ u $ S =>
   263                    if is_Free S orelse is_Var S then
   263                    if is_Free S orelse is_Var S then
   264                      let val ps = HOLogic.flat_tuple_paths u
   264                      let val ps = HOLogic.flat_tuple_paths u
   265                      in (SOME ps, (S, ps) :: fs) end
   265                      in (SOME ps, (S, ps) :: fs) end
   266                    else (NONE, fs)
   266                    else (NONE, fs)
   267                | _ => (NONE, fs);
   267                | _ => (NONE, fs);
   268              val (h, ts) = strip_comb lhs
   268              val (h, ts) = strip_comb lhs
   269              val (pfs, fs) = fold_map factors_of ts [];
   269              val (pfs, fs) = fold_map factors_of ts [];
   270              val ((h', ts'), fs') = (case rhs of
   270              val ((h', ts'), fs') = (case rhs of
   271                  Abs _ => (case strip_abs_body rhs of
   271                  Abs _ => (case strip_abs_body rhs of
   272                      Const (@{const_name Set.member}, _) $ u $ S =>
   272                      Const (\<^const_name>\<open>Set.member\<close>, _) $ u $ S =>
   273                        (strip_comb S, SOME (HOLogic.flat_tuple_paths u))
   273                        (strip_comb S, SOME (HOLogic.flat_tuple_paths u))
   274                    | _ => raise Malformed "member symbol on right-hand side expected")
   274                    | _ => raise Malformed "member symbol on right-hand side expected")
   275                | _ => (strip_comb rhs, NONE))
   275                | _ => (strip_comb rhs, NONE))
   276            in
   276            in
   277              case (name_type_of h, name_type_of h') of
   277              case (name_type_of h, name_type_of h') of
   382       end) fs;
   382       end) fs;
   383   in
   383   in
   384     thm |>
   384     thm |>
   385     Thm.instantiate ([], insts) |>
   385     Thm.instantiate ([], insts) |>
   386     Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimps to_set_simps
   386     Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimps to_set_simps
   387         addsimprocs [strong_ind_simproc pred_arities, @{simproc Collect_mem}]) |>
   387         addsimprocs [strong_ind_simproc pred_arities, \<^simproc>\<open>Collect_mem\<close>]) |>
   388     Rule_Cases.save thm
   388     Rule_Cases.save thm
   389   end;
   389   end;
   390 
   390 
   391 val to_set_att = Thm.rule_attribute [] o to_set;
   391 val to_set_att = Thm.rule_attribute [] o to_set;
   392 
   392 
   399   let
   399   let
   400     val thy = Proof_Context.theory_of lthy;
   400     val thy = Proof_Context.theory_of lthy;
   401     val {set_arities, pred_arities, to_pred_simps, ...} =
   401     val {set_arities, pred_arities, to_pred_simps, ...} =
   402       Data.get (Context.Proof lthy);
   402       Data.get (Context.Proof lthy);
   403     fun infer (Abs (_, _, t)) = infer t
   403     fun infer (Abs (_, _, t)) = infer t
   404       | infer (Const (@{const_name Set.member}, _) $ t $ u) =
   404       | infer (Const (\<^const_name>\<open>Set.member\<close>, _) $ t $ u) =
   405           infer_arities thy set_arities (SOME (HOLogic.flat_tuple_paths t), u)
   405           infer_arities thy set_arities (SOME (HOLogic.flat_tuple_paths t), u)
   406       | infer (t $ u) = infer t #> infer u
   406       | infer (t $ u) = infer t #> infer u
   407       | infer _ = I;
   407       | infer _ = I;
   408     val new_arities = filter_out
   408     val new_arities = filter_out
   409       (fn (x as Free (_, T), _) => member (op =) params x andalso length (binder_types T) > 0
   409       (fn (x as Free (_, T), _) => member (op =) params x andalso length (binder_types T) > 0
   532 
   532 
   533 (* attributes *)
   533 (* attributes *)
   534 
   534 
   535 val _ =
   535 val _ =
   536   Theory.setup
   536   Theory.setup
   537    (Attrib.setup @{binding pred_set_conv} (Scan.succeed pred_set_conv_att)
   537    (Attrib.setup \<^binding>\<open>pred_set_conv\<close> (Scan.succeed pred_set_conv_att)
   538       "declare rules for converting between predicate and set notation" #>
   538       "declare rules for converting between predicate and set notation" #>
   539     Attrib.setup @{binding to_set} (Attrib.thms >> to_set_att)
   539     Attrib.setup \<^binding>\<open>to_set\<close> (Attrib.thms >> to_set_att)
   540       "convert rule to set notation" #>
   540       "convert rule to set notation" #>
   541     Attrib.setup @{binding to_pred} (Attrib.thms >> to_pred_att)
   541     Attrib.setup \<^binding>\<open>to_pred\<close> (Attrib.thms >> to_pred_att)
   542       "convert rule to predicate notation" #>
   542       "convert rule to predicate notation" #>
   543     Attrib.setup @{binding mono_set} (Attrib.add_del mono_add mono_del)
   543     Attrib.setup \<^binding>\<open>mono_set\<close> (Attrib.add_del mono_add mono_del)
   544       "declare of monotonicity rule for set operators");
   544       "declare of monotonicity rule for set operators");
   545 
   545 
   546 
   546 
   547 (* commands *)                           
   547 (* commands *)                           
   548 
   548 
   549 val ind_set_decl = Inductive.gen_ind_decl add_ind_set_def;
   549 val ind_set_decl = Inductive.gen_ind_decl add_ind_set_def;
   550 
   550 
   551 val _ =
   551 val _ =
   552   Outer_Syntax.local_theory @{command_keyword inductive_set} "define inductive sets"
   552   Outer_Syntax.local_theory \<^command_keyword>\<open>inductive_set\<close> "define inductive sets"
   553     (ind_set_decl false);
   553     (ind_set_decl false);
   554 
   554 
   555 val _ =
   555 val _ =
   556   Outer_Syntax.local_theory @{command_keyword coinductive_set} "define coinductive sets"
   556   Outer_Syntax.local_theory \<^command_keyword>\<open>coinductive_set\<close> "define coinductive sets"
   557     (ind_set_decl true);
   557     (ind_set_decl true);
   558 
   558 
   559 end;
   559 end;