Check out the new USENIX Web site. USENIX - Summaries


These reports were originally published in ;login: Vol. 23, No.1, February 1998.

Conference on Domain-Specific Languages

SANTA BARBARA, CA
October 15-17, 1997

Summaries by Andrew J. Forrest

OVERVIEW

USENIX held its first ever conference on the subject of Domain-Specific Languages (DSLs). The purpose of the conference was to bring together people who are interested in the idea that programming languages are first-class tools to exploit in the creation of software, and that the development of problem-appropriate computer languages is the basis for a valuable approach to software engineering.

Although this conference was organized into seven sessions, each with a specific focus, a number of themes emerged, cutting across sessions and recurring in many presentations.

Domain-Specific Languages ­ The Ultimate Abstraction

This theme holds that Domain-Specific Languages represent direct support for key abstractions in a programming domain. A DSL can represent an abstraction in a way that offers advantages when compared with other abstraction approaches, such as the use of libraries.

Language as a First-Class Tool

This theme presents language as a fundamental tool; it revolves around the idea that in many circumstances it is appropriate to create a new language rather than rely on the less specialized features of an existing general-purpose programming language.

Domain Analysis and Design for DSLs

A key step in the creation of a DSL, domain analysis is done to varying degrees of formality. The main question is "How does one pick the appropriate abstractions for the DSL to contain?" Is there a process for this? What is the relationship between the language designer and the domain expert(s)? Does the domain already have an accepted notation that suggests itself as a syntax for the DSL?

DSL Implementation Framework

This theme examines the various means by which a DSL can be implemented. Should a DSL be embedded in a larger, more general-purpose language (GPL)? Should it be implemented via a preprocessor? Or should an entirely separate implementation be developed?

DSLs and Rapid Prototyping

This theme occurs in two forms: DSLs support rapid prototyping because they tend to operate at a high level of abstraction; and rapid prototyping supports DSL creation by facilitating iterative design of the language.

Compiler Support and Tools for DSLs

Because DSLs are created more frequently than full GPLs, and because they may be changed more frequently, the need for compiler-compiler and other translator tools is greater with DSLs than with GPLs. It seems that the needs of DSL creators could influence compiler construction technology toward such benefits as more debugging, better debugging, support for specifying semantics, and more visualization.

Advantages of DSLs

Finally, there are many, many advantages to DSLs, such as notational convenience, certain type checking and global optimization opportunities, the ability to make additional safety guarantees, the potential for domain experts to program, the possibility of a variety of analysis, and the ability to capture an abstraction, thereby serving as an example of reuse.

Regarding the conference as a whole: a very high proportion of attendees was present for the entire conference despite the pleasant weather and beachfront venue. Interest in the BOFs was so great that initial plans to run them concurrently were shelved in favor of a consecutive schedule, and the papers presented were of such uniformly high quality that the program committee was unable to single out one for special commendation! Overall, I believe the conference was a great success and would not be at all surprised if USENIX were to repeat it at some point in the future. See you there!

KEYNOTE ADDRESS

The Promise of Domain-Specific Languages

Paul Hudak, Yale University Department of Computer Science

Domain-Specific Languages: Some Definitions

With help from a motley crew of animated agents residing in his laptop computer, Paul Hudak began his entertaining and thoughtful keynote address on the promise of Domain-Specific Languages. Hudak offered a framework for thinking about and working with DSLs, starting with a definition of the term itself: "A programming language tailored specifically for an application domain: it is not general purpose but rather captures precisely the semantics of the domain, no more and no less." He quickly followed with a definition of "application domain," which he accomplished by way of example, citing simulation, lexing and parsing, CAD/CAM, hardware description, text/pattern matching, computer music, and database queries, among others. To add to the list, Hudak said, one merely needs to reflect on the question: "How many papers have you seen with a title such as XXX: A Language for YYY?"

Hudak also offered a second definition of a DSL: "the ultimate abstraction of an application domain; a language that you can teach to the intended user in less than a day." This definition relies on the observation that the intended user of a DSL is probably already well versed in the semantics of its domain and needs only a suitable notation with which to program.

In case you think DSLs are something new, you could ponder the list of popular and successful DSLs and their domains that Hudak presented:

  • Lex and Yacc (for program lexing and parsing)
  • (for text/file manipulation/scripting)
  • VHDL (for hardware description)
  • TeX and LaTex (for document layout)
  • HTML/SGML (for document markup) * Postscript (for low-level graphics)
  • Open GL (for high-level 3D graphics)
  • Tcl/Tk (for GUI scripting)
  • Macromedia Director (for multimedia design)
  • Prolog (for logic)
  • Mathematica/Maple (for symbolic computation)
  • AutoLisp/AutoCAD (for CAD)
  • emacs Lisp (for editing)
  • Excel Macro Language (for things never intended)

Advantages and Disadvantages of the DSL Approach

Chief among the advantages of the DSL approach to software development is higher programmer productivity because programs written in a DSL tend to be more concise, quicker to write and maintain, as well as easier to (automatically) reason about. Furthermore, although it sounds oxymoronic, DSL programs can sometimes be written by nonprogrammers. Hudak observed that these motivators are the very ones that drove the adoption of high-level general-purpose languages in the first place!

