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

AbstractWe use multi-stage programming, monads and Ocaml’s advanced module system to demonstrate how to eliminate all abstraction overhead from generic programs, while avoiding any inspection of the resulting code. We demonstrate this clearly with Gaussian Elimination as a representative family of symbolic and numeric algorithms. We parameterize our code to a great extent–over domain, input and permutation matrix representations, determinant and rank tracking, pivoting policies, result types, etc.–at no run-time cost. Because the resulting code is generated just right and not changed afterward, MetaOCaml guarantees 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 “interleaving” of aspects. We also show how to encode some domain-specific knowledge so that “clearly wrong” compositions can be rejected at or before generation time, rather than during the compilation or running of the generated code