Multi-stage Programming with Functors and Monads: Eliminating Abstraction Overhead from Generic Code

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.