mlton/backend/equivalence-graph.sig

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  * Copyright (C) 1997-2000 NEC Research Institute.
   5  *
   6  * MLton is released under a BSD-style license.
   7  * See the file MLton-LICENSE for details.
   8  *)
   9
  10 signature EQUIVALENCE_GRAPH_STRUCTS =
  11    sig
  12    end
  13
  14 (* An equivalence graph is an equivalence relation with a weight function on
  15  * classes and an edge relation between classes.
  16  *
  17  * The main operation is coarsen, which takes an equivalence graph and coarsens
  18  * the equivalence relation so that the class weights are as large as possible
  19  * subject to a constraint.
  20  *)
  21
  22 signature EQUIVALENCE_GRAPH =
  23    sig
  24       include EQUIVALENCE_GRAPH_STRUCTS
  25
  26       structure Class:
  27          sig
  28             (* The type of equivalence classes. *)
  29             type t
  30
  31             val plist: t -> PropertyList.t
  32          end
  33
  34       (* The type of equivalence graphs. *)
  35       type t
  36
  37       (* Make two classes equivalent.
  38        * The size of the resulting class is the sum of the sizes of the original
  39        * two classes.  This is a no-op if the classes are already equivalent.
  40        *)
  41       val == : t * Class.t * Class.t -> unit
  42
  43       (* Add a new edge between two classes. *)
  44       val addEdge: t * Class.t * Class.t -> unit
  45
  46       (* Make the equivalence relation as coarse as possible so that the
  47        * number of edges between classes is minimized, subject to the constraint
  48        * that the sum of the node sizes in an equivalence class is
  49        * <= maxClassSize.  Classes for which this constraint was violated by
  50        * previous calls to == should not be made coarser.
  51        *)
  52       val coarsen: t * {maxClassSize: int} -> unit
  53
  54       (* Return a new relation. *)
  55       val new: unit -> t
  56
  57       (* newClass (g, {classSize}) adds a new class to the equivalence graph. *)
  58       val newClass: t * {size: int} -> Class.t
  59    end