Skip to main content
main-content

Über dieses Buch

Dijkstra once wrote that computer science is no more about computers than astronomy is about telescopes. Despite the many incredible advances in c- puter science from times that predate practical mechanical computing, there is still a myriad of fundamental questions in understanding the interface between computers and the rest of the world. Why is it still hard to mechanize many tasks that seem to be fundamentally routine, even as we see ever-increasing - pacity for raw mechanical computing? The disciplined study of domain-speci?c languages (DSLs) is an emerging area in computer science, and is one which has the potential to revolutionize the ?eld, and bring us closer to answering this question. DSLs are formalisms that have four general characteristics. – They relate to a well-de?ned domain of discourse, be it controlling tra?c lights or space ships. – They have well-de?ned notation, such as the ones that exist for prescribing music, dance routines, or strategy in a football game. – The informal or intuitive meaning of the notation is clear. This can easily be overlooked, especially since intuitive meaning can be expressed by many di?erent notations that may be received very di?erently by users. – The formal meaning is clear and mechanizable, as is, hopefully, the case for the instructions we give to our bank or to a merchant online.

Inhaltsverzeichnis

Frontmatter

Semantics

J Is for JavaScript: A Direct-Style Correspondence between Algol-Like Languages and JavaScript Using First-Class Continuations

It is a time-honored fashion to implement a domain-specific language (DSL) by translation to a general-purpose language. Such an implementation is more portable, but an unidiomatic translation jeopardizes performance because, in practice, language implementations favor the common cases. This tension arises especially when the domain calls for complex control structures. We illustrate this tension by revisiting Landin’s original correspondence between Algol and Church’s lambda-notation.

We translate domain-specific programs with lexically scoped jumps to JavaScript. Our translation produces the same block structure and binding structure as in the source program, à la Abdali. The target code uses a control operator in direct style, à la Landin. In fact, the control operator used is almost Landin’s J—hence our title. Our translation thus complements a continuation-passing translation à la Steele. These two extreme translations require JavaScript implementations to cater either for first-class continuations, as Rhino does, or for proper tail recursion. Less extreme translations should emit more idiomatic control-flow instructions such as

for

,

break

, and

throw

.

The present experiment leads us to conclude that translations should preserve not just the data structures and the block structure of a source program, but also its control structure. We thus identify a new class of use cases for control structures in JavaScript, namely the idiomatic translation of control structures from DSLs.

Olivier Danvy, Chung-chieh Shan, Ian Zerny

Model-Driven Engineering from Modular Monadic Semantics: Implementation Techniques Targeting Hardware and Software

Recent research has shown how the formal modeling of concurrent systems can benefit from monadic structuring. With this approach, a formal system model is really a program in a domain specific language defined by a monad for shared-state concurrency. Can these models be compiled into efficient implementations? This paper addresses this question and presents an overview of techniques for compiling monadic concurrency models directly into reasonably efficient software and hardware implementations. The implementation techniques described in this article form the basis of a semantics-directed approach to model-driven engineering.

William L. Harrison, Adam M. Procter, Jason Agron, Garrin Kimmell, Gerard Allwein

Methods and Tools

A MuDDy Experience–ML Bindings to a BDD Library

Binary Decision Diagrams (BDDs) are a data structure used to efficiently represent boolean expressions on canonical form. BDDs are often the core data structure in model checkers. MuDDy is an ML interface (both for Standard ML and Objective Caml) to the BDD package BuDDy that is written in C. This combination of an ML interface to a high-performance C library is surprisingly fruitful. ML allows you to quickly experiment with high-level symbolic algorithms before handing over the grunt work to the C library. I show how, with a relatively little effort, you can make a domain specific language for concurrent finite state-machines embedded in Standard ML and then write various custom model-checking algorithms for this domain specific embedded language (DSEL).

Ken Friis Larsen

Gel: A Generic Extensible Language

Both XML and Lisp have demonstrated the utility of generic syntax for expressing tree-structured data. But generic languages do not provide the syntactic richness of custom languages. Generic Extensible Language (Gel) is a rich generic syntax that embodies many of the common syntactic conventions for operators, grouping and lists in widely-used languages. Prefix/infix operators are disambiguated by white-space, so that documents which violate common white-space conventions will not necessarily parse correctly with Gel. With some character replacements and adjusting for mismatch in operator precedence, Gel can extract meaningful structure from typical files in many languages, including Java, Cascading Style Sheets, Smalltalk, and ANTLR grammars. This evaluation shows the expressive power of Gel, not that Gel can be used as a parser for existing languages. Gel is intended to serve as a generic language for creating composable domain-specific languages.

