Yin-yang: concealing the deep embedding of DSLs

Abstract

Deeply embedded domain-specific languages (EDSLs) intrinsically compromise programmer experience for improved program performance. Shallow EDSLs complement them by trading program performance for good programmer experience. We present Yin-Yang, a framework for DSL embedding that uses Scala macros to reliably translate shallow EDSL programs to the corresponding deep EDSL programs. The translation allows program prototyping and development in the user friendly shallow embedding, while the corresponding deep embedding is used where performance is important. The reliability of the translation completely conceals the deep em- bedding from the user. For the DSL author, Yin-Yang automatically generates the deep DSL embeddings from their shallow counterparts by reusing the core translation. This obviates the need for code duplication and leads to reliability by construction.

References

1. M. Abadi, L. Cardelli, B. Pierce, and G. Plotkin. Dynamic typing in a statically typed language. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(2):237–268, 1991.
2. K. J. Brown, A. K. Sujeeth, H. J. Lee, T. Rompf, H. Chafi, M. Odersky, and K. Olukotun. A heterogeneous parallel framework for domainspecific languages. In Parallel Architectures and Compilation Techniques (PACT), 2011.
3. E. Burmako. Scala macros: Let our powers combine! In Workshop on Scala (SCALA), 2013.
4. J. Carette, O. Kiselyov, and C.-c. Shan. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. Journal of Functional Programming, 19(05):509–543, 2009.
5. D. Coutts, R. Leshchinskiy, and D. Stewart. Stream fusion: From lists to streams to nothing at all. In International Conference on Functional Programming (ICFP), 2007.
6. K. Czarnecki, J. O’Donnell, J. Striegnitz, and W. Taha. DSL implementation in MetaOCaml, Template Haskell, and C++. Domain-Specific Program Generation, page 51–72, 2004.
7. S. Erdweg, T. Rendel, C. Kästner, and K. Ostermann. Sugarj: Librarybased syntactic language extensibility. In Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 2011.
8. M. Guerrero, E. Pizzi, R. Rosenbaum, K. Swadi, and W. Taha. Implementing DSLs in metaOCaml. In Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 2004.
9. C. Hofer, K. Ostermann, T. Rendel, and A. Moors. Polymorphic embedding of DSLs. In International Conference on Generative Programming and Component Engineering (GPCE), 2008.
10. P. Hudak. Building domain-specific embedded languages. ACM Computing Surveys, 28(4es):196, 1996.
11. P. Hudak. Modular domain specific languages and tools. In International Conference on Software Reuse (ICSR), 1998.
12. N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Inc., 1993.
13. V. Jovanovic, A. Shaikhha, S. Stucki, V. NIkolaev, C. Koch, and M. Odersky. Yin-Yang: Concealing the deep embedding of DSLs. Technical Report EPFL-REPORT-200500, EPFL Lausanne, Switzerland, 2014.
14. T. Lokhorst. Awesome prelude, 2012. Dutch Haskell User Group, http://vimeo.com/9351844.
15. V. Nikolaev. Sprinter. http://vladimirnik.github.io/ sprinter/.
16. M. Odersky and M. Zenger. Scalable component abstractions. In Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 2005.
17. M. Odersky, P. Altherr, V. Cremet, B. Emir, S. Micheloud, N. Mihaylov, M. Schinz, E. Stenman, and M. Zenger. The Scala Language Specification. 2011.
18. B. C. Oliveira, A. Moors, and M. Odersky. Type classes as objects and implicits. In Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 2010.
19. H. Plociniczak. Scalad: an interactive type-level debugger. In Workshop on Scala (SCALA), 2013.
20. T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled DSLs. Communications of the ACM, 55(6):121–130, June 2012.
21. T. Rompf, A. Sujeeth, H. Lee, K. Brown, H. Chafi, M. Odersky, and K. Olukotun. Building-blocks for performance oriented DSLs. In IFIP Working Conference on Domain-Specific Languages (DSL), 2011.
22. T. Rompf, N. Amin, A. Moors, P. Haller, and M. Odersky. Scalavirtualized: Linguistic reuse for deep embeddings. Higher-Order and Symbolic Computation, page 1–43, 2013.
23. T. Rompf, A. K. Sujeeth, N. Amin, K. J. Brown, V. Jovanovi´c, H. Lee, M. Jonnalagedda, K. Olukotun, and M. Odersky. Optimizing data structures in high-level programs: New directions for extensible compilers based on staging. In Symposium on Principles of Programming Languages (POPL), 2013.
24. T. Rompf, A. K. Sujeeth, K. J. Brown, H. Lee, H. Chafi, K. Olukotun, and M. Odersky. Project Lancet: Surgical precision JIT compilers. In International Conference on Programming Language Design and Implementation (PLDI), 2013.
25. L. Rytz, M. Odersky, and P. Haller. Lightweight polymorphic effects. In European Conference on Object-Oriented Programming (ECOOP), 2012.
26. M. Scherr and S. Chiba. Implicit staging of EDSL expressions: A bridge between shallow and deep embedding. In European Conference on Object-Oriented Programming (ECOOP), 2014.
27. A. Sujeeth, T. Rompf, K. Brown, H. Lee, H. Chafi, V. Popic, M. Wu, A. Prokopec, V. Jovanovi´c, M. Odersky, and K. Olukotun. Composition and reuse with compiled domain-specific languages. In European Conference on Object-Oriented Programming (ECOOP), 2013.
28. A. K. Sujeeth, H. Lee, K. J. Brown, T. Rompf, H. Chafi, M. Wu, A. Atreya, M. Odersky, and K. Olukotun. OptiML: An implicitly parallel domain-specific language for machine learning. In International Conference on Machine Learning (ICML), 2011.
29. A. K. Sujeeth, A. Gibbons, K. J. Brown, H. Lee, T. Rompf, M. Odersky, and K. Olukotun. Forge: generating a high performance DSL implementation from a declarative specification. In International Conference on Generative Programming and Component Engineering (GPCE), 2013.
30. J. Svenningsson and E. Axelsson. Combining deep and shallow embedding for EDSL. In Trends in Functional Programming (TFP), pages 21–36, 2013.
31. W. Taha and T. Sheard. Multi-stage programming with explicit annotations. In Workshop on Partial Evaluation and Program Manipulation (PEPM), 1997.
32. Typesafe. Slick. http://slick.typesafe.com/. Introduction Background on Scala Deep Embedding of DSLs with LMS Scala Macros Motivation The Deep Embedding Abstraction Leaks in the Deep Embedding Translation of the Direct Embedding Alternative Type Translations Correctness Restricting Host Language Constructs Automatic Generation of the Deep Embedding Constructing High-Level IR Nodes Lowering High-Level IR Nodes to their Low-Level Implementation Evaluation Automatic Deep EDSL Generation No Annotations in the Direct Embedding Yin-Yang for Slick Discussion Related Work Conclusions

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features