110 val classess = map (complete_proper_sort thy) |
116 val classess = map (complete_proper_sort thy) |
111 (Sign.arity_sorts thy tyco [class]); |
117 (Sign.arity_sorts thy tyco [class]); |
112 val inst_params = inst_params thy tyco all_classes; |
118 val inst_params = inst_params thy tyco all_classes; |
113 in (classess, (superclasses, inst_params)) end; |
119 in (classess, (superclasses, inst_params)) end; |
114 |
120 |
|
121 |
|
122 (* computing instantiations *) |
|
123 |
115 fun add_classes thy arities eqngr c_k new_classes vardeps_data = |
124 fun add_classes thy arities eqngr c_k new_classes vardeps_data = |
116 let |
125 let |
117 val (styps, old_classes) = Vargraph.get_node (fst vardeps_data) c_k; |
126 val (styps, old_classes) = Vargraph.get_node (fst vardeps_data) c_k; |
118 val diff_classes = new_classes |> subtract (op =) old_classes; |
127 val diff_classes = new_classes |> subtract (op =) old_classes; |
119 in if null diff_classes then vardeps_data |
128 in if null diff_classes then vardeps_data |
120 else let |
129 else let |
121 val c_ks = Vargraph.imm_succs (fst vardeps_data) c_k |> insert (op =) c_k; |
130 val c_ks = Vargraph.imm_succs (fst vardeps_data) c_k |> insert (op =) c_k; |
122 in |
131 in |
123 vardeps_data |
132 vardeps_data |
124 |> (apfst o Vargraph.map_node c_k o apsnd) (append diff_classes) |
133 |> (apfst o Vargraph.map_node c_k o apsnd) (append diff_classes) |
125 |> fold (fn styp => fold (add_typmatch_inst thy arities eqngr styp) new_classes) styps |
134 |> fold (fn styp => fold (assert_typmatch_inst thy arities eqngr styp) new_classes) styps |
126 |> fold (fn c_k => add_classes thy arities eqngr c_k diff_classes) c_ks |
135 |> fold (fn c_k => add_classes thy arities eqngr c_k diff_classes) c_ks |
127 end end |
136 end end |
128 and add_styp thy arities eqngr c_k tyco_styps vardeps_data = |
137 and add_styp thy arities eqngr c_k tyco_styps vardeps_data = |
129 let |
138 let |
130 val (old_styps, classes) = Vargraph.get_node (fst vardeps_data) c_k; |
139 val (old_styps, classes) = Vargraph.get_node (fst vardeps_data) c_k; |
131 in if member (op =) old_styps tyco_styps then vardeps_data |
140 in if member (op =) old_styps tyco_styps then vardeps_data |
132 else |
141 else |
133 vardeps_data |
142 vardeps_data |
134 |> (apfst o Vargraph.map_node c_k o apfst) (cons tyco_styps) |
143 |> (apfst o Vargraph.map_node c_k o apfst) (cons tyco_styps) |
135 |> fold (add_typmatch_inst thy arities eqngr tyco_styps) classes |
144 |> fold (assert_typmatch_inst thy arities eqngr tyco_styps) classes |
136 end |
145 end |
137 and add_dep thy arities eqngr c_k c_k' vardeps_data = |
146 and add_dep thy arities eqngr c_k c_k' vardeps_data = |
138 let |
147 let |
139 val (_, classes) = Vargraph.get_node (fst vardeps_data) c_k; |
148 val (_, classes) = Vargraph.get_node (fst vardeps_data) c_k; |
140 in |
149 in |
141 vardeps_data |
150 vardeps_data |
142 |> add_classes thy arities eqngr c_k' classes |
151 |> add_classes thy arities eqngr c_k' classes |
143 |> apfst (Vargraph.add_edge (c_k, c_k')) |
152 |> apfst (Vargraph.add_edge (c_k, c_k')) |
144 end |
153 end |
145 and add_typmatch_inst thy arities eqngr (tyco, styps) class vardeps_data = |
154 and assert_typmatch_inst thy arities eqngr (tyco, styps) class vardeps_data = |
146 if can (Sign.arity_sorts thy tyco) [class] |
155 if can (Sign.arity_sorts thy tyco) [class] |
147 then vardeps_data |
156 then vardeps_data |
148 |> assert thy arities eqngr (Inst (class, tyco)) |
157 |> assert_inst thy arities eqngr (class, tyco) |
149 |> fold_index (fn (k, styp) => |
158 |> fold_index (fn (k, styp) => |
150 add_typmatch thy arities eqngr styp (Inst (class, tyco), k)) styps |
159 assert_typmatch thy arities eqngr styp (Inst (class, tyco), k)) styps |
151 else vardeps_data (*permissive!*) |
160 else vardeps_data (*permissive!*) |
152 and add_typmatch thy arities eqngr (Var c_k') c_k vardeps_data = |
161 and assert_inst thy arities eqngr (inst as (class, tyco)) (vardeps_data as (_, (_, insts))) = |
153 vardeps_data |
162 if member (op =) insts inst then vardeps_data |
154 |> add_dep thy arities eqngr c_k c_k' |
163 else let |
155 | add_typmatch thy arities eqngr (Tyco tyco_styps) c_k vardeps_data = |
|
156 vardeps_data |
|
157 |> add_styp thy arities eqngr c_k tyco_styps |
|
158 and add_inst thy arities eqngr (inst as (class, tyco)) vardeps_data = |
|
159 let |
|
160 val (classess, (superclasses, inst_params)) = |
164 val (classess, (superclasses, inst_params)) = |
161 obtain_instance thy arities inst; |
165 obtain_instance thy arities inst; |
162 in |
166 in |
163 vardeps_data |
167 vardeps_data |
164 |> fold (fn superclass => assert thy arities eqngr (Inst (superclass, tyco))) superclasses |
168 |> (apsnd o apsnd) (insert (op =) inst) |
165 |> fold (assert thy arities eqngr o Fun) inst_params |
169 |> fold (fn superclass => assert_inst thy arities eqngr (superclass, tyco)) superclasses |
|
170 |> fold (assert_fun thy arities eqngr) inst_params |
166 |> fold_index (fn (k, classes) => |
171 |> fold_index (fn (k, classes) => |
167 apfst (Vargraph.new_node ((Inst (class, tyco), k), ([] ,[]))) |
172 apfst (Vargraph.new_node ((Inst (class, tyco), k), ([] ,[]))) |
168 #> add_classes thy arities eqngr (Inst (class, tyco), k) classes |
173 #> add_classes thy arities eqngr (Inst (class, tyco), k) classes |
169 #> fold (fn superclass => |
174 #> fold (fn superclass => |
170 add_dep thy arities eqngr (Inst (superclass, tyco), k) |
175 add_dep thy arities eqngr (Inst (superclass, tyco), k) |
173 add_dep thy arities eqngr (Fun inst_param, k) |
178 add_dep thy arities eqngr (Fun inst_param, k) |
174 (Inst (class, tyco), k) |
179 (Inst (class, tyco), k) |
175 ) inst_params |
180 ) inst_params |
176 ) classess |
181 ) classess |
177 end |
182 end |
178 and add_const thy arities eqngr c vardeps_data = |
183 and assert_typmatch thy arities eqngr (Tyco tyco_styps) c_k vardeps_data = |
179 let |
184 vardeps_data |
|
185 |> add_styp thy arities eqngr c_k tyco_styps |
|
186 | assert_typmatch thy arities eqngr (Var c_k') c_k vardeps_data = |
|
187 vardeps_data |
|
188 |> add_dep thy arities eqngr c_k c_k' |
|
189 | assert_typmatch thy arities eqngr Free c_k vardeps_data = |
|
190 vardeps_data |
|
191 and assert_rhs thy arities eqngr (c', styps) vardeps_data = |
|
192 vardeps_data |
|
193 |> assert_fun thy arities eqngr c' |
|
194 |> fold_index (fn (k, styp) => |
|
195 assert_typmatch thy arities eqngr styp (Fun c', k)) styps |
|
196 and assert_fun thy arities eqngr c (vardeps_data as (_, (eqntab, _))) = |
|
197 if Symtab.defined eqntab c then vardeps_data |
|
198 else let |
180 val ((lhs, rhss), eqns) = obtain_eqns thy eqngr c; |
199 val ((lhs, rhss), eqns) = obtain_eqns thy eqngr c; |
181 fun styp_of (Type (tyco, tys)) = Tyco (tyco, map styp_of tys) |
200 val rhss' = (map o apsnd o map) (styp_of (SOME (c, lhs))) rhss; |
182 | styp_of (TFree (v, _)) = Var (Fun c, find_index (fn (v', _) => v = v') lhs); |
|
183 val rhss' = (map o apsnd o map) styp_of rhss; |
|
184 in |
201 in |
185 vardeps_data |
202 vardeps_data |
186 |> (apsnd o apsnd) (Symtab.update_new (c, (lhs, eqns))) |
203 |> (apsnd o apfst) (Symtab.update_new (c, (lhs, eqns))) |
187 |> fold_index (fn (k, (_, sort)) => |
204 |> fold_index (fn (k, (_, sort)) => |
188 apfst (Vargraph.new_node ((Fun c, k), ([] ,[]))) |
205 apfst (Vargraph.new_node ((Fun c, k), ([] ,[]))) |
189 #> add_classes thy arities eqngr (Fun c, k) (complete_proper_sort thy sort)) lhs |
206 #> add_classes thy arities eqngr (Fun c, k) (complete_proper_sort thy sort)) lhs |
190 |> fold (assert thy arities eqngr o Fun o fst) rhss' |
207 |> fold (assert_rhs thy arities eqngr) rhss' |
191 |> fold (fn (c', styps) => fold_index (fn (k', styp) => |
208 end; |
192 add_typmatch thy arities eqngr styp (Fun c', k')) styps) rhss' |
|
193 end |
|
194 and assert thy arities eqngr c vardeps_data = |
|
195 if member (op =) ((fst o snd) vardeps_data) c then vardeps_data |
|
196 else case c |
|
197 of Fun const => vardeps_data |> (apsnd o apfst) (cons c) |> add_const thy arities eqngr const |
|
198 | Inst inst => vardeps_data |> (apsnd o apfst) (cons c) |> add_inst thy arities eqngr inst; |
|
199 |
209 |
200 |
210 |
201 (* applying instantiations *) |
211 (* applying instantiations *) |
202 |
212 |
203 fun build_algebra thy arities = |
213 fun build_algebra thy arities = |
207 val is_proper = can (AxClass.get_info thy); |
217 val is_proper = can (AxClass.get_info thy); |
208 val classrels = Sorts.classrels_of thy_algebra |
218 val classrels = Sorts.classrels_of thy_algebra |
209 |> filter (is_proper o fst) |
219 |> filter (is_proper o fst) |
210 |> (map o apsnd) (filter is_proper); |
220 |> (map o apsnd) (filter is_proper); |
211 val instances = Sorts.instances_of thy_algebra |
221 val instances = Sorts.instances_of thy_algebra |
212 |> filter (is_proper o snd); |
222 |> filter (is_proper o snd) |
|
223 |> map swap (*FIXME*) |
213 fun add_class (class, superclasses) algebra = |
224 fun add_class (class, superclasses) algebra = |
214 Sorts.add_class pp (class, Sorts.minimize_sort algebra superclasses) algebra; |
225 Sorts.add_class pp (class, Sorts.minimize_sort algebra superclasses) algebra; |
215 fun add_arity (tyco, class) algebra = |
226 fun add_arity (class, tyco) algebra = Sorts.add_arities pp |
216 case AList.lookup (op =) arities (tyco, class) |
227 (tyco, [(class, ((map (Sorts.minimize_sort algebra) o the |
217 of SOME sorts => Sorts.add_arities pp |
228 o AList.lookup (op =) arities) (class, tyco)))]) algebra; |
218 (tyco, [(class, map (Sorts.minimize_sort algebra) sorts)]) algebra |
|
219 | NONE => if Sign.arity_number thy tyco = 0 |
|
220 then Sorts.add_arities pp (tyco, [(class, [])]) algebra |
|
221 else algebra; |
|
222 in |
229 in |
223 Sorts.empty_algebra |
230 Sorts.empty_algebra |
224 |> fold add_class classrels |
231 |> fold add_class classrels |
225 |> fold add_arity instances |
232 |> fold add_arity instances |
226 end; |
233 end; |
227 |
234 |
228 fun dicts_of thy (proj_sort, algebra) (T, sort) = |
235 fun dicts_of thy (proj_sort, algebra) (T, sort) = |
229 let |
236 let |
230 fun class_relation (x, _) _ = x; |
237 fun class_relation (x, _) _ = x; |
231 fun type_constructor tyco xs class = |
238 fun type_constructor tyco xs class = |
232 inst_params thy tyco (Sorts.complete_sort algebra [class]) @ (maps o maps) fst xs; |
239 inst_params thy tyco (Sorts.complete_sort algebra [class]) |
|
240 @ (maps o maps) fst xs; |
233 fun type_variable (TFree (_, sort)) = map (pair []) (proj_sort sort); |
241 fun type_variable (TFree (_, sort)) = map (pair []) (proj_sort sort); |
234 in |
242 in |
235 flat (Sorts.of_sort_derivation (Syntax.pp_global thy) algebra |
243 flat (Sorts.of_sort_derivation (Syntax.pp_global thy) algebra |
236 { class_relation = class_relation, type_constructor = type_constructor, |
244 { class_relation = class_relation, type_constructor = type_constructor, |
237 type_variable = type_variable } (T, proj_sort sort) |
245 type_variable = type_variable } (T, proj_sort sort) |
238 handle Sorts.CLASS_ERROR _ => [] (*permissive!*)) |
246 handle Sorts.CLASS_ERROR _ => [] (*permissive!*)) |
239 end; |
247 end; |
240 |
248 |
241 fun add_arities thy vardeps = Vargraph.fold (fn ((Fun _, _), _) => I |
249 fun add_arity thy vardeps (class, tyco) = |
242 | ((Inst (class, tyco), k), ((_, classes), _)) => |
250 AList.update (op =) |
243 AList.map_default (op =) |
251 ((class, tyco), map (fn k => (snd o Vargraph.get_node vardeps) (Inst (class, tyco), k)) |
244 ((tyco, class), replicate (Sign.arity_number thy tyco) []) |
252 (0 upto Sign.arity_number thy tyco - 1)); |
245 (nth_map k (K classes))) vardeps; |
253 |
246 |
254 fun add_eqs thy (proj_sort, algebra) vardeps |
247 fun add_eqs thy (proj_sort, algebra) eqntab vardeps c gr = |
255 (c, (proto_lhs, proto_eqns)) (rhss, eqngr) = |
248 let |
256 let |
249 val (proto_lhs, proto_eqns) = (the o Symtab.lookup eqntab) c; |
|
250 val lhs = map_index (fn (k, (v, _)) => |
257 val lhs = map_index (fn (k, (v, _)) => |
251 (v, snd (Vargraph.get_node vardeps (Fun c, k)))) proto_lhs; |
258 (v, snd (Vargraph.get_node vardeps (Fun c, k)))) proto_lhs; |
252 val inst_tab = Vartab.empty |> fold (fn (v, sort) => |
259 val inst_tab = Vartab.empty |> fold (fn (v, sort) => |
253 Vartab.update ((v, 0), sort)) lhs; |
260 Vartab.update ((v, 0), sort)) lhs; |
254 val eqns = proto_eqns |
261 val eqns = proto_eqns |
255 |> (map o apfst) (Code_Unit.inst_thm thy inst_tab); |
262 |> (map o apfst) (Code_Unit.inst_thm thy inst_tab); |
256 val (tyscm, rhss) = tyscm_rhss_of thy c eqns; |
263 val (tyscm, rhss') = tyscm_rhss_of thy c eqns; |
257 in |
264 val eqngr' = Graph.new_node (c, (tyscm, eqns)) eqngr; |
258 gr |
265 in (map (pair c) rhss' @ rhss, eqngr') end; |
259 |> Graph.new_node (c, (tyscm, eqns)) |
266 |
260 |> fold (fn (c', Ts) => ensure_eqs_dep thy (proj_sort, algebra) eqntab vardeps c c' |
267 fun extend_arities_eqngr thy cs cs_rhss (arities, eqngr) = |
261 #-> (fn (vs, _) => |
268 let |
262 fold2 (ensure_match thy (proj_sort, algebra) eqntab vardeps c) Ts (map snd vs))) rhss |
269 val cs_rhss' = (map o apsnd o map) (styp_of NONE) cs_rhss; |
263 |> pair tyscm |
270 val (vardeps, (eqntab, insts)) = empty_vardeps_data |
264 end |
271 |> fold (assert_fun thy arities eqngr) cs |
265 and ensure_match thy (proj_sort, algebra) eqntab vardeps c T sort gr = |
272 |> fold (assert_rhs thy arities eqngr) cs_rhss'; |
266 gr |
273 val arities' = fold (add_arity thy vardeps) insts arities; |
267 |> fold (fn c' => ensure_eqs_dep thy (proj_sort, algebra) eqntab vardeps c c' #> snd) |
|
268 (dicts_of thy (proj_sort, algebra) (T, proj_sort sort)) |
|
269 and ensure_eqs_dep thy (proj_sort, algebra) eqntab vardeps c c' gr = |
|
270 gr |
|
271 |> ensure_eqs thy (proj_sort, algebra) eqntab vardeps c' |
|
272 ||> Graph.add_edge (c, c') |
|
273 and ensure_eqs thy (proj_sort, algebra) eqntab vardeps c gr = |
|
274 case try (Graph.get_node gr) c |
|
275 of SOME (tyscm, _) => (tyscm, gr) |
|
276 | NONE => add_eqs thy (proj_sort, algebra) eqntab vardeps c gr; |
|
277 |
|
278 fun extend_arities_eqngr thy cs insts (arities, eqngr) = |
|
279 let |
|
280 val (vardeps, (_, eqntab)) = empty_vardeps |
|
281 |> fold (assert thy arities eqngr o Fun) cs |
|
282 |> fold (assert thy arities eqngr o Inst) insts; |
|
283 val arities' = add_arities thy vardeps arities; |
|
284 val algebra = build_algebra thy arities'; |
274 val algebra = build_algebra thy arities'; |
285 val proj_sort = complete_proper_sort thy #> Sorts.minimize_sort algebra; |
275 val proj_sort = complete_proper_sort thy #> Sorts.minimize_sort algebra; |
286 fun complete_inst_params (class, tyco) = |
276 val (rhss, eqngr') = Symtab.fold |
287 inst_params thy tyco (Sorts.complete_sort algebra [class]); |
277 (add_eqs thy (proj_sort, algebra) vardeps) eqntab ([], eqngr); |
288 val cs' = maps complete_inst_params insts @ cs; (*FIXME*) |
278 fun deps_of (c, rhs) = c :: |
289 val (_, eqngr') = |
279 maps (dicts_of thy (proj_sort, algebra)) |
290 fold_map (ensure_eqs thy (proj_sort, algebra) eqntab vardeps) cs' eqngr; |
280 (rhs ~~ (map snd o fst o fst o Graph.get_node eqngr') c); |
291 in ((proj_sort, algebra), (arities', eqngr')) end; |
281 val eqngr'' = fold (fn (c, rhs) => fold |
|
282 (curry Graph.add_edge c) (deps_of rhs)) rhss eqngr'; |
|
283 in ((proj_sort, algebra), (arities', eqngr'')) end; |
292 |
284 |
293 |
285 |
294 (** retrieval interfaces **) |
286 (** retrieval interfaces **) |
295 |
|
296 fun instance_dicts_of thy (proj_sort, algebra) (T, sort) = (*FIXME vs. consts_dicts_of *) |
|
297 let |
|
298 fun class_relation (x, _) _ = x; |
|
299 fun type_constructor tyco xs class = |
|
300 (class, tyco) :: (maps o maps) fst xs; |
|
301 fun type_variable (TFree (_, sort)) = map (pair []) (proj_sort sort); |
|
302 in |
|
303 flat (Sorts.of_sort_derivation (Syntax.pp_global thy) algebra |
|
304 { class_relation = class_relation, type_constructor = type_constructor, |
|
305 type_variable = type_variable } (T, proj_sort sort) |
|
306 handle Sorts.CLASS_ERROR _ => [] (*permissive!*)) |
|
307 end; |
|
308 |
287 |
309 fun proto_eval thy cterm_of evaluator_lift evaluator proto_ct arities_eqngr = |
288 fun proto_eval thy cterm_of evaluator_lift evaluator proto_ct arities_eqngr = |
310 let |
289 let |
311 val ct = cterm_of proto_ct; |
290 val ct = cterm_of proto_ct; |
312 val _ = Sign.no_vars (Syntax.pp_global thy) (Thm.term_of ct); |
291 val _ = Sign.no_vars (Syntax.pp_global thy) (Thm.term_of ct); |
314 fun consts_of t = |
293 fun consts_of t = |
315 fold_aterms (fn Const c_ty => cons c_ty | _ => I) t []; |
294 fold_aterms (fn Const c_ty => cons c_ty | _ => I) t []; |
316 val thm = Code.preprocess_conv thy ct; |
295 val thm = Code.preprocess_conv thy ct; |
317 val ct' = Thm.rhs_of thm; |
296 val ct' = Thm.rhs_of thm; |
318 val t' = Thm.term_of ct'; |
297 val t' = Thm.term_of ct'; |
|
298 val (t'', evaluator_eqngr) = evaluator t'; |
319 val consts = map fst (consts_of t'); |
299 val consts = map fst (consts_of t'); |
320 val (algebra', arities_eqngr') = extend_arities_eqngr thy consts [] arities_eqngr; |
|
321 val (t'', evaluator_eqngr) = evaluator t'; |
|
322 val consts' = consts_of t''; |
300 val consts' = consts_of t''; |
323 val const_matches = fold (fn (c, ty) => |
301 val const_matches' = fold (fn (c, ty) => |
324 insert (op =) (Sign.const_typargs thy (c, Logic.unvarifyT ty), c)) consts' []; |
302 insert (op =) (c, Sign.const_typargs thy (c, Logic.unvarifyT ty))) consts' []; |
325 val typ_matches = maps (fn (tys, c) => |
303 val (algebra', arities_eqngr') = |
326 tys ~~ map snd (fst (fst (Graph.get_node (snd arities_eqngr') c)))) |
304 extend_arities_eqngr thy consts const_matches' arities_eqngr; |
327 const_matches; |
305 in |
328 val insts = maps (instance_dicts_of thy algebra') typ_matches; |
306 (evaluator_lift (evaluator_eqngr algebra') thm (snd arities_eqngr'), |
329 val (algebra'', arities_eqngr'') = extend_arities_eqngr thy [] insts arities_eqngr'; |
307 arities_eqngr') |
330 in (evaluator_lift (evaluator_eqngr algebra'') thm (snd arities_eqngr''), arities_eqngr'') end; |
308 end; |
331 |
309 |
332 fun proto_eval_conv thy = |
310 fun proto_eval_conv thy = |
333 let |
311 let |
334 fun evaluator_lift evaluator thm1 eqngr = |
312 fun evaluator_lift evaluator thm1 eqngr = |
335 let |
313 let |