Of course, the DSL approach is not without challenges, too: performance may be poor because high-level languages are sometimes inefficient; there may be unacceptable start-up costs associated with the development of a DSL; a "Tower of Babel" may result if every domain acquires a specific language; the temptation to add features incrementally to a DSL can lead to bloat; and perhaps most important, designing and implementing languages (well) is a very hard task typically requiring two to five years for a new one. All of these issues represent possible obstacles that we need to overcome in order to more readily enjoy the benefits of DSLs.

A Recommended Approach to DSL Development

Given his experience with implementing and using a number of DSLs, Hudak distilled these recommendations for building software with a DSL:

  • Choose your domain.
  • Design a DSL that accurately and effectively captures the domain semantics. Concentrate on the semantics. Don't let performance dominate design. Try to keep the end-user in mind at all times and to keep things as simple as possible.
  • Prototype your design; refine and iterate. Also build SW tools to support the DSL.
  • Develop applications (domain instances) using the DSL infrastructure.
  • Success equals a happy customer!

Hudak observed that, although syntax and semantics are well treated in current and prior DSL development, tools often receive short shrift.

The Embedded DSL: An Implementation Approach

To overcome the weakness in tool support and to address some of the earlier noted disadvantages, Hudak advocated an approach to DSL development whereby the DSL is embedded in an existing, more general-purpose programming language ­ an Embedded DSL or "DSEL." A DSEL inherits general-purpose features from the enclosing language, the "host," as well as that language's existing tool set as a base. This frees the DSL designer who is implementing the DSL to concentrate on semantic issues and then provide domain-specific optimizations and extensions for an existing tool set. Hudak also advocated the use of metaprogramming tools such as transformation systems or partial evaluators to recover performance and practicality that might otherwise be sacrificed by the embedded approach.

As advantages of the DSEL approach, Hudak cited rapid DSL design, increased changeability, familiar look and feel, reuse of infrastructure, a reduction in language bloat, and because whatever formal methods are applicable to the host language are applicable to the DSL, the possibility of using algebraic/denotational semantics.

A DSL tends to share the same limits and face the same problems as the underlying host language, so Hudak cautioned that the choice of host language should be made after the abstract design of the DSL so that it can be made based primarily (if not entirely) on its suitability for hosting the particular DSL rather than on some other considerations.

The Lightweight DSL: An Implementation Refinement

Hudak introduced a refinement to the embedding approach called the Lightweight DSEL, which is a "pure" embedding. He noted that this approach requires a fairly powerful base language, one with higher-order functions, automatic memory management, syntactic extensions, flexible evaluation, and a flexible type system. In fact, in his experience implementing DSLs in Haskell, Hudak has made significant use of the higher-order functions, lazy evaluation, type classes, monads, and infix syntax features of Haskell. According to Hudak, the definitive way to embed a DSL within Haskell is to treat the DSL as an abstract data type for which an implicit interpreter represents the semantics. In this way, equational reasoning can be used to verify key algebraic properties of the DSL.

Conclusion

Hudak concluded by saying that DSLs are a good thing. Embedded DSLs and lightweight DSELs can be good things, but we need more and better tools to help with the design and implementation of DSLs. He also said that there should be a shift in emphasis in tool design from syntax to semantics, that the science of computer science has a role to play here. Algebraic/denotational semantics, modular interpreters, modular program execution tools, extensible type systems, and program transformation/partial evaluation were all mentioned as fruitful areas for this work.

Hudak never explicitly addressed the teaser that introduced his abstract for the keynote address, namely, "Are domain-specific languages (DSLs) the long-awaited silver bullet of software engineering?" However, he did argue cogently that DSLs have value and that embedding can be an excellent approach to the implementation of DSLs. In addition, he framed the entire conference with his definitions of a DSL and his worthwhile recommendations for the design and implementation of DSLs.

To see more, consult his official and personal home pages:

<http://WWW.CS.Yale.edu/HTML/YALE/CS/faculty/hudak.html>
<http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/hudak-paul.html>
<http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/hudak-dir/dsl/index.htm>.

REFEREED PAPERS

Session: Domain-Specific Language Design

Each of the three presenters in this session introduced a problem domain, characterized some of its unique aspects, and described the design goals of an appropriate solution. In each case, the author showed how insight progressed to design and related the language design to the implementation architecture.

Service Combinators for Web Computing

Luca Cardelli, Digital Equipment Corporation, and Rowan Davies, Carnegie Mellon University

Cardelli and Davies based this work on observations about both the unique characteristics of the World Wide Web and the way it is used. On the Web, documents may be unavailable or slow to transfer. People compensate with interesting retrieval strategies involving multiple connections and preemptive behavior based on transfer rates. These strategies are not expressible via existing distributed paradigms, such as remote procedure calls. Cardelli and Davies therefore began with the view that the Web is a new and peculiar kind of computer, the "Berners-Lee Machine," and set out to derive a language for programming it.

The result is a nascent language of service combinators for which a Java-based interpreter exists and a useful look at how one might go about designing a DSL. The language can be used to express typical human Web-browsing strategies because it allows direct references to the important characteristics of the Berners-Lee machine (including transfer rate). The authors offered a succinct formal semantics for the language and proved the correctness of certain optimizing transformations. This language of combinators was implemented as a set of composable Java functions rather than as a full-fledged language with its own unique concrete syntax. The authors argued that this implementation approach can be a good prototyping technique because it provides a performance benefit, eliminates the possibility of parsing or lexing errors at runtime, and reuses the syntax of the host language and therefore the front end of that language's compiler. As Davies noted, this is a general technique suitable for any Domain-Specific Language that is to be translated via an interpreter embedded in a larger (general-purpose) language.

<http://www.cs.cmu.edu/afs/cs.cmu.edu/user/rowan/www/home.html>
<http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-148.html>

A Domain-Specific Language for Video Device Drivers: From Design to Implementation

Scott Thibault, Renaud Marlet, and Charles Consel, IRISA/INRIA­ Université de Rennes 1

In creating their DSL for implementing video device drivers, Thibault et al. undertook a formal domain analysis of a video device driver domain. As a result of this analysis, they adopted an architecture that combines a DSL, its interpreter, and an abstract machine in order to express and implement the video device drivers. The authors did not let performance concerns unduly influence their early design decisions and reclaimed the performance sacrificed by their architectural choice by using the technique of partial evaluation to curry the device driver program, its interpreter, and its abstract machine.

<http://www.irisa.fr/compose>
<http://www.irisa.fr/EXTERNE/projet/lande/consel/papers.html#SE>

Domain Specific Languages for ad hoc Distributed Applications

Matthew Fuchs, Walt Disney Imagineering

The final paper presented in the DSL Design session examined the value of DSLs as intermediate glue between distributed "agents," be they computational or human. Fuchs observed that humans find binary data inconvenient and that many ASCII formats prove tricky for programs to parse. Yet distributed application components may need to interact with both software agents and human ones, and rather than construct each component with two interfaces, it would be nice to find a single format suitable for both.

Fuchs recommended creating a DSL to subsume both of these interfaces ­ a single language for communicating state, behavior, and sequence to both human and computer-based agents. To represent the language, Fuchs advocated using SGML or its simplified subset, XML, because they are suitable for human use (they can be displayed by a graphical interface) and are easily processed by programs, especially in the latter case. To explore the value of this idea, Fuchs showed how the game of bridge can be represented by an XML object, which is passed from player to player during the course of a game. At each turn, the string is extended, with data representing a new bid or card play, and processed by an agent (human or computer) representing a player.

Fuchs placed great value on the power of separating syntax and semantics in defining a DSL. Interestingly, Fuchs also observed that LL(1) languages are particularly well suited to use in this domain, especially for applications with a high degree of interactivity. This is because LL(1) languages permit top-down parsing, which means that a string in the language can be successfully parsed (i.e., the relevant production can be known) at any point during the string's construction.

Session: Experience Reports

Participants outlined their experiences with DSLs, what benefits they realized, what challenges they faced, and what advice they could offer to other potential DSL developers.

Experience with a Domain Specific Language for Form-based Services

David Atkins, Thomas Ball, Michael Benedikt, Glenn Bruns, Kenneth Cox, Peter Mataga, and Kenneth Rehor, Bell Laboratories, Lucent Technologies

MAWL is a DSL for creating device-independent, form-based services. Such services are characterized by data flows between the service and its users in a series of query/response interactions. A form is the abstraction that describes each interaction between the user and the service. This simple but powerful abstraction is the key to the numerous benefits provided by MAWL. Ball reported that MAWL enabled certain properties of a Web service to be verified at compile time, something that cannot be done in general for CGI scripts. Additionally, MAWL and its corresponding implementation architecture permit certain flexibilities, such as the creation of a standalone service (independent of a Web server), the use of a variety of implementation languages, and even the substitution of different user interface devices. Furthermore, because a declaration of each form's signature is available to the MAWL compiler, a functional Web-based stub can be generated automatically for the application, thereby permitting rapid evaluation of the service before extensive effort is invested in the various aspects of the eventual user interface. Because all of these benefits accrue directly or indirectly from the central form concept, it seems safe to say that the experience with MAWL amply demonstrates Hudak's suggestion that a DSL is the "ultimate abstraction" in a domain.

<http://www.bell-labs.com/projects/MAWL/>

Experience with a Language for Writing Coherence Protocols

Satish Chandra and James R. Larus, University of Wisconsin, Madison; Michael Dahlin, University of Texas, Austin; Bradley Richards, Vassar College; and Randolph Y. Wang and Thomas E. Anderson, University of California, Berkeley

A veritable gold mine of concrete advice to DSL designers and implementers, this experience report described a language called "Teapot," which is for writing the coherence protocols found in Distributed Shared Memory (DSM) systems. The goal of the language is to eliminate a variety of programming errors by providing a language that is specific (and restricted) to the applicable domain as well as to obtain both an implementation of a protocol and a source for a protocol verifier from a single protocol description.

This report offered many suggestions to prospective DSL designers:

  • A DSL should probably be as small as you can stand.
  • The language should directly support programming scenarios that occur commonly in the domain.
  • A DSL's users should not need to know implementation details.
  • Compiler optimizations should be explicitly specified and user-selectable.
  • Provision of thread support should be considered from the outset.
  • Be prepared to assist users in adopting your DSL; otherwise, natural inertia will preclude it (examples help greatly here).
  • It is better to start with a small, focused DSL that satisfies a small user community and possibly extend it later rather than shoot for a rich language from the start.
  • It is important to be realistic and specific about the capabilities and shortcomings of your DSL (implementation) when dealing with its user community.

Chandra et al.'s report suggests that DSLs can be valuable, but that designing, implementing, and popularizing a DSL is not entirely straightforward.

<http://www.cs.wisc.edu/~chandra/teapot/>

