Implicitly Heterogeneous Multi-stage Programming

  • Jason Eckhardt
  • Roumen Kaiabachev
  • Emir Pašalić
  • Kedar Swadi
  • Walid Taha
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


Previous work on semantics-based multi-stage programming (MSP) language design focused on homogeneous designs, where the generating and the generated languages are the same. Homogeneous designs simply add a hygienic quasi-quotation and evaluation mechanism to a base language. An apparent disadvantage of this approach is that the programmer is bound to both the expressivity and performance characteristics of the base language. This paper proposes a practical means to avoid this by providing specialized translations from subsets of the base language to different target languages. This approach preserves the homogeneous “look” of multi-stage programs, and, more importantly, the static guarantees about the generated code. In addition, compared to an explicitly heterogeneous approach, it promotes reuse of generator source code and systematic exploration of the performance characteristics of the target languages.

To illustrate the proposed approach, we design and implement a translation to a subset of C suitable for numerical computation, and show that it preserves static typing. The translation is implemented, and evaluated with several benchmarks. The implementation is available in the online distribution of MetaOCaml.


Type System Target Language Source Language Runtime System Base Language 
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.
    Calcagno, C., Moggi, E., Taha, W.: Ml-like inference for classifiers. In: Schmidt, D. (ed.) ESOP 2004. LNCS, vol. 2986, pp. 79–93. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  2. 2.
    Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms, 14th edn. MIT Press and McGraw-Hill Book Company (1994)Google Scholar
  3. 3.
    Dynamic Programming Benchmarks (2005), Available online from:
  4. 4.
    Eckhardt, J., Kaiabachev, R., Pasalic, E., Swadi, K., Taha, W.: Implicitly heterogeneous multi-stage programming (extended version) (June 2005), Available online from:
  5. 5.
    Elliott, C., Finne, S., de Moore, O.: Compiling embedded languages. In: [17], pp. 9–27 (2000)Google Scholar
  6. 6.
    Frigo, M., Johnson, S.G.: FFTW: An adaptive software architecture for the FFT. In: Proc. 1998 IEEE Intl. Conf. Acoustics Speech and Signal Processing, vol. 3, pp. 1381–1384. IEEE, Los Alamitos (1998)Google Scholar
  7. 7.
    Glück, R., Jørgensen, J.: Multi-level specialization (extended abstract). In: Hatcliff, J., Mogensen, T., Thiemann, P. (eds.) DIKU 1998. LNCS, vol. 1706, pp. 326–337. Springer, Heidelberg (1999)Google Scholar
  8. 8.
    Kamin, S.: Standard ML as a meta-programming language. Technical report, Univ. of Illinois Computer Science Dept. (1996), Available at:
  9. 9.
    Kamin, S.N., Callahan, M., Clausen, L.: Lightweight and generative components i: Source-level components. In: Czarnecki, K., Eisenecker, U.W. (eds.) GCSE 1999. LNCS, vol. 1799, pp. 49–64. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  10. 10.
    MetaOCaml, A.: compiled, type-safe multi-stage programming language (2004), Available online from:
  11. 11.
    Neverov, G., Roe, P.: Towards a Fully-reflective Meta-programming Language. In: Conferences in Research and Practice in Information Technology, vol. 38, ACS, Newcastle (2005); Twenty-Eighth Australasian Computer Science Conference (ACSC 2005).Google Scholar
  12. 12.
    Oregon Graduate Institute Technical Reports. P.O. Box 91000, Portland, OR 97291-1000,USA, Available online from:
  13. 13.
    Pašalić, E., Taha, W., Sheard, T.: Tagless staged interpreters for typed languages. In: The International Conference on Functional Programming (ICFP 2002), Pittsburgh, USA. ACM, New York (2002)Google Scholar
  14. 14.
    Stolpmann, G.: Dl- ad-hoc dynamic loading for OCaml, Available from:
  15. 15.
    Swadi, K., Taha, W., Kiselyov, O.: Staging dynamic programming algorithms, Unpublished manuscript (April 2005), available from:
  16. 16.
    Taha, W.: Multi-Stage Programming: Its Theory and Applications. PhD thesis, Oregon Graduate Institute of Science and Technology, Available from [12] (1999)Google Scholar
  17. 17.
    Taha, W. (ed.): SAIG 2000. LNCS, vol. 1924. Springer, Heidelberg (2000)zbMATHGoogle Scholar
  18. 18.
    Taha, W.: A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trivial. In: Proceedings of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM). ACM Press, Boston (2000)Google Scholar
  19. 19.
    Taha, W., Nielsen, M.F.: Environment classifiers. In: The Symposium on Principles of Programming Languages (POPL 2003), New Orleans (2003)Google Scholar
  20. 20.
    Taha, W., Sheard, T.: Mult-stage programming with explicit annotations. In: Proceedings of Symposium on Partial Evaluation and Semantics Based Program manipulation, ACM SIGPLAN, pp. 203–217 (1997)Google Scholar
  21. 21.
    Tarditi, D., Lee, P., Acharya, A.: No assembly required: Compiling standard ML to C. ACM Letters on Programming Languages and Systems 1(2), 161–177 (1992)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Jason Eckhardt
    • 1
  • Roumen Kaiabachev
    • 1
  • Emir Pašalić
    • 1
  • Kedar Swadi
    • 1
  • Walid Taha
    • 1
  1. 1.Rice UniversityHoustonUSA

Personalised recommendations