More Web Proxy on the site http://driver.im/

research-article

Free access

Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs

Authors:

Martin OderskyAuthors Info & Claims

Communications of the ACM, Volume 55, Issue 6

Pages 121 - 130

https://doi.org/10.1145/2184319.2184345

Published: 01 June 2012 Publication History

All formats PDF

Abstract

Good software engineering practice demands generalization and abstraction, whereas high performance demands specialization and concretization. These goals are at odds, and compilers can only rarely translate expressive high-level programs to modern hardware platforms in a way that makes best use of the available resources.

Generative programming is a promising alternative to fully automatic translation. Instead of writing down the target program directly, developers write a program generator, which produces the target program as its output. The generator can be written in a high-level, generic style and can still produce efficient, specialized target programs. In practice, however, developing high-quality program generators requires a very large effort that is often hard to amortize.

We present lightweight modular staging (LMS), a generative programming approach that lowers this effort significantly. LMS seamlessly combines program generator logic with the generated code in a single program, using only types to distinguish the two stages of execution. Through extensive use of component technology, LMS makes a reusable and extensible compiler framework available at the library level, allowing programmers to tightly integrate domain-specific abstractions and optimizations into the generation process, with common generic optimizations provided by the framework.

LMS is well suited to develop embedded domain-specific languages (DSLs) and has been used to develop powerful performance-oriented DSLs for demanding domains such as machine learning, with code generation for heterogeneous platforms including GPUs. LMS has also been used to generate SQL for embedded database queries and JavaScript for web applications.

References

[1]

Calcagno, C., Taha, W., Huang, L., Leroy, X. Implementing multi-stage languages using asts, gensym, and reflection. GPCE, F. Pfenning and Y. smaragdakis, eds. Volume 2830 of Lecture Notes in Computer Science (2003). Springer, 57--76.

Digital Library

[2]

Carette, J. Kiselyov, O., chieh Shan, C., Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J. Funct. Program, 19, 5 (2009), 509--543.

Digital Library

[3]

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. Program. 62, 1 (2006), 25--46.

Digital Library

[4]

Czarnecki, K., O'Donnell, J.T., Striegnitz, J., Taha, W., Dsl implementation in metaocaml, template haskell, and c++. In Domain-Specific Program Generation (2003), 51--72.

[5]

Elliott, C., Finne, S., de Moor, O. Compiling embedded languages. J. Funct, Program, 13, 3 (2003), 455-481.

Digital Library

[6]

Frigo, M. A fast Fourier transform compiler. In PLDI (1999), 169--180.

Digital Library

[7]

Guerrero, M., Pizzi, E., Rosenbaum, R., Swadi, K.N., Taha, W. Implementing dsls in metaocaml. OOPSLA Companion, J. M. Vlissides and D. C. Schmidt, eds. (2004). ACM, 41--42.

Digital Library

[8]

Hofer, C., Ostermann, K., Rendel, T., Moors, A. Polymorphic embedding of dsls. GPCE, Y. Smaragdakis and J.G. Siek, eds. (2008). ACM, 137--148.

Digital Library

[9]

Hudak, P. Modular domain specific languages and tools. In Proceedings of Fifth International Conference on Software Reuse (June 1998), 134--142.

Digital Library

[10]

Kameyama, Y., Kiselyov, O., chieh Shan, C. Shifting the stage: staging with delimited control. PEPM, G. Puebla and G. Vidal, eds. (2009). ACM, 111--120.

Digital Library

[11]

Kennedy, K., Broom, B., Cooper, K.D., Dongarra, J., Fowler, R.J., Gannon, D., Johnsson, S.L., Mellor-Crummey, J.M., Torczon, L. Telescoping languages: A strategy for automatic generation of scientific problem-solving systems from annotated libraries. J. Parallel Distrib, Comput. 61, 12 (2001), 1803--1826.

[12]

Kiselyov, O., Swadi, K.N., Taha, W. A methodology for generating verified combinatorial circuits. EMSOFT, G.C. Buttazzo, ed. (2004). ACM, 249--258.

Digital Library

[13]

Lee, H., Brown, K.J., Sujeeth, A.K., Chafi, H., Rompf, T., Odersky, M., Olukotun, K. Implementing domain-specific languages for heterogeneous parallel computing. IEEE Micro 31, 5 (2011), 42--53.

Digital Library

[14]

Leijen, D., Meijer, E. Domain specific embedded compilers. In DSL (1999), 109--122.

Digital Library

[15]

Odersky, M., Zenger, M. Scalable component abstractions. OOPSLA, R. E. Johnson and R.P. Gabriel, eds. (2005). ACM, 41--57.

Digital Library

[16]

Pfenning, F., Elliott, C. Higher-order abstract syntax. In PLDI (1988), 199--208.

Digital Library

[17]

Püschel, M., Moura, J.M.F., Singer, B., Xiong, J., Johnson, J., Padua, D.A., Veloso, M.M., Johnson, R.W. Spiral: A generator for platform-adapted libraries of signal processing alogorithms. IJHPCA, 18, 1 (2004), 21--45.

Digital Library

[18]

Rompf, T., Sujeeth, A.K., Lee, H., Brown, K.J., Chafi, H., Odersky, M., Olukotun, K. Building-blocks for performance oriented dsls. In DSL (2011), 93--117.

[19]

