[MLton-devel] new basis library

[Matthew Fluet]

> I'm curious about  the implementation issues involved
> in getting opaque signature matching to work reasonably.  I haven't
> had a chance to read the new basis signatures carefully enough.

The first issue is conceptual; I've needed to overcome an instinct to
look at the specification and think that it corresponds to actual code
that should appear in the implementation.  This is most apparent in the
mutual references in sharing constraints between CharVector.vector and
String.string.

The other issue is when we choose to bind by an opaque signature.  The
best choice would seem to be as late as possible; that is, freely share
types inside the basis, but in the exported top level, use opaque
signatures.  This makes sense, except when there are lots sharing
constraints.  For example, here is how all the Bool related structures
should be exported, as listed by the basis library. 

structure Bool:> BOOL
structure BoolVector:> MONO_VECTOR 
                       where type elem = bool
structure BoolVectorSlice:> MONO_VECTOR_SLICE 
                            where type vector = BoolVector.vector
                            where type elem = bool
structure BoolArray:> MONO_ARRAY 
                      where type vector = BoolVector.vector
                      where type elem = bool
structure BoolArraySlice:> MONO_ARRAY_SLICE 
                           where type vector = BoolVector.vector
                           where type vector_slice = BoolVectorSlice.slice
                           where type array = BoolArray.array
                           where type elem = bool
structure BoolArray2:> MONO_ARRAY2 
                       where type vector = BoolVector.vector
                       where type bool = bool

There is also the requirement that Bool.bool be equal to the top-level
(unqualified) bool type.  So, the first structure should (equivalently)
read

structure Bool:> BOOL where type bool = bool

Now, in the old basis implementation, the top level bindings are effected
by the following:

structure Bool: BOOL = Bool
structure BoolArray: MONO_ARRAY = BoolArray
structure BoolArray2: MONO_ARRAY2 = BoolArray2
structure BoolVector: MONO_VECTOR = BoolVector

Simple, but BoolVector isn't in scope for the BoolArray:> MONO_ARRAY
binding, so something this simple can't work.  

The way the basis is currently implemented, we build the Bool structure
first, then rebind the Vector: VECTOR_EXTRA under the MONO_VECTOR_EXTRA
signature (the _EXTRA include the slice structure as a substructure as
well as a few other functions used elsewhere in the basis) as BoolVector,
then extract the MonoVectorSlice from BoolVector.  Similar process
produces BoolArray and BoolArraySlice.  Everything is fine, and all the
types that are supposed to be equal are equal.  Now, though, comes the
question of how to put the above constraints on the strutures lying 
around.  The naive approach doesn't work:

structure Bool: BOOL
= Bool
structure BoolVector:> MONO_VECTOR
                       where type elem = bool
= BoolVector (* : MONO_VECTOR_EXTRA *)
structure BoolVectorSlice:> MONO_VECTOR_SLICE
                            where type vector = BoolVector.vector
                            where type elem = bool
= BoolVectorSlice (* : MONO_VECTOR_SLICE_EXTRA *)

because after the opaque signature on BoolVector, BoolVector.vector is
abstract and not-equal to the type used by BoolVectorSlice.

One approach to deal with these monomorphic-sequence structures is to not
build them up piece by piece as they are currently (i.e., Bool in
bool.sml, BoolVector in mono-vector.sml, BoolArray in mono-array.sml), but
to have a functor build up all the mono-morphic sequence structures
together, and simultaneously export them under an opaque signature:

functor MonoSequences(type elem):>
sig
 type elem
 Vector: MONO_VECTOR where type elem = elem
 VectorSlice: MONO_VECTOR_SLICE where type vector = Vector.vector
                                where type elem = elem
 ...
end = 
struct
  type elem = elem
  structure Vector = struct
                      open Vector
                      type elem = elem
                      type vector = elem vector
                     end
  structure VectorSlice = struct
                           open VectorSlice
                           type elem = elem
                           type vector = Vector.vector
                          end
  ...
end

structure BoolSequences = MonoSequences(type elem = bool)
structure BoolVector = BoolSequences.Vector
structure BoolVectorSlice = BoolSequences.VectorSlice

I think that this has the same semantics as the constraints given in the
specification.


Note, I really like the idea of the opaque signatures, even if they'll be 
tough to get right. For example, MLton currently accepts the following
program:

val v = Vector.fromList [false, true, false]
val b = BoolVector.foldr (fn (a,b) => a andalso b) true v
val _ = print (Bool.toString b);

But, if we ever implemented BoolVector.vector as a bit-vector, then the
program would fail to type-check.

Under the new basis, the program fails to type check regardless of the
implementation of BoolVector.vector.



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel