Multi-stage programming with functors and monads:
eliminating abstraction overhead from generic code

Jacques Carette and Oleg Kiselyov

Abstract

With Gaussian Elimination as a representative family of numerical and symbolic algorithms, we use multi-stage programming, monads and Ocaml's advanced module system to demonstrate the complete elimination of the abstraction overhead while avoiding any inspection of the generated code. We parameterize our Gaussian Elimination code to a great extent (over domain, matrix representations, determinant tracking, pivoting policies, result types, etc) at no run-time cost. Because the resulting code is generated just right and not changed afterwards, we enjoy MetaOCaml's guaranty that the generated code is well-typed. We further demonstrate that various abstraction parameters (aspects) can be made orthogonal and compositional, even in the presence of name-generation for temporaries and other bindings and ``interleaving'' of aspects. We also show how to encode some domain-specific knowledge so that ``clearly wrong'' compositions can be statically rejected by the compiler when processing the generator rather than the generated code.

We now have a journal paper (accepted to Science of Computer Programming) describing the results in great detail. The original conference (GPCE) paper is available in PDF and postscript.

The code, the Camlp4 syntax extension, and a test file are available. To compile:

ocamlc -c -pp 'camlp4o pa_extend.cmo q_MLast.cmo' -I +camlp4 pa_monad.ml
metaocamlc -pp 'camlp4o ./pa_monad.cmo' -c gausselim.ml
ocamlmktop -o mytop nums.cma
./mytop ./gausselim.cmo < test.ml

The complete test output is also available.