src/Tools/code/code_funcgr.ML
author haftmann
Tue Jul 15 16:02:07 2008 +0200 (2008-07-15)
changeset 27609 b23c9ad0fe7d
parent 27103 d8549f4d900b
child 28054 2b84d34c5d02
permissions -rw-r--r--
tuned code theorem bookkeeping
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@24423
    12
  val funcs: T -> string -> thm list
haftmann@26971
    13
  val typ: T -> string -> (string * sort) list * typ
haftmann@24423
    14
  val all: T -> string list
haftmann@24219
    15
  val pretty: theory -> T -> Pretty.T
haftmann@24423
    16
  val make: theory -> string list -> T
haftmann@26740
    17
  val eval_conv: theory -> (term -> term * (T -> term -> thm)) -> cterm -> thm
haftmann@26740
    18
  val eval_term: theory -> (term -> term * (T -> term -> 'a)) -> term -> 'a
haftmann@26971
    19
  val timing: bool ref
haftmann@24219
    20
end
haftmann@24219
    21
haftmann@24283
    22
structure CodeFuncgr : CODE_FUNCGR =
haftmann@24219
    23
struct
haftmann@24219
    24
haftmann@24219
    25
(** the graph type **)
haftmann@24219
    26
haftmann@26971
    27
type T = (((string * sort) list * typ) * thm list) Graph.T;
haftmann@24219
    28
haftmann@24219
    29
fun funcs funcgr =
haftmann@24423
    30
  these o Option.map snd o try (Graph.get_node funcgr);
haftmann@24219
    31
haftmann@24219
    32
fun typ funcgr =
haftmann@24423
    33
  fst o Graph.get_node funcgr;
haftmann@24219
    34
haftmann@24423
    35
fun all funcgr = Graph.keys funcgr;
haftmann@24219
    36
haftmann@24219
    37
fun pretty thy funcgr =
haftmann@24423
    38
  AList.make (snd o Graph.get_node funcgr) (Graph.keys funcgr)
haftmann@24219
    39
  |> (map o apfst) (CodeUnit.string_of_const thy)
haftmann@24219
    40
  |> sort (string_ord o pairself fst)
haftmann@24219
    41
  |> map (fn (s, thms) =>
haftmann@24219
    42
       (Pretty.block o Pretty.fbreaks) (
haftmann@24219
    43
         Pretty.str s
haftmann@24219
    44
         :: map Display.pretty_thm thms
haftmann@24219
    45
       ))
haftmann@24219
    46
  |> Pretty.chunks;
haftmann@24219
    47
haftmann@24219
    48
haftmann@24219
    49
(** generic combinators **)
haftmann@24219
    50
haftmann@24219
    51
fun fold_consts f thms =
haftmann@24219
    52
  thms
haftmann@24219
    53
  |> maps (op :: o swap o apfst (snd o strip_comb) o Logic.dest_equals o Thm.plain_prop_of)
haftmann@24219
    54
  |> (fold o fold_aterms) (fn Const c => f c | _ => I);
haftmann@24219
    55
haftmann@24219
    56
fun consts_of (const, []) = []
haftmann@24423
    57
  | consts_of (const, thms as _ :: _) = 
haftmann@24219
    58
      let
haftmann@24423
    59
        fun the_const (c, _) = if c = const then I else insert (op =) c
haftmann@24219
    60
      in fold_consts the_const thms [] end;
haftmann@24219
    61
haftmann@26971
    62
fun insts_of thy algebra tys sorts =
haftmann@24219
    63
  let
haftmann@24219
    64
    fun class_relation (x, _) _ = x;
haftmann@24219
    65
    fun type_constructor tyco xs class =
haftmann@26971
    66
      (tyco, class) :: (maps o maps) fst xs;
haftmann@24219
    67
    fun type_variable (TVar (_, sort)) = map (pair []) sort
haftmann@24219
    68
      | type_variable (TFree (_, sort)) = map (pair []) sort;
haftmann@26971
    69
    fun of_sort_deriv ty sort =
wenzelm@26939
    70
      Sorts.of_sort_derivation (Syntax.pp_global thy) algebra
haftmann@24219
    71
        { class_relation = class_relation, type_constructor = type_constructor,
haftmann@24219
    72
          type_variable = type_variable }
haftmann@26517
    73
        (ty, sort) handle Sorts.CLASS_ERROR _ => [] (*permissive!*)
haftmann@26971
    74
  in (flat o flat) (map2 of_sort_deriv tys sorts) end;
haftmann@24219
    75
haftmann@26971
    76
fun meets_of thy algebra =
haftmann@24219
    77
  let
haftmann@26971
    78
    fun meet_of ty sort tab =
haftmann@26971
    79
      Sorts.meet_sort algebra (ty, sort) tab
haftmann@26971
    80
        handle Sorts.CLASS_ERROR _ => tab (*permissive!*);
haftmann@26971
    81
  in fold2 meet_of end;
haftmann@24219
    82
haftmann@24219
    83
haftmann@24219
    84
(** graph algorithm **)
haftmann@24219
    85
haftmann@24219
    86
val timing = ref false;
haftmann@24219
    87
haftmann@24219
    88
local
haftmann@24219
    89
haftmann@26971
    90
fun resort_thms thy algebra typ_of thms =
haftmann@26971
    91
  let
haftmann@26971
    92
    val cs = fold_consts (insert (op =)) thms [];
haftmann@26971
    93
    fun meets (c, ty) = case typ_of c
haftmann@26971
    94
       of SOME (vs, _) =>
haftmann@26971
    95
            meets_of thy algebra (Sign.const_typargs thy (c, ty)) (map snd vs)
haftmann@26971
    96
        | NONE => I;
haftmann@26971
    97
    val tab = fold meets cs Vartab.empty;
haftmann@26971
    98
  in map (CodeUnit.inst_thm tab) thms end;
haftmann@24219
    99
haftmann@24219
   100
fun resort_funcss thy algebra funcgr =
haftmann@24219
   101
  let
haftmann@24423
   102
    val typ_funcgr = try (fst o Graph.get_node funcgr);
haftmann@26971
   103
    val resort_dep = apsnd (resort_thms thy algebra typ_funcgr);
haftmann@26997
   104
    fun resort_rec typ_of (c, []) = (true, (c, []))
haftmann@26997
   105
      | resort_rec typ_of (c, thms as thm :: _) = if is_some (AxClass.inst_of_param thy c)
haftmann@26997
   106
          then (true, (c, thms))
haftmann@26997
   107
          else let
haftmann@26971
   108
            val (_, (vs, ty)) = CodeUnit.head_func thm;
haftmann@26971
   109
            val thms' as thm' :: _ = resort_thms thy algebra typ_of thms
haftmann@26971
   110
            val (_, (vs', ty')) = CodeUnit.head_func thm'; (*FIXME simplify check*)
haftmann@26997
   111
          in (Sign.typ_equiv thy (ty, ty'), (c, thms')) end;
haftmann@24219
   112
    fun resort_recs funcss =
haftmann@24219
   113
      let
haftmann@26971
   114
        fun typ_of c = case these (AList.lookup (op =) funcss c)
haftmann@26971
   115
         of thm :: _ => (SOME o snd o CodeUnit.head_func) thm
haftmann@26971
   116
          | [] => NONE;
haftmann@26971
   117
        val (unchangeds, funcss') = split_list (map (resort_rec typ_of) funcss);
haftmann@24219
   118
        val unchanged = fold (fn x => fn y => x andalso y) unchangeds true;
haftmann@24219
   119
      in (unchanged, funcss') end;
haftmann@24219
   120
    fun resort_rec_until funcss =
haftmann@24219
   121
      let
haftmann@24219
   122
        val (unchanged, funcss') = resort_recs funcss;
haftmann@24219
   123
      in if unchanged then funcss' else resort_rec_until funcss' end;
haftmann@24219
   124
  in map resort_dep #> resort_rec_until end;
haftmann@24219
   125
haftmann@24219
   126
fun instances_of thy algebra insts =
haftmann@24219
   127
  let
haftmann@24219
   128
    val thy_classes = (#classes o Sorts.rep_algebra o Sign.classes_of) thy;
haftmann@24835
   129
    fun all_classparams tyco class =
wenzelm@24969
   130
      these (try (#params o AxClass.get_info thy) class)
haftmann@26517
   131
      |> map_filter (fn (c, _) => try (AxClass.param_of_inst thy) (c, tyco))
haftmann@24219
   132
  in
haftmann@24219
   133
    Symtab.empty
haftmann@24219
   134
    |> fold (fn (tyco, class) =>
haftmann@24219
   135
        Symtab.map_default (tyco, []) (insert (op =) class)) insts
haftmann@24835
   136
    |> (fn tab => Symtab.fold (fn (tyco, classes) => append (maps (all_classparams tyco)
haftmann@24219
   137
         (Graph.all_succs thy_classes classes))) tab [])
haftmann@24219
   138
  end;
haftmann@24219
   139
haftmann@24219
   140
fun instances_of_consts thy algebra funcgr consts =
haftmann@24219
   141
  let
haftmann@26971
   142
    fun inst (cexpr as (c, ty)) = insts_of thy algebra
haftmann@26971
   143
      (Sign.const_typargs thy (c, ty)) ((map snd o fst) (typ funcgr c));
haftmann@24219
   144
  in
haftmann@24219
   145
    []
haftmann@24219
   146
    |> fold (fold (insert (op =)) o inst) consts
haftmann@24219
   147
    |> instances_of thy algebra
haftmann@24219
   148
  end;
haftmann@24219
   149
haftmann@24283
   150
fun ensure_const' thy algebra funcgr const auxgr =
haftmann@24423
   151
  if can (Graph.get_node funcgr) const
haftmann@24219
   152
    then (NONE, auxgr)
haftmann@24423
   153
  else if can (Graph.get_node auxgr) const
haftmann@24219
   154
    then (SOME const, auxgr)
haftmann@24219
   155
  else if is_some (Code.get_datatype_of_constr thy const) then
haftmann@24219
   156
    auxgr
haftmann@24423
   157
    |> Graph.new_node (const, [])
haftmann@24219
   158
    |> pair (SOME const)
haftmann@24219
   159
  else let
haftmann@24219
   160
    val thms = Code.these_funcs thy const
haftmann@24219
   161
      |> CodeUnit.norm_args
haftmann@24219
   162
      |> CodeUnit.norm_varnames CodeName.purify_tvar CodeName.purify_var;
haftmann@24219
   163
    val rhs = consts_of (const, thms);
haftmann@24219
   164
  in
haftmann@24219
   165
    auxgr
haftmann@24423
   166
    |> Graph.new_node (const, thms)
haftmann@24283
   167
    |> fold_map (ensure_const thy algebra funcgr) rhs
haftmann@24423
   168
    |-> (fn rhs' => fold (fn SOME const' => Graph.add_edge (const, const')
haftmann@24219
   169
                           | NONE => I) rhs')
haftmann@24219
   170
    |> pair (SOME const)
haftmann@24219
   171
  end
haftmann@24283
   172
and ensure_const thy algebra funcgr const =
haftmann@24219
   173
  let
haftmann@24219
   174
    val timeap = if !timing
haftmann@24219
   175
      then Output.timeap_msg ("time for " ^ CodeUnit.string_of_const thy const)
haftmann@24219
   176
      else I;
haftmann@24283
   177
  in timeap (ensure_const' thy algebra funcgr const) end;
haftmann@24219
   178
haftmann@24283
   179
fun merge_funcss thy algebra raw_funcss funcgr =
haftmann@24219
   180
  let
haftmann@24219
   181
    val funcss = raw_funcss
haftmann@24219
   182
      |> resort_funcss thy algebra funcgr
haftmann@24423
   183
      |> filter_out (can (Graph.get_node funcgr) o fst);
haftmann@24423
   184
    fun typ_func c [] = Code.default_typ thy c
haftmann@26997
   185
      | typ_func c (thms as thm :: _) = (snd o CodeUnit.head_func) thm;
haftmann@24219
   186
    fun add_funcs (const, thms) =
haftmann@24423
   187
      Graph.new_node (const, (typ_func const thms, thms));
haftmann@24219
   188
    fun add_deps (funcs as (const, thms)) funcgr =
haftmann@24219
   189
      let
haftmann@24219
   190
        val deps = consts_of funcs;
haftmann@24219
   191
        val insts = instances_of_consts thy algebra funcgr
haftmann@24219
   192
          (fold_consts (insert (op =)) thms []);
haftmann@24219
   193
      in
haftmann@24219
   194
        funcgr
haftmann@26997
   195
        |> ensure_consts thy algebra insts
haftmann@24423
   196
        |> fold (curry Graph.add_edge const) deps
haftmann@24423
   197
        |> fold (curry Graph.add_edge const) insts
haftmann@24219
   198
       end;
haftmann@24219
   199
  in
haftmann@24219
   200
    funcgr
haftmann@24219
   201
    |> fold add_funcs funcss
haftmann@24219
   202
    |> fold add_deps funcss
haftmann@24219
   203
  end
haftmann@26997
   204
and ensure_consts thy algebra cs funcgr =
haftmann@24219
   205
  let
haftmann@24423
   206
    val auxgr = Graph.empty
haftmann@24283
   207
      |> fold (snd oo ensure_const thy algebra funcgr) cs;
haftmann@24219
   208
  in
haftmann@24219
   209
    funcgr
haftmann@24283
   210
    |> fold (merge_funcss thy algebra)
haftmann@24423
   211
         (map (AList.make (Graph.get_node auxgr))
haftmann@24423
   212
         (rev (Graph.strong_conn auxgr)))
haftmann@26997
   213
  end;
haftmann@24219
   214
haftmann@24219
   215
in
haftmann@24219
   216
haftmann@24219
   217
(** retrieval interfaces **)
haftmann@24219
   218
haftmann@26997
   219
val ensure_consts = ensure_consts;
haftmann@24219
   220
haftmann@26740
   221
fun proto_eval thy cterm_of evaluator_fr evaluator proto_ct funcgr =
haftmann@24219
   222
  let
haftmann@26740
   223
    val ct = cterm_of proto_ct;
wenzelm@26939
   224
    val _ = Sign.no_vars (Syntax.pp_global thy) (Thm.term_of ct);
haftmann@24219
   225
    val _ = Term.fold_types (Type.no_tvars #> K I) (Thm.term_of ct) ();
haftmann@26740
   226
    fun consts_of t = fold_aterms (fn Const c_ty => cons c_ty | _ => I)
haftmann@26740
   227
      t [];
haftmann@26740
   228
    val algebra = Code.coregular_algebra thy;
haftmann@26740
   229
    val thm = Code.preprocess_conv ct;
haftmann@26740
   230
    val ct' = Thm.rhs_of thm;
haftmann@26740
   231
    val t' = Thm.term_of ct';
haftmann@26740
   232
    val consts = map fst (consts_of t');
haftmann@26740
   233
    val funcgr' = ensure_consts thy algebra consts funcgr;
haftmann@26740
   234
    val (t'', evaluator') = apsnd evaluator_fr (evaluator t');
haftmann@26740
   235
    val consts' = consts_of t'';
haftmann@26740
   236
    val dicts = instances_of_consts thy algebra funcgr' consts';
haftmann@26740
   237
    val funcgr'' = ensure_consts thy algebra dicts funcgr';
haftmann@26740
   238
  in (evaluator' thm funcgr'' t'', funcgr'') end;
haftmann@26740
   239
haftmann@26740
   240
fun proto_eval_conv thy =
haftmann@26740
   241
  let
haftmann@26740
   242
    fun evaluator evaluator' thm1 funcgr t =
haftmann@24219
   243
      let
haftmann@26740
   244
        val thm2 = evaluator' funcgr t;
haftmann@24219
   245
        val thm3 = Code.postprocess_conv (Thm.rhs_of thm2);
haftmann@24219
   246
      in
haftmann@26740
   247
        Thm.transitive thm1 (Thm.transitive thm2 thm3) handle THM _ =>
haftmann@26971
   248
          error ("could not construct evaluation proof:\n"
wenzelm@26928
   249
          ^ (cat_lines o map Display.string_of_thm) [thm1, thm2, thm3])
haftmann@24219
   250
      end;
haftmann@26740
   251
  in proto_eval thy I evaluator end;
haftmann@24283
   252
haftmann@26740
   253
fun proto_eval_term thy =
haftmann@24283
   254
  let
haftmann@26740
   255
    fun evaluator evaluator' _ funcgr t = evaluator' funcgr t;
haftmann@26740
   256
  in proto_eval thy (Thm.cterm_of thy) evaluator end;
haftmann@24219
   257
haftmann@24219
   258
end; (*local*)
haftmann@24219
   259
haftmann@24219
   260
structure Funcgr = CodeDataFun
wenzelm@24713
   261
(
haftmann@24219
   262
  type T = T;
haftmann@24423
   263
  val empty = Graph.empty;
haftmann@27609
   264
  fun purge _ cs funcgr =
haftmann@27609
   265
    Graph.del_nodes ((Graph.all_preds funcgr 
haftmann@27609
   266
      o filter (can (Graph.get_node funcgr))) cs) funcgr;
wenzelm@24713
   267
);
haftmann@24219
   268
haftmann@24219
   269
fun make thy =
haftmann@24423
   270
  Funcgr.change thy o ensure_consts thy (Code.coregular_algebra thy);
haftmann@24219
   271
haftmann@24219
   272
fun eval_conv thy f =
haftmann@26740
   273
  fst o Funcgr.change_yield thy o proto_eval_conv thy f;
haftmann@24283
   274
haftmann@24283
   275
fun eval_term thy f =
haftmann@26740
   276
  fst o Funcgr.change_yield thy o proto_eval_term thy f;
haftmann@24219
   277
haftmann@27103
   278
haftmann@27103
   279
(** diagnostic commands **)
haftmann@27103
   280
haftmann@27103
   281
fun code_depgr thy [] = make thy []
haftmann@27103
   282
  | code_depgr thy consts =
haftmann@27103
   283
      let
haftmann@27103
   284
        val gr = make thy consts;
haftmann@27103
   285
        val select = Graph.all_succs gr consts;
haftmann@27103
   286
      in
haftmann@27103
   287
        gr
haftmann@27103
   288
        |> Graph.subgraph (member (op =) select) 
haftmann@27103
   289
        |> Graph.map_nodes ((apsnd o map) (AxClass.overload thy))
haftmann@27103
   290
      end;
haftmann@27103
   291
haftmann@27103
   292
fun code_thms thy = Pretty.writeln o pretty thy o code_depgr thy;
haftmann@27103
   293
haftmann@27103
   294
fun code_deps thy consts =
haftmann@27103
   295
  let
haftmann@27103
   296
    val gr = code_depgr thy consts;
haftmann@27103
   297
    fun mk_entry (const, (_, (_, parents))) =
haftmann@27103
   298
      let
haftmann@27103
   299
        val name = CodeUnit.string_of_const thy const;
haftmann@27103
   300
        val nameparents = map (CodeUnit.string_of_const thy) parents;
haftmann@27103
   301
      in { name = name, ID = name, dir = "", unfold = true,
haftmann@27103
   302
        path = "", parents = nameparents }
haftmann@27103
   303
      end;
haftmann@27103
   304
    val prgr = Graph.fold ((fn x => fn xs => xs @ [x]) o mk_entry) gr [];
haftmann@27103
   305
  in Present.display_graph prgr end;
haftmann@27103
   306
haftmann@27103
   307
local
haftmann@27103
   308
haftmann@27103
   309
structure P = OuterParse
haftmann@27103
   310
and K = OuterKeyword
haftmann@27103
   311
haftmann@27103
   312
fun code_thms_cmd thy = code_thms thy o op @ o CodeName.read_const_exprs thy;
haftmann@27103
   313
fun code_deps_cmd thy = code_deps thy o op @ o CodeName.read_const_exprs thy;
haftmann@27103
   314
haftmann@27103
   315
in
haftmann@27103
   316
haftmann@27103
   317
val _ =
haftmann@27103
   318
  OuterSyntax.improper_command "code_thms" "print system of defining equations for code" OuterKeyword.diag
haftmann@27103
   319
    (Scan.repeat P.term
haftmann@27103
   320
      >> (fn cs => Toplevel.no_timing o Toplevel.unknown_theory
haftmann@27103
   321
        o Toplevel.keep ((fn thy => code_thms_cmd thy cs) o Toplevel.theory_of)));
haftmann@27103
   322
haftmann@27103
   323
val _ =
haftmann@27103
   324
  OuterSyntax.improper_command "code_deps" "visualize dependencies of defining equations for code" OuterKeyword.diag
haftmann@27103
   325
    (Scan.repeat P.term
haftmann@27103
   326
      >> (fn cs => Toplevel.no_timing o Toplevel.unknown_theory
haftmann@27103
   327
        o Toplevel.keep ((fn thy => code_deps_cmd thy cs) o Toplevel.theory_of)));
haftmann@27103
   328
haftmann@27103
   329
end;
haftmann@27103
   330
haftmann@24219
   331
end; (*struct*)