Internal DSLs in Scala

Quite some time ago I read the Programming in Scala and the Programming Scala book and decided to offer a student lab on a Scala-based implementation of a Reversi tournament framework. One part of this framework is a DSL for the configuration of a tournament. So I went on and investigated the Scala techniques that allow for the construction of internal DSLs. Although there is quite some information on the internet and in the books about Scala DSLs here is what I came up with to get my student started.

Compiling Business Process Models for Sensor Networks

Wireless sensor networks are increasingly being used to improve business processes. The behavior of such a process is usually captured in models while its implementation is typically created manually. Besides being expensive, this approach entails deviations between the model and the implementation of a business process, thus rendering it less effective. We aim at closing this gap by automatically generating applications from the model of the process instead. In our approach, software developers provide building blocks that are used by business analysts to model business processes and hereby effectively control their execution on an abstract level. Furthermore, the model editor integrates a compiler and a simulator so that the business analysts can test and debug the modeled processes on the same level of abstraction. Our evaluation results show that the generated code can be executed on resource-constrained sensor nodes consuming only 1% more energy than the hand-written equivalents. However, the benefits of our approach come at the price of 10% more RAM and 44% more flash space consumption on average.

MPS Experience

I have recently worked quite a bit with the language workbench MPS and I think it's about time to note the experiences I have made and the background knowledge I have collected.

Programming Abstractions with Debugging Support for Resource-Constrained Devices

Abstractions are crucial in order to manage complex systems. In pervasive computing, though, common programming abstractions tend to be too expensive for the employed resource-constrained devices. In recent years, the wireless sensor network community has proposed several solutions to this problem. However, little has been done to also support debugging on the level of the abstraction. Instead, a developer is forced to understand the lower-level details in order to find and correct defects. This clearly hampers the development of applications. We aim at advancing the state of the art in programming of resource-constrained devices by introducing debugging support for programming abstractions.

Meta-Debugging Pervasive Computers

As computers get more complex, the task of programming them gets more complex as well. This is especially true for the "Pervasive Computer", which is a massively distributed system consisting of unreliable embedded devices that communicate with each other over lousy wireless links. A common approach to address the programming problem is to offer programming abstractions that hide certain aspects of the complexity from the programmer. While several such abstractions and mappings thereof to low-level target languages have been proposed, there is a glaring lack of debugging support. It is typically impossible to debug at the conceptual level offered by the programming abstractions, instead one has to resort to debugging the generated target code. In this position paper we argue that programming abstractions should be designed in a way that allows debugging at the same conceptual level as programming. We further present requirements for such debugging tools, a taxonomy of programming abstractions and discuss debugging challenges, existing solutions, and potential approaches in each class.

xtc, meta-models and static typing

For my current work I want to implement a C* to C compiler, where * stands for a yet unknown set of extensions and restrictions.

In my opinion, parsing expression grammars are the tool of choice for growing a grammars. Among the existing PEG tools, the Rats! parser generator of the eXTensible C framework offers the most. Besides many handy features there is a complete C grammar and a pretty printer. Ready to take off!

meta level debugging

One of the challenges in meta programming is the ability to debug on the meta level. It is not satisfying to have to step through the generated code in order to figure out what is wrong in the model. And indeed many meta programming toolchains have poor support for proper debugging.

But wait, this problem has in principle actually been solved since ages. When we reduce meta programming to code transformation and realize that a C compiler in that sense is a code transformer this becomes apparent. Almost nobody steps through the assembler code in order to find a bug in the C source. Instead the toolchain has support for so called source level debugging, which is exactly what we want: debugging on the meta level. So it seams advisable to understand the concepts of source level debugging so that we can copy or adapt them to meta programming. That's why I decided to explore the GCC and the GDB together with its graphical frontend DDD which are the tools I am most familiar with.

Rats!

Rats! is an "easily extensible parser generator for C-like languages" written by Robert Grimm. The main idea of Rats! is to exploit the extensibility of PEGs by providing support for parametrizable grammar modules which can use, instantiate, extend and modify each other. Grimm describes version 1.8.2 of Rats! in Better Extensibility through Modular Syntax. More documentation can be found in the Rats! intro. It is part of the the extensive Javadoc of the xtc project, which is the framework project of Rats!. Here comes what I consider the main design principles, features and properties of Rats!.

Language Oriented Programming: The Next Programming Paradigm

As mentioned previously the term language-oriented programming (LOP) today mainly refers to the underlying paradigm of JetBrains's Meta Programming System. This is due to a publication from Sergey Dmitriev entitled Language Oriented Programming: The Next Programming Paradigm. There he proclaims the next technology revolution which leads us from the Stone Age to "a new age of invention and an explosion of new technologies". The paper is very stirringly written but while smiling at this I agree with him in many points. Here is what I consider his main statements.

language-oriented programming

The term "language-oriented programming" (LOP) is these days mainly used by JetBrains and refers to the underlying paradigm of their Meta Programming System. I will blog about that later. For now I want to focus on Martin Ward, because the LOP term was actually coined by him in 1994 with a paper entitled Language Oriented Programming. There he describes what I consider the core idea of meta-programming. And in fact he names many of the benefits, problems, guidelines and other insights that one can find in today's discussions about MDSD. Here is an extraction of these:

OMeta

OMeta is an object-oriented language for pattern matching based on Parsing Expression Grammars (PEG). It makes some valuable extensions to standard PEGs which I want to summarize here. My main source of information is the paper OMeta: an Object-Oriented Language for Pattern Matching by Alessandro Warth and Ian Piumatra.

Stratego/XT

Stratego/XT is the first meta programming system I had a closer look at. The project defines itself as "a language and tool set for program transformation". By program transformation they mean "programming tasks using some form of automatic program generation or transformation, such as code generation from a domain-specific language, aspect weaving, optimization, or specialization of a generic program to a particular context." So Stratego/XT follows a more generalized approach then what MDE needs.

Parsing Expression Grammars

Parsing Expression Grammar (PEG) is a rather new class of grammars for formal languages. The foundations date back to 1973 and come from "Parsing algorithms with backtrack" by Alexander Birman and Jeffrey D. Ullman. But in those days the approach was considered as not being practical because of limited memory resources. In 2002 Bryan Ford revived the topic in his master's thesis Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking by turning the theoretical model into an equivalent, but practical one. Since then the topic has been gaining more and more attraction and additional publications followed. Bryan is collecting the - in his mind - important ones on a PEG homepage.

Model-driven Software Development

It seems that the Software Engineering Podcast is going to keep me busy for a while. For me it is a valuable source of knowledge. I had no idea that I have no idea about software engineering ;-)

Patterns for Fault Tolerant Systems

Today I listened to the Software Engineering Radio podcast with Robert S. Hammer on fault tolerance. The podcast goes along the lines of Robert's book on Patterns for Fault Tolerant Systems.

Patterns

Chippy, a friend of mine, pointed me to the Heise developer SoftwareArchitekTOUR podcast (german), especially to the episode one about the usage of patterns. Chippy is a former colleague and at that time we were discussing a lot about pattern driven software architectures and code generation.

domain specific languages

As I wanted to obtain a deeper understanding on how code generation, DSLs and programming languages in general are related to each other I started to research. I found a lot of publications on DSLs from various authors and companies.

One of those authors is Martin Fowler who is writing a DSL book and has written a great article about what he calls Language Workbenches, a vision of an IDE which inherently operates with and on DSLs.