Sheard, T., Benaissa, Z.E.A., Pasalic, E. Dsl implementation using staging and monads. In DSL (1999), 81--94.

Digital Library

[20]

Sheard, T., Jones, S.L.P. Template meta-programming for haskell. SIGPLAN Not. 37, 12 (2002), 60--75.

Digital Library

[21]

Swadi, K.N., Taha, W., Kiselyov, O., Pasalic, E. A monadic approach for avoiding code duplication when staging memoized functions. PEPM, J. Hatcliff and F. Tip, eds. (2006). ACM, 160--169.

Digital Library

[22]

Taha, W., Sheard, T. Metaml and multi-stage programming with explicit annotations. Theor, Comput, Sci. 248(1--2) (2000), 211--242.

Digital Library

[23]

Veldhuizen. T "Expression Templates," in Stanley B. Lippman (Editor), C++ Gems (SIGS Books and Multimedia, 1996), pp. 475--488

Digital Library

[24]

Veldhuizen, T.L. Active libraries and universal languages. PhD thesis, Indiana University Computer Science (May 2004).

Digital Library

[25]

Whaley, R.C., Petitet, A., Dongarra, J. Automated empirical optimizations of software and the atlas project. Parallel Comput. 27(1--2) (2001), 3--35.

Digital Library

Cited By

Jungmair MEngelke AGiceva J(2024)HiPy: Extracting High-Level Semantics from Python Code for Data ProcessingProceedings of the ACM on Programming Languages10.1145/36897378:OOPSLA2(736-762)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689737
Shaikhha AChiba SThüm T(2024)Restaging Domain-Specific Languages: A Flexible Design Pattern for Rapid Development of Optimizing CompilersProceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3689484.3690739(80-93)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3689484.3690739
Kovács A(2024)Closure-Free Functional Programming in a Two-Level Type TheoryProceedings of the ACM on Programming Languages10.1145/36746488:ICFP(659-692)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674648
Show More Cited By

Index Terms

Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features

Recommendations

Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs
GPCE '10

Software engineering demands generality and abstraction, performance demands specialization and concretization. Generative programming can provide both, but the effort required to develop high-quality program generators likely offsets their benefits, ...
Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs
GPCE '10: Proceedings of the ninth international conference on Generative programming and component engineering

Software engineering demands generality and abstraction, performance demands specialization and concretization. Generative programming can provide both, but the effort required to develop high-quality program generators likely offsets their benefits, ...
DSL implementation using staging and monads
DSL '99: Proceedings of the 2nd conference on Domain-specific languages

The impact of Domain Specific Languages (DSLs) on software design is considerable. They allow programs to be more concise than equivalent programs written in a high-level programming languages. They relieve programmers from making decisions about data-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 55, Issue 6

June 2012

124 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/2184319

Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2012

Published in CACM Volume 55, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Popular
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
6,768
Total Downloads

Downloads (Last 12 months)491
Downloads (Last 6 weeks)104

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jungmair MEngelke AGiceva J(2024)HiPy: Extracting High-Level Semantics from Python Code for Data ProcessingProceedings of the ACM on Programming Languages10.1145/36897378:OOPSLA2(736-762)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689737
Shaikhha AChiba SThüm T(2024)Restaging Domain-Specific Languages: A Flexible Design Pattern for Rapid Development of Optimizing CompilersProceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3689484.3690739(80-93)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3689484.3690739
Kovács A(2024)Closure-Free Functional Programming in a Two-Level Type TheoryProceedings of the ACM on Programming Languages10.1145/36746488:ICFP(659-692)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674648
Kiselyov O(2024)Generating CScience of Computer Programming10.1016/j.scico.2023.103015231:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.scico.2023.103015
Abeysinghe SRompf T(2024)Rhyme: A Data-Centric Expressive Query Language for Nested Data StructuresPractical Aspects of Declarative Languages10.1007/978-3-031-52038-9_5(64-81)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1007/978-3-031-52038-9_5
Cao HTang SZhu QYu BChen W(2023)Mat2Stencil: A Modular Matrix-Based DSL for Explicit and Implicit Matrix-Free PDE Solvers on Structured GridProceedings of the ACM on Programming Languages10.1145/36228227:OOPSLA2(686-715)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622822
Hirzel M(2023)Low-Code Programming ModelsCommunications of the ACM10.1145/358769166:10(76-85)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3587691
Köster TWarnke TUhrmacher A(2022)Generating Fast Specialized Simulators for Stochastic Reaction Networks via Partial EvaluationACM Transactions on Modeling and Computer Simulation10.1145/348546532:2(1-25)Online publication date: 4-Mar-2022
https://dl.acm.org/doi/10.1145/3485465
Krook RHui JSvensson BEdwards SClaessen K(2022)Creating a Language for Writing Real-Time Applications for the Internet of Things2022 20th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE)10.1109/MEMOCODE57689.2022.9954383(1-20)Online publication date: 13-Oct-2022
https://doi.org/10.1109/MEMOCODE57689.2022.9954383
Kiselyov O(2022)Generating CFunctional and Logic Programming10.1007/978-3-030-99461-7_5(75-93)Online publication date: 10-May-2022
https://dl.acm.org/doi/10.1007/978-3-030-99461-7_5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Digital Edition

View this article in digital edition.

Digital Edition

Magazine Site

View this article on the magazine site (external)

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents