src/HOL/Tools/typedef.ML
author wenzelm
Sun Mar 07 12:19:47 2010 +0100 (2010-03-07)
changeset 35625 9c818cab0dd0
parent 35430 df2862dc23a8
child 35626 06197484c6ad
permissions -rw-r--r--
modernized structure Object_Logic;
     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 subset.
     6 *)
     7 
     8 signature TYPEDEF =
     9 sig
    10   type info =
    11    {rep_type: typ, abs_type: typ, Rep_name: string, Abs_name: string, inhabited: thm,
    12     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 add_typedef: bool -> binding option -> binding * string list * mixfix ->
    16     term -> (binding * binding) option -> tactic -> theory -> (string * info) * theory
    17   val typedef: (bool * binding) * (binding * string list * mixfix) * term *
    18     (binding * binding) option -> theory -> Proof.state
    19   val typedef_cmd: (bool * binding) * (binding * string list * mixfix) * string *
    20     (binding * binding) option -> theory -> Proof.state
    21   val get_info: theory -> string -> info option
    22   val the_info: theory -> string -> info
    23   val interpretation: (string -> theory -> theory) -> theory -> theory
    24   val setup: theory -> theory
    25 end;
    26 
    27 structure Typedef: TYPEDEF =
    28 struct
    29 
    30 (** type definitions **)
    31 
    32 (* theory data *)
    33 
    34 type info =
    35  {rep_type: typ, abs_type: typ, Rep_name: string, Abs_name: string, inhabited: thm,
    36   type_definition: thm, set_def: thm option, Rep: thm, Rep_inverse: thm,
    37   Abs_inverse: thm, Rep_inject: thm, Abs_inject: thm, Rep_cases: thm, Abs_cases: thm,
    38   Rep_induct: thm, Abs_induct: thm};
    39 
    40 structure TypedefData = Theory_Data
    41 (
    42   type T = info Symtab.table;
    43   val empty = Symtab.empty;
    44   val extend = I;
    45   fun merge data = Symtab.merge (K true) data;
    46 );
    47 
    48 val get_info = Symtab.lookup o TypedefData.get;
    49 
    50 fun the_info thy name =
    51   (case get_info thy name of
    52     SOME info => info
    53   | NONE => error ("Unknown typedef " ^ quote name));
    54 
    55 fun put_info name info = TypedefData.map (Symtab.update (name, info));
    56 
    57 
    58 (* prepare_typedef *)
    59 
    60 fun declare_type_name a = Variable.declare_constraints (Logic.mk_type (TFree (a, dummyS)));
    61 
    62 structure Typedef_Interpretation = Interpretation(type T = string val eq = op =);
    63 val interpretation = Typedef_Interpretation.interpretation;
    64 
    65 fun prepare_typedef prep_term def name (tname, vs, mx) raw_set opt_morphs thy =
    66   let
    67     val _ = Theory.requires thy "Typedef" "typedefs";
    68     val ctxt = ProofContext.init thy;
    69 
    70     val full = Sign.full_name thy;
    71     val full_name = full name;
    72     val bname = Binding.name_of name;
    73 
    74     (*rhs*)
    75     val set = prep_term (ctxt |> fold declare_type_name vs) raw_set;
    76     val setT = Term.fastype_of set;
    77     val rhs_tfrees = Term.add_tfrees set [];
    78     val rhs_tfreesT = Term.add_tfreesT setT [];
    79     val oldT = HOLogic.dest_setT setT handle TYPE _ =>
    80       error ("Not a set type: " ^ quote (Syntax.string_of_typ ctxt setT));
    81 
    82     (*lhs*)
    83     val defS = Sign.defaultS thy;
    84     val lhs_tfrees = map (fn v => (v, the_default defS (AList.lookup (op =) rhs_tfrees v))) vs;
    85     val args_setT = lhs_tfrees
    86       |> filter (member (op =) rhs_tfrees andf (not o member (op =) rhs_tfreesT))
    87       |> map TFree;
    88 
    89     val full_tname = full tname;
    90     val newT = Type (full_tname, map TFree lhs_tfrees);
    91 
    92     val (Rep_name, Abs_name) =
    93       (case opt_morphs of
    94         NONE => (Binding.prefix_name "Rep_" name, Binding.prefix_name "Abs_" name)
    95       | SOME morphs => morphs);
    96     val setT' = map Term.itselfT args_setT ---> setT;
    97     val setC = Term.list_comb (Const (full_name, setT'), map Logic.mk_type args_setT);
    98     val RepC = Const (full Rep_name, newT --> oldT);
    99     val AbsC = Const (full Abs_name, oldT --> newT);
   100 
   101     (*inhabitance*)
   102     fun mk_inhabited A =
   103       HOLogic.mk_Trueprop (HOLogic.mk_exists ("x", oldT, HOLogic.mk_mem (Free ("x", oldT), A)));
   104     val set' = if def then setC else set;
   105     val goal' = mk_inhabited set';
   106     val goal = mk_inhabited set;
   107     val goal_pat = mk_inhabited (Var (the_default (bname, 0) (Syntax.read_variable bname), setT));
   108 
   109     (*axiomatization*)
   110     val typedef_name = Binding.prefix_name "type_definition_" name;
   111     val typedefC =
   112       Const (@{const_name type_definition},
   113         (newT --> oldT) --> (oldT --> newT) --> setT --> HOLogic.boolT);
   114     val typedef_prop = Logic.mk_implies (goal', HOLogic.mk_Trueprop (typedefC $ RepC $ AbsC $ set'));
   115     val typedef_deps = Term.add_consts set' [];
   116 
   117     (*set definition*)
   118     fun add_def theory =
   119       if def then
   120         theory
   121         |> Sign.add_consts_i [(name, setT', NoSyn)]
   122         |> PureThy.add_defs false [((Thm.def_binding name, Logic.mk_equals (setC, set)), [])]
   123         |-> (fn [th] => pair (SOME th))
   124       else (NONE, theory);
   125     fun contract_def NONE th = th
   126       | contract_def (SOME def_eq) th =
   127           let
   128             val cert = Thm.cterm_of (Thm.theory_of_thm def_eq);
   129             val goal_eq = MetaSimplifier.rewrite true [def_eq] (cert goal');
   130           in Drule.export_without_context (Drule.equal_elim_rule2 OF [goal_eq, th]) end;
   131 
   132     fun typedef_result inhabited =
   133       Object_Logic.typedecl (tname, vs, mx)
   134       #> snd
   135       #> Sign.add_consts_i
   136         [(Rep_name, newT --> oldT, NoSyn),
   137          (Abs_name, oldT --> newT, NoSyn)]
   138       #> add_def
   139       #-> (fn set_def =>
   140         PureThy.add_axioms [((typedef_name, typedef_prop),
   141           [Thm.rule_attribute (K (fn cond_axm => contract_def set_def inhabited RS cond_axm))])]
   142         ##>> pair set_def)
   143       ##> Theory.add_deps "" (dest_Const RepC) typedef_deps
   144       ##> Theory.add_deps "" (dest_Const AbsC) typedef_deps
   145       #-> (fn ([type_definition], set_def) => fn thy1 =>
   146         let
   147           fun make th = Drule.export_without_context (th OF [type_definition]);
   148           val ([Rep, Rep_inverse, Abs_inverse, Rep_inject, Abs_inject,
   149               Rep_cases, Abs_cases, Rep_induct, Abs_induct], thy2) =
   150             thy1
   151             |> Sign.add_path (Binding.name_of name)
   152             |> PureThy.add_thms
   153               [((Rep_name, make @{thm type_definition.Rep}), []),
   154                 ((Binding.suffix_name "_inverse" Rep_name, make @{thm type_definition.Rep_inverse}), []),
   155                 ((Binding.suffix_name "_inverse" Abs_name, make @{thm type_definition.Abs_inverse}), []),
   156                 ((Binding.suffix_name "_inject" Rep_name, make @{thm type_definition.Rep_inject}), []),
   157                 ((Binding.suffix_name "_inject" Abs_name, make @{thm type_definition.Abs_inject}), []),
   158                 ((Binding.suffix_name "_cases" Rep_name, make @{thm type_definition.Rep_cases}),
   159                   [Rule_Cases.case_names [Binding.name_of Rep_name], Induct.cases_pred full_name]),
   160                 ((Binding.suffix_name "_cases" Abs_name, make @{thm type_definition.Abs_cases}),
   161                   [Rule_Cases.case_names [Binding.name_of Abs_name], Induct.cases_type full_tname]),
   162                 ((Binding.suffix_name "_induct" Rep_name, make @{thm type_definition.Rep_induct}),
   163                   [Rule_Cases.case_names [Binding.name_of Rep_name], Induct.induct_pred full_name]),
   164                 ((Binding.suffix_name "_induct" Abs_name, make @{thm type_definition.Abs_induct}),
   165                   [Rule_Cases.case_names [Binding.name_of Abs_name], Induct.induct_type full_tname])]
   166             ||> Sign.restore_naming thy1;
   167           val info = {rep_type = oldT, abs_type = newT,
   168             Rep_name = full Rep_name, Abs_name = full Abs_name,
   169               inhabited = inhabited, type_definition = type_definition, set_def = set_def,
   170               Rep = Rep, Rep_inverse = Rep_inverse, Abs_inverse = Abs_inverse,
   171               Rep_inject = Rep_inject, Abs_inject = Abs_inject, Rep_cases = Rep_cases,
   172             Abs_cases = Abs_cases, Rep_induct = Rep_induct, Abs_induct = Abs_induct};
   173         in
   174           thy2
   175           |> put_info full_tname info
   176           |> Typedef_Interpretation.data full_tname
   177           |> pair (full_tname, info)
   178         end);
   179 
   180 
   181     (* errors *)
   182 
   183     fun show_names pairs = commas_quote (map fst pairs);
   184 
   185     val illegal_vars =
   186       if null (Term.add_vars set []) andalso null (Term.add_tvars set []) then []
   187       else ["Illegal schematic variable(s) on rhs"];
   188 
   189     val dup_lhs_tfrees =
   190       (case duplicates (op =) lhs_tfrees of [] => []
   191       | dups => ["Duplicate type variables on lhs: " ^ show_names dups]);
   192 
   193     val extra_rhs_tfrees =
   194       (case fold (remove (op =)) lhs_tfrees rhs_tfrees of [] => []
   195       | extras => ["Extra type variables on rhs: " ^ show_names extras]);
   196 
   197     val illegal_frees =
   198       (case Term.add_frees set [] of [] => []
   199       | xs => ["Illegal variables on rhs: " ^ show_names xs]);
   200 
   201     val errs = illegal_vars @ dup_lhs_tfrees @ extra_rhs_tfrees @ illegal_frees;
   202     val _ = if null errs then () else error (cat_lines errs);
   203 
   204     (*test theory errors now!*)
   205     val test_thy = Theory.copy thy;
   206     val _ = typedef_result (Skip_Proof.make_thm test_thy goal) test_thy;
   207 
   208   in (set, goal, goal_pat, typedef_result) end
   209   handle ERROR msg =>
   210     cat_error msg ("The error(s) above occurred in typedef " ^ quote (Binding.str_of name));
   211 
   212 
   213 (* add_typedef: tactic interface *)
   214 
   215 fun add_typedef def opt_name typ set opt_morphs tac thy =
   216   let
   217     val name = the_default (#1 typ) opt_name;
   218     val (set, goal, _, typedef_result) =
   219       prepare_typedef Syntax.check_term def name typ set opt_morphs thy;
   220     val inhabited = Goal.prove_global thy [] [] goal (K tac)
   221       handle ERROR msg => cat_error msg
   222         ("Failed to prove non-emptiness of " ^ quote (Syntax.string_of_term_global thy set));
   223   in typedef_result inhabited thy end;
   224 
   225 
   226 (* typedef: proof interface *)
   227 
   228 local
   229 
   230 fun gen_typedef prep_term ((def, name), typ, set, opt_morphs) thy =
   231   let
   232     val (_, goal, goal_pat, typedef_result) =
   233       prepare_typedef prep_term def name typ set opt_morphs thy;
   234     fun after_qed [[th]] = ProofContext.theory (snd o typedef_result th);
   235   in Proof.theorem_i NONE after_qed [[(goal, [goal_pat])]] (ProofContext.init thy) end;
   236 
   237 in
   238 
   239 val typedef = gen_typedef Syntax.check_term;
   240 val typedef_cmd = gen_typedef Syntax.read_term;
   241 
   242 end;
   243 
   244 
   245 
   246 (** outer syntax **)
   247 
   248 local structure P = OuterParse in
   249 
   250 val _ = OuterKeyword.keyword "morphisms";
   251 
   252 val _ =
   253   OuterSyntax.command "typedef" "HOL type definition (requires non-emptiness proof)"
   254     OuterKeyword.thy_goal
   255     (Scan.optional (P.$$$ "(" |--
   256         ((P.$$$ "open" >> K false) -- Scan.option P.binding ||
   257           P.binding >> (fn s => (true, SOME s))) --| P.$$$ ")") (true, NONE) --
   258       (P.type_args -- P.binding) -- P.opt_mixfix -- (P.$$$ "=" |-- P.term) --
   259       Scan.option (P.$$$ "morphisms" |-- P.!!! (P.binding -- P.binding))
   260     >> (fn ((((((def, opt_name), (vs, t)), mx), A), morphs)) =>
   261         Toplevel.print o Toplevel.theory_to_proof
   262           (typedef_cmd ((def, the_default t opt_name), (t, vs, mx), A, morphs))));
   263 
   264 end;
   265 
   266 val setup = Typedef_Interpretation.init;
   267 
   268 end;