src/Pure/sorts.ML
changeset 26639 75ea79a50326
parent 26517 ef036a63f6e9
child 26994 197af793312c
equal deleted inserted replaced
26638:1d5d42d8fd66 26639:75ea79a50326
    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*)
   124 
   122 
   125 (* classes *)
   123 (* classes *)
   126 
   124 
   127 fun all_classes (Algebra {classes, ...}) = Graph.all_preds classes (Graph.maximals classes);
   125 fun all_classes (Algebra {classes, ...}) = Graph.all_preds classes (Graph.maximals classes);
   128 
   126 
   129 val minimal_classes = Graph.minimals o classes_of;
       
   130 val super_classes = Graph.imm_succs o classes_of;
   127 val super_classes = Graph.imm_succs o classes_of;
   131 
   128 
   132 
   129 
   133 (* class relations *)
   130 (* class relations *)
   134 
   131 
   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} =