In this post, our goal is to create a domain-specific language (DSL) for the state machine domain that we introduced in the last post. We already had a working example of a state machine (a totally realistic model of a baby), which suffered from being rather verbose and far from cleanly expressing our target domain.
To actually have a language, we need some kind of a syntax for it. In our case, we already have a nice textual representation of the domain, which is the ASCII table format I used to describe the different baby states (funny coincidence how that worked out so comfortably well). This format solves the repetitiveness issues and is definitely close to our domain.
To simplify the thought process, let’s have a smaller example of a state machine:
|| a | b | ============ 1 || b | a | 2 || b | b |
This time, we have only two states (a, b) and two inputs (1, 2), and we do not use the stack for anything. Simple enough for our purposes here.
Now, Joy’s syntax, or lack thereof, makes it possible to write this thing as is by just quoting it all into a list:
[ || a | b | ============ 1 || b | a | 2 || b | b | ]
Or how Joy really sees it:
1
| |
This works because quotes are not checked for invalid identifiers; they only need to contain valid Joy syntax, and that’s exactly what we have in our table (which is yet another amazing coincidence). Next, we can try to parse the contents of the quote and convert it into something that is runnable with our state machine runner. But that’s not a direction I would actually want to pursue. By doing this, we are not taking any advantage of Joy itself for language representation – we are just using it as a fancy tokenizer for what is essentially plain text. And that’s practically an external DSL. I find external DSLs much less interesting than embedded DSLs, as they give us less chances to flex our language’s syntax muscles. Let us come up with a proper embedded DSL.
As a first step in this direction, we can remove all the fluff from the table above, and convert it into a plain list of lists:
1
| |
This is a valid representation of the data from before, but the grouping is wrong. In the code we wrote in the previous post, each state had all its possible inputs grouped around it. What we have here is the opposite. By transposing the table, we get the right grouping:
1
| |
Which corresponds to the transposed table:
|| 1 | 2 | ============ a || b | b | b || a | b |
It’s not that complicated to write a transposing function to achieve this transformation, but for simplicity, let us just work with transposed tables to begin with.
Having an abstract way to represent the required data is quite a common thing when creating a DSL. From here, we need to proceed in two directions. The first one is creating some nice syntax for constructing the data. The second is converting the data into something executable.
Before we can proceed with either of those, we still have some aspects of our domain unattended: we don’t have a way to do anything on the stack. We’ll take the following approach: each cell is going to be implicitly executed on the current stack, so everything we leave there stays on the stack. The last thing on the stack is going to be the next state. We can embellish our simple state machine with some stack actions like so:
|| 1 | 2 | ==================== a || 0 b | pop b | b || pop a | 0 b |
Now, in the a state when the input is 1, it pushes 0 on the stack and moves to b, and when the input is 2, it pops a value from the stack and also moves to b. The b state acts analogously. Converting this into our list representation gives us:
1
| |
To group all of its action into a single piece of data, each cell has to be quoted now.
Because we are dealing with a very simple data structure, creating a palatable syntax for it shouldn’t be too complicated, so we’ll get to it first. Without further ado, here’s the syntax:
@ 1 | 2 |
[a] : [ 0 b ]|[ pop b ]|
[b] : [ pop a ]|[ 0 b ]|
(the code for the DSL can be found in state_machine_table_dsl.joy)
All of it is completely valid Joy syntax and creates the following list:
1
| |
Oops, our lists seem to be inverted. No biggie, this is as good a data representation as any other. It just happens to be that it’s easier to construct things in reverse when dealing with cons lists.
Let’s delve into our syntax a bit further. The @ pushes our initial value onto the stack, which is a [[]]; all further actions will be adding stuff to this value. The | symbol prepends the current thing on the stack to our nested list, e.g.:
1 2 | |
The names of the states are now quoted; otherwise we won’t be able to put them on the stack as we are doing while constructing the table (once they are on the stack, they get evaluated, but the state names don’t have any meaning, so that just gets us an error, possibly a silent one).
The : starts a new row; it converts the preceding symbol into a string and adds it to a new list in our nested list:
1
| |
Converting the symbol into a string makes it a bit simpler to work with it further down the road. Notice that the references to the state names in the cells remain as is; we’ll have to deal with those later.
And that’s all there is to it. This syntax is close enough to the ASCII table format we started with, and contains very little noise. This was the easy bit; now we actually have to turn this into something we can execute.
I’ll spare you the gory details of the transformation and focus on the more interesting bits. Having obtained our abstract representation, we convert it, using some not too complicated list manipulation code (the beauty of homoiconicity…), into the following construct:
1 2 3 4 5 6 7 8 9 10 11 12 | |
We can see a strong semblance to the sort of code we were writing to explicitly define a state machine. There are a couple of things to note here. First, we don’t have any top-level definitions for the states, everything is contained in a single list. This means that the a and b references in the code don’t have any actual meaning, so we are yet to obtain properly executable code. The second thing to note is what happened to the code inside the cells. Each piece of code got placed in its appropriate execution branch wrapped around in some mysterious incantations. This warrants a closer look.
The last problem that we had with manually constructing state machines is the lack of transparency when dealing with the stack; each function required special wrapping to be run against the stack. The against-stack function takes care of this problem. It uses the infra combinator (see manual) to run our code against the list we are currently using as our stack. So the code we are executing can treat our artificial stack as a regular Joy stack, hence no special wrapping for the functions that we use in the cells is required. In essence, we’ve managed to embed Joy itself back into our embedded DSL; that’s kind of mind-bendy. When execution is done, against-stack takes the result and splits out the next state from the rest of the stack, producing both a new state and a new stack.
The line [cur-stack [0 b] against-stack] i can be read as “take the current value of the stack, the code 0 b and run the code against the stack”; the i actually forces this code to be executed when we reach the branch.
To make our list executable, we need to somehow take care of the undefined state references. The first guess would be to just expand each reference with its explicit form as it is presented in the code above. The problem with this approach is that the states are mutually recursive. So the replacement process will go into an infinite loop. We didn’t have this problem when manually defining the states, because we used top-level definitions, which can be mutually recursive. But that’s not possible in this case, as we can’t dynamically add top-level definitions. What we need to do is to somehow delay the evaluation of these references until they are actually needed.
For this purpose, we are going to introduce an execution environment. The environment will contain a map where every entry is a state name with an unexpanded definition of that state, and so every reference to a state can be replaced by a call into the map, fetching the right state. For this to actually work, we first need to do this replacement, yielding:
1 2 3 4 5 6 7 8 9 10 11 12 | |
The line "b" states-map swap find-in-map replaced the state b, which is just a fancy way of saying “look for the name "b" in the states-map variable”. The states-map variable will be our environment when we execute the state machine, containing the states as they are presented above for its entries.
To run our state machine, we’ll write a function called run-state-from-stack-with-env, similar to the run-state-from-stack we defined before. The main difference is that we now have an additional argument for our environment. To achieve the use of the environment when actually executing the state transition function, we use the splice-from-map function that we developed in the metaprogramming post. It performs the appropriate “find and replace” every time we stumble upon a states-map reference.
That, essentially, concludes everything we need to define and run our state machines. But there’s a minor wrinkle about the process as described above, and that’s that in the current scheme of finding and replacing state references we may miss any such references that are hidden in other function definitions. For example, if our state machine was:
1 2 3 4 5 | |
We’d miss the a reference hidden inside func. To avoid this issue, when constructing the state machine code, we also recursively expand any user-defined symbols with the expand-user-syms function. This way, all state references are exposed when we do the “find and replace” routine described above.
Okay, now we are ready to rewrite the baby state machine (the full code is in baby_state_machine_dsl.joy):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
Apart from being transposed, this closely follows the table definition of the table state machine, so we don’t have the redundancies in the description that we had in the explicit version. As you can see, the stack manipulation functions do not require any special wrapping. Hence we’ve covered all of our pain points from before.
Because DSLs are all about their visual flare, we can add a bit of garnish to this definition. We define the following no-ops, which can be used as delimiters:
1 2 | |
This yields our final version of the state machine:
1 2 3 4 5 6 7 | |
Which I find to be slightly more visually pleasing.
We can run the state machine as before:
1 2 | |
I think this can be declared a success, and with an elated feeling of self-satisfaction we can call it quits now.
This concludes our excursion into the world of DSLs. As we experienced firsthand, developing a DSL is a lot like developing a real language. We have the actual syntax, we “compile” it into an intermediate representation, then “compile” it further down into executable code. And we even ran it with a non-trivial environment. If that’s not your definition of “fun”, I don’t know what is.
Using Joy for this purpose made the experience very lightweight, the whole definition of the DSL is about 100 lines of code. Minimal syntax and the corresponding homoiconicity make a language very amenable to embedding DSLs into it. I think our little exercise definitely demonstrates this point.
This also concludes my excursion into Joy, in the next post, I’ll sum up the experience.