author | haftmann |
Fri, 20 Feb 2009 18:29:11 +0100 | |
changeset 30024 | 5e9d471afef3 |
parent 29962 | bd4dc7fa742d |
child 30202 | 2775062fd3a9 |
permissions | -rw-r--r-- |
24219 | 1 |
(* Title: Tools/code/code_funcgr.ML |
2 |
Author: Florian Haftmann, TU Muenchen |
|
3 |
||
29962
bd4dc7fa742d
tuned comments, stripped ID, deleted superfluous code
haftmann
parents:
28924
diff
changeset
|
4 |
Retrieving, normalizing and structuring code equations in graph |
24219 | 5 |
with explicit dependencies. |
6 |
*) |
|
7 |
||
8 |
signature CODE_FUNCGR = |
|
9 |
sig |
|
10 |
type T |
|
28370 | 11 |
val eqns: T -> string -> (thm * bool) list |
26971 | 12 |
val typ: T -> string -> (string * sort) list * typ |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
13 |
val all: T -> string list |
24219 | 14 |
val pretty: theory -> T -> Pretty.T |
28924
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
15 |
val make: theory -> string list |
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
16 |
-> ((sort -> sort) * Sorts.algebra) * T |
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
17 |
val eval_conv: theory |
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
18 |
-> (term -> term * (((sort -> sort) * Sorts.algebra) -> T -> thm)) -> cterm -> thm |
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
19 |
val eval_term: theory |
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
20 |
-> (term -> term * (((sort -> sort) * Sorts.algebra) -> T -> 'a)) -> term -> 'a |
26971 | 21 |
val timing: bool ref |
24219 | 22 |
end |
23 |
||
28054 | 24 |
structure Code_Funcgr : CODE_FUNCGR = |
24219 | 25 |
struct |
26 |
||
27 |
(** the graph type **) |
|
28 |
||
28350 | 29 |
type T = (((string * sort) list * typ) * (thm * bool) list) Graph.T; |
24219 | 30 |
|
28370 | 31 |
fun eqns funcgr = |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
32 |
these o Option.map snd o try (Graph.get_node funcgr); |
24219 | 33 |
|
34 |
fun typ funcgr = |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
35 |
fst o Graph.get_node funcgr; |
24219 | 36 |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
37 |
fun all funcgr = Graph.keys funcgr; |
24219 | 38 |
|
39 |
fun pretty thy funcgr = |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
40 |
AList.make (snd o Graph.get_node funcgr) (Graph.keys funcgr) |
28054 | 41 |
|> (map o apfst) (Code_Unit.string_of_const thy) |
24219 | 42 |
|> sort (string_ord o pairself fst) |
43 |
|> map (fn (s, thms) => |
|
44 |
(Pretty.block o Pretty.fbreaks) ( |
|
45 |
Pretty.str s |
|
28350 | 46 |
:: map (Display.pretty_thm o fst) thms |
24219 | 47 |
)) |
48 |
|> Pretty.chunks; |
|
49 |
||
50 |
||
51 |
(** generic combinators **) |
|
52 |
||
53 |
fun fold_consts f thms = |
|
54 |
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); |
|
57 |
||
58 |
fun consts_of (const, []) = [] |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
59 |
| consts_of (const, thms as _ :: _) = |
24219 | 60 |
let |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
61 |
fun the_const (c, _) = if c = const then I else insert (op =) c |
28350 | 62 |
in fold_consts the_const (map fst thms) [] end; |
24219 | 63 |
|
26971 | 64 |
fun insts_of thy algebra tys sorts = |
24219 | 65 |
let |
66 |
fun class_relation (x, _) _ = x; |
|
67 |
fun type_constructor tyco xs class = |
|
26971 | 68 |
(tyco, class) :: (maps o maps) fst xs; |
24219 | 69 |
fun type_variable (TVar (_, sort)) = map (pair []) sort |
70 |
| type_variable (TFree (_, sort)) = map (pair []) sort; |
|
26971 | 71 |
fun of_sort_deriv ty sort = |
26939
1035c89b4c02
moved global pretty/string_of functions from Sign to Syntax;
wenzelm
parents:
26928
diff
changeset
|
72 |
Sorts.of_sort_derivation (Syntax.pp_global thy) algebra |
24219 | 73 |
{ class_relation = class_relation, type_constructor = type_constructor, |
74 |
type_variable = type_variable } |
|
26517 | 75 |
(ty, sort) handle Sorts.CLASS_ERROR _ => [] (*permissive!*) |
26971 | 76 |
in (flat o flat) (map2 of_sort_deriv tys sorts) end; |
24219 | 77 |
|
26971 | 78 |
fun meets_of thy algebra = |
24219 | 79 |
let |
26971 | 80 |
fun meet_of ty sort tab = |
81 |
Sorts.meet_sort algebra (ty, sort) tab |
|
82 |
handle Sorts.CLASS_ERROR _ => tab (*permissive!*); |
|
83 |
in fold2 meet_of end; |
|
24219 | 84 |
|
85 |
||
86 |
(** graph algorithm **) |
|
87 |
||
88 |
val timing = ref false; |
|
89 |
||
90 |
local |
|
91 |
||
26971 | 92 |
fun resort_thms thy algebra typ_of thms = |
93 |
let |
|
94 |
val cs = fold_consts (insert (op =)) thms []; |
|
95 |
fun meets (c, ty) = case typ_of c |
|
96 |
of SOME (vs, _) => |
|
97 |
meets_of thy algebra (Sign.const_typargs thy (c, ty)) (map snd vs) |
|
98 |
| NONE => I; |
|
99 |
val tab = fold meets cs Vartab.empty; |
|
28423 | 100 |
in map (Code_Unit.inst_thm thy tab) thms end; |
24219 | 101 |
|
28370 | 102 |
fun resort_eqnss thy algebra funcgr = |
24219 | 103 |
let |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
104 |
val typ_funcgr = try (fst o Graph.get_node funcgr); |
28350 | 105 |
val resort_dep = (apsnd o burrow_fst) (resort_thms thy algebra typ_funcgr); |
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
106 |
fun resort_rec typ_of (c, []) = (true, (c, [])) |
28350 | 107 |
| resort_rec typ_of (c, thms as (thm, _) :: _) = if is_some (AxClass.inst_of_param thy c) |
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
108 |
then (true, (c, thms)) |
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
109 |
else let |
28423 | 110 |
val (_, (vs, ty)) = Code_Unit.head_eqn thy thm; |
28350 | 111 |
val thms' as (thm', _) :: _ = burrow_fst (resort_thms thy algebra typ_of) thms |
28423 | 112 |
val (_, (vs', ty')) = Code_Unit.head_eqn thy thm'; (*FIXME simplify check*) |
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
113 |
in (Sign.typ_equiv thy (ty, ty'), (c, thms')) end; |
28370 | 114 |
fun resort_recs eqnss = |
24219 | 115 |
let |
28370 | 116 |
fun typ_of c = case these (AList.lookup (op =) eqnss c) |
28423 | 117 |
of (thm, _) :: _ => (SOME o snd o Code_Unit.head_eqn thy) thm |
26971 | 118 |
| [] => NONE; |
28370 | 119 |
val (unchangeds, eqnss') = split_list (map (resort_rec typ_of) eqnss); |
24219 | 120 |
val unchanged = fold (fn x => fn y => x andalso y) unchangeds true; |
28370 | 121 |
in (unchanged, eqnss') end; |
122 |
fun resort_rec_until eqnss = |
|
24219 | 123 |
let |
28370 | 124 |
val (unchanged, eqnss') = resort_recs eqnss; |
125 |
in if unchanged then eqnss' else resort_rec_until eqnss' end; |
|
24219 | 126 |
in map resort_dep #> resort_rec_until end; |
127 |
||
128 |
fun instances_of thy algebra insts = |
|
129 |
let |
|
130 |
val thy_classes = (#classes o Sorts.rep_algebra o Sign.classes_of) thy; |
|
24835
8c26128f8997
clarified relationship of code generator conversions and evaluations
haftmann
parents:
24713
diff
changeset
|
131 |
fun all_classparams tyco class = |
24969 | 132 |
these (try (#params o AxClass.get_info thy) class) |
26517 | 133 |
|> map_filter (fn (c, _) => try (AxClass.param_of_inst thy) (c, tyco)) |
24219 | 134 |
in |
135 |
Symtab.empty |
|
136 |
|> fold (fn (tyco, class) => |
|
137 |
Symtab.map_default (tyco, []) (insert (op =) class)) insts |
|
24835
8c26128f8997
clarified relationship of code generator conversions and evaluations
haftmann
parents:
24713
diff
changeset
|
138 |
|> (fn tab => Symtab.fold (fn (tyco, classes) => append (maps (all_classparams tyco) |
24219 | 139 |
(Graph.all_succs thy_classes classes))) tab []) |
140 |
end; |
|
141 |
||
142 |
fun instances_of_consts thy algebra funcgr consts = |
|
143 |
let |
|
26971 | 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)); |
|
24219 | 146 |
in |
147 |
[] |
|
148 |
|> fold (fold (insert (op =)) o inst) consts |
|
149 |
|> instances_of thy algebra |
|
150 |
end; |
|
151 |
||
24283 | 152 |
fun ensure_const' thy algebra funcgr const auxgr = |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
153 |
if can (Graph.get_node funcgr) const |
24219 | 154 |
then (NONE, auxgr) |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
155 |
else if can (Graph.get_node auxgr) const |
24219 | 156 |
then (SOME const, auxgr) |
157 |
else if is_some (Code.get_datatype_of_constr thy const) then |
|
158 |
auxgr |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
159 |
|> Graph.new_node (const, []) |
24219 | 160 |
|> pair (SOME const) |
161 |
else let |
|
28370 | 162 |
val thms = Code.these_eqns thy const |
28423 | 163 |
|> burrow_fst (Code_Unit.norm_args thy) |
164 |
|> burrow_fst (Code_Unit.norm_varnames thy Code_Name.purify_tvar Code_Name.purify_var); |
|
24219 | 165 |
val rhs = consts_of (const, thms); |
166 |
in |
|
167 |
auxgr |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
168 |
|> Graph.new_node (const, thms) |
24283 | 169 |
|> fold_map (ensure_const thy algebra funcgr) rhs |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
170 |
|-> (fn rhs' => fold (fn SOME const' => Graph.add_edge (const, const') |
24219 | 171 |
| NONE => I) rhs') |
172 |
|> pair (SOME const) |
|
173 |
end |
|
24283 | 174 |
and ensure_const thy algebra funcgr const = |
24219 | 175 |
let |
176 |
val timeap = if !timing |
|
28054 | 177 |
then Output.timeap_msg ("time for " ^ Code_Unit.string_of_const thy const) |
24219 | 178 |
else I; |
24283 | 179 |
in timeap (ensure_const' thy algebra funcgr const) end; |
24219 | 180 |
|
28370 | 181 |
fun merge_eqnss thy algebra raw_eqnss funcgr = |
24219 | 182 |
let |
28370 | 183 |
val eqnss = raw_eqnss |
184 |
|> resort_eqnss thy algebra funcgr |
|
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
185 |
|> filter_out (can (Graph.get_node funcgr) o fst); |
28423 | 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; |
|
28370 | 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 = |
|
24219 | 191 |
let |
28370 | 192 |
val deps = consts_of eqns; |
24219 | 193 |
val insts = instances_of_consts thy algebra funcgr |
28350 | 194 |
(fold_consts (insert (op =)) (map fst thms) []); |
24219 | 195 |
in |
196 |
funcgr |
|
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
197 |
|> ensure_consts thy algebra insts |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
198 |
|> fold (curry Graph.add_edge const) deps |
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
199 |
|> fold (curry Graph.add_edge const) insts |
24219 | 200 |
end; |
201 |
in |
|
202 |
funcgr |
|
28370 | 203 |
|> fold add_eqns eqnss |
204 |
|> fold add_deps eqnss |
|
24219 | 205 |
end |
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
206 |
and ensure_consts thy algebra cs funcgr = |
24219 | 207 |
let |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
208 |
val auxgr = Graph.empty |
24283 | 209 |
|> fold (snd oo ensure_const thy algebra funcgr) cs; |
24219 | 210 |
in |
211 |
funcgr |
|
28370 | 212 |
|> fold (merge_eqnss thy algebra) |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
213 |
(map (AList.make (Graph.get_node auxgr)) |
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
214 |
(rev (Graph.strong_conn auxgr))) |
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
215 |
end; |
24219 | 216 |
|
217 |
in |
|
218 |
||
219 |
(** retrieval interfaces **) |
|
220 |
||
26997
40552bbac005
permissive wrt. instantiation of class operations
haftmann
parents:
26971
diff
changeset
|
221 |
val ensure_consts = ensure_consts; |
24219 | 222 |
|
28724 | 223 |
fun proto_eval thy cterm_of evaluator_lift evaluator proto_ct funcgr = |
24219 | 224 |
let |
26740 | 225 |
val ct = cterm_of proto_ct; |
26939
1035c89b4c02
moved global pretty/string_of functions from Sign to Syntax;
wenzelm
parents:
26928
diff
changeset
|
226 |
val _ = Sign.no_vars (Syntax.pp_global thy) (Thm.term_of ct); |
24219 | 227 |
val _ = Term.fold_types (Type.no_tvars #> K I) (Thm.term_of ct) (); |
28724 | 228 |
fun consts_of t = |
229 |
fold_aterms (fn Const c_ty => cons c_ty | _ => I) t []; |
|
26740 | 230 |
val algebra = Code.coregular_algebra thy; |
28423 | 231 |
val thm = Code.preprocess_conv thy ct; |
26740 | 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; |
|
28724 | 236 |
val (t'', evaluator_funcgr) = evaluator t'; |
26740 | 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'; |
|
28924
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
240 |
in (evaluator_lift (evaluator_funcgr (Code.operational_algebra thy)) thm funcgr'', funcgr'') end; |
26740 | 241 |
|
242 |
fun proto_eval_conv thy = |
|
243 |
let |
|
28724 | 244 |
fun evaluator_lift evaluator thm1 funcgr = |
24219 | 245 |
let |
28724 | 246 |
val thm2 = evaluator funcgr; |
28423 | 247 |
val thm3 = Code.postprocess_conv thy (Thm.rhs_of thm2); |
24219 | 248 |
in |
26740 | 249 |
Thm.transitive thm1 (Thm.transitive thm2 thm3) handle THM _ => |
26971 | 250 |
error ("could not construct evaluation proof:\n" |
26928 | 251 |
^ (cat_lines o map Display.string_of_thm) [thm1, thm2, thm3]) |
24219 | 252 |
end; |
28724 | 253 |
in proto_eval thy I evaluator_lift end; |
24283 | 254 |
|
26740 | 255 |
fun proto_eval_term thy = |
24283 | 256 |
let |
28724 | 257 |
fun evaluator_lift evaluator _ funcgr = evaluator funcgr; |
258 |
in proto_eval thy (Thm.cterm_of thy) evaluator_lift end; |
|
24219 | 259 |
|
260 |
end; (*local*) |
|
261 |
||
262 |
structure Funcgr = CodeDataFun |
|
24713 | 263 |
( |
24219 | 264 |
type T = T; |
24423
ae9cd0e92423
overloaded definitions accompanied by explicit constants
haftmann
parents:
24283
diff
changeset
|
265 |
val empty = Graph.empty; |
27609 | 266 |
fun purge _ cs funcgr = |
267 |
Graph.del_nodes ((Graph.all_preds funcgr |
|
268 |
o filter (can (Graph.get_node funcgr))) cs) funcgr; |
|
24713 | 269 |
); |
24219 | 270 |
|
271 |
fun make thy = |
|
28924
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
272 |
pair (Code.operational_algebra thy) |
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
273 |
o Funcgr.change thy o ensure_consts thy (Code.coregular_algebra thy); |
24219 | 274 |
|
275 |
fun eval_conv thy f = |
|
26740 | 276 |
fst o Funcgr.change_yield thy o proto_eval_conv thy f; |
24283 | 277 |
|
278 |
fun eval_term thy f = |
|
26740 | 279 |
fst o Funcgr.change_yield thy o proto_eval_term thy f; |
24219 | 280 |
|
27103 | 281 |
|
282 |
(** diagnostic commands **) |
|
283 |
||
28350 | 284 |
fun code_depgr thy consts = |
285 |
let |
|
28924
5c8781b7d6a4
code_funcgr interface includes also sort algebra
haftmann
parents:
28724
diff
changeset
|
286 |
val (_, gr) = make thy consts; |
28350 | 287 |
val select = Graph.all_succs gr consts; |
288 |
in |
|
289 |
gr |
|
290 |
|> not (null consts) ? Graph.subgraph (member (op =) select) |
|
291 |
|> Graph.map_nodes ((apsnd o map o apfst) (AxClass.overload thy)) |
|
292 |
end; |
|
27103 | 293 |
|
294 |
fun code_thms thy = Pretty.writeln o pretty thy o code_depgr thy; |
|
295 |
||
296 |
fun code_deps thy consts = |
|
297 |
let |
|
298 |
val gr = code_depgr thy consts; |
|
299 |
fun mk_entry (const, (_, (_, parents))) = |
|
300 |
let |
|
28054 | 301 |
val name = Code_Unit.string_of_const thy const; |
302 |
val nameparents = map (Code_Unit.string_of_const thy) parents; |
|
27103 | 303 |
in { name = name, ID = name, dir = "", unfold = true, |
304 |
path = "", parents = nameparents } |
|
305 |
end; |
|
306 |
val prgr = Graph.fold ((fn x => fn xs => xs @ [x]) o mk_entry) gr []; |
|
307 |
in Present.display_graph prgr end; |
|
308 |
||
309 |
local |
|
310 |
||
311 |
structure P = OuterParse |
|
312 |
and K = OuterKeyword |
|
313 |
||
28054 | 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; |
|
27103 | 316 |
|
317 |
in |
|
318 |
||
319 |
val _ = |
|
30024 | 320 |
OuterSyntax.improper_command "code_thms" "print system of code equations for code" OuterKeyword.diag |
28338 | 321 |
(Scan.repeat P.term_group |
27103 | 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))); |
|
324 |
||
325 |
val _ = |
|
30024 | 326 |
OuterSyntax.improper_command "code_deps" "visualize dependencies of code equations for code" OuterKeyword.diag |
28338 | 327 |
(Scan.repeat P.term_group |
27103 | 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))); |
|
330 |
||
331 |
end; |
|
332 |
||
24219 | 333 |
end; (*struct*) |