Domain-speci c languages o er a variety of advantages, but their implementation techniques have disadvantages that sometimes prevent their use in practice. Language extension o ers a potential solution to some of these problems, but remains essentially unused in practice. It is our contention that the main obstacle to adoption is the lack of any assurance that the compiler composed of multiple independent language extensions will work without the need for additional modi cations, or at all. We propose to solve this problem by requiring extensions to independently pass a composition test that will ensure that any such extensions can be safely composed without \glue code," and we propose to demonstrate that interesting extensions are still possible that satisfy such a test.
Domain-speci c languages (DSLs) come with a variety of reasonably well-known
advantages and disadvantages [
To be more precise about what we mean by language composition, we will
use some of the classi cation and notation of Erdweg, Giarrusso, and Rendel [
What we seek is a composition method L1 ]; L2, that is, language uni cation without needing any glue code (g = ;.) This may seem impossible in general, but there is hope in special cases, such as when both languages are extensions to a common host: (H / E1) ]; (H / E2). Here we are tasked with resolving only con icts between E1 and E2, while the host language H is shared. We will say that a DSL implementation technique supports composable language extension if it is capable of composition of the form H / (E1 ]; E2). We further require that the technique provides some assurance that the resulting composed language will work as intended, and is not simply broken.
The goal of this work is to build a DSL implementation tool and demonstrate that it satis es the following criteria: { Supports composable language extension, as de ned above. { Permits introduction of new syntax. { Permits introduction of new static analysis on existing syntax. { Capable of generating good, domain-speci c error messages. { Capable of complex translation, such as domain-speci c optimizations.
In Section 2 we provide some background on the tools we will be making use of in pursuit of this goal. In Section 2.1 we survey some of the other tools for implementing domain-speci c languages. In Section 3 we propose the work we plan for this thesis. In Section 3.1 we outline work beyond the scope of this thesis. 2
The rst major obstacle to supporting composable language extension is to
allow composition of syntax extensions. Although context-free grammars are easily
composed, the resulting composition may no longer be deterministic, or
otherwise amenable to parser generation. Copper [
Attribute grammars [
There is a natural con ict between introducing new syntax and static analysis, referred to as the \expression problem1." Although normally formulated in 1 http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt terms of data types, it applies equally well to abstract syntax trees, and thus has consequences for language extension. If one language extension introduces new syntax, and another a new analysis, the combination of the two extensions would be missing the implementation of this analysis for this syntax. Either the composition is then broken, glue code must be written to bridge this con ict, or there must be some mechanism to accurately and automatically generate this glue code.
Attribute grammars are capable of solving the expression problem by manually providing \glue code" that provides for evaluating new attributes on new productions. However, the expression problem can also be automatically resolved without glue code for attribute grammars that include forwarding [19]. An extension production that forwards to a \semantically equivalent" tree in the host language can evaluate new attributes introduced in other extensions via that host language tree, where the attribute will have de ning semantic equations.
Although forwarding removes the need for the \glue code" necessary to
resolve the expression problem, there are other ways in which a composition
of attribute grammars may cause con icts. Attribute grammars have a
\wellde nedness" property that, roughly speaking, ensures each attribute can
actually be evaluated. However, although H, H / E1 and H / E2 may be well-de ned,
there is no guarantee that H / (E1 ]; E2) will also be well-de ned. As part of this
thesis, we have developed a modular well-de nedness analysis [
Domain-speci c languages are traditionally implemented as an \external" DSL,
and therefore incapable of composition with each other. Internal (or Embedded
DSLs) are those implemented as a \mere" library in a suitable host language [
One way of making internal DSLs capable of domain-speci c analysis is to
take advantage of complex embeddings into the host language's type system.
AspectAG [21] and Ur/Web [
One way to improve the ability of internal DSLs to generate code is to take
advantage of meta-programming facilities in the language, like LISP macros, or
C++ templates. Racket [
There are several systems for specifying languages that enable language
extension and uni cation, as described in the introduction. JastAdd [
MPS [23] is a meta-programming environment that leans heavily on an object-oriented view of abstract syntax, and consequently struggles with expression problem in its support for composition. Consequently, the host language limits the possible analyses over syntax that are possible. Many useful language extensions do not necessarily need new analysis over the host language, however, as macro systems for dynamic languages already demonstrate. 3
One component of this thesis has already been mentioned: our modular
wellde nedness analysis for attribute grammars [
This modular well-de nedness analysis, together with Copper's modular
determinism analysis, o ers a potential path towards composable language
extension. Silver [
In light of these potential restrictions on the kinds of extensions that can be speci ed in Silver, we wish to validate each of our goals: { The analyses themselves accomplish the goal of supporting composable language extension. { We will need to implement at least two new extensions to the syntax. { We will need to implement at least one new extension to static analysis. { That static analysis extension should demonstrate the ability to generate good, domain-speci c error messages. { One of the extensions should involve either complex translation, require domain-speci c optimizations, or have at least stringent e ciency requirements, to demonstrate the approach has little to no runtime overhead.
We propose to build a host language speci cation for C in Silver. C is an ambitious choice, but choosing a rich, practical language of independent design is necessary to evaluate whether the analyses' restrictions are practical, as they depend on the host language. To this speci cation of C, we propose to build language extensions that will meet the above requirements. These should ideally be language extensions that already exist in the literature, so that the changes to their design or syntax that are necessary to satisfy the analyses can be evaluated.
From this we hope to learn: { How to better design extensible host language implementations, to support the development of interesting extensions. Many of the limitations imposed by the analyses depend upon the host language implementation more so than on the host language itself. { Ways in which Silver itself may need to be extended to help specify the host language and extensions. For example, proper aggregation of error messages in the extensions could be ensured with language features speci c to error message aggregation. { Whether the restrictions still permit interesting and practical language extensions. { Informally, whether the resulting extended languages are useful. We intend for our colleagues to make use of these extended languages, providing some feedback in this area, though we do not intend to perform an empirical investigation. 3.1
Beyond the scope of this thesis, there lie many more problems that must be solved to bring language extension to practicality.
First, host languages must be developed in Silver before they can be extended, and extensions can only be composed for a common host language, so fragmentation must be kept to a minimum to avoid splitting apart the ecosystem. High enough quality implementations of host languages for production use remains future work.
Second, numerous less daunting engineering issues would also need resolving. No obstacles to composing language extensions at runtime exist for Silver and Copper, but the feature has yet to be fully implemented. Further, the build process for making use of an extended compiler in large software projects must be worked out.
Third, a variety of other tooling must also be composable. Languages extensions must result not only in composed compilers, but also composed debuggers and integrated development environments. Abandoning these tools is not an option for practical use. We do not intend to directly address this problem in this thesis, though concurrent work for such tools in Silver is ongoing.
Finally, although these analyses ensure con icts do not arise from the parser or attribute evaluator, it is possible that con icts could arise in some other fashion. Certainly we can imagine blatantly wrong code, like suppressing all error messages from subtrees. But the formulation of composable proofs of the compiler's correctness would complete our understanding the problem posed by composable language extension. 4
We believe that no existing DSL implementation tool satis es all ve goals listed in the introduction: support composable language extension, allow extension to both and static analysis, provide good domain-speci c error messages, and allow complex translation requirements. These goals are motivated by the desire to ensure that the users of language extensions can be certain they can draw on whatever high-quality extensions they need, without fear of breaking their compiler.
We have developed an analysis that ensures Silver meets the goal of supporting composable language extension, and we have implemented this analysis. We intend to develop an extensible speci cation of a popular and practical language, C, and we intended to demonstrate that practical language extensions to it are possible that satisfy this analysis. We believe this will demonstrate that Silver satis es all ve goals listed in the introduction for an ideal DSL implementation technique. 18. Van Wyk, E., Bodin, D., Krishnan, L., Gao, J.: Silver: an extensible attribute grammar system. Scinece of Computer Programming (2009), accpeted, In Press 19. Van Wyk, E., de Moor, O., Backhouse, K., Kwiatkowski, P.: Forwarding in attribute grammars for modular language design. In: Proc. 11th Intl. Conf. on Compiler Construction. LNCS, vol. 2304, pp. 128{142 (2002) 20. Van Wyk, E., Schwerdfeger, A.: Context-aware scanning for parsing extensible languages. In: Intl. Conf. on Generative Programming and Component Engineering, (GPCE). ACM Press (October 2007) 21. Viera, M., Swierstra, S.D., Swierstra, W.: Attribute grammars y rst-class: How to do aspect oriented programming in haskell. In: Proc. of 2009 International Conference on Functional Programming (ICFP'09) (2009) 22. Visser, E.: Stratego: A language for program transformation based on rewriting strategies. System description of Stratego 0.5. In: Rewriting Techniques and Applications (RTA'01). LNCS, vol. 2051, pp. 357{361. Springer-Verlag (2001) 23. Voelter, M.: Language and ide modularization, extension and composition with mps. In: GTTSE 2011 (2011)