Lightweight Languages as Software Engineering Tools

Diomidis Spinellis, University of the Aegean, and V. Guruprasad, IBM T. J. Watson Research Center

Guruprasad showcased various advantages, disadvantages, and implementation techniques germane to the DSL arena by presenting a survey of representative DSL systems covering user interface specification, the software development process, text processing, multiparadigm programming, and language implementation. The principal advantage cited in this work is that the DSL reduces the semantic gap between specification and implementation, echoing once again the "ultimate abstraction" theme.

Disadvantages do exist, however, and they include a tendency for the ad hoc nature of DSLs to contribute to a lack of suitably skilled personnel, training materials, and appropriate tools; doubts about scalability; and, through proliferation, a computer language "tower of babel." Never- theless, the overall experience described by Guruprasad has been favorable.

Implementation techniques were also discussed, and implementers were encouraged to (re)use existing source code and tools wherever possible, in the latter case, by combining language processors (i.e., generate a high-level language source). Simple syntax with lexical hints and self-documenting source files should all be used as well. Finally, features of the target and implementation languages may prove valuable to use.

Session: Compiler Infrastructure for Domain-Specific Languages

This session examined language technologies that could provide benefits to DSL implementors. Two of the papers examined techniques that require opening up the language translator itself.

A Slicing-Based Approach for Locating Type Errors

T. B. Dinesh, CWI, and Frank Tip, IBM T. J. Watson Research Center

The quality of tools that accompany a DSL can affect its success in being adopted. One way to ease the creation of good and useful tools for DSLs is to generate them from specifications. Dinesh presented work that describes a novel technique for incorporating dynamic dependence tracking in an algebraically specified type checker. While a program's abstract syntax tree is being rewritten into a list of type errors, a minimal portion of the source (a "slice") is computed for each error. The slice has a special property: it is guaranteed to reproduce the original error. An entire slice is necessary because type errors are the result of source that is distributed throughout a program, unlike syntax errors, which can usually be localized to a single token. This work, called "CLaX," has been implemented in the ASF+SDF Meta-environment for a substantial subset of Pascal.

<http://www.cwi.nl/~dinesh/>

Typed Common Intermediate Format

Zhong Shao, Yale University

In order to facilitate both the ready generation of compilers for DSLs and the interoperation of DSLs and general-purpose languages, a common substrate is required. FLINT, a typed intermediate format that satisfies this requirement, is discussed by Shao in this paper. Translator implementation is simplified by FLINT because a reusable "back end" is provided. Another benefit of FLINT is that it enables code written in multiple languages to interoperate. This is because each language's translator can share the same back-end facilities (e.g., optimizers, verifiers, and generators) as well as runtime conventions (e.g., garbage collector, foreign function calling mechanisms). Finally, unlike other intermediate languages, FLINT is capable of supporting higher-order languages such as ML.

<http://flint.cs.yale.edu>
<ftp://ftp.research.bell-labs.com/dist/smlnj> <http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/shao-zhong.html>

Incorporating Application Semantics and Control into Compilation

Dawson R. Engler, MIT Laboratory for Computer Science

What would happen if one stopped viewing one's compiler as a black box and opened it up, even just a little bit? What kinds of things could one do? Engler provided one answer to these questions with a paper describing MAGIK, a system that permits users to hook into the compilation process and provide transformations or verifications that are driven by application semantics and yet still benefit from the optimization phase of the original compiler. Examples of the kinds of transformations and verifications possible with MAGIK include verifying type safety between the format string and other arguments of the C language's printf; determining if system call return codes are examined and, if not, adding code to do so; enforcing adherence to "programming rules" such as restrictions to be observed when coding UNIX signal handlers; and partial evaluation in the context of RPC parameter marshalling.

<http://www.pdos.lcs.mit.edu/~engler/>

Code Composition as an Implementation Language for Compilers

James M. Stichnoth and Thomas Gross, Carnegie Mellon University

Code composition is a technique that promises speedy implementation of compilers that are capable of translating high-level or complex operations with both good quality and efficiency. Catacomb performs code composition through the interaction of a composition system with a compiler. The compiler partitions the source program into two sets of constructs, those for which code composition is offered and those for which it is not. For each construct that permits code composition, the compiler invokes the composition system. The composition system, in turn, processes code templates that are separate source-comprising code constructs and control constructs. The control constructs are "executed" by the composition system producing custom-generated code, which is then passed back to the compiler proper. Once under the compiler's control, the custom-generated code can be combined with the remaining code constructs and processed by all the further downstream processors (e.g., optimizers).

Session: Logic and Semantics for Domain-Specific Languages

This session focused on the role of mathematical foundations in the creation of DSLs. The first two papers described valuable DSLs that have firm mathematical foundations. The last paper described an advance in the specification of formal semantics.

BDL: A Language to Control the Behavior of Concurrent Objects

Frédéric Bertrand and Michel Augeraud, Université de La Rochelle

This work was motivated by the observation that managing concurrency in object-oriented systems is difficult. This is because, without language support, it is hard in general to ensure that programmers manage to avoid such concurrent-programming pitfalls as failure to observe mutual exclusion protocols and dead-lock situations. The Behavioral Description Language (BDL) is a DSL that is used to specify and enforce various temporal constraints that may be placed on the use of one or more object's interfaces. BDL programs run on an execution controller that enforces the program's specification. The mathematical foundation of BDL is the well-developed field of automata theory, which confers three principal advantages to BDL. Automata can be made to execute efficiently, many verification tools already exist for analyzing BDL programs, and an existing reactive programming language (in this case, Esterel) can be used to translate BDL into executable code.

