1 (* Title: Tools/code/code_funcgr.ML
2 Author: Florian Haftmann, TU Muenchen
4 Retrieving, normalizing and structuring code equations in graph
5 with explicit dependencies.
8 signature CODE_FUNCGR =
11 val eqns: T -> string -> (thm * bool) list
12 val typ: T -> string -> (string * sort) list * typ
13 val all: T -> string list
14 val pretty: theory -> T -> Pretty.T
15 val make: theory -> string list
16 -> ((sort -> sort) * Sorts.algebra) * T
18 -> (term -> term * (((sort -> sort) * Sorts.algebra) -> T -> thm)) -> cterm -> thm
20 -> (term -> term * (((sort -> sort) * Sorts.algebra) -> T -> 'a)) -> term -> 'a
24 structure Code_Funcgr : CODE_FUNCGR =
27 (** the graph type **)
29 type T = (((string * sort) list * typ) * (thm * bool) list) Graph.T;
32 these o Option.map snd o try (Graph.get_node funcgr);
35 fst o Graph.get_node funcgr;
37 fun all funcgr = Graph.keys funcgr;
39 fun pretty thy funcgr =
40 AList.make (snd o Graph.get_node funcgr) (Graph.keys funcgr)
41 |> (map o apfst) (Code_Unit.string_of_const thy)
42 |> sort (string_ord o pairself fst)
43 |> map (fn (s, thms) =>
44 (Pretty.block o Pretty.fbreaks) (
46 :: map (Display.pretty_thm o fst) thms
51 (** generic combinators **)
53 fun fold_consts f thms =
55 |> maps (op :: o swap o apfst (snd o strip_comb) o Logic.dest_equals o Thm.plain_prop_of)
56 |> (fold o fold_aterms) (fn Const c => f c | _ => I);
58 fun consts_of (const, []) = []
59 | consts_of (const, thms as _ :: _) =
61 fun the_const (c, _) = if c = const then I else insert (op =) c
62 in fold_consts the_const (map fst thms) [] end;
64 fun insts_of thy algebra tys sorts =
66 fun class_relation (x, _) _ = x;
67 fun type_constructor tyco xs class =
68 (tyco, class) :: (maps o maps) fst xs;
69 fun type_variable (TVar (_, sort)) = map (pair []) sort
70 | type_variable (TFree (_, sort)) = map (pair []) sort;
71 fun of_sort_deriv ty sort =
72 Sorts.of_sort_derivation (Syntax.pp_global thy) algebra
73 { class_relation = class_relation, type_constructor = type_constructor,
74 type_variable = type_variable }
75 (ty, sort) handle Sorts.CLASS_ERROR _ => [] (*permissive!*)
76 in (flat o flat) (map2 of_sort_deriv tys sorts) end;
78 fun meets_of thy algebra =
80 fun meet_of ty sort tab =
81 Sorts.meet_sort algebra (ty, sort) tab
82 handle Sorts.CLASS_ERROR _ => tab (*permissive!*);
86 (** graph algorithm **)
88 val timing = ref false;
92 fun resort_thms thy algebra typ_of thms =
94 val cs = fold_consts (insert (op =)) thms [];
95 fun meets (c, ty) = case typ_of c
97 meets_of thy algebra (Sign.const_typargs thy (c, ty)) (map snd vs)
99 val tab = fold meets cs Vartab.empty;
100 in map (Code_Unit.inst_thm thy tab) thms end;
102 fun resort_eqnss thy algebra funcgr =
104 val typ_funcgr = try (fst o Graph.get_node funcgr);
105 val resort_dep = (apsnd o burrow_fst) (resort_thms thy algebra typ_funcgr);
106 fun resort_rec typ_of (c, []) = (true, (c, []))
107 | resort_rec typ_of (c, thms as (thm, _) :: _) = if is_some (AxClass.inst_of_param thy c)
108 then (true, (c, thms))
110 val (_, (vs, ty)) = Code_Unit.head_eqn thy thm;
111 val thms' as (thm', _) :: _ = burrow_fst (resort_thms thy algebra typ_of) thms
112 val (_, (vs', ty')) = Code_Unit.head_eqn thy thm'; (*FIXME simplify check*)
113 in (Sign.typ_equiv thy (ty, ty'), (c, thms')) end;
114 fun resort_recs eqnss =
116 fun typ_of c = case these (AList.lookup (op =) eqnss c)
117 of (thm, _) :: _ => (SOME o snd o Code_Unit.head_eqn thy) thm
119 val (unchangeds, eqnss') = split_list (map (resort_rec typ_of) eqnss);
120 val unchanged = fold (fn x => fn y => x andalso y) unchangeds true;
121 in (unchanged, eqnss') end;
122 fun resort_rec_until eqnss =
124 val (unchanged, eqnss') = resort_recs eqnss;
125 in if unchanged then eqnss' else resort_rec_until eqnss' end;
126 in map resort_dep #> resort_rec_until end;
128 fun instances_of thy algebra insts =
130 val thy_classes = (#classes o Sorts.rep_algebra o Sign.classes_of) thy;
131 fun all_classparams tyco class =
132 these (try (#params o AxClass.get_info thy) class)
133 |> map_filter (fn (c, _) => try (AxClass.param_of_inst thy) (c, tyco))
136 |> fold (fn (tyco, class) =>
137 Symtab.map_default (tyco, []) (insert (op =) class)) insts
138 |> (fn tab => Symtab.fold (fn (tyco, classes) => append (maps (all_classparams tyco)
139 (Graph.all_succs thy_classes classes))) tab [])
142 fun instances_of_consts thy algebra funcgr consts =
144 fun inst (cexpr as (c, ty)) = insts_of thy algebra
145 (Sign.const_typargs thy (c, ty)) ((map snd o fst) (typ funcgr c));
148 |> fold (fold (insert (op =)) o inst) consts
149 |> instances_of thy algebra
152 fun ensure_const' thy algebra funcgr const auxgr =
153 if can (Graph.get_node funcgr) const
155 else if can (Graph.get_node auxgr) const
156 then (SOME const, auxgr)
157 else if is_some (Code.get_datatype_of_constr thy const) then
159 |> Graph.new_node (const, [])
162 val thms = Code.these_eqns thy const
163 |> burrow_fst (Code_Unit.norm_args thy)
164 |> burrow_fst (Code_Unit.norm_varnames thy Code_Name.purify_tvar Code_Name.purify_var);
165 val rhs = consts_of (const, thms);
168 |> Graph.new_node (const, thms)
169 |> fold_map (ensure_const thy algebra funcgr) rhs
170 |-> (fn rhs' => fold (fn SOME const' => Graph.add_edge (const, const')
174 and ensure_const thy algebra funcgr const =
176 val timeap = if !timing
177 then Output.timeap_msg ("time for " ^ Code_Unit.string_of_const thy const)
179 in timeap (ensure_const' thy algebra funcgr const) end;
181 fun merge_eqnss thy algebra raw_eqnss funcgr =
183 val eqnss = raw_eqnss
184 |> resort_eqnss thy algebra funcgr
185 |> filter_out (can (Graph.get_node funcgr) o fst);
186 fun typ_eqn c [] = Code.default_typscheme thy c
187 | typ_eqn c (thms as (thm, _) :: _) = (snd o Code_Unit.head_eqn thy) thm;
188 fun add_eqns (const, thms) =
189 Graph.new_node (const, (typ_eqn const thms, thms));
190 fun add_deps (eqns as (const, thms)) funcgr =
192 val deps = consts_of eqns;
193 val insts = instances_of_consts thy algebra funcgr
194 (fold_consts (insert (op =)) (map fst thms) []);
197 |> ensure_consts thy algebra insts
198 |> fold (curry Graph.add_edge const) deps
199 |> fold (curry Graph.add_edge const) insts
203 |> fold add_eqns eqnss
204 |> fold add_deps eqnss
206 and ensure_consts thy algebra cs funcgr =
208 val auxgr = Graph.empty
209 |> fold (snd oo ensure_const thy algebra funcgr) cs;
212 |> fold (merge_eqnss thy algebra)
213 (map (AList.make (Graph.get_node auxgr))
214 (rev (Graph.strong_conn auxgr)))
219 (** retrieval interfaces **)
221 val ensure_consts = ensure_consts;
223 fun proto_eval thy cterm_of evaluator_lift evaluator proto_ct funcgr =
225 val ct = cterm_of proto_ct;
226 val _ = Sign.no_vars (Syntax.pp_global thy) (Thm.term_of ct);
227 val _ = Term.fold_types (Type.no_tvars #> K I) (Thm.term_of ct) ();
229 fold_aterms (fn Const c_ty => cons c_ty | _ => I) t [];
230 val algebra = Code.coregular_algebra thy;
231 val thm = Code.preprocess_conv thy ct;
232 val ct' = Thm.rhs_of thm;
233 val t' = Thm.term_of ct';
234 val consts = map fst (consts_of t');
235 val funcgr' = ensure_consts thy algebra consts funcgr;
236 val (t'', evaluator_funcgr) = evaluator t';
237 val consts' = consts_of t'';
238 val dicts = instances_of_consts thy algebra funcgr' consts';
239 val funcgr'' = ensure_consts thy algebra dicts funcgr';
240 in (evaluator_lift (evaluator_funcgr (Code.operational_algebra thy)) thm funcgr'', funcgr'') end;
242 fun proto_eval_conv thy =
244 fun evaluator_lift evaluator thm1 funcgr =
246 val thm2 = evaluator funcgr;
247 val thm3 = Code.postprocess_conv thy (Thm.rhs_of thm2);
249 Thm.transitive thm1 (Thm.transitive thm2 thm3) handle THM _ =>
250 error ("could not construct evaluation proof:\n"
251 ^ (cat_lines o map Display.string_of_thm) [thm1, thm2, thm3])
253 in proto_eval thy I evaluator_lift end;
255 fun proto_eval_term thy =
257 fun evaluator_lift evaluator _ funcgr = evaluator funcgr;
258 in proto_eval thy (Thm.cterm_of thy) evaluator_lift end;
262 structure Funcgr = CodeDataFun
265 val empty = Graph.empty;
266 fun purge _ cs funcgr =
267 Graph.del_nodes ((Graph.all_preds funcgr
268 o filter (can (Graph.get_node funcgr))) cs) funcgr;
272 pair (Code.operational_algebra thy)
273 o Funcgr.change thy o ensure_consts thy (Code.coregular_algebra thy);
275 fun eval_conv thy f =
276 fst o Funcgr.change_yield thy o proto_eval_conv thy f;
278 fun eval_term thy f =
279 fst o Funcgr.change_yield thy o proto_eval_term thy f;
282 (** diagnostic commands **)
284 fun code_depgr thy consts =
286 val (_, gr) = make thy consts;
287 val select = Graph.all_succs gr consts;
290 |> not (null consts) ? Graph.subgraph (member (op =) select)
291 |> Graph.map_nodes ((apsnd o map o apfst) (AxClass.overload thy))
294 fun code_thms thy = Pretty.writeln o pretty thy o code_depgr thy;
296 fun code_deps thy consts =
298 val gr = code_depgr thy consts;
299 fun mk_entry (const, (_, (_, parents))) =
301 val name = Code_Unit.string_of_const thy const;
302 val nameparents = map (Code_Unit.string_of_const thy) parents;
303 in { name = name, ID = name, dir = "", unfold = true,
304 path = "", parents = nameparents }
306 val prgr = Graph.fold ((fn x => fn xs => xs @ [x]) o mk_entry) gr [];
307 in Present.display_graph prgr end;
311 structure P = OuterParse
314 fun code_thms_cmd thy = code_thms thy o op @ o Code_Name.read_const_exprs thy;
315 fun code_deps_cmd thy = code_deps thy o op @ o Code_Name.read_const_exprs thy;
320 OuterSyntax.improper_command "code_thms" "print system of defining equations for code" OuterKeyword.diag
321 (Scan.repeat P.term_group
322 >> (fn cs => Toplevel.no_timing o Toplevel.unknown_theory
323 o Toplevel.keep ((fn thy => code_thms_cmd thy cs) o Toplevel.theory_of)));
326 OuterSyntax.improper_command "code_deps" "visualize dependencies of defining equations for code" OuterKeyword.diag
327 (Scan.repeat P.term_group
328 >> (fn cs => Toplevel.no_timing o Toplevel.unknown_theory
329 o Toplevel.keep ((fn thy => code_deps_cmd thy cs) o Toplevel.theory_of)));