×

zbMATH — the first resource for mathematics

Multi-stage programming with functors and monads: eliminating abstraction overhead from generic code. (English) Zbl 1215.68059
Summary: We 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.

MSC:
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Carette, J.: Gaussian elimination: A case study in efficient genericity with metaocaml, Sci. comput. Programming 62, No. 1, 3-24 (2006) · Zbl 1100.68130
[2] Monagan, M. B.; Geddes, K. O.; Heal, K. M.; Labahn, G.; Vorkoetter, S. M.; Mccarron, J.; Demarco, P.: Maple 7 programming guide, (2001)
[3] Gruntz, D.; Monagan, M.: Introduction to Gauss, SIGSAM bull. 28, No. 2, 3-19 (1994)
[4] Jenks, R. D.; Sutor, R. S.: AXIOM: the scientific computation system, (1992) · Zbl 0758.68010
[5] 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, J. parallel distrib. Comput. 61, No. 12, 1803-1826 (2001) · Zbl 1006.68025
[6] T.L. Veldhuizen, Active libraries and universal languages, Ph.D. Thesis, Indiana University Computer Science, May 2004. http://osl.iu.edu/ tveldhui/papers/2004/dissertation.pdf
[7] Cohen, A.; Donadio, S.; Garzarán, M. J.; Herrmann, C. A.; Kiselyov, O.; Padua, D. A.: In search of a program generator to implement generic transformations for high-performance computing, Sci. comput. Programming 62, No. 1, 25-46 (2006) · Zbl 1100.68535
[8] Czarnecki, K.; Eisenecker, U. W.: Generative programming: methods, tools, and applications, (2000)
[9] Veldhuizen, T. L.: Arrays in blitz++, Lecture notes in computer science, 223-230 (1998)
[10] Musser, D. R.; Stepanov, A. A.: Generic programming, Lecture notes in computer science 358, 13-25 (1989)
[11] Musser, D. R.; Stepanov, A. A.: Algorithm-oriented generic libraries, Softw. - pract. Exp. 24, No. 7, 623-642 (1994)
[12] Siek, J.; Lee, L. -Q.; Lumsdaine, A.: The boost graph library: user guide and reference manual, (2002)
[13] John, I.; Reynders, V. W.; Cummings, J. C.: The POOMA framework, Comput. phys. 12, No. 5, 453-459 (1998)
[14] Whaley, R. C.; Petitet, A.; Dongarra, J. J.: Automated empirical optimization of software and the ATLAS project, Parallel comput. 27, No. 1–2, 3-35 (2001) · Zbl 0971.68033
[15] Kohlbecker, E. E.; Friedman, D. P.; Felleisen, M.; Duba, B. F.: Hygienic macro expansion, , 151-161 (1986)
[16] D. de Rauglaudre, Camlp4 reference manual, January 2002. http://caml.inria.fr/camlp4/manual/
[17] Czarnecki, K.; O’donnell, J. T.; Striegnitz, J.; Taha, W.: DSL implementation in metaocaml, template haskell, and C++, Lecture notes in computer science 3016, 51-72 (2003)
[18] Calcagno, C.; Taha, W.; Huang, L.; Leroy, X.: Implementing multi-stage languages using asts, gensym, and reflection, Lecture notes in computer science 2830, 57-76 (2003)
[19] MetaOCaml. http://www.metaocaml.org
[20] Taha, W.; Sheard, T.: Multi-stage programming with explicit annotations, , 203-217 (1997) · Zbl 0949.68047
[21] W. Taha, Multi-stage programming: Its theory and applications, Ph.D. Thesis, Oregon Graduate Institute of Science and Technology, 1999
[22] Taha, W.: A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of metaml is non-trival, , 34-43 (2000)
[23] M. Püschel, J.M.F. Moura, J. Johnson, D. Padua, M. Veloso, B.W. Singer, J. Xiong, F. Franchetti, A. Gačić, Y. Voronenko, K. Chen, R.W. Johnson, N. Rizzolo, SPIRAL: Code generation for DSP transforms, in: Program Generation, Optimization, and Adaptation, Proc. IEEE 93 (2) (special issue)
[24] Z. Chen, J. Dongarra, P. Luszczek, K. Rothe, Lapack for clusters project: An example of self adapting numerical software, in: Hawaii International Conference on System Sciences, HICSS-37
[25] Kiselyov, O.; Swadi, K. N.; Taha, W.: A methodology for generating verified combinatorial circuits, , 249-258 (2004)
[26] J. Carette, O. Kiselyov, Multi-stage programming with functors and monads: Eliminating abstraction overhead from generic code, in: Glück, Lowry [R. Glück, M.R. Lowry (Eds.), Generative Programming and Component Engineering, 4th Internation Conference, GPCE 2005, Tallinn, Estonia, September 29–October 1, 2005, Proceedings, in: Lecture Notes in Computer Science, vol. 3676, Springer, 2005], pp. 256–274 · Zbl 1215.68059
[27] Swadi, K. N.; Taha, W.; Kiselyov, O.; Pasalic, E.: A monadic approach for avoiding code duplication when staging memoized functions, Pepm, 160-169 (2006)
[28] Source code. http://www.cas.mcmaster.ca/ carette/metamonads/ · Zbl 1252.68055
[29] Golub, G. H.; Van Loan, C. F.: Matrix computations, (1996) · Zbl 0865.65009
[30] Kiczales, G.; Lamping, J.; Menhdhekar, A.; Maeda, C.; Lopes, C.; Loingtier, J. -M.; Irwin, J.: Aspect-oriented programming, Proceedings European conference on object-oriented programming 1241, 220-242 (1997)
[31] Irwin, J.; Loingtier, J. -M.; Gilbert, J. R.; Kiczales, G.; Lamping, J.; Mendhekar, A.; Shpeisman, T.: Aspect-oriented programming of sparse matrix code, , 249-256 (1997)
[32] A. Mendhekar, G. Kiczales, J. Lamping, RG: A case-study for aspect-oriented programming, Tech. Rep. SPL97-009 P9710044, Xerox PARC, Palo Alto, CA, USA, February 1997
[33] Parnas, D. L.: On the criteria to be used in decomposing systems into modules, Commun. ACM 15, No. 12, 1053-1058 (1972)
[34] Parnas, D. L.: On the design and development of program families, IEEE trans. Softw. eng. 2, No. 1, 1-9 (1976) · Zbl 0352.68032
[35] E.W. Dijkstra, On the role of scientific thought, published as [E.W. Dijkstra, On the role of scientific thought, in: Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982, pp. 60–66]. http://www.cs.utexas.edu/users/EWD/ewd04xx/EWD447.PDF
[36] Zhou, W.; Carette, J.; Jeffrey, D. J.; Monagan, M. B.: Hierarchical representations with signatures for large expression management, Lecture notes in computer science 4120, 254-268 (2006) · Zbl 1156.68641
[37] A. Bondorf, Improving binding times without explicit CPS-conversion, in: 1992 ACM Conference on Lisp and Functional Programming, San Francisco, CA, 1992, pp. 1–10
[38] A. Bondorf, D. Dussart, Improving CPS-based partial evaluation: Writing cogen by hand, in: ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, FL, 1994, pp. 1–9
[39] Jones, S. Peyton: The revised haskell 98 report, (2003) · Zbl 1067.68041
[40] Moggi, E.: Notions of computation and monads, Inform. comp. 93, No. 1, 55-92 (1991) · Zbl 0723.68073
[41] A. Filinski, Representing monads, in: POPL, 1994, pp. 446–457
[42] Liang, S.; Hudak, P.; Jones, M.: Monad transformers and modular interpreters, , 333-343 (1995)
[43] Taha, W.; Nielsen, M. F.: Environment classifiers, , 26-37 (2003) · Zbl 1321.68175
[44] MLton team, Property list. http://mlton.org/PropertyList
[45] Burden, R. L.; Faires, J. D.: Numerical analysis, (1989) · Zbl 0671.65001
[46] Bareiss, E. H.: Sylvester’s identity and multistep Gaussian elimination, Math. comput. 22, No. 103, 565-579 (1968) · Zbl 0187.09701
[47] J. Eckhardt, R. Kaiabachev, E. Pasalic, K.N. Swadi, W. Taha, Implicitly heterogeneous multi-stage programming, in: Glück, Lowry [R. Glück, M.R. Lowry (Eds.), Generative Programming and Component Engineering, 4th Internation Conference, GPCE 2005, Tallinn, Estonia, September 29–October 1, 2005, Proceedings, in: Lecture Notes in Computer Science, vol. 3676, Springer, 2005], pp. 275–292 · Zbl 1161.68379
[48] Watt, S. M.; Aldor: J.grabmeiere.kaltofenv.weispfennigcomputer algebra handbook: foundations, applications, systems, Computer algebra handbook: foundations, applications, systems, 265-270 (2003)
[49] Glück, R.; Nakashige, R.; Zöchling, R.: Binding-time analysis applied to mathematical algorithms, , 137-146 (1995) · Zbl 0881.68052
[50] Glück, R.; Jørgensen, J.: An automatic program generator for multi-level specialization, LISP symb. Comput. 10, No. 2, 113-158 (1997)
[51] Hudak, P.: Building domain-specific embedded languages, ACM comput. Surv. 28, No. 4es, 196 (1996)
[52] Mernik, M.; Heering, J.; Sloane, A. M.: When and how to develop domain-specific languages, ACM comput. Surv. 37, No. 4, 316-344 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.