A Domain-Specific Language for Regular Sets of Strings and Trees

Nils Klarlund, AT&T Labs Research, and Michael I. Schwartzbach, University of Aarhus

Schwartzbach presented both FIDO, a high-level programming notation that concisely expresses regular sets of strings or trees, and a thorough analysis of the DSL experience as he and his colleagues see it. FIDO combines standard programming language concepts such as recursive data types, unification, implicit coercions, and subtyping with a variation of predicate logic called the Monadic Second-order Logic (M2L) on trees. M2L has proved very useful to Schwartzbach and his colleagues, but suffers from a tedious notation. FIDO corrects this.

Schwartzbach indicated that there is no substitute for domain experience in maximizing the likelihood of creating a successful DSL. Often, such experience will expose a repetitive or error-prone software activity that must be performed when solving problems in the domain. Removing this repetitive activity from the programmer's work and placing a solution to it within a language is a key impetus for the creation of a DSL.

Once a commitment to DSL creation is made, some reflection on the nature of the software problem and a domain analysis (formal or otherwise) takes place. The outcome of these steps is combined with a general knowledge of language concepts and language technology to create an implementation that, if everything goes well, provides relief from the original software problem. As with everything computational, some iteration may be necessary, in part because of imperfect execution of the earlier steps, but, surprisingly, also due to one more issue: the DSL's implementation and its effect on your software problem may actually lead to further insight in the domain! It is this feedback that yields a deeper understanding of the domain that may, additionally, prompt another iteration in the cycle.

A Modular Monadic Action Semantics

Keith Wansbrough and John Hamer, University of Auckland

If there had been an award for "Presentation with the Most Audience Participation," Hamer certainly would have won it. After entertaining the audience with an exercise in creating an origami frog, he presented some work done principally by Wansbrough on the fusing of Modular Monadic Semantics (MMS) with Action Semantics (AS) (yielding Modular Monadic Action Semantics). Action Semantics is popular for its highly readable notation, yet it is monolithic, supports only a fixed range of language concepts, and is somewhat difficult to employ in proving properties about a language or its programs. Modular Monadic Semantics is highly extensible due to excellent modularity and, because it is implemented in a functional programming language, its specifications can be directly executed. Modular Monadic Semantics is considered to be at a slightly lower level of abstraction than Action Semantics and, unfortunately, is also considered to be a bit challenging to use. Modular Monadic Action Semantics thus combines the best aspects of Action Semantics and Modular Monadic Semantics to provide an extensible, easy-to-write notation.

Session: Case Studies and Frameworks

This session discussed work in interesting problem domains. In the first two papers, case studies of DSL creation and use were presented. The third paper documented a survey and analysis of Architecture Description Languages that could provide the kind of domain understanding required for the creation of a new DSL.

SHIFT and SMART-AHS: A Language for Hybrid System Engineering Modelling and Simulation

Marco Antoniotti and Aleks Göllü, University of California, Berkeley

The domain in which SHIFT operates is that of Hybrid Systems Analysis and Modelling which can be likened to simulation of situations where both continuous and discrete phenomena are present and interact. The SHIFT language contains terminology, notation, and semantics straight from the domain, making it readily usable by the intended audience: control system engineers. Befitting a case study, SHIFT has received significant use. This paper describes the reimplementation of the Traffic Simulation framework, SMART-AHS, in SHIFT. Users reported a 50% reduction in the size of both libraries and projects and greater ability to reuse code. Credit is given in the evaluation of SHIFT to it containing the "right" abstractions, being somewhat restrictive compared to a GPL, and consequently requiring fewer "programming rules" than other systems. This last aspect is important because, as a DSL, SHIFT can enforce programming rules, so they become language rules and less of a cognitive load for developers.

<http://www.path.berkeley.edu/> <http://www.path.berkeley.edu/shift> <http://www.path.berkeley.edu/smart-ahs>

Design and Semantics of Quantum: A Language to Control Resource Consumption in Distributed Computing

Luc Moreau, University of Southampton, and Christian Queinnec, Université de Paris

With the advent of mobile agents comes increased interest in the ability to control the resource consumption of computations either because one needs to pay for such consumption or because one is providing the resources for others to consume. The DSL Quantum was developed for users to specify and enforce resource consumption limits and patterns for distributed computing. Quantum is the synthesis of three ideas:

  • Quotas of energy can be associated with computations, and energy is being consumed during every evaluation step.
  • Asynchronous notifications inform [interested parties] of energy exhaustion or computation termination.
  • Mechanisms exist to transfer energy to or from computations; supplying more energy to a computation gives the right to continue the computation, and removing energy from a computation acts as energy-based preemption.

This paper contrasts Quantum with a broad variety of similar work in this field.

<http://diana.ecs.soton.ac.uk/~lavm/>

Domains of Concern in Software Architectures and Architecture Description Languages

Nenad Medvidovic and David S. Rosenblum, University of California, Irvine

