When you start looking at DSLs there seems to be a big difference between internal and external DSLs, particularly when we look at implementing them. As it turns out they have a lot more in common than you might think.
Architecture of DSL Processing
Perhaps one of the most central things to talk about is the broad structure of how DSL implementations work, what I might call the architecture of a DSL system.
In the usual case, which isn't all the time but is most of the time, I argue for centering your DSL work on a Semantic Model. This is a domain model, much the same as any other model, that captures the core structure and behavior that you want to manipulate with your DSL. In the example of controllers for secret doors that I used early on, this is the state machine model with classes for State, Event, and Command.
The Semantic Model will usually be a part of the domain model of the system you are working with. As such it will be a completely normal model, which can be manipulated in the same way as any object model you might have. (I tend to assume an object model as my default environment is an object-oriented environment, but much of this implementation can be done in a non-OO world.) In the state example, we can populate a state machine by using the machinery of the state model, and then run it to get our state behavior. In a sense it's thus independent of the DSL, although in practice the two are close siblings.
Keeping a Semantic Model that's separate from the DSL has several advantages. The primary benefit is that you can think about the semantics of this domain without getting tangled up in the DSL syntax or parser. If you're using a DSL at all, it's usually because you're representing something pretty complex, for otherwise you wouldn't be using a DSL. Since you're representing something quite complex, that's enough to deserve it's own model.
In particular this allows you to test the Semantic Model by creating objects in the model and manipulating them directly. I can create a bunch of states and transitions, and test to see if the events and commands run without having to deal with parsing at all. If there's problems in how the state machine executes I can isolate the problem in the model without having to understand how the parsing works.
An explicit Semantic Model allows you to support multiple DSLs to populate it. You might start with a simple internal DSL, and then later add an external DSL as a later version that's easier to read. Since you have existing scripts and existing users you might want to keep the existing internal DSL and support both. Since both DSLs can parse into the same Semantic Model this isn't difficult. It also helps to avoid any duplication between the languages.
More to the point, having a separate Semantic Model allows you to evolve the model and language separately. If I want to change the model, I can explore that without changing the DSL, adding the necessary constructs to the DSL once I have it working. Or I can experiment with new syntaxes for the DSL and just verify that they create the same objects in the model. I can compare two syntaxes by comparing how they populate the Semantic Model.
In many ways this separation of Semantic Model and DSL syntax mirrors the separation of domain model and presentation that we see in designing enterprise software. Indeed on a hot day I think of a DSL as another form of user interface.
The comparison between DSLs and presentations also suggests limitations. The DSL and the Semantic Model are still connected. If I add new constructs to the DSL I need to ensure they are supported in the Semantic Model, which often means modifying the two at the same time. However the separation does mean I can think about semantic issues separately to parsing issues, which simplifies the task.
The difference between internal and external DSL lies in the parsing step, both in what is parsed and how the parsing is done. Both styles of DSL will produce the same kinds of Semantic Model, and as I implied earlier there's no reason why you can't have a single Semantic Model populated by both internal and external DSLs.
With an external DSL there is a very clear separation between the DSL scripts, the parser, and the Semantic Model. The DSL scripts are written in a clearly separate language, the parser then reads these scripts and populates the Semantic Model. With an internal DSL it's much easier for things to get mixed up. I advocate having an explicit layer of Expression Builders whose job is to provide the necessary fluent interfaces to act as the language. DSL scripts run by invoking methods on an Expression Builder which then populates the Semantic Model. Thus in an internal DSL, parsing the DSL scripts are done by a combination of the host language parser and the Expression Builders.
Once we have a Semantic Model we then need to make the model do what we want. In the state machine example, this task is to control the security system. There's two broad ways we can do this. The simplest, and usually the best, is just to execute the Semantic Model itself. The Semantic Model is code and as such can run and do all it needs to.
Another option is to use code generation. Code generation means that we generate code which is separately compiled and run. In some circles, code generation is seen as an essential part of DSLs. I've seen talks about code generation that make the assumption that to do any DSL work requires you to generate code. In the rare event that I see someone talking or writing about parser generators, they inevitably talk about generating code. Yet DSLs have no inherent need for code generation. A lot time the best thing to do is just to execute the Semantic Model.
The strongest case for where you do need code generation is where there is a difference between where you want to run the model and where you want to parse the DSL. A good example of this is where you want to execute code in an environment has limited language choices, such as executing on limited hardware or inside a relational database. You don't want to write a parser in your toaster or in SQL, so the parser and Semantic Model are done in a more suitable language and you generate C or SQL. A related case is where you have library dependencies in your parser that you don't want in the production environment. This situation is particularly common if you are using a complex tool for your DSL, which is why Language Workbenches tend to do code generation.
In these situation it's still useful to have a Semantic Model in your parsing environment that can run without generating code. Running the Semantic Model allows you to experiment with the execution of the DSL without having to simultaneously understand how the code generation is working. You can also test parsing and semantics without generating code, which will often help running tests more quickly and in isolating problems.
But the most important thing to remember about code generation is that it's an optional part of the DSL landscape. It's one of those things that is absolutely essential if you need it, yet most of the time you don't. I think of code generators as like snowshoes. If I'm hiking in winter over deep snow I really have to have them, but I'd never carry them on a summer's day.
With code generation we see another benefit to using a Semantic Model, it decouples the code generators from the parser. I can write a code generator without having to understand anything about the parsing process, and test it independently too. This makes it easier to support multiple code-generation targets should I need them.
The workings of a parser
So the differences between internal and external DSLs lie entirely in parsing, and indeed there are many differences in detail between the two. But even here there are a lot of similarities.
One of the most important similarities is that parsing is a strongly hierarchical operation. When we parse text, we to arrange the chunks into a tree structure. Consider the simple structure of a list of events from the state machine. In the external syntax it looked something like this:
events doorClosed D1CL drawOpened D2OP end
We can look at this composite structure: an event list containing a list of events, with each event having a name and a code.
We can take a similar view in the internal DSL
event :doorClosed "D1CL" event :drawOpened "D2OP"
Here there's no explicit notion of an overall list, but each event is still a hierarchy of an event containing a name symbol and a code string.
Whenever you look at a script like this, you can imagine that script represented as a hierarchy in this way, such a hierarchy is called a syntax tree (or parse tree). Any script can be turned into many potential syntax trees, it just depends on how you decide to break it down. A syntax tree is a much more useful representation of the script than the words, we can manipulate it in many ways by walking the tree.
If we are using a Semantic Model, we take the syntax tree and translate it into the Semantic Model. If you read material in the language community, you'll often see more emphasis to the syntax tree - people execute the syntax tree directly or generate code off the syntax tree. Effectively people can use the syntax tree as a semantic model. Most of the time I would not do that because the syntax tree is very tied to the syntax of the DSL script and thus couples the processing of the DSL to the syntax of the DSL.
I've been talking about the syntax tree as if it's a tangible data structure in your system, like the XML DOM. Sometimes it is, but often it isn't. A lot of the time the syntax tree is formed on the call stack and processed as we walk it. As a result you never see the whole tree, just the branch that you are currently processing. Despite this it's usually very helpful to think about a ghostly syntax tree hiding in the shadows of the call stack. For an internal DSL, this tree is formed by arguments in a function call (Nested Function), and by nested objects (Method Chaining). Sometimes you don't see a strong hierarchy and you have to simulate it (Function Sequence with the hierarchy simulated with Context Variables). But it's still a useful mental tool. Using an external DSL leads to a more explicit syntax tree, indeed sometimes you actually do create a full-blown syntax tree data structure (Tree Construction). But even external DSLs are commonly processed with the syntax tree forming and pruning continuously on the call stack.
Grammars and Syntax
When you work with languages syntax, an important tool is a
grammar. A grammar is a set of rules which describe how a
stream of text is turned into a syntax tree. Most programmers have
come across grammars at some point in their lives as they usually used
to describe the programming languages they work with. Grammars consist
of a list of production rules, where each rule has term and a
statement of how it gets broken down. So we might have a grammar for
an addition statement that would look like additionStatement :=
number '+' number. This would tell us that if we saw the
language sentence 5 + 3 the parser can recognize that as
an addition statement. Rules mention each other, so we would also have
a rule for number that tells us how to recognize a legal number. We
can compose a grammar for a language with these rules.
It's important to realize that a language can have multiple grammars that define it. There is no such thing as the grammar for a language. A grammar defines the structure of the syntax tree that's generated for the language, and we can recognize many tree structures for a particular piece of language text. A grammar just defines one form of syntax tree, the actual grammar and syntax tree you'll choose depends on many factors including the features of the grammar language you're working with, and how you want to process the syntax tree.
The grammar also only defines the syntax of a language - how it gets represented in the syntax tree. It doesn't tell us anything about the semantics - what an expression means. Depending on our context "5 + 3" could mean "8" or "53", the syntax is the same but the semantics are different. With a Semantic Model the definition of the semantics boils down to how we populate the Semantic Model from the syntax tree and what we do with the Semantic Model. In particular we can say that if two expressions produce the same structure in the Semantic Model then they have the same semantics, even if their syntax is different.
If you're using an external DSL, particularly if you use Syntax Directed Translation you're likely to make explicit use of a grammar in building a parser. With internal DSLs, there won't be an explicit grammar, but it's still useful to think in terms of a grammar for your DSL. The grammar does help you choose which of various internal DSL patterns you might use.
One of the things that makes talking about a grammar tricky for internal DSLs is that there are two parses and thus two grammars involved. The first parse is the parse of the host language itself, which obviously depends on the host grammar. This parse creates the executable instructions for the host language. As the DSL part of that host language executes it will create the syntax tree of the DSL. It's only in this section that the notional DSL grammar comes into play.
Parsing Data
As the parse executes, it needs to store various bits of data about the parse. This data could be a complete syntax tree, but a lot of the time that isn't the case - and even when it is there's other data that usually needs to be stored to make the parse work well.
The parse is inherently a tree walk, and whenever you are processing part of a DSL script you'll have some information about the context within the branch of the syntax tree that you're processing. However often you need information that's outside that branch. Again let's take a fragment of a state machine example"
commands
unlockDoor D1UL
end
state idle
actions {unlockDoor}
end
Here we see a common situation of a command defined in one part of the language and referred to somewhere else. When the command is referred to as part of the state's actions, we're on a different branch of the syntax tree to where the command was defined. If the only representation of the syntax tree is on the call stack, then the command definition has disappeared by now. As a result we need to both store the command object for later use, and be able to resolve the reference in the action clause.
In order to do this we use a Symbol Table, which is essentially a dictionary whose key is the identifier "unlockDoor" and whose value is an object that represents the command in our parse. The value may be the semantic model object for command, or it could be an intermediate object that's local to the syntax tree. Either way a Symbol Table is a crucial tool for making the cross references. If you actually do create a full syntax tree during the parse, you can theoretically dispense with a Symbol Table, although usually it's still a useful construct to make it easier to stitch things together.
As the parse continues, you'll need to keep the results of the parse. Sometimes all the results can be weaved into a Symbol Table, sometimes a lot of information can be kept on the call stack, sometimes you'll need additional data structures in the parser. In all of these cases the most obvious thing to do is to create Semantic Model objects as your results, but often you'll need to create intermediate objects, such as Construction Builders, because you can't create Semantic Model objects till later in the parse. Indeed sometimes you might defer all creation of Semantic Model objects till you've processed all the DSL script. In this case the parse has distinct phases, the first one reading through the DSL script and creating intermediate parsing data and the second phase running through that intermediate data and populating the Semantic Model. The choice between how much to do during the processing text and what to do afterwards usually depends on how the Semantic Model needs to be populated. Often design decision which are the right ones to make the Semantic Model do complicate parsing. The classic example of this is immutable fields in the Semantic Model. If Semantic Model objects have fields that are immutable while the model is running, this can make it harder to create them during the parse as you often gather data during the parse gradually and don't get all the immutable data together. In this kind of case I'd rather complicate the parser a bit, by using a Construction Builder rather than make the Semantic Model harder to understand.
As you parse an expression, the way you process that expression often depends on the context that you are working in. Consider this text:
state idle
actions {unlockDoor}
end
state unlockedPanel
actions {lockDoor}
end
When we process actions {lockDoor} it's important to
know that this is in the context of the unlockedPanel state and not the idle
state. Often this context is supplied by the way the parser builds and
walks the parse tree, but there are many cases where it's difficult to
do that. If we can't find the context by examining the parse tree,
then a good way to deal with it is by holding the context in a
Context Variable. Essentially we have a
currentState variable in our code that we set when we process the
state idle expression. This Context Variable, like a Symbol Table can
hold a Semantic Model object or some
intermediate object.
Although a Context Variable is often a straightforward tool to use, in general I prefer to avoid them as much as possible. The parsing code is easier to follow if you can read it without having to mentally juggle Context Variables, just as lots of mutable variables make procedural code more complicated to follow. Certainly there are times when you can't avoid using a Context Variable, but I tend to see them as a smell to be avoided as much as possible.
Testing with DSLs
Over the last couple of decades I've become quite a bore on the subject of testing. I'm a big fan of Test Driven Development and similar techniques that put testing into the forefront of programming. As a result I can't think about DSLs without thinking about testing them.
With DSLs I can break testing down into three separate areas: testing the Semantic Model, testing the parser, and testing the scripts.
Testing the Semantic Model
The first area I think about is testing the Semantic Model. The tests here are about ensuring that the Semantic Model behaves the way I expect it to - as I execute it the right outputs happen depending on what I place in the model. This is standard testing practice just as you would test any framework of objects. For this testing I don't really need the DSL at all - I can populate the model using the basic interface of the model itself. This is good as it allows me to test the model independently of the DSL and the parser.
Let me illustrate this with the secret panel controller. Here my Semantic Model is the state machine. I can test the Semantic Model by populating it with the basic framework code I used at the beginning of the introduction, this doesn't require any DSL.
@Test
public void eventCausesTransition() {
State idle = new State("idle");
StateMachine machine = new StateMachine(idle);
Event cause = new Event("cause", "EV01");
State target = new State("target");
idle.addTransition(cause, target);
Controller controller = new Controller(machine, new CommandChannel());
controller.handle("EV01");
assertEquals(target, controller.getCurrentState());
}
The above code brings out the point - I can simply test the Semantic Model in isolation. However I should point out that real test code for this case will be more involved and should be better factored.
Here's a couple of ways to better factor this kind of code. First off we can make a bunch of small state machines which provide minimal fixtures for testing various features of the Semantic Model. To test that an event triggers a transition, all we need is a simple state machine with and idle state and two outbound transitions to separate states.
class TransitionTester...
State idle, a, b;
Event trigger_a, trigger_b, unknown;
protected StateMachine createMachine() {
idle = new State("idle");
StateMachine result = new StateMachine(idle);
trigger_a = new Event("trigger_a", "TRGA");
trigger_b = new Event("trigger_b", "TRGB");
unknown = new Event("Unknown", "UNKN");
a = new State("a");
idle.addTransition(trigger_a, a);
idle.addTransition(trigger_b, b);
return result;
}
When we want to test commands, however, we might just want a smaller machine with just a single state off our idle state.
class CommandTester...
Command commenceEarthquake = new Command("Commence Earthquake", "EQST");
State idle = new State("idle");
State second = new State("second");
Event trigger = new Event("trigger", "TGGR");
protected StateMachine createMachine() {
second.addCommand(commenceEarthquake);
idle.addTransition(trigger, second);
return new StateMachine(idle);
}
These different test fixtures can be run and tests probed in similar ways. I can make this easier by giving them a common superclass. The first thing this class provides is the ability to set up some common fixture: in this initializing a controller and command channel with the supplied state machine.
class AbstractStateTester...
protected CommandChannel commandChannel = new CommandChannel();
protected StateMachine machine;
protected Controller controller;
@Before
public void setup() {
machine = createMachine();
controller = new Controller(machine, commandChannel);
}
abstract protected StateMachine createMachine();
I can now write tests by firing events at the controller and checking the state.
class TransitionTester...
@Test
public void event_causes_transition() {
fire(trigger_a);
assertCurrentState(a);
}
@Test
public void event_without_transition_is_ignored() {
fire(unknown);
assertCurrentState(idle);
}
class AbstractStateTester...
//-------- Utility methods --------------------------
protected void fire(Event e) {
controller.handle(e.getCode());
}
//------- Custom asserts --------------------------
protected void assertCurrentState(State s) {
assertEquals(s, controller.getCurrentState());
}
The superclass provides Test Utility Methods and Custom Assertions to make the tests easier to read.
An alternative approach for testing the Semantic Model is to populate a larger model that demonstrates many features of the model, and run multiple tests on that. In this case I can use Mrs H's controller as a test fixture.
class ModelTest... private Event doorClosed, drawOpened, lightOn, doorOpened, panelClosed; private State activeState, waitingForLightState, unlockedPanelState, idle, waitingForDrawState; private Command unlockPanelCmd, lockDoorCmd, lockPanelCmd, unlockDoorCmd; private CommandChannel channel = new CommandChannel(); private Controller con; private StateMachine machine;
@Before
public void setup() {
doorClosed = new Event("doorClosed", "D1CL");
drawOpened = new Event("drawOpened", "D2OP");
lightOn = new Event("lightOn", "L1ON");
doorOpened = new Event("doorOpened", "D1OP");
panelClosed = new Event("panelClosed", "PNCL");
unlockPanelCmd = new Command("unlockPanel", "PNUL");
lockPanelCmd = new Command("lockPanel", "PNLK");
lockDoorCmd = new Command("lockDoor", "D1LK");
unlockDoorCmd = new Command("unlockDoor", "D1UL");
idle = new State("idle");
activeState = new State("active");
waitingForLightState = new State("waitingForLight");
waitingForDrawState = new State("waitingForDraw");
unlockedPanelState = new State("unlockedPanel");
machine = new StateMachine(idle);
idle.addTransition(doorClosed, activeState);
idle.addCommand(unlockDoorCmd);
idle.addCommand(lockPanelCmd);
activeState.addTransition(drawOpened, waitingForLightState);
activeState.addTransition(lightOn, waitingForDrawState);
waitingForLightState.addTransition(lightOn, unlockedPanelState);
waitingForDrawState.addTransition(drawOpened, unlockedPanelState);
unlockedPanelState.addCommand(unlockPanelCmd);
unlockedPanelState.addCommand(lockDoorCmd);
unlockedPanelState.addTransition(panelClosed, idle);
machine.addResetEvents(doorOpened);
con = new Controller(machine, channel);
channel.clearHistory();
}
@Test
public void event_causes_state_change() {
fire(doorClosed);
assertCurrentState(activeState);
}
@Test
public void ignore_event_if_no_transition() {
fire(drawOpened);
assertCurrentState(idle);
}
In this case I again populated the Semantic Model using its own push-button interface. As the test fixtures get more complex, however, I can simplify the test code by using the DSL to create fixtures. I can do this if I have tests for the parser.
Testing the Parser
When we're using a Semantic Model the job of the parser is to populate the Semantic Model. So our testing of the parser is about creating small fragments of DSL and ensuring that these create the right structures in the Semantic Model.
@Test
public void loads_states_with_transition() {
String code =
"events trigger TGGR end " +
"state idle " +
"trigger => target " +
"end " +
"state target end ";
StateMachine actual = StateMachineLoader.loadString(code);
State idle = actual.getState("idle");
State target = actual.getState("target");
assertTrue(idle.hasTransition("TGGR"));
assertEquals(idle.targetState("TGGR"), target);
}
Poking around in the Semantic Model like this is rather awkward, and may result in breaking encapsulation on the the objects in the Semantic Model. So another way to test the output of the parser is to define methods to compare Semantic Models and use those.
@Test
public void loads_states_with_transition_using_compare() {
String code =
"events trigger TGGR end " +
"state idle " +
"trigger => target " +
"end " +
"state target end ";
StateMachine actual = StateMachineLoader.loadString(code);
State idle = new State("idle");
State target = new State("target");
Event trigger = new Event("trigger", "TGGR");
idle.addTransition(trigger, target);
StateMachine expected = new StateMachine(idle);
assertEquivalentMachines(expected, actual);
}
Checking a complex structure for equivalence is rather more involved than the regular notions of equality. We also want rather more information than just a boolean answer since we want some information on what's different. As a result I have a more complicated comparison that uses a Notification[TBD: Consider adding Notification pattern to this book].
class StateMachine...
public Notification probeEquivalence(StateMachine other) {
Notification result = new Notification();
probeEquivalence(other, result);
return result;
}
private void probeEquivalence(StateMachine other, Notification note) {
for (State s : getStates()) {
State otherState = other.getState(s.getName());
if (null == otherState) note.error("missing state: %s", s.getName()) ;
else s.probeEquivalence(otherState, note);
}
for (State s : other.getStates())
if (null == getState(s.getName())) note.error("extra state: %s", s.getName());
}
class State...
void probeEquivalence(State other, Notification note) {
assert name.equals(other.name);
probeEquivalentTransitions(other, note);
probeEquivalentActions(other, note);
}
private void probeEquivalentActions(State other, Notification note) {
if (!commands.equals(other.commands))
note.error("%s has different commands", name);
}
private void probeEquivalentTransitions(State other, Notification note) {
for (Map.Entry<Event, State> e : transitions.entrySet())
probeEquivalentTransition(e.getKey(), e.getValue(), other, note);
for (Map.Entry<Event, State> e : other.transitions.entrySet())
if(!this.transitions.containsKey(e.getKey()))
note.error("%s has extra transition with %s", name, e.getKey());
}
private void probeEquivalentTransition(Event myEvent, State myTarget, State otherState, Notification note) {
if (otherState.transitions.containsKey(myEvent)) {
State otherTarget = otherState.transitions.get(myEvent);
if (!myTarget.getName().equals(otherTarget.getName()))
note.error("%s transitions to %s instead of %s", myEvent, otherTarget.getName(), myTarget.getName());
} else {
note.error("%s has missing transition for %s", name, myEvent);
}
}
The approach of this probe is to walk through the objects in the Semantic Model and record any differences in a Notification. This way I find all differences rather than stopping with the first one. My assertion then just checks to see if the Notification has any errors.
class AntlrLoaderTest...
private void assertEquivalentMachines(StateMachine left, StateMachine right) {
assertNotificationOk(left.probeEquivalence(right));
assertNotificationOk(right.probeEquivalence(left));
}
private void assertNotificationOk(Notification n) {
assertTrue(n.report(), n.isOk());
}
class Notification...
public boolean isOk() {return errors.isEmpty();}
You may think I'm being paranoid by doing the equivalence assertion in both directions, but usually the code is out to get me.
Testing the Scripts
Testing the Semantic Model and the parser handles unit testing for the generic code. However the DSL scripts are also code, and thus we should consider testing them. I do hear arguments along the lines of the DSL scripts are too simple and obvious to be worth testing, but I'm naturally suspicious of that. I see testing as a double-check mechanism. When we write code and tests we are specifying the same behavior using too different mechanisms, one involving abstractions (the code) and the other using examples (the tests). For anything of lasting value we should always double check.
The details of script tests very much depends on what it is you're testing. The general approach is to provide a test environment that allows you to create text fixtures, run DSL scripts and compare results. It's usually some effort to prepare such an environment, but just because a DSL is easy to read doesn't mean people won't make mistakes. If you don't provide a test environment and thus don't have a double check mechanism, you greatly increase the risk of errors in the DSL scripts.
Script tests also act as integration tests, since any errors in the parser or Semantic Model should cause them to fail. As a result it's worth sampling the DSL scripts to use a few for this purpose.
[TBD: Discuss how to test this in the State Machine Computational Network when I write that up.]