Implicitly heterogeneous multi-stage programming. (English) Zbl 1161.68379
Summary: Previous work on semantics-based multi-stage programming 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.
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.
References:
| [1] | Calcagno, C., Moggi, E. and Taha, W., ”ML-like inference for classifiers,” in European Symposium on Programming (ESOP ’04), LNCS 2986, Springer-Verlag, pp. 79-93, 2004. · Zbl 1126.68330 |
| [2] | Cormen, T., Leiserson, C. and Rivest, R., Introduction to Algorithms, 14th ed. MIT Press and McGraw-Hill Book Company, 1994. · Zbl 1187.68679 |
| [3] | Dynamic Programming Benchmarks, available online from: http://www.metaocaml.org/examples/dp , 2005. |
| [4] | Eckhardt, J., Kaiabachev, R., Pasalic, E., Swadi, K. and Taha, T., ”Implicitly heterogeneous multi-stage programming,” in Proc. of the 4th ACM Intl. Conf. on Generative Programming and Component Engineering (GPCE ’05), LNCS 3676, Springer-Verlag, pp. 275-292, 2005. · Zbl 1161.68379 |
| [5] | Elliott, C., Finne, S. and de Moore, O., ”Compiling embedded languages,” in 17), pp. 9-7, 2000. · Zbl 1044.68545 |
| [6] | Frigo, M and Johnson, S.G, ”FFTW: An adaptive software architecture for the FFT,” in Proc. 1998 IEEE Intl. Conf. Acoustics Speech and Signal Processing vol. 3, IEEE, pp. 1381-1384, 1998. |
| [7] | Gluck, R. and Jorgensen, J., ”Multi-level specialization (extended abstract)” in Partial Evaluation: Practice and Theory (Hatcli, J., Torben, M. and Thiemann, P, ed.), LNCS 1706, Springer-Verlag, pp. 326-337, 1999. |
| [8] | Kamin, S., ”Standard ML as a meta-programming language,” Technical Report, Univ. of Illinois Computer Science Dept, 1996, available at http://www-faculty.cs.uiuc.edu/\(\sim\)kamin/pubs . |
| [9] | Kamin, S.N., Callahan, M. and Clausen, L., ”Lightweight and generative components I: Source-level components,” in Proc. of the First Intl. Symposium on Generative and Component-Based Software Engineering (GCSE ’99), LNCS 1799, Springer-Verlag, pp. 49-64, London, UK, 2000. · Zbl 1044.68529 |
| [10] | MetaOCaml: A compiled, type-safe multi-stage programming language, available online from http://www.metaocaml.org/ , 2004. |
| [11] | Neverov, G. and Roe, P., ”Towards a Fully-reflective Meta-programming Language,” Twenty-Eighth Australasian Computer Science Conference (ACSC ’05), Conferences in Research and Practice in Information Institute Technology Vol. 38, ACS, pp. 151-158, Newcastle, Australia, 2005. |
| [12] | Oregon Graduate Institute Technical Reports, P.O. Box 91000, Portland, OR 97291-1000, USA, available online from ftp://cse.ogi.edu/pub/tech-reports/README.html . |
| [13] | Pasalic, E., Taha, W. and Sheard, T., ”Tagless staged interpreters for typed languages,” in Proc. of the Intl Conf. on Functional Programming (ICFP ’02), Pittsburgh, USA, ACM, pp. 218-229, October 2002. · Zbl 1322.68033 |
| [14] | Stolpmann, G.. DL-ad-hoc dynamic loading for OCaml, available from http://www.ocaml-programming.de/packages/documentation/dl . |
| [15] | Swadi, K., Taha, W., Kiselyov, O. and Pasalic, E., ”A monadic approach for avoiding code duplication when staging memoized functions,” in Proc. of the ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM ’06), ACM Press, January 2006. |
| [16] | Taha, W., Multi-Stage Programming: Its Theory and Applications, PhD thesis, Oregon Graduate Institute of Science and Technology, 1999, available from 12). |
| [17] | Semantics, Applications, and Implementation of Program Generation(Taha, W. (ed.)), LNCS 1924, Springer-Verlag, Montréal, 2000. |
| [18] | Taha, W., ”A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trivial,” in Proc. of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM ’00), Boston, ACM Press, pp. 34-43, 2000. |
| [19] | Taha, W. and Nielsen, M.F., ”Environment classifiers,” in Proc. of the Symposium on Principles of Programming Languages (POPL ’03) New Orleans, Louisisana, ACM SIGPLAN vol. 38(1), pp. 26-37, 2003. · Zbl 1321.68175 |
| [20] | Taha, W. and Sheard, T., ”Multi-stage programming with explicit annotations,” in Proc. of Symposium on Partial Evaluation and Semantics Based Program manipulation, ACM SEGPLAN, pp. 203-217, 1997. · Zbl 0949.68047 |
| [21] | Tarditi, D., Lee, P. and Acharya, A., ”No assembly required: Compiling standard ML to C,” ACM Letters on Programming Languages and Systems, 1(2), pp. 161-177, June 1992. |
| [22] | Xi, H., Chen, C. and Chen, G., ”Guarded recursive datatype constructors,” in Proc. of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of programming languages (POPL ’03), New Orleans, Louisiana, USA, ACM Press, pp. 224-235, 2003. · Zbl 1321.68161 |
| [23] | Cheney, J. and Hinze, R., ”First-Class Phantom Types,” Technical Report 1901, Cornell University, Mar. 2006. |
| [24] | Sheard, T. and Pasalic, E., ”Meta-programming with built-in type equality,” presented at the Fourth International Workshop on Logical Frameworks and Meta-Languages (LFM 4), Cork, Ireland, July, 2004. · Zbl 1278.68062 |
| [25] | Jones, S.P., Vytiniotis, D., Weirich, S and Washburn, G., ”Simple unification-based type inference for GADTs,” in ACM SIGPLAN Notices, vol. 41(9), pp. 50-61, Sep, 2006. |
| [26] | Engler, D.R., ”VCODE : A Retargetable, Extensible, Very Fast Dynamic Code Generation System,” in Proc. of the ACM SIGPLAN Conference on Programming Language Design and Implemantation, New York, ACM Press, pp. 160-170, May, 1996. |
| [27] | Consel, C., and Noel, F., ”A General Approach for Run-Time Specialization and its Application to C,” in Proc. of The 23 rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’96), pp. 145-156, 1996. |
| [28] | Grant, B., Mock, M., Philipose, M., Chambers, C. and Eggers, S.J., ”Annotation-Directed Run-Time Specialization in C,” in Proc. of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, Amsterdam, The Netherlands, pp. 163-178, Jun 1997,. · Zbl 0949.68052 |
| [29] | Sperber, M. and Thiemann, P, ”Two for the Price of One: Composing Partial Evaluation and Compilation” in Proc. of the ACM SIGPLAN ’97 Conference on Programming Language Design and Implementation (PLDI), Las Vegas, Nevada, pp. 215-225, Jun, 1997. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