Architecture Description Languages (ADLs) abound, but, as often happens when there is not yet agreement on what the problem is, these "solutions" differ widely, especially in their coverage of software architectural concerns. Medvidovic presented a comprehensive framework of architectural concerns and evaluated several major ADLs with respect to this framework. More understanding of the domain(s), how they relate to application domains, and what effect they should have on ADLs are required, noted Medvidovic. Medvidovic's framework showed the kind of analysis that one can imagine forming the basis for a new DSL; whether it is arrived at by virtue of a formal process or by intuition, at some point, an understanding of the domain in this depth becomes necessary. Watch this space for a DSL.

<http://www.ics.uci.edu/pub/arch/sw-and-pubs.shtml>

Session: Abstract Syntax Trees

This session concentrated on a fundamental building block of language tools: the Abstract Syntax Tree. Papers were presented that discussed superior tools and techniques for representing such trees, searching them, and manipulating them.

The Zephyr Abstract Syntax Description Language

Daniel C. Wang, Andrew W. Appel, Jeff L. Korn, and Christopher S. Serra, Princeton University

One area where DSLs shine is in the creation of a glue or interchange language that can serve as input to various automated program generators. Such meta-programming languages can aid in the integration of tools from diverse sources. The Zephyr Abstract Syntax Description Language (ASDL) was designed to provide a concise notation for describing abstract syntax trees. This notation is processed by several companion tools that generate data structure definitions

and procedures in several target languages for converting ASTs to and from a standardized flat representation (pickles). Interoperation of compiler components is greatly facilitated by the capability to exchange ASTs easily. As a proof of concept, Wang described the use of the Zephyr ASDL to respecify the Stanford University Intermediate Format (SUIF) (among others), with impressive reduction in "program" size.

<http://www.cs.virginia.edu/zephyr/> <http://www.cs.virginia.edu/zephyr/asdl.html> <http://www.cs.princeton.edu/~danwang/zdoc/slp.html>
<http://www.cs.princeton.edu/~danwang/zdoc/ztalk.pdf>

ASTLOG: A Language for Examining Abstract Syntax Trees

Roger F. Crew, Microsoft Research

Crew described a clever and useful adaptation of Prolog for locating and analyzing complex syntactic constructs in program sources (as opposed to the lexical searching capabilities of tools such as Awk and grep). ASTLOG was inspired by Prolog and its implicit pattern-matching and backtracking capabilities. Program source, instead of being converted to a Prolog fact database, can be directly examined by predicates present in ASTLOG. This feature is the key to making this approach feasible for examining large programs. The principal consequence of the inclusion of these predicates is what Crew termed an inside-out functional programming style, which turns out to be particularly suitable for searching and pattern matching on parse-trees. Performance of the system on substantial real-world examples is comparable to the time taken for compilation.

<http://www.research.microsoft.com/%7Erfc/default.htm>

KHEPERA: A System for Rapid Implementation of Domain Specific Languages

Rickard E. Faith, Lars S. Nyland, and Jan F. Prins, University of North Carolina, Chapel Hill

Check this out if you're looking for support for DSL development: KHEPERA is a toolkit that creates DSL processors by generating source-to-source translators that rely on sophisticated tree-based analysis and manipulation to provide ease of implementation and superior debugging information. Systems built with KHEPERA not only provide support for debugging DSL translators themselves, but also support debugging the end-user's DSL program. Faith started with a software problem in which repetitive work was being performed on custom translators for the DSL PROTEUS, and he was thus motivated to find an automated way of generating DSL translators. Such a system is advantageous because of the recognition that DSLs are likely to evolve. Such evolution implies frequent syntax and other translator-affecting changes. KHEPERA itself contains a DSL ­ the KHEPERA Transformation Language ­ that describes the fundamental tree matching and manipulation primitives required to specify a source-to-source translator.

<http://www.cs.unc.edu/~faith/khepera.html>

Session: Embedded Languages and Abstract Data Types

This session was the combination of two topics: how fully supporting a useful abstract data type may require a DSL, and what kinds of considerations one faces when using the embedded approach to implement a DSL. The papers covering the former topic showed two cases where supporting an abstract data type required

features that aren't available in general-purpose languages, and therefore a DSL was the best recourse. The latter topic's papers, based on actual experiences, cataloged many of the choices (and their consequences) that are encountered when implementing a DSL as an embedded language.

DiSTiL: A Transformation Library for Data Structures

Yannis Smaragdakis and Don Batory, University of Texas, Austin

The domain for DiSTiL is that of complex container data structures. The authors argue that these data types should have uniform interfaces that allow the application and implementation to evolve independently. The implementation of DiSTiL was described as an extension of Microsoft's Intentional Programming system, which is discussed in some detail within the paper. Furthermore, work described in this paper develops a metaprogramming framework above IP called "generational scoping," which the paper concludes might develop into a general-purpose set of primitives for describing program generators. In addition to describing the primary technical contribution surrounding DiSTiL, the paper enumerates many conclusions about the suitability of IP and its potential influence on DSL design, implementation, and use.

<http://www.research.microsoft.com/research/ip/tedb/page6.html>

Programming Language Support for Digitized Images or The Monsters in the Closet

Daniel E. Stevenson and Margaret M. Fleck, University of Iowa

In this work, Fleck argues that language support in the form of a new abstract data type, the "sheet," and various associated primitives can dramatically simplify the task of programmers writing in the field of computer vision (image understanding) algorithms. A host of benefits other than direct programming relief accrues: easier collaboration and teaching and replication of research results. By codifying various "hard" parts of image processing into language primitives, Fleck hoped to get her colleagues to focus on images instead of programming. She also challenged DSL designers to bring the appropriate level of programming language abstraction (via a DSL) to this field, claiming that previous approaches are either too high or too low. The last half of this paper describes the particular aspects of computer vision that should be supported in a DSL and a proposed instance of this DSL named Envision.

