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

  • Jacques Carette
  • Oleg Kiselyov
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


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.


Gaussian Elimination Code Expression Abstract Data Type Sharing Constraint Tracking Variable 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bondorf, A.: Improving binding times without explicit CPS-conversion. In: 1992 ACM Conference on Lisp and Functional Programming, San Francisco, California, pp. 1–10 (1992)Google Scholar
  2. 2.
    Calcagno, C., Taha, W., Huang, L., Leroy, X.: Implementing multi-stage languages using asts, gensym, and reflection. In: Czarnecki, K., Pfenning, F., Smaragdakis, Y. (eds.) GPCE 2003. LNCS, vol. 2830, pp. 57–76. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  3. 3.
    Carette, J.: Gaussian Elimination: a case study in efficient genericity with MetaOCaml (2005) (submitted)Google Scholar
  4. 4.
    Chen, Z., Dongarra, J., Luszczek, P., Rothe, K.: Lapack for clusters project: An example of self adapting numerical software. In: Hawaii International Conference on System Sciences HICSS-37 (2004)Google Scholar
  5. 5.
  6. 6.
    Cohen, A., Donadio, S., Garzara’n, M.J., Herrmann, C., Padua, D. In Search for a program generator to implement generic transformations for high-performance computing. In: MetaOCaml Workshop (October 2004)Google Scholar
  7. 7.
    Czarnecki, K., Eisenecker, U.W.: Generative programming: methods, tools, and applications. ACM Press/Addison-Wesley Publishing Co. (2000)Google Scholar
  8. 8.
    Czarnecki, K., O’Donnell, J.T., Striegnitz, J., Taha, W.: DSL implementation in MetaOCaml, Template Haskell, and C++. In: Lengauer, C., Batory, D.S., Consel, C., Odersky, M. (eds.) Domain-Specific Program Generation. LNCS, vol. 3016, pp. 51–72. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  9. 9.
    de Rauglaudre, D.: Camlp4 reference manual (January 2002),
  10. 10.
    Dijkstra, E.W.: On the role of scientific thought. Published as [11]Google Scholar
  11. 11.
    Dijkstra, E.W.: On the role of scientific thought. In: Selected Writings on Computing: A Personal Perspective, pp. 60–66. Springer, Heidelberg (1982)Google Scholar
  12. 12.
    Eckhardt, J.L., Kaiabachev, R., Swadi, K.N., Taha, W., Kiselyov, O.: Practical aspects of multi-stage programming. Rice University Techical Report TR05-451 (2004), (February 2004)
  13. 13.
    Filinski, A.: Representing monads. In: POPL, pp. 446–457 (1994)Google Scholar
  14. 14.
    Glück, R., Jørgensen, J.: An automatic program generator for multi-level specialization. Lisp and Symbolic Computation 10(2), 113–158 (1997)CrossRefGoogle Scholar
  15. 15.
    Glück, R., Nakashige, R., Zöchling, R.: Binding-time analysis applied to mathematical algorithms. In: System Modelling and Optimization (1995)Google Scholar
  16. 16.
    Jenks, R.D., Sutor, R.S.: AXIOM: The Scientific Computation System. Springer, Heidelberg (1992)zbMATHGoogle Scholar
  17. 17.
    Reynders III, J.V.W., Cummings, J.C.: The POOMA framework. Comput. Phys. 12(5), 453–459 (1998)CrossRefGoogle Scholar
  18. 18.
    Kennedy, K., Broom, B., Cooper, K., Dongarra, J., Fowler, R., Gannon, D., Johnsson, L., Mellor-Crummey, J., Torczon, L.: Telescoping languages: A strategy for automatic generation of scientific problem-solving systems from annotated libraries. Journal of Parallel and Distributed Computing 61(12), 1803–1826 (2001)zbMATHCrossRefGoogle Scholar
  19. 19.
    Kiczales, G., Lamping, J., Menhdhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M., Irwin, J.: Aspect-oriented programming. In: Aksit, M., Matsuoka, S. (eds.) ECOOP 1997. LNCS, vol. 1241, pp. 220–242. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  20. 20.
    Kiselyov, O., Swadi, K.N., Taha, W.: A methodology for generating verified combinatorial circuits. In: EMSOFT 2004: Proceedings of the fourth ACM international conference on Embedded software, pp. 249–258. ACM Press, New York (2004)CrossRefGoogle Scholar
  21. 21.
    Kohlbecker, E.E., Friedman, D.P., Felleisen, M., Duba, B.F.: Hygienic macro expansion. In: LISP and Functional Programming, pp. 151–161 (1986)Google Scholar
  22. 22.
    Liang, S., Hudak, P., Jones, M.: Monad transformers and modular interpreters. In: POPL 1995: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, pp. 333–343. ACM Press, New York (1995)Google Scholar
  23. 23.
  24. 24.
    Moggi, E.: Notions of computation and monads. Information and Computation 93(1), 55–92 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  25. 25.
    Musser, D.R., Stepanov, A.A.: Algorithm-oriented generic libraries. Software - Practice and Experience 24(7), 623–642 (1994)CrossRefGoogle Scholar
  26. 26.
    Parnas, D.L.: On the criteria to be used in decomposing systems into modules. Commun. ACM 15(12), 1053–1058 (1972)CrossRefGoogle Scholar
  27. 27.
    Jones, S.P., et al.: The Revised Haskell 1998 Report. Cambridge Univ. Press, Cambridge (2003), Also on: Google Scholar
  28. 28.
    Püschel, M., Moura, J.M.F., Johnson, J., Padua, D., Veloso, M., Singer, B.W., Xiong, J., Franchetti, F., Gačić, A., Voronenko, Y., Chen, K., Johnson, R.W., Rizzolo, N.: SPIRAL: Code generation for DSP transforms. In: Proceedings of the IEEE, special issue on Program Generation, Optimization, and Adaptation, vol. 93(2) (2005)Google Scholar
  29. 29.
    Siek, J., Lee, L.-Q., Lumsdaine, A.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, Reading (2002)Google Scholar
  30. 30.
    Taha, W.: Multi-Stage Programming: its theory and applications. PhD thesis, Oregon Graduate Institute of Science and Technology (1999)Google Scholar
  31. 31.
    Taha, W.: A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trival. In: PEPM, pp. 34–43 (2000)Google Scholar
  32. 32.
    Taha, W., Sheard, T.: Multi-stage programming with explicit annotations. In: Proceedings of the Symposium on Partial Evaluation and Semantic-Based Program Manipulation (PEPM), Amsterdam, pp. 203–217. ACM Press, New York (1997)CrossRefGoogle Scholar
  33. 33.
    Veldhuizen, T.L.: Arrays in Blitz++. In: Caromel, D., Oldehoeft, R.R., Tholburn, M. (eds.) ISCOPE 1998. LNCS, vol. 1505, pp. 223–230. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  34. 34.
    Veldhuizen, T.L.: Active Libraries and Universal Languages. PhD thesis, Indiana University Computer Science (May 2004)Google Scholar
  35. 35.
    Watt, S.M.: Aldor. In: Grabmeier, J., Kaltofen, E., Weispfennig, V. (eds.) Computer Algebra Handbook: Foundations, Applications, Systems. Springer, Heidelberg (2003)Google Scholar
  36. 36.
    Clint Whaley, R., Petitet, A., Dongarra, J.J.: Automated empirical optimization of software and the ATLAS project. Parallel Computing 27(1-2), 3–35 (2001)zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Jacques Carette
    • 1
  • Oleg Kiselyov
    • 2
  1. 1.McMaster UniversityHamiltonCanada
  2. 2.FNMOCMontereyUSA

Personalised recommendations