[MLton] Number theory and MLton C FFI

[Wesley W. Terpstra]

On Thu, Oct 21, 2004 at 12:20:47PM -0700, Stephen Weeks wrote:
> If you want to guarantee that a vector is flattened (and I understand
> your reasons), the only solution I see is to do it yourself, and to
> build some code to make it feel like you're dealing with pairs.
> Something like the following.
> 
> ----------------------------------------------------------------------
> structure FlatPairVector:
>    sig
>       type 'a t
> 
>       val length: 'a t -> int
>       val tabulate: int * (int -> 'a * 'a) -> 'a t
>       val sub: 'a t * int -> 'a * 'a
>    end =
>    struct
>       datatype 'a t = T of 'a vector
> 
>       fun length (T v) = Int.quot (Vector.length v, 2)
> 
>       fun sub (T v, i) = (Vector.sub (v, 2 * i), Vector.sub (v, 2 * i + 1))
> 
>       fun tabulate (n, f) =
> 	 let
> 	    val index = ref 0
> 	    val elt = ref NONE
> 	 in
> 	    T (Vector.tabulate
> 	       (2 * n, fn _ =>
> 		case !elt of
> 		   NONE => 
> 		      let
> 			 val (x, y) = f (!index)
> 			 val () = elt := SOME y
> 			 val () = index := 1 + !index
> 		      in
> 			 x
> 		      end
> 		 | SOME y => (elt := NONE; y)))
> 	 end
>    end

> You can use FlatPairVector when you build your polynomials over
> complex numbers.  This can be made easier and more general if your
> functor for making polynomials abstracts over the implementation of
> vectors, so that you pass it both the field element and the vector
> implementation.

Ok... I think I get it.

The code for instantiating a polynomial over say Mersenne complex
numbers looks like this:

structure R = EuclideanDomainOps(
	(* The EuclideanDomain only includes ops +,-,*, etc *)
	structure EuclideanDomain = PolynomialOverFiniteField(
		structure FiniteField = FiniteFieldOfComplex(
			structure FiniteField = Mersenne)))

(* as a side note, Mersenne at the moment is a module, but I'd like
 * to make it into functor too which takes the k in 2^k-1
 *)

open R (* all the ED ops and also algos like gcd, exp, factor ... *)

So, I can tell the PolynomialOverFiniteField functor to use a special vector
type, which is like your example and expects some form of tuple elements
like FiniteFieldOfComplex or QuotientFieldOfEuclideanDomain ?

I need to think about this, but it does sound like it might solve my
problem. =) So I would have PolynomialOverFiniteFieldWithCustomVector
which is the real implementation and PolynomialOverFiniteField just
passes a vector to it for default behaviour?

The problem I see is that code doesn't 'automatically' benefit from the
vector flattening. It has to target it. Any code which doesn't do it will 
be incompatible with code that does. If I could somehow automatically 
predicate functors off the parameters I could solve this transparently.

Also, future constructions might accept an arbitrary field, and internally
build a polynomial over it, they wouldn't know that they should provide a
special vector to the polynomial functor.

Certainly your adaptor suggestion would leave the ComplexMersennes as the
same type, but the polynomial types themselves would be different and could
not be multiplied, etc.

Also, I'm probably mistaken, but I feel that an MLton array of pairs like
this will already be 'flat' and this special adaptor just makes one version
appear different mlton to coerce it to work with the FFI.

Another question, how would I initialize a vector from C?
They're supposed to be constant --- what happens if I blithely
overwrite the contents?

> > There is optimized C code only available for some of these
> > combinations.  Ideally, I would like to be somehow able to check if
> > FiniteFieldOfComplex is applied to a particular module, and then use
> > the C methods, otherwise use the generic module-polymorphic SML
> > implementation.
> >
> > Is it feasible to acheive this goal with MLton?
> 
> The only way I see to do this is to step outside the language, and to
> produce different "linking" code (i.e. functor applications and
> structure definitions) depending on what's available via C libraries.
> The SML type system should be quite helpful here.

So, the MLton compiler peeks inside a library to see if there already is a
method with the right name? (assuming there's some sort of name mangling
involving the parameters to a functor...)

That would be perfect!
Does this already exist?
How would I go about doing that?

-- 
Wesley W. Terpstra