<http://www.cs.hmc.edu/~fleck/envision/envision.html>

Modelling Interactive 3D and Multimedia Animation with an Embedded Language

Conal Elliott, Microsoft Research

Fran is a DSL for describing and composing animations. A key insight behind Fran is that an animation can be thought of as a function of time. Elliott suggested that much animation work is frustrated by the level of detail required and the fundamental mismatch between the medium and the computer. For instance, computers operate in discrete steps, whereas time is continuous; or, for example, single-processing computers must be used to implement concurrent animations. The declarative nature of Fran alleviates these problems. Although Elliott's talk centered on successively complex animation examples, the corresponding paper conveys a wealth of insight into design and implementation techniques

for domain-specific languages, particularly in its discussion of modelling and host-language embedding.

<http://www.research.microsoft.com/~conal/fran/default.htm>
Also see Landin's "The Next 700 Programming Languages, " Communications of the ACM, March 1966, pp. 157-164.

A Special-Purpose Language for Picture Drawing

Samuel Kamin and David Hyatt, University of Illinois, Urbana-Champaign

Kamin described an experiment in domain-specific language design and implementation. Inspired by PIC, Kamin reproduced a set of drawing primitives implemented within Standard ML. Kamin showed the design and evolution of his language, FPIC, carefully illuminating his design decisions at each step along the way. He also revealed the trade-offs inherent in his choice to use the embedded-language implementation approach. Kamin noted one interesting limitation of the embedded approach: complications can arise because the ordinary language has an environment distinct from that used by the embedded language's primitives. Nonetheless, Kamin concluded that the cost-benefit ratio of the embedded language approach is favorable.

<http://www-sal.cs.uiuc.edu/~kamin/fpic>

INVITED TALKS

Synchronous Languages ­ An Experience in Domain-Specific Language Design

Gérard Berry, École des Mines de Paris, Centre de Mathématiques Appliquées: INRIA, Projet Meije

Berry presented ideas about DSLs drawn from his experience in designing and using Esterel, a language for programming deterministic reactive systems (systems that execute indefinitely, reacting deterministically to asynchronous inputs). Berry's inquiry was quite thorough in both its breadth and detail; however, a few key points can be selected for special mention.

When DSL designers wish to implement their language by the embedded approach, care must be taken to consider whether the host language is too rich or lacks a precise definition. This would complicate rigorous analysis.

For safety-critical applications, a sound mathematical foundation, and therefore a precise semantics, is an absolute necessity for the language. Automated analysis depends upon it.

There should be a compelling reason for introducing a new language. Either useful mathematical properties or the abstraction of complex computation is a suitable reason.

Sometimes the domain on which a designer is focused can be enlarged from the immediate application to a broader, more foundational one, in which case the resulting DSL can be more widely useful.

Orthogonality of language features should be supported.

It is the particular mathematical properties of a formalism and its usefulness, not just its mere existence, that ultimately determines the value of any formalism.

It is a myth that DSLs must be less efficient than general-purpose programming languages. Because DSLs tend to be small and may operate at quite high levels, sophisticated optimizations may be feasible. Or DSLs may perform functions that are impractical for a human, thereby increasing the scale at which a solution

can be obtained or yielding efficient solutions without the cost of hand coding.

Berry's conclusion: "language design never ends."

For interested readers, much more information, including the latest Esterel compiler, can be had at <http://www.inria.fr/meije/esterel/esterel-eng.html>

Intentional Programming ­ An Ecology for Abstractions

Charles Simonyi, Chief Architect, Microsoft

Charles Simonyi presented an overview of Intentional Programming (IP), which is referred to in Microsoft papers variously as a process, a programming environment, and an ecology. From a DSL-design perspective, a novel aspect of IP is that it seeks to reduce or eliminate the rigidity of syntax in programming languages. Instead of a text-based syntax, intentional programs are created "preparsed" as trees of nodes (the intentions) aimed at capturing the programmer's intent. Each node can be thought of as an object or component, possibly quite fine grained, that presents an appearance to the programmer and is capable of behavior. Both the appearance and the implementation of the behavior are permitted to change; however, the intention remains the same, as do its relationships with other intentions in the intentional program. Intentions can operate on other intentions to transform them to forms already understood by an IP system. Such intention-transforming intentions are called enzymes, in keeping with the biological metaphors.

Why program this way? The hope is that the adoption of IP will create an environment where the biological principles of evolution will be brought to bear on software componentry in the hopes that the "fittest" will prevail. Simonyi envisions a vast soup of intentions, each vying for a place in your programs.

IP needs more explanation than an invited talk (or its review) can provide; therefore, I strongly encourage interested parties to pursue this topic by visiting <http://www.research.microsoft.com/> and searching for "intentional programming" or perhaps just by starting with these two pages:

Aspect-Oriented Programming ­ Improved Support for Separation of Concerns in Design and Implementation

Gregor Kiczales, Xerox Palo Alto Research Center

