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

article

Compiling embedded languages

Authors:

Sigbjørn Finne,

Oege De MoorAuthors Info & Claims

Journal of Functional Programming, Volume 13, Issue 3

Pages 455 - 481

https://doi.org/10.1017/S0956796802004574

Published: 01 May 2003 Publication History

Abstract

Functional languages are particularly well-suited to the interpretive implementations of Domain-Specific Embedded Languages (DSELs). We describe an implemented technique for producing optimizing compilers for DSELs, based on Kamin's idea of DSELs for program generation. The technique uses a data type of syntax for basic types, a set of smart constructors that perform rewriting over those types, some code motion transformations, and a back-end code generator. Domain-specific optimization results from chains of domain-independent rewrites on basic types. New DSELs are defined directly in terms of the basic syntactic types, plus host language functions and tuples. This definition style makes compilers easy to write and, in fact, almost identical to the simplest embedded interpreters. We illustrate this technique with a language Pan for the computationally intensive domain of image synthesis and manipulation.

References

[1]

Alstrup, S., Harel, D., Lauridsen, P. W. and Thorup, M. (1999) Dominators in linear time. SICOMP: SIAM J. Comput. 28.

Digital Library

[2]

Appel, A. (1998) Modern Compiler Implementation in ML. Cambridge University Press.

Digital Library

[3]

Berlin, A. (1989) A compilation strategy for numerical programs based on partial evaluation. Technical Report AITR-1144, Massachusetts Institute of Technology.

Digital Library

[4]

Berlin, A. and Weise, D. (1990) Compiling scientific code using partial evaluation. IEEE Computer, 23(12), 25-37.

Digital Library

[5]

Bird, R. S. (1984) Using circular programs to eliminate multiple traversals of data. Acta Informatica, 21(3), 239-250.

Digital Library

[6]

Boiten, E. A. (1992) Improving recursive functions by inverting the order of evaluation. Sci. Comput. Program. 18(2), 139-179.

Digital Library

[7]

Chin, W. (1993) Towards an automated tupling strategy. Proceedings ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, pp. 119-132.

Digital Library

[8]

Claessen, K. and Sands, D. (1999) Observable sharing for functional circuit description. In: Thiagarajan, P. S. and Yap, R., editors, Advances in Computing Science ASIAN'99; 5th Asian Computing Science Conference: Lecture Notes in Computer Science 1742, pp. 62-73. Springer-Verlag.

[9]

Danvy, O. (1998) Online type-directed partial evaluation. Third Fuji International Symposium on Functional and Logic Programming, FLOPS '98 Proceedings, pp. 271-295. World Scientific. (Extended version at http://www.brics.dk/RS/97/Ref/BRICS-RS-97-Ref/- BRICS-RS-97-Ref.html#BRICS-RS-97-53.)

[10]

Day, N. A., Lewis, J. R. and Cook, B. (1999) Symbolic simulation of microprocessor models using type classes in Haskell. CHARME'99 poster session, Bad Herranald, Germany. http://www.cse.ogi.edu/PacSoft/projects/Hawk/papers/sym sim.ps. Companion tech report with details, examples, and Haskell code (OGI Technical Report CSE-99-005), http://www.cse.ogi.edu/PacSoft/projects/Hawk/papers/- tr99-005.ps.

Digital Library

[11]

de Moor, O. and Secher, J. P. (2001) Common subexpression elimination of conditional expressions. Submitted.

[12]

de Moor, O. and Sittampalam, G. (1999) Generic program transformation. Proceedings 3rd International Summer School on Advanced Functional Programming. http://users.comlab.ox.ac.uk/oege.demoor/papers/braga.ps.gz.

[13]

Elliott, C. (1998) Functional implementations of continuous modeled animation. Proceedings PLILP/ALP. Springer-Verlag.

Digital Library

[14]

Elliott, C. (1999) An embedded modeling language approach to interactive 3D and multimedia animation. IEEE Trans. Softw. Eng. 25(3), 291-308.

Digital Library

[15]

Elliott, C. (2000) A Pan image gallery. http://research.microsoft.com/~conal/- pan/Gallery.

[16]

Elliott, C. (2001) Functional image synthesis. In: Sarhangi, R. and Jablan, S., editors, Proceedings Bridges 2001, Mathematical Connections in Art, Music, and Science. http://research.microsoft.com/~conal/papers/bridges2001. An extended version, submitted for publication, is available as http://research.microsoft.com/~conal/- papers/functional-images.

