26 type algebra |
26 type algebra |
27 val rep_algebra: algebra -> |
27 val rep_algebra: algebra -> |
28 {classes: serial Graph.T, |
28 {classes: serial Graph.T, |
29 arities: (class * (class * sort list)) list Symtab.table} |
29 arities: (class * (class * sort list)) list Symtab.table} |
30 val all_classes: algebra -> class list |
30 val all_classes: algebra -> class list |
31 val minimal_classes: algebra -> class list |
|
32 val super_classes: algebra -> class -> class list |
31 val super_classes: algebra -> class -> class list |
33 val class_less: algebra -> class * class -> bool |
32 val class_less: algebra -> class * class -> bool |
34 val class_le: algebra -> class * class -> bool |
33 val class_le: algebra -> class * class -> bool |
35 val sort_eq: algebra -> sort * sort -> bool |
34 val sort_eq: algebra -> sort * sort -> bool |
36 val sort_le: algebra -> sort * sort -> bool |
35 val sort_le: algebra -> sort * sort -> bool |
46 val empty_algebra: algebra |
45 val empty_algebra: algebra |
47 val merge_algebra: Pretty.pp -> algebra * algebra -> algebra |
46 val merge_algebra: Pretty.pp -> algebra * algebra -> algebra |
48 val subalgebra: Pretty.pp -> (class -> bool) -> (class * string -> sort list) |
47 val subalgebra: Pretty.pp -> (class -> bool) -> (class * string -> sort list) |
49 -> algebra -> (sort -> sort) * algebra |
48 -> algebra -> (sort -> sort) * algebra |
50 type class_error |
49 type class_error |
51 val msg_class_error: Pretty.pp -> class_error -> string |
50 val class_error: Pretty.pp -> class_error -> string |
52 val class_error: Pretty.pp -> class_error -> 'a |
|
53 exception CLASS_ERROR of class_error |
51 exception CLASS_ERROR of class_error |
54 val mg_domain: algebra -> string -> sort -> sort list (*exception CLASS_ERROR*) |
52 val mg_domain: algebra -> string -> sort -> sort list (*exception CLASS_ERROR*) |
|
53 val meet_sort: algebra -> typ * sort -> sort Vartab.table -> sort Vartab.table |
55 val of_sort: algebra -> typ * sort -> bool |
54 val of_sort: algebra -> typ * sort -> bool |
56 val meet_sort: algebra -> typ * sort -> sort Vartab.table -> sort Vartab.table |
|
57 val of_sort_derivation: Pretty.pp -> algebra -> |
55 val of_sort_derivation: Pretty.pp -> algebra -> |
58 {class_relation: 'a * class -> class -> 'a, |
56 {class_relation: 'a * class -> class -> 'a, |
59 type_constructor: string -> ('a * class) list list -> class -> 'a, |
57 type_constructor: string -> ('a * class) list list -> class -> 'a, |
60 type_variable: typ -> ('a * class) list} -> |
58 type_variable: typ -> ('a * class) list} -> |
61 typ * sort -> 'a list (*exception CLASS_ERROR*) |
59 typ * sort -> 'a list (*exception CLASS_ERROR*) |
304 |
301 |
305 |
302 |
306 |
303 |
307 (** sorts of types **) |
304 (** sorts of types **) |
308 |
305 |
309 (* errors *) |
306 (* errors -- delayed message composition *) |
310 |
307 |
311 datatype class_error = NoClassrel of class * class |
308 datatype class_error = |
312 | NoArity of string * class |
309 NoClassrel of class * class | |
313 | NoSubsort of sort * sort |
310 NoArity of string * class | |
314 |
311 NoSubsort of sort * sort; |
315 fun msg_class_error pp (NoClassrel (c1, c2)) = |
312 |
|
313 fun class_error pp (NoClassrel (c1, c2)) = |
316 "No class relation " ^ Pretty.string_of_classrel pp [c1, c2] |
314 "No class relation " ^ Pretty.string_of_classrel pp [c1, c2] |
317 | msg_class_error pp (NoArity (a, c)) = |
315 | class_error pp (NoArity (a, c)) = |
318 "No type arity " ^ Pretty.string_of_arity pp (a, [], [c]) |
316 "No type arity " ^ Pretty.string_of_arity pp (a, [], [c]) |
319 | msg_class_error pp (NoSubsort (s1, s2)) = |
317 | class_error pp (NoSubsort (s1, s2)) = |
320 Pretty.string_of_sort pp s1 ^ " is not subsort of " ^ Pretty.string_of_sort pp s2; |
318 Pretty.string_of_sort pp s1 ^ " is not a subsort of " ^ Pretty.string_of_sort pp s2; |
321 |
|
322 fun class_error pp = error o msg_class_error pp; |
|
323 |
319 |
324 exception CLASS_ERROR of class_error; |
320 exception CLASS_ERROR of class_error; |
325 |
321 |
326 |
322 |
327 (* mg_domain *) |
323 (* mg_domain *) |
339 [] => raise Fail "Unknown domain of empty intersection" |
335 [] => raise Fail "Unknown domain of empty intersection" |
340 | c :: cs => fold dom_inter cs (dom c)) |
336 | c :: cs => fold dom_inter cs (dom c)) |
341 end; |
337 end; |
342 |
338 |
343 |
339 |
|
340 (* meet_sort *) |
|
341 |
|
342 fun meet_sort algebra = |
|
343 let |
|
344 fun inters S S' = inter_sort algebra (S, S'); |
|
345 fun meet _ [] = I |
|
346 | meet (TFree (_, S)) S' = |
|
347 if sort_le algebra (S, S') then I |
|
348 else raise CLASS_ERROR (NoSubsort (S, S')) |
|
349 | meet (TVar (v, S)) S' = |
|
350 if sort_le algebra (S, S') then I |
|
351 else Vartab.map_default (v, S) (inters S') |
|
352 | meet (Type (a, Ts)) S = fold2 meet Ts (mg_domain algebra a S); |
|
353 in uncurry meet end; |
|
354 |
|
355 |
344 (* of_sort *) |
356 (* of_sort *) |
345 |
357 |
346 fun of_sort algebra = |
358 fun of_sort algebra = |
347 let |
359 let |
348 fun ofS (_, []) = true |
360 fun ofS (_, []) = true |
351 | ofS (Type (a, Ts), S) = |
363 | ofS (Type (a, Ts), S) = |
352 let val Ss = mg_domain algebra a S in |
364 let val Ss = mg_domain algebra a S in |
353 ListPair.all ofS (Ts, Ss) |
365 ListPair.all ofS (Ts, Ss) |
354 end handle CLASS_ERROR _ => false; |
366 end handle CLASS_ERROR _ => false; |
355 in ofS end; |
367 in ofS end; |
356 |
|
357 |
|
358 (* meet_sort *) |
|
359 |
|
360 fun meet_sort algebra = |
|
361 let |
|
362 fun meet _ [] = I |
|
363 | meet (TFree (_, S)) S' = if sort_le algebra (S, S') then I |
|
364 else raise CLASS_ERROR (NoSubsort (S, S')) |
|
365 | meet (TVar (v, S)) S' = if sort_le algebra (S, S') then I |
|
366 else Vartab.map_default (v, S) (curry (inter_sort algebra) S') |
|
367 | meet (Type (a, Ts)) S = |
|
368 fold2 meet Ts (mg_domain algebra a S) |
|
369 in uncurry meet end; |
|
370 |
368 |
371 |
369 |
372 (* of_sort_derivation *) |
370 (* of_sort_derivation *) |
373 |
371 |
374 fun of_sort_derivation pp algebra {class_relation, type_constructor, type_variable} = |
372 fun of_sort_derivation pp algebra {class_relation, type_constructor, type_variable} = |