Concluding the conference was the privilege of hearing Gregor Kiczales, co-author of "The Art of the Metaobject Protocol." He chose to talk about his most recent work, which he calls Aspect-Oriented Programming (AOP), in which another "domain" (really a view or slice) for programs is introduced. It leads to programs that are much more tolerant of changes in the requirements of runtime behavior and other systemic properties.

Starting from first principles, Kiczales reminded us how (in general) we build complex systems by first partitioning the system into cognitively manageable parts ­ the separation of concerns, or decomposition ­ and then by constructing and/or composing implementation elements in a way that is "suggested" by the decomposition. In this way, concerns that are known from the outset tend to appear localized in the implementation and permit relatively easy modification in the face of changing requirements. There is, however, a class of concerns for which this fails dramatically ­ systemic properties (e.g., runtime behavior). The interaction of software components whose structure was determined largely by static considerations gives rise to what Kiczales terms "emergent entities." The recognition of these entities provides the key insight that motivates AOP: emergent entities are important, are difficult to manage classically, and require languages and tools for their explicit description and use.

Emergent entities are important because they can represent things like performance concerns, synchronization behaviors, memory usage, and replication properties. They are difficult to manage classically because accommodating any single one could involve changes to many components in a system. This arises because emergent entities involve the interaction of components and therefore cut across component boundaries. Kiczales allows that there is frequently a way to refactor a design post hoc to accommodate changes in the runtime behavior requirements; however, what is needed is something more accommodating of such changes. Finally, emergent entities need language and tool support precisely because they do not (yet) appear explicitly in the implementation of a system.

The mechanism Kiczales proposes to manage emergent entities is the "aspect," which he defines as a "modular unit of control over emergent entities." He further proposes (and has implemented) "aspect languages" and their translators, "aspect weavers." The translators work by taking a modular program and the expression of one or more aspects and weaving the codes together, yielding a program that reflects the original modular system, modified to account for the

aspect. Through this technique, the aspect can be coded in a compact, local form and yet, through the actions of the aspect weaver, have a widely distributed effect on the implementation. Thus, AOP is a "modularity for that which was previously amodular" and is robust in the face of changes in the requirements for runtime behaviors and other systemic properties.

Slides from a similar talk are available at:
<http://www.parc.xerox.com/spl/projects/aop/forum/index.htm>

BOFS

There were three Birds-of-a-Feather (BOF) sessions at DSL '97, all of which were arranged by interested parties before the conference began. In part, the BOFs were a great success because of this preparation, and this points the way to a potential approach for increasing the likelihood of having interesting and well-attended BOFs.

Musical Languages

Attendees of the Musical Languages BOF session were treated to a number of speakers, some human, some electromechanical. The organizer, Tim Thompson, brought musical equipment and recordings with him, as did some of the other presenters, including Paul Hudak, the conference's keynote speaker. Several music and sound composition systems were demonstrated and contrasted. These exposed themes such as the use of interactive or visual DSLs and their relationship(s) to text-based languages and the nature of the interaction between domain experts and the language developers.

Patenting Domain-Specific Languages

At first glance, having a BOF concerned with intellectual property at a Domain-Specific Language conference might strike one as unusual, and it is. But it was certainly useful and intriguing. Christa Schwartz, a onetime software designer at Bell Labs and now a patent attorney, acquitted herself very well in delivering an interesting, realistic, and thought-provoking presentation about DSLs from the intellectual property perspective. Covering the background of patent law briefly, she went on to describe what elements are involved in both the decision to patent and also the process of patenting a Domain-Specific Language, its concepts and/or its implementation. Drawing on her interdisciplinary knowledge, Schwartz finished with an example in which she patented a language all DSLers should know: YACC.

Program Generators

This discussion began with Samuel Kamin's proposal that program generators should be considered programming languages that have programs and program fragments as their intrinsic data types instead of the more usual characters, integers, and floating point numbers. These program fragments parameterize a generator and determine the range of possible output programs, effectively defining an application domain. Kamin further framed the discussion by suggesting some points to ponder when considering program generators:

  • How can (or even should) the logic that generates the code and the "template" of the code be separated?
  • To what extent can ideas and features from other languages and implementations (such as static type checking, recursion, and optimization) be applied to program generators?
  • What kinds of languages work well as the target language of a program generator?
  • What is a good way to organize, structure, or maintain a program generator?
  • When should a program generator, rather than a full-fledged language or an embedded approach, be used to solve a problem?

The popularity of this BOF and the content of the discussion revealed substantial interest in program generators as a technique for creating parameterized solutions in certain problem domains.

Evolution of a domain-specific language

Quotable Quotes from the DSL Conference

Satish Chandra: "Avoid frustrating potential users. Avoid potential frustrating users."

Gerard Berry: "Language Design Never Ends" (just ask B.S.).

"0 is a beautiful number."

Charles Simonyi:"It's better to have DS Bugs than bugs bugs."

"I don't believe in simplicity. Simplicity is a trap."

"Haskel ­ you will really have to commit to it before you don't like it."

"I always feel funny when I hear the word 'simplicity.' "

Samuel Kamin: "Fn Langs: you either love 'em or you don't know what you're doing."

Gregor Kiczales: "You sound just like someone from PARC: you talk a long time about a simple problem."

"Exception handling: many many powerful minds have gone there . . . and come back."

Unknown limo driver: "What's this Unisex LSD Conference?"


?Need help? Use our Contacts page.
First posted: 30th January 1998 efc
Last changed: 30th January 1998 efc
Conference index
Proceedings index
USENIX home