[17]

Frigo, M. (1999) A fast Fourier transform compiler. Proceedings ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pp. 169- 180. http://www.acm.org/pubs/articles/proceedings/pldi/301618/p169-frigo/- p169-frigo.pdf.

Digital Library

[18]

GHC Team The Glasgow Haskell compiler. http://haskell.org/ghc.

[19]

Harel, D. (1985) A linear time algorithm for finding dominators in flow graphs and related problems. Proceedings 17th Annual ACM Symposium on Theory of Computing, pp. 185-194.

Digital Library

[20]

Harel, D. and Tarjan, R. E. (1984) Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338-355.

Digital Library

[21]

Hatcliff, J., Mogensen, T. and Thiemann, P. (editors) (1999) Partial Evaluation: Practice and theory. Vol. 1706. Springer-Verlag.

[22]

Hudak, P. (1998) Modular domain specific languages and tools. In: Devanbu, P. and Poulin, J., editors, Proceedings: Fifth International Conference on Software Reuse, pp. 134-142. IEEE Press.

Digital Library

[23]

Hudak, P. (2000) The Haskell School of Expression: Learning functional programming through multimedia. Cambridge University Press.

Digital Library

[24]

Hudak, P. and Jones, M. P. (1994) Haskell vs. Ada vs. C++ vs. Awk vs.an experiment in software prototyping productivity. Technical report, Yale.

[25]

Johnsson, T. (1987) Attribute grammars as a functional programming paradigm. In: Kahn, G., editor, Functional Programming Languages and Computer Architecture: Lecture Notes in Computer Science 274, pp. 154-173. Springer-Verlag.

Digital Library

[26]

Jones, N. D., Gomard, C. K. and Sestoft, P. (1993) Partial evaluation and automatic program generation. International Series in Computer Science: Prentice Hall International. http://www.dina.kvl.dk/sestoft/pebook/pebook.html.

Digital Library

[27]

Kamin, S. (1996) Standard ML as a meta-programming language. Technical report, University of Illinois at Urbana-Champaign. http://www-sal.cs.uiuc.edu/~kamin/- pubs/ml-meta.ps.

[28]

Kamin, S. and Hyatt, D. (1997) A special-purpose language for picture-drawing. Proceedings Conference on Domain-Specific Languages, pp. 297-310. http://www-sal.cs.uiuc.edu/- ~kamin/fpic/doc/fpic-paper.ps.

Digital Library

[29]

Landin, P. J. (1966) The next 700 programming languages. Comm. ACM, 9(3), 157-164.

Digital Library

[30]

Launchbury, J. and Peyton Jones, S. L. (1994) Lazy functional state threads. Proceedings ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pp. 24-35.

Digital Library

[31]

Leijen, D. and Meijer, E. (1999) Domain specific embedded compilers. 2nd Conference on Domain-Specific Languages (DSL), Austin, TX. http://www.cs.uu.nl/people/daan/- papers/dsec.ps.

Digital Library

[32]

Pettorossi, A. (1984) Methodologies for transformations and memoing in applicative languages. PhD thesis, University of Edinburgh, Scotland.

[33]

Peyton Jones, S., Jones, M. and Meijer, E. (1997) Type classes: exploring the design space. Haskell workshop.

[34]

Rus, T. and Van Wyk, E. (1997) Model checking as a tool used by parallelizing compilers. Proceedings 2nd Formal Methods for Parallel Processing: Theory and Applications.

[35]

Taha, W. and Sheard, T. (2000) MetaML: Multi-stage programming with explicit annotations. Theor. Comput. Sci. 248(1-2).

Digital Library

[36]

Thiemann, P. and Sperber, M. (1997) Program generation with class. GI-Arbeitstagung Programmiersprachen.

[37]

Veldhuizen, T. (1995) Expression templates. C++ Report, 7(5), 26-31. http://extreme.- indiana.edu/~tveldhui/papers/pepm99.ps. Reprinted in C++ Gems, ed. Stanley Lippman.

[38]

