Uniting Language Embeddings for Fast and Friendly DSLs

The holy grail for a domain-specific language (DSL) is to be friendly and fast. A DSL should be friendly in the sense that it is easy to use by DSL end-users, and easy to develop by DSL authors. DSLs can be developed as entirely new compilers and ecosystems, which requires tremendous effort and often requires DSL authors to reinvent the wheel. Or, DSLs can be developed as libraries embedded in an existing host language, which requires significantly less effort. Embedded DSLs (EDSLs) manifest a trade-off between being friendly and fast as they stand divided in two groups: - Deep EDSLs trade user experience of both DSL authors and DSL end-users, for improved program performance. As proposed by Elliott et al., deep EDSLs build an intermediate representation (IR) of a program that can be used to drive domain-specific optimizations, which can significantly improve performance. However, this program IR introduces significant usability hurdles for both the DSL authors and DSL end-users. Correctly transforming programs is difficult and error prone for DSL authors, while error messages can be cryptic and confusing for DSL end-users. - Shallow EDSLs trade program performance for good user experience. As proposed by P. Hudak, shallow EDSLs omit construction of the IR, i.e., they are executed directly in the host language. Although friendly to both DSL end-users and DSL authors, they can not perform domain-specific optimizations and thus exhibit inferior performance. This thesis makes a stride towards achieving both (1) good user experience for DSL authors and DSL end-users, as well as (2) enabling domain-specific optimizations for improved performance. It unites shallow and deep DSLs by defining an automatic translation from end-user-friendly shallow DSLs, to better-performing deep DSLs. The translation uses reflection of the host language to cherry-pick the best of both shallow and deep EDSLs. During program development, a DSL end-user is presented with user friendly features of a shallow EDSL. Before execution in a production environment, programs are reliably translated into the high-performance deep EDSL with equivalent semantics. Since maintaining both shallow and deep EDSLs is difficult, the thesis further shows how to reuse the shallow-to-deep translation to automatically generate deep EDSLs based on shallow EDSLs. With automatic generation of the deep EDSL, the DSL author is required only to develop a shallow EDSL and the domain-specific optimizations for the deep EDSL that she deems useful. Finally, the thesis discusses a new programming abstraction that eases the development, of a specific kind, of deep EDSLs that are compiled in two stages. The new abstraction simplifies management of dynamic compilation in two-stage deep EDSLs.

Lightweight Modular Staging and Embedded Compilers

Tiark Rompf

Programs expressed in a high-level programming language need to be translated to a low-level machine dialect for execution. This translation is usually accomplished by a compiler, which is able to translate any legal program to equivalent low-level code. But for individual source programs, automatic translation does not always deliver good results: 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 tomodern hardware platforms in a way that makes best use of the available resources. Explicit program generation is a promising alternative to fully automatic translation. Instead of writing down the program and relying on a compiler for translation, developers write a program generator, which produces a specialized, efficient, low-level program as its output. However, developing high-quality program generators requires a very large effort that is often hard to amortize. In this thesis, we propose a hybrid design: Integrate compilers into programs so that programs can take control of the translation process, but rely on libraries of common compiler functionality for help. We present Lightweight Modular Staging (LMS), a generative programming approach that lowers the development effort significantly. LMS 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. Compared to previous work on programgeneration, a key aspect of our design is the use of staging not only as a front-end, but also as a way to implement internal compiler passes and optimizations, many of which can be combined into powerful joint simplification passes. 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.

EPFL2012

Embedded Domain-Specific Languages using Libraries and Dynamic Metaprogramming

Gilles Dubochet

Domain-specific programming is bound to play a central role in improving the productivity of writing software. This is because modern, intricate, general-purpose abstractions are rarely applicable directly to everyday programming. However, such abstractions can be used to encode domain-specific abstractions, so that the general-purpose language serves as a host in which domain-specific fragments are embedded. The benefit of traditional software engineering is maintained, while allowing writing software that integrates multiple domains. This thesis describes two such techniques in Scala –a modern language with functional and object-oriented features. The first allows embedding fragments of code with domain-specific syntax, which is weaved within the host language's own syntax so that it appears as being different. The second technique uses structural types to encode domain-specific correctness properties that object-oriented types cannot represent. An implementation of structural types in Scala is also described. The common characteristic of both techniques is that domain-specific properties are provided by a library relying only on general-purpose abstractions. However, the techniques also exemplify how certain embedding tasks rely on data that is available in the compiler but is then lost in statically-typed languages. General-purpose abstractions do not give access to this data, nor do traditional runtime reflection techniques; keeping all data is also impractical. This thesis describes two metaprogramming techniques whereby compiler data on code (code lifting) and types (manifests) can be requested by embedding libraries when needed. Compiler data is then available as literal values in the program. It further describes a metaprogramming framework that combine compiler data available in code with reflection. Its design is mirror-based, and allows a high degree of code sharing between the metaprogramming framework and the compiler.

EPFL2011

Yin-Yang: Concealing the Deep Embedding of DSLs

Vojin Jovanovic, Christoph Koch, Vladimir Nikolaev, Martin Odersky, Amir Shaikhha, Sandro Stucki

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 embedding 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.