skip to main content
10.1145/1449913.1449935acmconferencesArticle/Chapter ViewAbstractPublication PagesgpceConference Proceedingsconference-collections
research-article

Polymorphic embedding of dsls

Published: 19 October 2008 Publication History

Abstract

The influential pure embedding methodology of embedding domain-specific languages (DSLs) as libraries into a general-purpose host language forces the DSL designer to commit to a single semantics. This precludes the subsequent addition of compilation, optimization or domain-specific analyses. We propose polymorphic embedding of DSLs, where many different interpretations of a DSL can be provided as reusable components, and show how polymorphic embedding can be realized in the programming language Scala. With polymorphic embedding, the static type-safety, modularity, composability and rapid prototyping of pure embedding are reconciled with the flexibility attainable by external toolchains.

References

[1]
J. Carette, O. Kiselyov, and C. Shan. Finally tagless, partially evaluated. In Asian Symposium on Programming Languages and Systems (APLAS'07), pages 222--238. Springer LNCS 4807, 2007.
[2]
K. Czarnecki, J. T. O'Donnell, J. Striegnitz, and W. Taha. DSL implementation in MetaOCaml, Template Haskell, and C++. In Domain-Specific Program Generation, volume 3016 of LNCS, pages 51--72. Springer, 2003.
[3]
T. Ekman and G. Hedin. The JastAdd extensible Java compiler. In R. P. Gabriel, D. F. Bacon, C. V. Lopes, and G. L. S. Jr., editors, OOPSLA '07: Proceedings of the 22th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 1--18. ACM, 2007.
[4]
C. Elliott. Functional images. "In The Fun of Programming", "Cornerstones of Computing" series. Palgrave, Mar. 2003.
[5]
C. Elliott, S. Finne, and O. D. Moor. Compiling embedded languages. J. Funct. Program., 13(3):455--481, 2003.
[6]
E. Ernst. Family polymorphism. In ECOOP '01: Proceedings of the 15th European Conference on Object-Oriented Programming, pages 303--326, London, UK, 2001. Springer-Verlag.
[7]
E. Ernst, K. Ostermann, and W. Cook. A virtual class calculus. In 33rd ACM Symposium on Principles of Programming Languages (POPL'06). ACM SIGPLAN-SIGACT, 2006.
[8]
E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design patterns: elements of reusable object-oriented software. Addison-Wesley Professional, Boston, MA, 1995.
[9]
R. Garcia, J. Jarvi, A. Lumsdaine, J. Siek, and J. Willcock. An extended comparative study of language support for generic programming. J. Funct. Program., 17(2):145--205, 2007.
[10]
J. A. Goguen, J. W. Thatcher, E. G. Wagner, and J. B. Wright. Initial algebra semantics and continuous algebras. J. ACM, 24(1):68--95, 1977.
[11]
S. S. Huang, D. Zook, and Y. Smaragdakis. Morphing: Safely shaping a class in the image of others. In Proceedings ECOOP'07, pages 399--424. Springer LNCS, 2007.
[12]
P. Hudak. Building domain-specific embedded languages. ACM Comput. Surv., 28(4), 1996.
[13]
P. Hudak. Modular domain specific languages and tools. In P. Devanbu and J. Poulin, editors, Proceedings: Fifth International Conference on Software Reuse, pages 134--142. IEEE Computer Society Press, 1998.
[14]
G. Hutton and E. Meijer. Monadic Parsing in Haskell. Journal of Functional Programming, 8(4):437--444, July 1998.
[15]
S. Kamin. Research on domain-specific embedded languages and program generators, 1998.
[16]
M. Mernik, J. Heering, and A. M. Sloane. When and how to develop domain-specific languages. ACM Comput. Surv., 37(4):316--344, 2005.
[17]
E. Moggi. A modular approach to denotational semantics. In Category Theory and Computer Science, Springer LNCS 530, pages 138--139, 1991.
[18]
A. Moors, F. Piessens, and M. Odersky. Generics of a higher kind. In Proceedings of OOPSLA '08 (to appear), 2008.
[19]
P. D. Mosses. Denotational semantics. In Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pages 575--631. 1990.
[20]
P. D. Mosses. Modular structural operational semantics. J. Log. Algebr. Program., 60-61:195--228, 2004.
[21]
M. Odersky, P. Altherr, V. Cremet, I. Dragos, G. Dubochet, B. Emir, S. McDirmid, S. Micheloud, N. Mihaylov, M. Schinz, L. Spoon, E. Stenman, and M. Zenger. An Overview of the Scala Programming Language (2. edition). Technical report, 2006.
[22]
M. Odersky, V. Cremet, C. Rckl, and M. Zenger. A nominal theory of objects with dependent types. In Proceedings ECOOP '03. Springer LNCS, 2003.
[23]
M. Odersky and M. Zenger. Scalable component abstractions. In OOPSLA '05, pages 41--57, New York, NY, USA, 2005. ACM.
[24]
J. Paakki. Attribute grammar paradigms - a high-level methodology in language implementation. ACM Comput. Surv., 27(2):196--255, 1995.
[25]
F. Pfenning and C. Elliot. Higher-order abstract syntax. SIGPLAN Not., 23(7):199--208, 1988.
[26]
S. Seefried, M. M. T. Chakravarty, and G. Keller. Optimising embedded DSLs using Template Haskell. In G. Karsai and E. Visser, editors, GPCE, volume 3286 of Lecture Notes in Computer Science, pages 186--205. Springer, 2004.
[27]
T. Sheard. Languages of the future. In OOPSLA '04 Companion, pages 116--119, New York, NY, USA, 2004. ACM.
[28]
T. Sheard and S. Peyton Jones. Template metaprogramming for Haskell. In M. M. T. Chakravarty, editor, ACM SIGPLAN Haskell Workshop 02, pages 1--16. ACM Press, Oct. 2002.
[29]
W. Taha. A gentle introduction to multi-stage programming. In Domain-Specific Program Generation, Springer LNCS 3016, pages 30--50, 2003.
[30]
E. Van Wyk, L. Krishnan, A. Schwerdfeger, and D. Bodin. Attribute grammar-based language extensions for Java. In ECOOP'07, LNCS. Springer Verlag, July 2007.
[31]
H. Xi, C. Chen, and G. Chen. Guarded recursive datatype constructors. In POPL '03: Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 224--235, New York, NY, USA, 2003. ACM.

Cited By

View all
  • (2024)Imperative Compositional Programming: Type Sound Distributive Intersection Subtyping with References via Bidirectional TypingProceedings of the ACM on Programming Languages10.1145/36897828:OOPSLA2(2010-2039)Online publication date: 8-Oct-2024
  • (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
  • (2022)Compositional embeddings of domain-specific languagesProceedings of the ACM on Programming Languages10.1145/35632946:OOPSLA2(175-203)Online publication date: 31-Oct-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GPCE '08: Proceedings of the 7th international conference on Generative programming and component engineering
October 2008
194 pages
ISBN:9781605582672
DOI:10.1145/1449913
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. algebraic semantics
  2. compositionality
  3. domain-specific languages
  4. extensibility
  5. pure embedding
  6. scala

Qualifiers

  • Research-article

Conference

GPCE '08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 56 of 180 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)19
  • Downloads (Last 6 weeks)2
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Imperative Compositional Programming: Type Sound Distributive Intersection Subtyping with References via Bidirectional TypingProceedings of the ACM on Programming Languages10.1145/36897828:OOPSLA2(2010-2039)Online publication date: 8-Oct-2024
  • (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
  • (2022)Compositional embeddings of domain-specific languagesProceedings of the ACM on Programming Languages10.1145/35632946:OOPSLA2(175-203)Online publication date: 31-Oct-2022
  • (2021)Compositional ProgrammingACM Transactions on Programming Languages and Systems10.1145/346022843:3(1-61)Online publication date: 3-Sep-2021
  • (2020)Compiling symbolic execution with staging and algebraic effectsProceedings of the ACM on Programming Languages10.1145/34282324:OOPSLA(1-33)Online publication date: 13-Nov-2020
  • (2020)Pattern matching in an open worldACM SIGPLAN Notices10.1145/3393934.327812453:9(134-146)Online publication date: 7-Apr-2020
  • (2020)Castor: Programming with extensible generative visitorsScience of Computer Programming10.1016/j.scico.2020.102449(102449)Online publication date: Mar-2020
  • (2020)Behavioral interfaces for executable DSLsSoftware and Systems Modeling10.1007/s10270-020-00798-2Online publication date: 23-Apr-2020
  • (2019)From definitional interpreter to symbolic executorProceedings of the 4th ACM SIGPLAN International Workshop on Meta-Programming Techniques and Reflection10.1145/3358502.3361269(11-20)Online publication date: 20-Oct-2019
  • (2019)Polymorphic extractors for semantic and portable pattern matching (short paper)Proceedings of the 18th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3357765.3359522(61-67)Online publication date: 21-Oct-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media