src/HOL/Tools/typedef_package.ML
changeset 29056 dc08e3990c77
parent 29054 6f61794f1ff7
child 29057 d219318fd89a
equal deleted inserted replaced
29055:edaef19665e6 29056:dc08e3990c77
     1 (*  Title:      HOL/Tools/typedef_package.ML
     1 (*  Title:      HOL/Tools/typedef_package.ML
     2     ID:         $Id$
       
     3     Author:     Markus Wenzel and Stefan Berghofer, TU Muenchen
     2     Author:     Markus Wenzel and Stefan Berghofer, TU Muenchen
     4 
     3 
     5 Gordon/HOL-style type definitions: create a new syntactic type
     4 Gordon/HOL-style type definitions: create a new syntactic type
     6 represented by a non-empty subset.
     5 represented by a non-empty subset.
     7 *)
     6 *)
    25 end;
    24 end;
    26 
    25 
    27 structure TypedefPackage: TYPEDEF_PACKAGE =
    26 structure TypedefPackage: TYPEDEF_PACKAGE =
    28 struct
    27 struct
    29 
    28 
    30 (** theory context references **)
       
    31 
       
    32 val type_definitionN = "Typedef.type_definition";
       
    33 
       
    34 val Rep = @{thm "type_definition.Rep"};
       
    35 val Rep_inverse = @{thm "type_definition.Rep_inverse"};
       
    36 val Abs_inverse = @{thm "type_definition.Abs_inverse"};
       
    37 val Rep_inject = @{thm "type_definition.Rep_inject"};
       
    38 val Abs_inject = @{thm "type_definition.Abs_inject"};
       
    39 val Rep_cases = @{thm "type_definition.Rep_cases"};
       
    40 val Abs_cases = @{thm "type_definition.Abs_cases"};
       
    41 val Rep_induct = @{thm "type_definition.Rep_induct"};
       
    42 val Abs_induct = @{thm "type_definition.Abs_induct"};
       
    43 
       
    44 
       
    45 
       
    46 (** type definitions **)
    29 (** type definitions **)
    47 
    30 
    48 (* theory data *)
    31 (* theory data *)
    49 
    32 
    50 type info =
    33 type info =
   106     val setT' = map Term.itselfT args_setT ---> setT;
    89     val setT' = map Term.itselfT args_setT ---> setT;
   107     val setC = Term.list_comb (Const (full_name, setT'), map Logic.mk_type args_setT);
    90     val setC = Term.list_comb (Const (full_name, setT'), map Logic.mk_type args_setT);
   108     val RepC = Const (full Rep_name, newT --> oldT);
    91     val RepC = Const (full Rep_name, newT --> oldT);
   109     val AbsC = Const (full Abs_name, oldT --> newT);
    92     val AbsC = Const (full Abs_name, oldT --> newT);
   110 
    93 
   111     val set' = if def then setC else set;
    94     val A = if def then setC else set;
   112     fun mk_inhabited A =
    95     val goal =
   113       HOLogic.mk_Trueprop (HOLogic.mk_exists ("x", oldT, HOLogic.mk_mem (Free ("x", oldT), A)));
    96       HOLogic.mk_Trueprop (HOLogic.mk_exists ("x", oldT, HOLogic.mk_mem (Free ("x", oldT), A)));
   114     val goal = mk_inhabited set';
    97     val term_binding = (the_default (name, 0) (Syntax.read_variable name), SOME set);
   115     val term_binding = (the_default (name, 0) (Syntax.read_variable name), SOME set)
       
   116 
    98 
   117     val typedef_name = "type_definition_" ^ name;
    99     val typedef_name = "type_definition_" ^ name;
   118     val typedefC =
   100     val typedefC =
   119       Const (type_definitionN, (newT --> oldT) --> (oldT --> newT) --> setT --> HOLogic.boolT);
   101       Const (@{const_name type_definition},
   120     val typedef_prop =
   102         (newT --> oldT) --> (oldT --> newT) --> setT --> HOLogic.boolT);
   121       Logic.mk_implies (goal, HOLogic.mk_Trueprop (typedefC $ RepC $ AbsC $ set'));
   103     val typedef_prop = Logic.mk_implies (goal, HOLogic.mk_Trueprop (typedefC $ RepC $ AbsC $ A));
   122     val typedef_deps = Term.fold_aterms (fn Const c => insert (op =) c | _ => I) set' [];
   104     val typedef_deps = Term.fold_aterms (fn Const c => insert (op =) c | _ => I) A [];
   123 
   105 
   124     val (set_def, thy') = if def then
   106     val (set_def, thy') =
       
   107       if def then
   125         thy
   108         thy
   126         |> Sign.add_consts_i [(name, setT', NoSyn)]
   109         |> Sign.add_consts_i [(name, setT', NoSyn)]
   127         |> PureThy.add_defs false [Thm.no_attributes (PrimitiveDefs.mk_defpair (setC, set))]
   110         |> PureThy.add_defs false [Thm.no_attributes (PrimitiveDefs.mk_defpair (setC, set))]
   128         |-> (fn [th] => pair (SOME th))
   111         |-> (fn [th] => pair (SOME th))
   129       else (NONE, thy);
   112       else (NONE, thy);
   130 
   113 
   131     fun typedef_result inhabited = 
   114     fun typedef_result inhabited =
   132       ObjectLogic.typedecl (t, vs, mx)
   115       ObjectLogic.typedecl (t, vs, mx)
   133       #> snd
   116       #> snd
   134       #> Sign.add_consts_i
   117       #> Sign.add_consts_i
   135         [(Rep_name, newT --> oldT, NoSyn),
   118         [(Rep_name, newT --> oldT, NoSyn),
   136          (Abs_name, oldT --> newT, NoSyn)]
   119          (Abs_name, oldT --> newT, NoSyn)]
   137       #> PureThy.add_axioms [((typedef_name, typedef_prop),
   120       #> PureThy.add_axioms [((typedef_name, typedef_prop),
   138           [apsnd (fn cond_axm => inhabited RS cond_axm)])]
   121           [Thm.rule_attribute (fn _ => fn cond_axm => inhabited RS cond_axm)])]
   139       ##> Theory.add_deps "" (dest_Const RepC) typedef_deps
   122       ##> Theory.add_deps "" (dest_Const RepC) typedef_deps
   140       ##> Theory.add_deps "" (dest_Const AbsC) typedef_deps
   123       ##> Theory.add_deps "" (dest_Const AbsC) typedef_deps
   141       #-> (fn [type_definition] => fn thy1 =>
   124       #-> (fn [type_definition] => fn thy1 =>
   142         let
   125         let
   143           fun make th = Drule.standard (th OF [type_definition]);
   126           fun make th = Drule.standard (th OF [type_definition]);
   144           val abs_inject = make Abs_inject;
       
   145           val abs_inverse = make Abs_inverse;
       
   146           val ([Rep, Rep_inverse, Abs_inverse, Rep_inject, Abs_inject,
   127           val ([Rep, Rep_inverse, Abs_inverse, Rep_inject, Abs_inject,
   147               Rep_cases, Abs_cases, Rep_induct, Abs_induct], thy2) =
   128               Rep_cases, Abs_cases, Rep_induct, Abs_induct], thy2) =
   148             thy1
   129             thy1
   149             |> Sign.add_path name
   130             |> Sign.add_path name
   150             |> PureThy.add_thms
   131             |> PureThy.add_thms
   151               ([((Rep_name, make Rep), []),
   132               ([((Rep_name, make @{thm type_definition.Rep}), []),
   152                 ((Rep_name ^ "_inverse", make Rep_inverse), []),
   133                 ((Rep_name ^ "_inverse", make @{thm type_definition.Rep_inverse}), []),
   153                 ((Abs_name ^ "_inverse", abs_inverse), []),
   134                 ((Abs_name ^ "_inverse", make @{thm type_definition.Abs_inverse}), []),
   154                 ((Rep_name ^ "_inject", make Rep_inject), []),
   135                 ((Rep_name ^ "_inject", make @{thm type_definition.Rep_inject}), []),
   155                 ((Abs_name ^ "_inject", abs_inject), []),
   136                 ((Abs_name ^ "_inject", make @{thm type_definition.Abs_inject}), []),
   156                 ((Rep_name ^ "_cases", make Rep_cases),
   137                 ((Rep_name ^ "_cases", make @{thm type_definition.Rep_cases}),
   157                   [RuleCases.case_names [Rep_name], Induct.cases_pred full_name]),
   138                   [RuleCases.case_names [Rep_name], Induct.cases_pred full_name]),
   158                 ((Abs_name ^ "_cases", make Abs_cases),
   139                 ((Abs_name ^ "_cases", make @{thm type_definition.Abs_cases}),
   159                   [RuleCases.case_names [Abs_name], Induct.cases_type full_tname]),
   140                   [RuleCases.case_names [Abs_name], Induct.cases_type full_tname]),
   160                 ((Rep_name ^ "_induct", make Rep_induct),
   141                 ((Rep_name ^ "_induct", make @{thm type_definition.Rep_induct}),
   161                   [RuleCases.case_names [Rep_name], Induct.induct_pred full_name]),
   142                   [RuleCases.case_names [Rep_name], Induct.induct_pred full_name]),
   162                 ((Abs_name ^ "_induct", make Abs_induct),
   143                 ((Abs_name ^ "_induct", make @{thm type_definition.Abs_induct}),
   163                   [RuleCases.case_names [Abs_name], Induct.induct_type full_tname])])
   144                   [RuleCases.case_names [Abs_name], Induct.induct_type full_tname])])
   164             ||> Sign.parent_path;
   145             ||> Sign.parent_path;
   165           val info = {rep_type = oldT, abs_type = newT,
   146           val info = {rep_type = oldT, abs_type = newT,
   166             Rep_name = full Rep_name, Abs_name = full Abs_name,
   147             Rep_name = full Rep_name, Abs_name = full Abs_name,
   167               inhabited = inhabited, type_definition = type_definition, set_def = set_def,
   148               inhabited = inhabited, type_definition = type_definition, set_def = set_def,
   173           |> put_info full_tname info
   154           |> put_info full_tname info
   174           |> TypedefInterpretation.data full_tname
   155           |> TypedefInterpretation.data full_tname
   175           |> pair (full_tname, info)
   156           |> pair (full_tname, info)
   176         end);
   157         end);
   177 
   158 
       
   159 
   178     (* errors *)
   160     (* errors *)
   179 
   161 
   180     fun show_names pairs = commas_quote (map fst pairs);
   162     fun show_names pairs = commas_quote (map fst pairs);
   181 
   163 
   182     val illegal_vars =
   164     val illegal_vars =
   205 
   187 
   206   in ((set, goal, term_binding, set_def, typedef_result), thy') end
   188   in ((set, goal, term_binding, set_def, typedef_result), thy') end
   207   handle ERROR msg => err_in_typedef msg name;
   189   handle ERROR msg => err_in_typedef msg name;
   208 
   190 
   209 
   191 
   210 (* add_typedef interface *)
   192 (* add_typedef: tactic interface *)
   211 
   193 
   212 fun add_typedef def opt_name typ set opt_morphs tac thy =
   194 fun add_typedef def opt_name typ set opt_morphs tac thy =
   213   let
   195   let
   214     val name = the_default (#1 typ) opt_name;
   196     val name = the_default (#1 typ) opt_name;
   215     val ((set, goal, _, set_def, typedef_result), thy') =
   197     val ((set, goal, _, set_def, typedef_result), thy') =
   218       handle ERROR msg => cat_error msg
   200       handle ERROR msg => cat_error msg
   219         ("Failed to prove non-emptiness of " ^ quote (Syntax.string_of_term_global thy set));
   201         ("Failed to prove non-emptiness of " ^ quote (Syntax.string_of_term_global thy set));
   220   in typedef_result non_empty thy' end;
   202   in typedef_result non_empty thy' end;
   221 
   203 
   222 
   204 
   223 (* Isar typedef interface *)
   205 (* typedef: proof interface *)
   224 
   206 
   225 local
   207 local
   226 
   208 
   227 fun gen_typedef prep_term ((def, name), typ, set, opt_morphs) thy =
   209 fun gen_typedef prep_term ((def, name), typ, set, opt_morphs) thy =
   228   let
   210   let
   229     val ((_, goal, term_binding, set_def, typedef_result), thy') =
   211     val ((_, goal, term_binding, set_def, typedef_result), thy') =
   230       prepare_typedef prep_term def name typ set opt_morphs thy;
   212       prepare_typedef prep_term def name typ set opt_morphs thy;
   231     fun after_qed [[th]] = ProofContext.theory (snd o typedef_result th);
   213     fun after_qed [[th]] = ProofContext.theory (snd o typedef_result th);
   232   in 
   214   in
   233     Proof.theorem_i NONE after_qed [[(goal, [])]] (ProofContext.init thy')
   215     ProofContext.init thy'
   234     |> Proof.add_binds_i [term_binding] 
   216     |> Proof.theorem_i NONE after_qed [[(goal, [])]]
   235     |> (if def 
   217     |> Proof.add_binds_i [term_binding]
   236         then Seq.hd o Proof.refine (Method.Basic (Method.unfold [the set_def], Position.none))
   218     |> Proof.unfolding_i [[(the_list set_def, [])]]
   237         else I)
       
   238   end;
   219   end;
   239 
   220 
   240 in
   221 in
   241 
   222 
   242 val typedef = gen_typedef Syntax.check_term;
   223 val typedef = gen_typedef Syntax.check_term;
   246 
   227 
   247 
   228 
   248 
   229 
   249 (** outer syntax **)
   230 (** outer syntax **)
   250 
   231 
   251 local structure P = OuterParse and K = OuterKeyword in
   232 local structure P = OuterParse in
   252 
   233 
   253 val _ = OuterKeyword.keyword "morphisms";
   234 val _ = OuterKeyword.keyword "morphisms";
   254 
   235 
   255 val typedef_decl =
   236 val typedef_decl =
   256   Scan.optional (P.$$$ "(" |--
   237   Scan.optional (P.$$$ "(" |--
   261 
   242 
   262 fun mk_typedef ((((((def, opt_name), (vs, t)), mx), A), morphs)) =
   243 fun mk_typedef ((((((def, opt_name), (vs, t)), mx), A), morphs)) =
   263   typedef_cmd ((def, the_default (Syntax.type_name t mx) opt_name), (t, vs, mx), A, morphs);
   244   typedef_cmd ((def, the_default (Syntax.type_name t mx) opt_name), (t, vs, mx), A, morphs);
   264 
   245 
   265 val _ =
   246 val _ =
   266   OuterSyntax.command "typedef" "HOL type definition (requires non-emptiness proof)" K.thy_goal
   247   OuterSyntax.command "typedef" "HOL type definition (requires non-emptiness proof)"
       
   248     OuterKeyword.thy_goal
   267     (typedef_decl >> (Toplevel.print oo (Toplevel.theory_to_proof o mk_typedef)));
   249     (typedef_decl >> (Toplevel.print oo (Toplevel.theory_to_proof o mk_typedef)));
   268 
   250 
       
   251 end;
       
   252 
       
   253 
   269 val setup = TypedefInterpretation.init;
   254 val setup = TypedefInterpretation.init;
   270 
   255 
   271 end;
   256 end;
   272 
       
   273 end;