src/HOL/Tools/typedef.ML
author haftmann
Wed Dec 08 13:34:50 2010 +0100 (2010-12-08)
changeset 41075 4bed56dc95fb
parent 38757 2b3e054ae6fc
child 42290 b1f544c84040
permissions -rw-r--r--
primitive definitions of bot/top/inf/sup for bool and fun are named with canonical suffix `_def` rather than `_eq`
     1 (*  Title:      HOL/Tools/typedef.ML
     2     Author:     Markus Wenzel and Stefan Berghofer, TU Muenchen
     3 
     4 Gordon/HOL-style type definitions: create a new syntactic type
     5 represented by a non-empty set.
     6 *)
     7 
     8 signature TYPEDEF =
     9 sig
    10   type info =
    11    {rep_type: typ, abs_type: typ, Rep_name: string, Abs_name: string, axiom_name: string} *
    12    {inhabited: thm, type_definition: thm, set_def: thm option, Rep: thm, Rep_inverse: thm,
    13     Abs_inverse: thm, Rep_inject: thm, Abs_inject: thm, Rep_cases: thm, Abs_cases: thm,
    14     Rep_induct: thm, Abs_induct: thm}
    15   val transform_info: morphism -> info -> info
    16   val get_info: Proof.context -> string -> info list
    17   val get_info_global: theory -> string -> info list
    18   val interpretation: (string -> theory -> theory) -> theory -> theory
    19   val setup: theory -> theory
    20   val add_typedef: bool -> binding option -> binding * (string * sort) list * mixfix ->
    21     term -> (binding * binding) option -> tactic -> local_theory -> (string * info) * local_theory
    22   val add_typedef_global: bool -> binding option -> binding * (string * sort) list * mixfix ->
    23     term -> (binding * binding) option -> tactic -> theory -> (string * info) * theory
    24   val typedef: (bool * binding) * (binding * (string * sort) list * mixfix) * term *
    25     (binding * binding) option -> local_theory -> Proof.state
    26   val typedef_cmd: (bool * binding) * (binding * (string * string option) list * mixfix) * string *
    27     (binding * binding) option -> local_theory -> Proof.state
    28 end;
    29 
    30 structure Typedef: TYPEDEF =
    31 struct
    32 
    33 (** type definitions **)
    34 
    35 (* theory data *)
    36 
    37 type info =
    38   (*global part*)
    39   {rep_type: typ, abs_type: typ, Rep_name: string, Abs_name: string, axiom_name: string} *
    40   (*local part*)
    41   {inhabited: thm, type_definition: thm, set_def: thm option, Rep: thm, Rep_inverse: thm,
    42     Abs_inverse: thm, Rep_inject: thm, Abs_inject: thm, Rep_cases: thm, Abs_cases: thm,
    43     Rep_induct: thm, Abs_induct: thm};
    44 
    45 fun transform_info phi (info: info) =
    46   let
    47     val thm = Morphism.thm phi;
    48     val (global_info, {inhabited, type_definition,
    49       set_def, Rep, Rep_inverse, Abs_inverse, Rep_inject, Abs_inject,
    50       Rep_cases, Abs_cases, Rep_induct, Abs_induct}) = info;
    51   in
    52     (global_info,
    53      {inhabited = thm inhabited, type_definition = thm type_definition,
    54       set_def = Option.map thm set_def, Rep = thm Rep, Rep_inverse = thm Rep_inverse,
    55       Abs_inverse = thm Abs_inverse, Rep_inject = thm Rep_inject, Abs_inject = thm Abs_inject,
    56       Rep_cases = thm Rep_cases, Abs_cases = thm Abs_cases, Rep_induct = thm Rep_induct,
    57       Abs_induct = thm Abs_induct})
    58   end;
    59 
    60 structure Data = Generic_Data
    61 (
    62   type T = info list Symtab.table;
    63   val empty = Symtab.empty;
    64   val extend = I;
    65   fun merge data = Symtab.merge_list (K true) data;
    66 );
    67 
    68 val get_info = Symtab.lookup_list o Data.get o Context.Proof;
    69 val get_info_global = Symtab.lookup_list o Data.get o Context.Theory;
    70 
    71 fun put_info name info = Data.map (Symtab.cons_list (name, info));
    72 
    73 
    74 (* global interpretation *)
    75 
    76 structure Typedef_Interpretation = Interpretation(type T = string val eq = op =);
    77 val interpretation = Typedef_Interpretation.interpretation;
    78 
    79 val setup = Typedef_Interpretation.init;
    80 
    81 
    82 (* primitive typedef axiomatization -- for fresh typedecl *)
    83 
    84 fun mk_inhabited A =
    85   let val T = HOLogic.dest_setT (Term.fastype_of A)
    86   in HOLogic.mk_Trueprop (HOLogic.exists_const T $ Abs ("x", T, HOLogic.mk_mem (Bound 0, A))) end;
    87 
    88 fun mk_typedef newT oldT RepC AbsC A =
    89   let
    90     val typedefC =
    91       Const (@{const_name type_definition},
    92         (newT --> oldT) --> (oldT --> newT) --> HOLogic.mk_setT oldT --> HOLogic.boolT);
    93   in Logic.mk_implies (mk_inhabited A, HOLogic.mk_Trueprop (typedefC $ RepC $ AbsC $ A)) end;
    94 
    95 fun primitive_typedef typedef_name newT oldT Rep_name Abs_name A thy =
    96   let
    97     (* errors *)
    98 
    99     fun show_names pairs = commas_quote (map fst pairs);
   100 
   101     val lhs_tfrees = Term.add_tfreesT newT [];
   102     val rhs_tfrees = Term.add_tfreesT oldT [];
   103     val _ =
   104       (case fold (remove (op =)) lhs_tfrees rhs_tfrees of [] => ()
   105       | extras => error ("Extra type variables in representing set: " ^ show_names extras));
   106 
   107     val _ =
   108       (case Term.add_frees A [] of [] => []
   109       | xs => error ("Illegal variables in representing set: " ^ show_names xs));
   110 
   111 
   112     (* axiomatization *)
   113 
   114     val ((RepC, AbsC), consts_thy) = thy
   115       |> Sign.declare_const ((Rep_name, newT --> oldT), NoSyn)
   116       ||>> Sign.declare_const ((Abs_name, oldT --> newT), NoSyn);
   117 
   118     val typedef_deps = Term.add_consts A [];
   119 
   120     val ((axiom_name, axiom), axiom_thy) = consts_thy
   121       |> Thm.add_axiom (typedef_name, mk_typedef newT oldT RepC AbsC A)
   122       ||> Theory.add_deps "" (dest_Const RepC) typedef_deps
   123       ||> Theory.add_deps "" (dest_Const AbsC) typedef_deps;
   124 
   125   in ((RepC, AbsC, axiom_name, axiom), axiom_thy) end;
   126 
   127 
   128 (* prepare_typedef *)
   129 
   130 fun prepare_typedef prep_term def_set name (tname, raw_args, mx) raw_set opt_morphs lthy =
   131   let
   132     val full_name = Local_Theory.full_name lthy name;
   133     val bname = Binding.name_of name;
   134 
   135 
   136     (* rhs *)
   137 
   138     val tmp_ctxt = lthy |> fold (Variable.declare_typ o TFree) raw_args;
   139     val set = prep_term tmp_ctxt raw_set;
   140     val tmp_ctxt' = tmp_ctxt |> Variable.declare_term set;
   141 
   142     val setT = Term.fastype_of set;
   143     val oldT = HOLogic.dest_setT setT handle TYPE _ =>
   144       error ("Not a set type: " ^ quote (Syntax.string_of_typ lthy setT));
   145 
   146     val goal = mk_inhabited set;
   147     val goal_pat = mk_inhabited (Var (the_default (bname, 0) (Syntax.read_variable bname), setT));
   148 
   149 
   150     (* lhs *)
   151 
   152     val args = map (ProofContext.check_tfree tmp_ctxt') raw_args;
   153     val (newT, typedecl_lthy) = lthy
   154       |> Typedecl.typedecl (tname, args, mx)
   155       ||> Variable.declare_term set;
   156 
   157     val Type (full_tname, type_args) = newT;
   158     val lhs_tfrees = map Term.dest_TFree type_args;
   159 
   160 
   161     (* set definition *)
   162 
   163     val ((set', set_def), set_lthy) =
   164       if def_set then
   165         typedecl_lthy
   166         |> Local_Theory.define ((name, NoSyn), ((Thm.def_binding name, []), set))
   167         |>> (fn (set', (_, set_def)) => (set', SOME set_def))
   168       else ((set, NONE), typedecl_lthy);
   169 
   170 
   171     (* axiomatization *)
   172 
   173     val (Rep_name, Abs_name) =
   174       (case opt_morphs of
   175         NONE => (Binding.prefix_name "Rep_" name, Binding.prefix_name "Abs_" name)
   176       | SOME morphs => morphs);
   177 
   178     val typedef_name = Binding.prefix_name "type_definition_" name;
   179 
   180     val ((RepC, AbsC, axiom_name, typedef), typedef_lthy) =
   181       let
   182         val thy = ProofContext.theory_of set_lthy;
   183         val cert = Thm.cterm_of thy;
   184         val (defs, A) =
   185           Local_Defs.export_cterm set_lthy (ProofContext.init_global thy) (cert set')
   186           ||> Thm.term_of;
   187 
   188         val ((RepC, AbsC, axiom_name, axiom), axiom_lthy) = set_lthy |>
   189           Local_Theory.background_theory_result
   190             (primitive_typedef typedef_name newT oldT Rep_name Abs_name A);
   191 
   192         val cert = Thm.cterm_of (ProofContext.theory_of axiom_lthy);
   193         val typedef =
   194           Local_Defs.contract axiom_lthy defs (cert (mk_typedef newT oldT RepC AbsC set')) axiom;
   195       in ((RepC, AbsC, axiom_name, typedef), axiom_lthy) end;
   196 
   197     val alias_lthy = typedef_lthy
   198       |> Local_Theory.const_alias Rep_name (#1 (Term.dest_Const RepC))
   199       |> Local_Theory.const_alias Abs_name (#1 (Term.dest_Const AbsC));
   200 
   201 
   202     (* result *)
   203 
   204     fun note_qualify ((b, atts), th) =
   205       Local_Theory.note ((Binding.qualify false bname b, map (Attrib.internal o K) atts), [th])
   206       #>> (fn (_, [th']) => th');
   207 
   208     fun typedef_result inhabited lthy1 =
   209       let
   210         val cert = Thm.cterm_of (ProofContext.theory_of lthy1);
   211         val inhabited' =
   212           Local_Defs.contract lthy1 (the_list set_def) (cert (mk_inhabited set')) inhabited;
   213         val typedef' = inhabited' RS typedef;
   214         fun make th = Goal.norm_result (typedef' RS th);
   215         val (((((((((((_, [type_definition]), Rep), Rep_inverse), Abs_inverse), Rep_inject),
   216             Abs_inject), Rep_cases), Abs_cases), Rep_induct), Abs_induct), lthy2) = lthy1
   217           |> Local_Theory.note ((typedef_name, []), [typedef'])
   218           ||>> note_qualify ((Rep_name, []), make @{thm type_definition.Rep})
   219           ||>> note_qualify ((Binding.suffix_name "_inverse" Rep_name, []),
   220               make @{thm type_definition.Rep_inverse})
   221           ||>> note_qualify ((Binding.suffix_name "_inverse" Abs_name, []),
   222               make @{thm type_definition.Abs_inverse})
   223           ||>> note_qualify ((Binding.suffix_name "_inject" Rep_name, []),
   224               make @{thm type_definition.Rep_inject})
   225           ||>> note_qualify ((Binding.suffix_name "_inject" Abs_name, []),
   226               make @{thm type_definition.Abs_inject})
   227           ||>> note_qualify ((Binding.suffix_name "_cases" Rep_name,
   228                 [Rule_Cases.case_names [Binding.name_of Rep_name], Induct.cases_pred full_name]),
   229               make @{thm type_definition.Rep_cases})
   230           ||>> note_qualify ((Binding.suffix_name "_cases" Abs_name,
   231                 [Rule_Cases.case_names [Binding.name_of Abs_name], Induct.cases_type full_tname]),
   232               make @{thm type_definition.Abs_cases})
   233           ||>> note_qualify ((Binding.suffix_name "_induct" Rep_name,
   234                 [Rule_Cases.case_names [Binding.name_of Rep_name], Induct.induct_pred full_name]),
   235               make @{thm type_definition.Rep_induct})
   236           ||>> note_qualify ((Binding.suffix_name "_induct" Abs_name,
   237                 [Rule_Cases.case_names [Binding.name_of Abs_name], Induct.induct_type full_tname]),
   238               make @{thm type_definition.Abs_induct});
   239 
   240         val info =
   241           ({rep_type = oldT, abs_type = newT, Rep_name = #1 (Term.dest_Const RepC),
   242             Abs_name = #1 (Term.dest_Const AbsC), axiom_name = axiom_name},
   243            {inhabited = inhabited, type_definition = type_definition, set_def = set_def,
   244             Rep = Rep, Rep_inverse = Rep_inverse, Abs_inverse = Abs_inverse,
   245             Rep_inject = Rep_inject, Abs_inject = Abs_inject, Rep_cases = Rep_cases,
   246           Abs_cases = Abs_cases, Rep_induct = Rep_induct, Abs_induct = Abs_induct});
   247       in
   248         lthy2
   249         |> Local_Theory.declaration true (fn phi => put_info full_tname (transform_info phi info))
   250         |> Local_Theory.background_theory (Typedef_Interpretation.data full_tname)
   251         |> pair (full_tname, info)
   252       end;
   253 
   254   in ((goal, goal_pat, typedef_result), alias_lthy) end
   255   handle ERROR msg =>
   256     cat_error msg ("The error(s) above occurred in typedef " ^ quote (Binding.str_of name));
   257 
   258 
   259 (* add_typedef: tactic interface *)
   260 
   261 fun add_typedef def opt_name typ set opt_morphs tac lthy =
   262   let
   263     val name = the_default (#1 typ) opt_name;
   264     val ((goal, _, typedef_result), lthy') =
   265       prepare_typedef Syntax.check_term def name typ set opt_morphs lthy;
   266     val inhabited =
   267       Goal.prove lthy' [] [] goal (K tac)
   268       |> Goal.norm_result |> Thm.close_derivation;
   269   in typedef_result inhabited lthy' end;
   270 
   271 fun add_typedef_global def opt_name typ set opt_morphs tac =
   272   Named_Target.theory_init
   273   #> add_typedef def opt_name typ set opt_morphs tac
   274   #> Local_Theory.exit_result_global (apsnd o transform_info);
   275 
   276 
   277 (* typedef: proof interface *)
   278 
   279 local
   280 
   281 fun gen_typedef prep_term prep_constraint ((def, name), (b, raw_args, mx), set, opt_morphs) lthy =
   282   let
   283     val args = map (apsnd (prep_constraint lthy)) raw_args;
   284     val ((goal, goal_pat, typedef_result), lthy') =
   285       prepare_typedef prep_term def name (b, args, mx) set opt_morphs lthy;
   286     fun after_qed [[th]] = snd o typedef_result th;
   287   in Proof.theorem NONE after_qed [[(goal, [goal_pat])]] lthy' end;
   288 
   289 in
   290 
   291 val typedef = gen_typedef Syntax.check_term (K I);
   292 val typedef_cmd = gen_typedef Syntax.read_term Typedecl.read_constraint;
   293 
   294 end;
   295 
   296 
   297 
   298 (** outer syntax **)
   299 
   300 val _ = Keyword.keyword "morphisms";
   301 
   302 val _ =
   303   Outer_Syntax.local_theory_to_proof "typedef" "HOL type definition (requires non-emptiness proof)"
   304     Keyword.thy_goal
   305     (Scan.optional (Parse.$$$ "(" |--
   306         ((Parse.$$$ "open" >> K false) -- Scan.option Parse.binding ||
   307           Parse.binding >> (fn s => (true, SOME s))) --| Parse.$$$ ")") (true, NONE) --
   308       (Parse.type_args_constrained -- Parse.binding) --
   309         Parse.opt_mixfix -- (Parse.$$$ "=" |-- Parse.term) --
   310         Scan.option (Parse.$$$ "morphisms" |-- Parse.!!! (Parse.binding -- Parse.binding))
   311     >> (fn ((((((def, opt_name), (args, t)), mx), A), morphs)) =>
   312         typedef_cmd ((def, the_default t opt_name), (t, args, mx), A, morphs)));
   313 
   314 end;
   315