Jose Falcon, William R. Cook

A Taxonomy-Driven Approach to Visually Prototyping Pervasive Computing Applications

Various forms of pervasive computing environments are being deployed in an increasing number of areas including healthcare, home automation, and military. This evolution makes the development of pervasive computing applications challenging because it requires to manage a range of heterogeneous entities with a wide variety of functionalities.

This paper presents Pantagruel, an approach to integrating a taxonomical description of a pervasive computing environment into a visual programming language. A taxonomy describes the relevant entities of a given pervasive computing area and serves as a parameter to a sensor-controller-actuator development paradigm. The orchestration of area-specific entities is supported by high-level constructs, customized with respect to taxonomical information.

We have implemented a visual environment to develop taxonomies and orchestration rules. Furthermore, we have developed a compiler for Pantagruel and successfully used it for applications in various pervasive computing areas, such as home automation and building management.

Zoé Drey, Julien Mercadal, Charles Consel

LEESA: Embedding Strategic and XPath-Like Object Structure Traversals in C++

Traversals of heterogeneous object structures are the most common operations in

schema-first

applications where the three key issues are (1) separation of traversal specifications from type-specific actions, (2) expressiveness and reusability of traversal specifications, and (3) supporting structure-shy traversal specifications that require minimal adaptation in the face of schema evolution. This paper presents

L

anguage for

E

mbedded qu

E

ry and traver

SA

l (LEESA), which provides a generative programming approach to address the above issues. LEESA is an object structure traversal language embedded in C++. Using C++ templates, LEESA combines the expressiveness of XPath’s axes-oriented traversal notation with the genericity and programmability of Strategic Programming. LEESA uses the object structure meta-information to statically optimize the traversals and check their compatibility against the schema. Moreover, a key usability issue of

domain-specific error reporting

in embedded DSL languages has been addressed in LEESA through a novel application of

Concepts

, which is an upcoming C++ standard (C++0x) feature. We present a quantitative evaluation of LEESA illustrating how it can significantly reduce the development efforts of schema-first applications.

Sumant Tambe, Aniruddha Gokhale

Unit Testing for Domain-Specific Languages

Domain-specific languages (DSLs) offer several advantages by providing idioms that are similar to the abstractions found in a specific problem domain. However, a challenge is that tool support for DSLs is lacking when compared to the capabilities offered in general-purpose languages (GPLs), such as Java and C++. For example, support for unit testing a DSL program is absent and debuggers for DSLs are rare. This limits the ability of a developer to discover the existence of software errors and to locate them in a DSL program. Currently, software developers using a DSL are generally forced to test and debug their DSL programs using available GPL tools, rather than tools that are informed by the domain abstractions at the DSL level. This reduces the utility of DSL adoption and minimizes the benefits of working with higher abstractions, which can bring into question the suitability of using DSLs in the development process. This paper introduces our initial investigation into a unit testing framework that can be customized for specific DSLs through a reusable mapping of GPL testing tool functionality. We provide examples from two different DSL categories that serve as case studies demonstrating the possibilities of a unit testing engine for DSLs.

Hui Wu, Jeff Gray, Marjan Mernik

Combining DSLs and Ontologies Using Metamodel Integration

This paper reports on a case study where the domain specific language BEDSL for the description of network devices for computer networks is combined with the feature description language FODA used for defining the variability structure of product lines. Furthermore, annotations by fragments of the web ontology language OWL can be added.

In essence, the approach is a three-way integration, which regards two documents written in BEDSL and FODA, respectively, and semantic OWL-annotations as three equally important views of the system under discussion. The integration of languages is done on the level of their metamodels. The standard metamodel of OWL 2 is merged with two self-developed metamodels for the respective domain specific languages.

The merge is loss-free, i.e. the resulting merged model still contains all information from its parts. Thus, the BEDSL part can be used to visualize the network model, the FODA part still defines the feature structure of the corresponding product line and the OWL part can be extracted and fed into an OWL tool to assert the semantic conditions.

Tobias Walter, Jürgen Ebert

Case Studies

A Domain Specific Language for Composable Memory Transactions in Java

In this paper we present CMTJava, a domain specific language for

composable memory transactions

[7] in Java. CMTJava provides the abstraction of

transactional objects

. Transactional objects have their fields accessed only by special get and set methods that are automatically generated by the compiler. These methods return

transactional actions

as a result. A transactional action is an action that, when executed, will produce the desired effect. Transactional actions can only be executed by the

atomic

method. Transactional actions are first class values in Java and they are composable: transactions can be combined to generate new transactions. The Java type system guarantees that the fields of transactional objects will never be accessed outside a transaction. CMTJava supports the

retry

and

orElse

constructs from STM Haskell. To validate our design we implemented a simple transactional system following the description of the original Haskell system. CMTJava is implemented as a state passing monad using BBGA closures, a Java extension that supports closures in Java.

André Rauber Du Bois, Marcos Echevarria

CLOPS: A DSL for Command Line Options

Programmers often write custom parsers for the command line input of their programs. They do so, in part, because they believe that both their program’s parameterization and their option formats are simple. But as the program evolves, so does the parameterization and the available options. Gradually, option parsing, data structure complexity, and maintenance of related program documentation becomes unwieldy. This article introduces a novel DSL called

CLOPS

that lets a programmer specify command line options and their complex inter-dependencies in a declarative fashion. The DSL is supported by a tool that generates the following features to support command line option processing: (1) data structures to represent option values, (2) a command line parser that performs validity checks, and (3) command line documentation. We have exercised CLOPS by specifying the options of a small set of programs like

ls

,

gzip

, and

svn

which have complex command line interfaces. These examples are provided with the Open Source release of the CLOPS system.

Mikoláš Janota, Fintan Fairmichael, Viliam Holub, Radu Grigore, Julien Charles, Dermot Cochran, Joseph R. Kiniry

Nettle: A Language for Configuring Routing Networks

Interdomain routing

is the task of establishing connectivity among the independently administered networks (called

autonomous systems

) that constitute the Internet. The protocol used for this task is the

Border Gateway Protocol

(BGP) [1], which allows autonomous systems to independently define their own route preferences and route advertisement policies. By careful design of these BGP policies, autonomous systems can achieve a variety of objectives.

Currently available configuration and policy languages are low-level and provide only a few basic constructs for abstraction, thus preventing network operators from expressing their intentions naturally.

To alleviate this problem, we have designed

Nettle

, a domain-specific embedded language (DSEL) for configuring BGP networks, using Haskell [3] as the host language. The embedding in Haskell gives users comprehensive abstraction and calculation constructs, allowing them to clearly describe the ideas generating their BGP policies and router configurations. Furthermore, unlike previous router configuration and policy languages, Nettle allows users to both specify BGP policies at an abstract, network-wide level, and specify vendor-specific router details in a single uniform language.

We have built a compiler that translates Nettle programs into configuration scripts for XORP [4] routers and a simulator that allows operators to test their network configurations before deployment.

Andreas Voellmy, Paul Hudak

Generic Libraries in C++ with Concepts from High-Level Domain Descriptions in Haskell

A Domain-Specific Library for Computational Vulnerability Assessment

A class of closely related problems, a problem domain, can often be described by a domain-specific language, which consists of algorithms and combinators useful for solving that particular class of problems. Such a language can be of two kinds: it can form a new language or it can be embedded as a sublanguage in an existing one. We describe an embedded DSL in the form of a library which extends a general purpose language. Our domain is that of vulnerability assessment in the context of climate change, formally described at the Potsdam Institute for Climate Impact Research. The domain is described using Haskell, yielding a domain specific sublanguage of Haskell that can be used for prototyping of implementations.

In this paper we present a generic C++ library that implements a domain-specific language for vulnerability assessment, based on the formal Haskell description. The library rests upon and implements only a few notions, most importantly, that of a monadic system, a crucial part in the vulnerability assessment formalisation. We describe the Haskell description of monadic systems and we show our mapping of the description to generic C++ components. Our library heavily relies on

concepts

, a C++ feature supporting generic programming: a conceptual framework forms the domain-specific type system of our library. By using functions, parametrised types and concepts from our conceptual framework, we represent the combinators and algorithms of the domain. Furthermore, we discuss what makes our library a domain specific language and how our domain-specific library scheme can be used for other domains (concerning language design, software design, and implementation techniques).

Daniel Lincke, Patrik Jansson, Marcin Zalewski, Cezar Ionescu

Domain-Specific Language for HW/SW Co-design for FPGAs

This article describes FSMLanguage, a domain-specific language for HW/SW co-design targeting platform FPGAs. Modern platform FPGAs provide a wealth of configurable logic in addition to embedded processors, distributed RAM blocks, and DSP slices in order to help facilitate building HW/SW co-designed systems. A technical challenge in building such systems is that the practice of designing software and hardware requires different areas of expertise

and

