[MLton] Number theory and MLton C FFI

Stephen Weeks MLton@mlton.org
Thu, 21 Oct 2004 12:20:47 -0700

> FGTs and FFTs operate on arrays of complex numbers.
> The correct SML types are (Word32 * Word32) array/vector and (real *
> real) array/vector respectively. Certainly, I could flatten this to
> Word32 array, but then the SML code would not be able to perform
> arithmetic on the elements in the array correctly; the granularity
> is wrong.
> Furthermore, the constructed SML modules for FGTs and FFTs build a
> complex number out of pairs and polynomials are then a vector over
> those pairs.  This means the type checker will prevent me from
> passing the polynomial to C because of the pair.

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:
      type 'a t

      val length: 'a t -> int
      val tabulate: int * (int -> 'a * 'a) -> 'a t
      val sub: 'a t * int -> 'a * 'a
   end =
      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) =
	    val index = ref 0
	    val elt = ref NONE
	    T (Vector.tabulate
	       (2 * n, fn _ =>
		case !elt of
		   NONE => 
			 val (x, y) = f (!index)
			 val () = elt := SOME y
			 val () = index := 1 + !index
		 | SOME y => (elt := NONE; y)))

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.  With suitable abstraction, the SML code should never
know that the underlying representation is flat, and your
"granularity" worry goes away.

> At the level of the ComplexOfField functor there is no way to
> 'unzip' the vector as it does not look inside the implementation of
> the Field module it was built from. This leads too...

Hopefully abstracting over the vector implementation solves this.

> My abstract SML code is able to construct arbitrary groups, euclidean
> domains, fields etc from standard algebraic rules.
> 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.