[MLton] Number theory and MLton C FFI

[Stephen Weeks]

> 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:
   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.  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.