[MLton] Structures inside a function?

Matthew Fluet fluet@cs.cornell.edu
Thu, 20 Jan 2005 10:02:28 -0500 (EST)


> The problem is that Math(...) is used on a RING.
> A RING includes multiplication, addition, comparison, and some guarantees.
> There is nothing to say a RING even _has_ a modulus.

Yes, I see.

> Any other suggestions?

Having mused briefly before seeing your reply, I was going to make another
point, which was that functors with non-type arguments are in some sense
suspect, because they cannot be instantiated in a local (expression)  
scope.  I many situations, this isn't a problem; but in some, it really
can be.  For example, I believe that the Standard ML Basis Library has
such a problem with regards to the IO stream and sockets; namely, I don't
believe that there is a way to open a socket (a core-level operation) and
then lift that socket through the IO functors (a module-level operation)  
to get an IMPERATIVE_IO structure for reading from the socket.  (There is 
a degenerate mechanism by opening the socket at the top-level, but then 
you can't recover from errors nicely.)

> I suppose I could incorporate some sort of generalized state which has
> RING-specific type. For everything else I could use unit, but here include
> the modulus.

That appears to be one solution.

> However, how would I then curry this with the operators?
> Right now, for example, a GROUP looks like:
> 
> signature GROUP =
>   sig
>     type t
>     (* type s  (* add some sort of magic state? *) *)
>     val EQ:  (* s -> *)  (t * t) -> t 
>     val MUL: (* s -> *)  (t * t) -> t
>     val DIV: (* s -> *)  (t * t) -> t
>     val INV: (* s -> *)  t -> t
>     val one: (* s -> *)  t
>     ...
>   end
> 
> I then  have a functor called GroupBinding like:
> 
> functor GroupMulPercent(G : GROUP) = 
>   struct
>     val (op *%) = G.MUL
>     val (op /%) = G.DIV
>     val (op !%) = G.INV
>     ...
>   end
> 
> Is there a way to put the currying into the binding functor GroupMulPercent?

You could "prime the pump" with the state in the GroupMulPercent functor:

functor GroupMulPercent(sig structure G : GROUP val s : G.s end) = 
  struct
    val (op *%) = G.MUL s
    val (op /%) = G.DIV s
    val (op !%) = G.INV s
    ...
  end

But, I suspect this just leads us in circles.  You eventually want to pass 
the x argument of factor as the state for a redisue ring.

> The list of functions in my example is small, but in the case of rings or
> polynomials gets quite large. The binding is designed so you can use many
> different groups with multiplication at once. eg: *%, *$, ...

That is an interesting technique for quickly generating different 
bindings.


Here is one more option.  Structures and functors are good at generating 
new types and new polymorphic values; if you require neither, then a 
record is (pretty much) just as good.  So, depending on the other 
operations in your GROUP and RING signatures, the following might help.

signature GROUP =
  sig
    structure Elt : sig type t end
    datatype t = Group of {EQ: Elt.t * Elt.t -> Elt.t,
                           MUL: Elt.t * Elt.t -> Elt.t,
                           INV: Elt.t * Elt.t -> Elt.t,
                           one: Elt.t,
                           ...}
  end

signature GROUP_FLAT =
  sig
    include GROUP
    val group : t (* the group which is flattented into the following *)
    val EQ : Elt.t * Elt.t -> Elt.t
    val MUL : Elt.t * Elt.t -> Elt.t
    val INV : Elt.t * Elt.t -> Elt.t
    val one : Elt.t
    ...
    (* possibly even more that use polymorphism *)
  end

functor FlattenGroup(sig
                       structure G : GROUP
                       val group : G.t
                     end) : GROUP_FLAT
                            where type Elt.t = G.Elt.t
                            where type t = G.t =
struct
  val G.Group {EQ, MUL, INV, one, ...} = group
  val group = group
  (* possibly even more that use polymorphism *)
end

signature RING =
  sig
    structure Elt : sig type t end
    datatype t = Ring of {...}
  end

signature RING_FLAT = ...

functor FlattenRing(...) = ...

signature MATH =
  sig
    structure Ring : RING
    datatype t = Math of {...}
  end

signature MATH_FLAT = ...

functor Math(R : RING) : sig
                           include MATH
                           val mkMath : Ring.t -> t
                         end

functor FlattenMath(...) = ...

functor MathFlat(R : RING_FLAT) : MATH_FLAT where ... =
  struct
    structure M = Math(R)
    val math = mkMath R.ring
    structure MF = FlattenMath(struct
                                 structure M = M
                                 val math = math
                               end)
    open MF
  end

signature RESIDUE_PARAM =
  sig
    structure Base: EUCLIDEAN_DOMAIN
  end

functor Residue(P : RESIDUE_PARAM) : sig 
                                       include RING where Elt.t = Base.t 
                                       val mkRing : Elt.t -> t
                                     end = ...

signature RESIDUE_FLAT_PARAM =
  sig
    structure Base: EUCLIDEAN_DOMAIN
    val modulus : Base.t
  end

functor ResidueFlat(P : FLAT_RESIDUE_PARAM) : RING_FLAT where Elt.t = Base.t =
  struct
     structure R = Residue(P)
     val ring = mkRing P.modulus
     val RF = FlattenRing(struct
                            structure R = R
                            val ring = ring
                          end)
     open RF
  end

So, you can flatten a group/ring/math/etc. if you can construct such an 
object at the top-level (which apparently is your common case).  Once you 
flatten such an object, you have more convenient access to its members.  
However, if your group/ring/etc. depends on a runtime value (like your 
factor example), then you can't flatten it.  You'll still have all the 
operations, just in record form.  You can still project out each of the 
operations.  It is unforunate that you can't use your functor binding 
trick; I think you will need to resort to cut-n-paste in those situations.
(It is truly unfortunate because there is no type-theoretic problem with 
that sort of functor being used in a local scope; it is a clever way of 
generating a bunch of val bindings (with no type or polymorphism)).

Although, after writing all this, I suspect this won't always help in your 
situation, because I assume you want to say things like

signature RING =
  sig
    include GROUP
    (* the ring specific operations *)
  end

indicating that every ring is also a group.