Veldhuizen, T. (1999) C++ templates as partial evaluation. Workshop on Partial Evaluation and Semantics-based Program Manipulation (PEPM'99). http://extreme.indiana.edu/- ~tveldhui/papers/pepm99.ps.

[39]

Weise, D., Conybeare, R., Ruf, E. and Seligman, S. (1991) Automatic online partial evaluation. In: Hughes, R. J. M., editor, Functional Programming Languages and Computer Architecture: Lecture Notes in Computer Science 523, pp. 165-191. Springer-Verlag.

Digital Library

Cited By

Ballantyne MGamburg MHemann J(2024)Compiled, Extensible, Multi-language DSLs (Functional Pearl)Proceedings of the ACM on Programming Languages10.1145/36746278:ICFP(64-87)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674627
Bračevac OWei GJia SAbeysinghe SJiang YBao YRompf T(2023)Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesProceedings of the ACM on Programming Languages10.1145/36228137:OOPSLA2(400-430)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622813
Ragan-Kelley JAdams AParis SLevoy MAmarasinghe SDurand F(2023)Decoupling Algorithms from Schedules for Easy Optimization of Image Processing PipelinesSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596751(361-372)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596751
Show More Cited By

Compiling embedded languages
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Semantics and reasoning

Recommendations

On compiling embedded languages in LISP
LFP '80: Proceedings of the 1980 ACM conference on LISP and functional programming

In INTERLISP we find a number of embedded languages such as the iterative statement and the pattern match facility in the CLISP package, the editor and makefile languages and so forth. We will in this paper concentrate on the problem of extending the ...
Compiling Embedded Languages
SAIG '00: Proceedings of the International Workshop on Semantics, Applications, and Implementation of Program Generation

Functional languages are particularly well-suited to the implementation of interpreters for domain-specific embedded languages (DSELs). We describe an implemented technique for producing optimizing compilers for DSELs, based on Kamin's idea of DSELs for ...
Compiling Embedded Programs to Byte Code
PADL '02: Proceedings of the 4th International Symposium on Practical Aspects of Declarative Languages

Functional languages have proven substantially useful for hosting embedded domain-specific languages. They provide an infrastructure rich enough to define both a convenient syntax for the embedded language, a type system for embedded programs, and an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Functional Programming

Journal of Functional Programming Volume 13, Issue 3

May 2003

253 pages

ISSN:0956-7968

Issue’s Table of Contents

Publisher

Cambridge University Press

United States

Publication History

Published: 01 May 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

78
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ballantyne MGamburg MHemann J(2024)Compiled, Extensible, Multi-language DSLs (Functional Pearl)Proceedings of the ACM on Programming Languages10.1145/36746278:ICFP(64-87)Online publication date: 15-Aug-2024
https://dl.acm.org/doi/10.1145/3674627
Bračevac OWei GJia SAbeysinghe SJiang YBao YRompf T(2023)Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesProceedings of the ACM on Programming Languages10.1145/36228137:OOPSLA2(400-430)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622813
Ragan-Kelley JAdams AParis SLevoy MAmarasinghe SDurand F(2023)Decoupling Algorithms from Schedules for Easy Optimization of Image Processing PipelinesSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596751(361-372)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596751
Wei GJia SGao RDeng HTan SBračevac ORompf TGrundy JPollock LPenta M(2023)Compiling Parallel Symbolic Execution with ContinuationsProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00116(1316-1328)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00116
Lubbers MKoopman PPlasmeijer R(2022)First-Class Data Types in Shallow Embedded Domain-Specific Languages using MetaprogrammingProceedings of the 34th Symposium on Implementation and Application of Functional Languages10.1145/3587216.3587219(1-12)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3587216.3587219
Nguyen MPerera RWang MWu N(2022)Modular probabilistic models via algebraic effectsProceedings of the ACM on Programming Languages10.1145/35476356:ICFP(381-410)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547635
Lin ZDubach CHenriksen TLow T(2022)From functional to imperative: combining destination-passing style and viewsProceedings of the 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming10.1145/3520306.3534502(25-36)Online publication date: 13-Jun-2022
https://dl.acm.org/doi/10.1145/3520306.3534502
Shahmohammadian MMainland GTilevich EDe Roover C(2021)Metaprogramming with combinatorsProceedings of the 20th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3486609.3487198(43-54)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1145/3486609.3487198
Dawson JGrebe MGill A(2017)Composable network stacks and remote monadsACM SIGPLAN Notices10.1145/3156695.312296852:10(86-97)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3156695.3122968
Dawson JGrebe MGill ADiatchki I(2017)Composable network stacks and remote monadsProceedings of the 10th ACM SIGPLAN International Symposium on Haskell10.1145/3122955.3122968(86-97)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122955.3122968
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents