src/Tools/code/code_funcgr.ML
author wenzelm
Sun Apr 13 16:40:08 2008 +0200 (2008-04-13)
changeset 26642 454d11701fa4
parent 26517 ef036a63f6e9
child 26740 6c8cd101f875
permissions -rw-r--r--
Sorts.class_error: produce message only (formerly msg_class_error);
haftmann@24219
     1
(*  Title:      Tools/code/code_funcgr.ML
haftmann@24219
     2
    ID:         $Id$
haftmann@24219
     3
    Author:     Florian Haftmann, TU Muenchen
haftmann@24219
     4
haftmann@24219
     5
Retrieving, normalizing and structuring defining equations in graph
haftmann@24219
     6
with explicit dependencies.
haftmann@24219
     7
*)
haftmann@24219
     8
haftmann@24219
     9
signature CODE_FUNCGR =
haftmann@24219
    10
sig
haftmann@24219
    11
  type T
haftmann@24219
    12
  val timing: bool ref
haftmann@24423
    13
  val funcs: T -> string -> thm list
haftmann@24423
    14
  val typ: T -> string -> typ
haftmann@24423
    15
  val all: T -> string list
haftmann@24219
    16
  val pretty: theory -> T -> Pretty.T
haftmann@24423
    17
  val make: theory -> string list -> T
haftmann@24423
    18
  val make_consts: theory -> string list -> string list * T
haftmann@24283
    19
  val eval_conv: theory -> (T -> cterm -> thm) -> cterm -> thm
haftmann@24835
    20
  val eval_term: theory -> (T -> term -> 'a) -> term -> 'a
haftmann@24219
    21
end
haftmann@24219
    22
haftmann@24283
    23
structure CodeFuncgr : CODE_FUNCGR =
haftmann@24219
    24
struct
haftmann@24219
    25
haftmann@24219
    26
(** the graph type **)
haftmann@24219
    27
haftmann@24423
    28
type T = (typ * thm list) Graph.T;
haftmann@24219
    29
haftmann@24219
    30
fun funcs funcgr =
haftmann@24423
    31
  these o Option.map snd o try (Graph.get_node funcgr);
haftmann@24219
    32
haftmann@24219
    33
fun typ funcgr =
haftmann@24423
    34
  fst o Graph.get_node funcgr;
haftmann@24219
    35
haftmann@24423
    36
fun all funcgr = Graph.keys funcgr;
haftmann@24219
    37
haftmann@24219
    38
fun pretty thy funcgr =
haftmann@24423
    39
  AList.make (snd o Graph.get_node funcgr) (Graph.keys funcgr)
haftmann@24219
    40
  |> (map o apfst) (CodeUnit.string_of_const thy)
haftmann@24219
    41
  |> sort (string_ord o pairself fst)
haftmann@24219
    42
  |> map (fn (s, thms) =>
haftmann@24219
    43
       (Pretty.block o Pretty.fbreaks) (
haftmann@24219
    44
         Pretty.str s
haftmann@24219
    45
         :: map Display.pretty_thm thms
haftmann@24219
    46
       ))
haftmann@24219
    47
  |> Pretty.chunks;
haftmann@24219
    48
haftmann@24219
    49
haftmann@24219
    50
(** generic combinators **)
haftmann@24219
    51
haftmann@24219
    52
fun fold_consts f thms =
haftmann@24219
    53
  thms
haftmann@24219
    54
  |> maps (op :: o swap o apfst (snd o strip_comb) o Logic.dest_equals o Thm.plain_prop_of)
haftmann@24219
    55
  |> (fold o fold_aterms) (fn Const c => f c | _ => I);
haftmann@24219
    56
haftmann@24219
    57
fun consts_of (const, []) = []
haftmann@24423
    58
  | consts_of (const, thms as _ :: _) = 
haftmann@24219
    59
      let
haftmann@24423
    60
        fun the_const (c, _) = if c = const then I else insert (op =) c
haftmann@24219
    61
      in fold_consts the_const thms [] end;
haftmann@24219
    62
haftmann@24219
    63
fun insts_of thy algebra c ty_decl ty =
haftmann@24219
    64
  let
haftmann@24219
    65
    val tys_decl = Sign.const_typargs thy (c, ty_decl);
haftmann@24219
    66
    val tys = Sign.const_typargs thy (c, ty);
haftmann@24219
    67
    fun class_relation (x, _) _ = x;
haftmann@24219
    68
    fun type_constructor tyco xs class =
haftmann@24219
    69
      (tyco, class) :: maps (maps fst) xs;
haftmann@24219
    70
    fun type_variable (TVar (_, sort)) = map (pair []) sort
haftmann@24219
    71
      | type_variable (TFree (_, sort)) = map (pair []) sort;
haftmann@24219
    72
    fun mk_inst ty (TVar (_, sort)) = cons (ty, sort)
haftmann@24219
    73
      | mk_inst ty (TFree (_, sort)) = cons (ty, sort)
haftmann@24219
    74
      | mk_inst (Type (_, tys1)) (Type (_, tys2)) = fold2 mk_inst tys1 tys2;
haftmann@24219
    75
    fun of_sort_deriv (ty, sort) =
haftmann@24219
    76
      Sorts.of_sort_derivation (Sign.pp thy) algebra
haftmann@24219
    77
        { class_relation = class_relation, type_constructor = type_constructor,
haftmann@24219
    78
          type_variable = type_variable }
haftmann@26517
    79
        (ty, sort) handle Sorts.CLASS_ERROR _ => [] (*permissive!*)
haftmann@24219
    80
  in
haftmann@24219
    81
    flat (maps of_sort_deriv (fold2 mk_inst tys tys_decl []))
haftmann@24219
    82
  end;
haftmann@24219
    83
haftmann@24219
    84
fun drop_classes thy tfrees thm =
haftmann@24219
    85
  let
haftmann@24219
    86
    val (_, thm') = Thm.varifyT' [] thm;
haftmann@24219
    87
    val tvars = Term.add_tvars (Thm.prop_of thm') [];
haftmann@24219
    88
    val unconstr = map (Thm.ctyp_of thy o TVar) tvars;
haftmann@24219
    89
    val instmap = map2 (fn (v_i, _) => fn (v, sort) => pairself (Thm.ctyp_of thy)
haftmann@24219
    90
      (TVar (v_i, []), TFree (v, sort))) tvars tfrees;
haftmann@24219
    91
  in
haftmann@24219
    92
    thm'
haftmann@24219
    93
    |> fold Thm.unconstrainT unconstr
haftmann@24219
    94
    |> Thm.instantiate (instmap, [])
haftmann@24219
    95
    |> Tactic.rule_by_tactic ((REPEAT o CHANGED o ALLGOALS o Tactic.resolve_tac) (AxClass.class_intros thy))
haftmann@24219
    96
  end;
haftmann@24219
    97
haftmann@24219
    98
haftmann@24219
    99
(** graph algorithm **)
haftmann@24219
   100
haftmann@24219
   101
val timing = ref false;
haftmann@24219
   102
haftmann@24219
   103
local
haftmann@24219
   104
haftmann@26331
   105
exception CLASS_ERROR of string list * string;
haftmann@24219
   106
haftmann@24219
   107
fun resort_thms algebra tap_typ [] = []
haftmann@24219
   108
  | resort_thms algebra tap_typ (thms as thm :: _) =
haftmann@24219
   109
      let
haftmann@24219
   110
        val thy = Thm.theory_of_thm thm;
haftmann@26331
   111
        val pp = Sign.pp thy;
haftmann@24219
   112
        val cs = fold_consts (insert (op =)) thms [];
haftmann@24219
   113
        fun match_const c (ty, ty_decl) =
haftmann@24219
   114
          let
haftmann@24423
   115
            val tys = Sign.const_typargs thy (c, ty);
haftmann@24423
   116
            val sorts = map (snd o dest_TVar) (Sign.const_typargs thy (c, ty_decl));
haftmann@26517
   117
          in fn tab => fold2 (curry (Sorts.meet_sort algebra)) tys sorts tab
wenzelm@26642
   118
            handle Sorts.CLASS_ERROR e => raise CLASS_ERROR ([c], Sorts.class_error pp e ^ ",\n"
haftmann@26331
   119
              ^ "for constant " ^ CodeUnit.string_of_const thy c
haftmann@26331
   120
              ^ "\nin defining equations(s)\n"
haftmann@26331
   121
              ^ (cat_lines o map string_of_thm) thms)
haftmann@26517
   122
            (*handle Sorts.CLASS_ERROR _ => tab (*permissive!*)*)
haftmann@26331
   123
          end;
haftmann@26517
   124
        fun match (c, ty) = case tap_typ c
haftmann@24219
   125
           of SOME ty_decl => match_const c (ty, ty_decl)
haftmann@24219
   126
            | NONE => I;
haftmann@24219
   127
        val tvars = fold match cs Vartab.empty;
haftmann@24219
   128
      in map (CodeUnit.inst_thm tvars) thms end;
haftmann@24219
   129
haftmann@24219
   130
fun resort_funcss thy algebra funcgr =
haftmann@24219
   131
  let
haftmann@24423
   132
    val typ_funcgr = try (fst o Graph.get_node funcgr);
haftmann@26331
   133
    val resort_dep = apsnd (resort_thms algebra typ_funcgr);
haftmann@24219
   134
    fun resort_rec tap_typ (const, []) = (true, (const, []))
haftmann@24219
   135
      | resort_rec tap_typ (const, thms as thm :: _) =
haftmann@24219
   136
          let
haftmann@24219
   137
            val (_, ty) = CodeUnit.head_func thm;
haftmann@24219
   138
            val thms' as thm' :: _ = resort_thms algebra tap_typ thms
haftmann@24219
   139
            val (_, ty') = CodeUnit.head_func thm';
haftmann@24219
   140
          in (Sign.typ_equiv thy (ty, ty'), (const, thms')) end;
haftmann@24219
   141
    fun resort_recs funcss =
haftmann@24219
   142
      let
haftmann@24423
   143
        fun tap_typ c =
haftmann@24423
   144
          AList.lookup (op =) funcss c
haftmann@24423
   145
          |> these
haftmann@24423
   146
          |> try hd
haftmann@24423
   147
          |> Option.map (snd o CodeUnit.head_func);
haftmann@24219
   148
        val (unchangeds, funcss') = split_list (map (resort_rec tap_typ) funcss);
haftmann@24219
   149
        val unchanged = fold (fn x => fn y => x andalso y) unchangeds true;
haftmann@24219
   150
      in (unchanged, funcss') end;
haftmann@24219
   151
    fun resort_rec_until funcss =
haftmann@24219
   152
      let
haftmann@24219
   153
        val (unchanged, funcss') = resort_recs funcss;
haftmann@24219
   154
      in if unchanged then funcss' else resort_rec_until funcss' end;
haftmann@24219
   155
  in map resort_dep #> resort_rec_until end;
haftmann@24219
   156
haftmann@24219
   157
fun instances_of thy algebra insts =
haftmann@24219
   158
  let
haftmann@24219
   159
    val thy_classes = (#classes o Sorts.rep_algebra o Sign.classes_of) thy;
haftmann@24835
   160
    fun all_classparams tyco class =
wenzelm@24969
   161
      these (try (#params o AxClass.get_info thy) class)
haftmann@26517
   162
      |> map_filter (fn (c, _) => try (AxClass.param_of_inst thy) (c, tyco))
haftmann@24219
   163
  in
haftmann@24219
   164
    Symtab.empty
haftmann@24219
   165
    |> fold (fn (tyco, class) =>
haftmann@24219
   166
        Symtab.map_default (tyco, []) (insert (op =) class)) insts
haftmann@24835
   167
    |> (fn tab => Symtab.fold (fn (tyco, classes) => append (maps (all_classparams tyco)
haftmann@24219
   168
         (Graph.all_succs thy_classes classes))) tab [])
haftmann@24219
   169
  end;
haftmann@24219
   170
haftmann@24219
   171
fun instances_of_consts thy algebra funcgr consts =
haftmann@24219
   172
  let
haftmann@24219
   173
    fun inst (cexpr as (c, ty)) = insts_of thy algebra c
haftmann@26517
   174
      ((fst o Graph.get_node funcgr) c) ty;
haftmann@24219
   175
  in
haftmann@24219
   176
    []
haftmann@24219
   177
    |> fold (fold (insert (op =)) o inst) consts
haftmann@24219
   178
    |> instances_of thy algebra
haftmann@24219
   179
  end;
haftmann@24219
   180
haftmann@24283
   181
fun ensure_const' thy algebra funcgr const auxgr =
haftmann@24423
   182
  if can (Graph.get_node funcgr) const
haftmann@24219
   183
    then (NONE, auxgr)
haftmann@24423
   184
  else if can (Graph.get_node auxgr) const
haftmann@24219
   185
    then (SOME const, auxgr)
haftmann@24219
   186
  else if is_some (Code.get_datatype_of_constr thy const) then
haftmann@24219
   187
    auxgr
haftmann@24423
   188
    |> Graph.new_node (const, [])
haftmann@24219
   189
    |> pair (SOME const)
haftmann@24219
   190
  else let
haftmann@24219
   191
    val thms = Code.these_funcs thy const
haftmann@24219
   192
      |> CodeUnit.norm_args
haftmann@24219
   193
      |> CodeUnit.norm_varnames CodeName.purify_tvar CodeName.purify_var;
haftmann@24219
   194
    val rhs = consts_of (const, thms);
haftmann@24219
   195
  in
haftmann@24219
   196
    auxgr
haftmann@24423
   197
    |> Graph.new_node (const, thms)
haftmann@24283
   198
    |> fold_map (ensure_const thy algebra funcgr) rhs
haftmann@24423
   199
    |-> (fn rhs' => fold (fn SOME const' => Graph.add_edge (const, const')
haftmann@24219
   200
                           | NONE => I) rhs')
haftmann@24219
   201
    |> pair (SOME const)
haftmann@24219
   202
  end
haftmann@24283
   203
and ensure_const thy algebra funcgr const =
haftmann@24219
   204
  let
haftmann@24219
   205
    val timeap = if !timing
haftmann@24219
   206
      then Output.timeap_msg ("time for " ^ CodeUnit.string_of_const thy const)
haftmann@24219
   207
      else I;
haftmann@24283
   208
  in timeap (ensure_const' thy algebra funcgr const) end;
haftmann@24219
   209
haftmann@24283
   210
fun merge_funcss thy algebra raw_funcss funcgr =
haftmann@24219
   211
  let
haftmann@24219
   212
    val funcss = raw_funcss
haftmann@24219
   213
      |> resort_funcss thy algebra funcgr
haftmann@24423
   214
      |> filter_out (can (Graph.get_node funcgr) o fst);
haftmann@24423
   215
    fun typ_func c [] = Code.default_typ thy c
haftmann@25597
   216
      | typ_func c (thms as thm :: _) = case AxClass.inst_of_param thy c
haftmann@24423
   217
         of SOME (c', tyco) => 
haftmann@24423
   218
              let
haftmann@24423
   219
                val (_, ty) = CodeUnit.head_func thm;
haftmann@24423
   220
                val SOME class = AxClass.class_of_param thy c';
haftmann@24423
   221
                val sorts_decl = Sorts.mg_domain algebra tyco [class];
haftmann@24423
   222
                val tys = Sign.const_typargs thy (c, ty);
haftmann@24423
   223
                val sorts = map (snd o dest_TVar) tys;
haftmann@24423
   224
              in if sorts = sorts_decl then ty
haftmann@26331
   225
                else raise CLASS_ERROR ([c], "Illegal instantation for class operation "
haftmann@24423
   226
                  ^ CodeUnit.string_of_const thy c
haftmann@24423
   227
                  ^ "\nin defining equations\n"
haftmann@26331
   228
                  ^ (cat_lines o map (string_of_thm o AxClass.overload thy)) thms)
haftmann@24423
   229
              end
haftmann@24423
   230
          | NONE => (snd o CodeUnit.head_func) thm;
haftmann@24219
   231
    fun add_funcs (const, thms) =
haftmann@24423
   232
      Graph.new_node (const, (typ_func const thms, thms));
haftmann@24219
   233
    fun add_deps (funcs as (const, thms)) funcgr =
haftmann@24219
   234
      let
haftmann@24219
   235
        val deps = consts_of funcs;
haftmann@24219
   236
        val insts = instances_of_consts thy algebra funcgr
haftmann@24219
   237
          (fold_consts (insert (op =)) thms []);
haftmann@24219
   238
      in
haftmann@24219
   239
        funcgr
haftmann@24283
   240
        |> ensure_consts' thy algebra insts
haftmann@24423
   241
        |> fold (curry Graph.add_edge const) deps
haftmann@24423
   242
        |> fold (curry Graph.add_edge const) insts
haftmann@24219
   243
       end;
haftmann@24219
   244
  in
haftmann@24219
   245
    funcgr
haftmann@24219
   246
    |> fold add_funcs funcss
haftmann@24219
   247
    |> fold add_deps funcss
haftmann@24219
   248
  end
haftmann@24283
   249
and ensure_consts' thy algebra cs funcgr =
haftmann@24219
   250
  let
haftmann@24423
   251
    val auxgr = Graph.empty
haftmann@24283
   252
      |> fold (snd oo ensure_const thy algebra funcgr) cs;
haftmann@24219
   253
  in
haftmann@24219
   254
    funcgr
haftmann@24283
   255
    |> fold (merge_funcss thy algebra)
haftmann@24423
   256
         (map (AList.make (Graph.get_node auxgr))
haftmann@24423
   257
         (rev (Graph.strong_conn auxgr)))
haftmann@26331
   258
  end handle CLASS_ERROR (cs', msg)
haftmann@26331
   259
    => raise CLASS_ERROR (fold (insert (op =)) cs' cs, msg);
haftmann@24219
   260
haftmann@24219
   261
in
haftmann@24219
   262
haftmann@24219
   263
(** retrieval interfaces **)
haftmann@24219
   264
haftmann@24423
   265
fun ensure_consts thy algebra consts funcgr =
haftmann@24423
   266
  ensure_consts' thy algebra consts funcgr
haftmann@26331
   267
    handle CLASS_ERROR (cs', msg) => error (msg ^ ",\nwhile preprocessing equations for constant(s) "
haftmann@24423
   268
    ^ commas (map (CodeUnit.string_of_const thy) cs'));
haftmann@24219
   269
haftmann@24283
   270
fun check_consts thy consts funcgr =
haftmann@24219
   271
  let
haftmann@24219
   272
    val algebra = Code.coregular_algebra thy;
haftmann@24219
   273
    fun try_const const funcgr =
haftmann@24283
   274
      (SOME const, ensure_consts' thy algebra [const] funcgr)
haftmann@26331
   275
      handle CLASS_ERROR (cs', msg) => (NONE, funcgr);
haftmann@24219
   276
    val (consts', funcgr') = fold_map try_const consts funcgr;
haftmann@24219
   277
  in (map_filter I consts', funcgr') end;
haftmann@24219
   278
haftmann@24423
   279
fun raw_eval thy f ct funcgr =
haftmann@24219
   280
  let
haftmann@24423
   281
    val algebra = Code.coregular_algebra thy;
haftmann@24423
   282
    fun consts_of ct = fold_aterms (fn Const c_ty => cons c_ty | _ => I)
haftmann@24423
   283
      (Thm.term_of ct) [];
haftmann@24219
   284
    val _ = Sign.no_vars (Sign.pp thy) (Thm.term_of ct);
haftmann@24219
   285
    val _ = Term.fold_types (Type.no_tvars #> K I) (Thm.term_of ct) ();
haftmann@24283
   286
    val thm1 = Code.preprocess_conv ct;
haftmann@24219
   287
    val ct' = Thm.rhs_of thm1;
haftmann@24423
   288
    val cs = map fst (consts_of ct');
haftmann@24423
   289
    val funcgr' = ensure_consts thy algebra cs funcgr;
haftmann@24219
   290
    val (_, thm2) = Thm.varifyT' [] thm1;
haftmann@24219
   291
    val thm3 = Thm.reflexive (Thm.rhs_of thm2);
haftmann@26331
   292
    val [thm4] = resort_thms algebra (try (fst o Graph.get_node funcgr')) [thm3]
haftmann@26331
   293
      handle CLASS_ERROR (_, msg) => error msg;
haftmann@24219
   294
    val tfrees = Term.add_tfrees (Thm.prop_of thm1) [];
haftmann@24219
   295
    fun inst thm =
haftmann@24219
   296
      let
haftmann@24219
   297
        val tvars = Term.add_tvars (Thm.prop_of thm) [];
haftmann@24219
   298
        val instmap = map2 (fn (v_i, sort) => fn (v, _) => pairself (Thm.ctyp_of thy)
haftmann@24219
   299
          (TVar (v_i, sort), TFree (v, sort))) tvars tfrees;
haftmann@24219
   300
      in Thm.instantiate (instmap, []) thm end;
haftmann@24219
   301
    val thm5 = inst thm2;
haftmann@24219
   302
    val thm6 = inst thm4;
haftmann@24219
   303
    val ct'' = Thm.rhs_of thm6;
haftmann@24423
   304
    val c_exprs = consts_of ct'';
haftmann@24219
   305
    val drop = drop_classes thy tfrees;
haftmann@24423
   306
    val instdefs = instances_of_consts thy algebra funcgr' c_exprs;
haftmann@24423
   307
    val funcgr'' = ensure_consts thy algebra instdefs funcgr';
haftmann@25103
   308
  in (f drop thm5 funcgr'' ct'', funcgr'') end;
haftmann@24219
   309
haftmann@24423
   310
fun raw_eval_conv thy conv =
haftmann@24219
   311
  let
haftmann@24423
   312
    fun conv' drop_classes thm1 funcgr ct =
haftmann@24219
   313
      let
haftmann@24219
   314
        val thm2 = conv funcgr ct;
haftmann@24219
   315
        val thm3 = Code.postprocess_conv (Thm.rhs_of thm2);
haftmann@24219
   316
        val thm23 = drop_classes (Thm.transitive thm2 thm3);
haftmann@24219
   317
      in
haftmann@24219
   318
        Thm.transitive thm1 thm23 handle THM _ =>
haftmann@24423
   319
          error ("could not construct proof:\n"
haftmann@24219
   320
          ^ (cat_lines o map string_of_thm) [thm1, thm2, thm3])
haftmann@24219
   321
      end;
haftmann@24423
   322
  in raw_eval thy conv' end;
haftmann@24283
   323
haftmann@24835
   324
fun raw_eval_term thy f t =
haftmann@24283
   325
  let
haftmann@24835
   326
    fun f' _ _ funcgr ct = f funcgr (Thm.term_of ct);
haftmann@24835
   327
  in raw_eval thy f' (Thm.cterm_of thy t) end;
haftmann@24219
   328
haftmann@24219
   329
end; (*local*)
haftmann@24219
   330
haftmann@24219
   331
structure Funcgr = CodeDataFun
wenzelm@24713
   332
(
haftmann@24219
   333
  type T = T;
haftmann@24423
   334
  val empty = Graph.empty;
haftmann@24423
   335
  fun merge _ _ = Graph.empty;
haftmann@24423
   336
  fun purge _ NONE _ = Graph.empty
haftmann@24219
   337
    | purge _ (SOME cs) funcgr =
haftmann@24423
   338
        Graph.del_nodes ((Graph.all_preds funcgr 
haftmann@24423
   339
          o filter (can (Graph.get_node funcgr))) cs) funcgr;
wenzelm@24713
   340
);
haftmann@24219
   341
haftmann@24219
   342
fun make thy =
haftmann@24423
   343
  Funcgr.change thy o ensure_consts thy (Code.coregular_algebra thy);
haftmann@24219
   344
haftmann@24219
   345
fun make_consts thy =
haftmann@24283
   346
  Funcgr.change_yield thy o check_consts thy;
haftmann@24219
   347
haftmann@24219
   348
fun eval_conv thy f =
haftmann@24423
   349
  fst o Funcgr.change_yield thy o raw_eval_conv thy f;
haftmann@24283
   350
haftmann@24283
   351
fun eval_term thy f =
haftmann@24423
   352
  fst o Funcgr.change_yield thy o raw_eval_term thy f;
haftmann@24219
   353
haftmann@24219
   354
end; (*struct*)