different description domains, i.e. languages and vocabulary. FSMLanguage attempts to unify these domains by defining a way to describe HW/SW co-designed systems in terms of sets of finite-state machines – a concept that is reasonably familiar to both software programmers and hardware designers. FSMLanguage is a domain-specific language for describing the functionality of a finite-state machine in such a way that its implementation can be re-targeted to software or hardware in an efficient manner. The efficiency is achieved by exploiting the resources found within modern platform FPGAs – namely the distributed RAM blocks, soft-core processors, and the ability to construct dedicated communication channels between FSMs in the reconfigurable fabric. The language and its compiler promote uniformity in the description of a HW/SW co-designed system, which allows a system designer to make partitioning and implementation strategy decisions later in the design cycle.

Jason Agron

A Haskell Hosted DSL for Writing Transformation Systems

KURE is a Haskell hosted Domain Specific Language (DSL) for writing transformation systems based on rewrite strategies. When writing transformation systems, a significant amount of engineering effort goes into setting up plumbing to make sure that specific rewrite rules can fire. Systems like Stratego and Strafunski provide most of this plumbing as infrastructure, allowing the DSL user to focus on the rewrite rules. KURE is a strongly typed strategy control language in the tradition of Stratego and Strafunski. It is intended for writing reasonably efficient rewrite systems, makes use of type families to provide a delimited generic mechanism for tree rewriting, and provides support for efficient identity rewrite detection.

Andy Gill

Varying Domain Representations in Hagl

Extending the Expressiveness of a DSL for Experimental Game Theory

Experimental game theory is an increasingly important research tool in many fields, providing insight into strategic behavior through simulation and experimentation on game theoretic models. Unfortunately, despite relying heavily on automation, this approach has not been well supported by tools. Here we present our continuing work on Hagl, a domain-specific language embedded in Haskell, intended to drastically reduce the development time of such experiments and support a highly explorative research style.

In this paper we present a fundamental redesign of the underlying game representation in Hagl. These changes allow us to better utilize domain knowledge by allowing different classes of games to be represented differently, exploiting existing domain representations and algorithms. In particular, we show how this supports analytical extensions to Hagl, and makes strategies for state-based games vastly simpler and more efficient.

Eric Walkingshaw, Martin Erwig

A DSL for Explaining Probabilistic Reasoning

We propose a new focus in language design where languages provide constructs that not only describe the computation of results, but also produce explanations of how and why those results were obtained. We posit that if users are to understand computations produced by a language, that language should provide explanations to the user.

As an example of such an explanation-oriented language we present a domain-specific language for explaining probabilistic reasoning, a domain that is not well understood by non-experts. We show the design of the DSL in several steps. Based on a story-telling metaphor of explanations, we identify generic constructs for building stories out of events, and obtaining explanations by applying stories to specific examples. These generic constructs are then adapted to the particular explanation domain of probabilistic reasoning. Finally, we develop a visual notation for explaining probabilistic reasoning.

Martin Erwig, Eric Walkingshaw

Embedded Probabilistic Programming

Two general techniques for implementing a domain-specific language (DSL) with less overhead are the

finally-tagless

embedding of object programs and the

direct-style

representation of side effects. We use these techniques to build a DSL for

probabilistic programming

, for expressing countable probabilistic models and performing exact inference and importance sampling on them. Our language is embedded as an ordinary OCaml library and represents probability distributions as ordinary OCaml programs. We use delimited continuations to reify probabilistic programs as lazy search trees, which inference algorithms may traverse without imposing any interpretive overhead on deterministic parts of a model. We thus take advantage of the existing OCaml implementation to achieve competitive performance and ease of use. Inference algorithms can easily be embedded in probabilistic programs themselves.

Oleg Kiselyov, Chung-chieh Shan

Operator Language: A Program Generation Framework for Fast Kernels

We present the Operator Language (OL), a framework to automatically generate fast numerical kernels. OL provides the structure to extend the program generation system Spiral beyond the transform domain. Using OL, we show how to automatically generate library functionality for the fast Fourier transform and multiple non-transform kernels, including matrix-matrix multiplication, synthetic aperture radar (SAR), circular convolution, sorting networks, and Viterbi decoding. The control flow of the kernels is data-independent, which allows us to cast their algorithms as operator expressions. Using rewriting systems, a structural architecture model and empirical search, we automatically generate very fast C implementations for state-of-the-art multicore CPUs that rival hand-tuned implementations.

Franz Franchetti, Frédéric de Mesmay, Daniel McFarlin, Markus Püschel

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise