[MLton] Number theory and MLton C FFI

[Wesley W. Terpstra]

Good evening.

I have been developing various number theoretic algorithms in C and SML
(MLton), in particular, Number Theoretic Transforms (NTTs) and Fast Galois
Transforms (FGTs). Additionally, I make heavy use of fftw3's Fast Fourier
Transforms (FFTs).

No offence to sml, but these operations simply must be performed in
assembler-style C in order to be efficient. However, as part of prototyping
the C implementation, I have developed a nice algebra abstraction layer in
SML which cannot be ported to C.

What I would like to be able to do now is to replace the prototype
transforms I wrote in SML (for conformance checking of the C code) with
calls to the optimized C equivalents. Then I could continue to use my
abstract SML code, but benefit from the optimized performance.

If I can do this properly, it would make cryptographic and error-correcting
code libraries under SML very convenient to implement. You could just write
up the library and/or application quickly using whatever algebraic
constructions you need. If there is a C implementation to back them, it
is fast, otherwise it still works fine, just slower. Later, you can pick the
speed critical algebraic operations, and back them by an optimized C version.

Unfortunately, there are some snags: 

1- tuples cannot cross the FFI

This might not sound like a big deal, but it actually is.
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. 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...

2- polymorphism has no 'backdoors'

My abstract SML code is able to construct arbitrary groups, euclidean
domains, fields etc from standard algebraic rules. For example, you can
generate a Field from the Euclidean Domain of integers by forming the
rationals using the FractionFieldOfEuclideanDomain functor.

You could also apply FractionFieldOfEuclideanDomain to polynomials.

Similarly, the elements used in a Galois Transform are formed by:
structure F = FiniteFieldOps(
        structure FiniteField = FiniteFieldOfComplex(
                structure FiniteField = Mersenne))

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?

-- 
Wesley W. Terpstra