Starting a State Machine External Domain Specific Language (DSL)

I was going to write about the existing state machine I have working. It’s very powerful, has parallel features, and its output was shown in Rethinking State Machines meaning I wouldn’t have to actually create any code, just go through a post-mortem.

Then I changed my mind.

My Lisp version was designed intentionally to be an integral extension of the Lisp technology we use internally. It’s not that it’s a trade secret (how does one make a “trade secret” out of something as well known as state machines?) but rather, it’s not actually comprehensible without an understanding of Lisp and the nature of the Lisp development needs that drove its creation.

What I really want to write about is the process of creation that allows one to make the step from “code that works with data” to “data that is representing code.” That’s the jump, the spark, that enables metaprogramming, where the program code is the data to other program code.

And that process warrants starting at the beginning, which is with the problem.

The problem is my desire to allow direct expression of the basis for responding over time to external events. Think of this as the architect’s perspective instead of a developer’s perspective. No matter the language of the system implementation (or set of languages) I want the system to respond properly to any sequence of events.

I want this to be independent of the code that carries out the intention so that I can work “at a higher abstraction.”

What Does Event Logic In Code Look Like?

Event handling in code, unless one is incredibly well disciplined, actually disperses through the code base.

Basic event handlers are generally either a dispatcher or a “method per event.” When methods per event are used, there is no distinction to the caller that something is an event vs. a simple setter or getter or action. In fact, in most OO languages, events aren’t special. Here’s a basic Python class with a method named b() that does something different based on a history of being called. It could be called an event …

class Demo:
        def __init__(self):
               self.x = 0
        def a(self):
                print("x =", self.x)
        def b(self):
                if self.x == 0:
                        self.x = 1
                        print("turn on")
                        self.x = 0
                        print("turn off")

Each time an instance of Demo has b() invoked it will change state and output a message. This is NOT production code!

It’s already showing signs of mixing abstractions. It shows a common pattern:

  1. Something happens (the event — invoking b())
  2. A decision based on the current known values is made
  3. Actions unique to the current values are carried out
  4. known values are updated to a new set of values

The problem is that the logic of the machine (toggling on and off each time b() is invoked) is “buried” in the details of how the logic is expressed in Python and among the other mechanical parts of the code, such as the declaration of x itself.

What I want to be able to do is precisely capture just the intention of events over time so that I can work only with the interaction and not get bogged down in the implementation details of carrying out the work.

I want, in fact, to be able to define the system’s behavior over time independent of the code that implements the system. I want to be able to simulate the system as well as generate all the code that represents the event/decision/action pattern above.

Obviously, I can’t generate the action code itself, but I can definitely generate the call to a named action.

I don’t want to seek understanding of message responses by deciphering intention from general expressions embedded in general purpose code. I want that intention expressed directly.

So How to Start Such a Thing?

There’s a tendency to start by defining a syntax. That’s not a bad way to start, but I’ve chosen to start it from a different way. I want to describe the vocabulary and model of an agent (or a machine) that consumes events and responds to them with actions.

I have chosen to start with the vocabulary precisely because that is what would drive the choice of syntactic representation later.

Starting with syntax allows one to discover the vocabulary through expressing ideas “in the language being developed.” That’s really easy to do for one person, but it’s hard to explain as you go. Models are a tool for understanding.

So, let’s start by modeling this concept of intentional response to events …

The first diagram I’m starting with is a simple UML class diagram. That’s a useful start to vocabulary. Notice that this diagram is done at the analysis level of detail. This isn’t a diagram of Python code to generate. Rather, it’s a diagram for describing precisely all the elements that will make up the capture of the intentions.

The First Elements

Just describing the problem, shifting to more formal terms, “An agent’s behavior is described by defining the events that it processes, the internal states that it transitions through, and the external actions it carries out.”

So, I’m going to let “the agent” simply be the machine. But, there’s events, states, transitions, and actions in the above sentence.

Let’s diagram!

Starting Vocabulary Elements

Technically, one could define most state machines using just those four. There’s no guard conditions, and of course there’s no concurrent regions or nested states, etc., but the basics are there.

For these to be useful, they must be more than boxes.

EventInput describing something which happened
StateA well-defined (and identified) consistent status in which the machine rests when waiting for events
TransitionThe decision (and operation) of moving from one State to Another as a result of an Event
ActionRequest made to the outside world to perform work
Initial Vocabulary

So, a machine sits in a state until an event arrives which causes a transition to a new state and causes actions to be emitted to the outside world.

This basic set of elements is a start, but it is by no means the end.

For instance, what if I want an event to cause actions but not change the state?

Iterating Because It’s Never Right the First Time

Going with that example, it seems that transitions are in fact optional.

Of course, one can read the formal state machine notation guide (this one from Wikipedia is fine) and see that transitions aren’t optional in their definition, but may be internal or external. The idea of an optional transition and the idea of an internal transition actually seem very similar. However, because this machine is going to take advantage of the research I did in parallel firing, I’m going to update the vocabulary and expand the model to prepare for the richer semantics I want.

I’m going to refine the idea by saying that a reaction might be a transition … and likewise, it might have actions. Neither is mandatory, after all. This results in a few more details

Basic reaction notion

This makes the distinction clear between reactions which change to a new destination state and those which don’t.

To allow parallel reactions, meaning a single event causing more than one reaction (and thus more than one potential set of actions and transitions) it’s far easier to have explicit transition to a new state. Only when there are conflicting transition instances (a set in which there is more than one destination) is there an error in a parallel model.

Of course, this is not showing the event. Let’s add in event, that will lead to the next expanded feature beyond the simple state model.

Having Different Events Treated the Same

Sometimes, you want multiple events to have the same actions. Of course, it’s possible to have many different reactions, and copy the set of actions, but that’s happenstance. It’s not obvious that the intent is for many events to do the same thing.

Why might this be desired? In a parallel machine it’s very reasonable that a set of events share a set of actions. For instance, changing the color, rotation, or position of a graphical widget should trigger some common actions (such as redraw) but also there may be different actions in addition for each of them. That set of common actions is not happenstance. It’s important.

So, some sets of actions are triggered by multiple events by intent. Let’s extend the model to have the notion of a trigger …

A trigger isn’t just a simple event, but it’s actually a qualified event, meaning it’s potentially been approved by a guard condition. As guard conditions haven’t been involved yet, let’s just look at what a trigger might be as a way to bring guards in as well.

Defining Trigger and Drawing in Guard

Guards are optional, but a trigger must have an event. A single event. In most state machines, transitions actually merge the roles of trigger and action mapping. But, here, those are expressly not synonymous.

Here is why:

Reaction with Many Triggers (made up of guarded events)

In this way, the intention that a particular reaction has many causes is expressly indicated.

Reactions and triggers aren’t part of the normal state machine lexicon. Generally, machines have transitions with optional actions.

Let’s bring these together and see what the bigger picture is starting to look like …

Elements So Far

With these terms, it’s possible to express most simple and even moderately complex machines.

What Is Done With the Model?

Well, I’ve got seven boxes with some lines. It’s pretty. The fonts are nice. The lines are generally laid out in a pleasing manner. Ship it!

This is an analysis model. It’s clearly not possible to generate executable code from this. There’s no attributes, no methods, and in fact State doesn’t even have any identity. The analysis model is a starting point. It sets up the next stages.

And the next stages will let us create something that can be run. Not production, not yet. But unless this is exercised in some basic manner, why should it be trusted?

Accomplished So Far

So far, the key elements and the relationships between them that must be known to represent arbitrary machines have been declared. There’s a way to go yet to define them enough.

And the ability to capture certain key ideas is present:

  1. The state a machine is in waiting on an event
  2. The state determines a reaction to one or more triggers, made up of guarded events
  3. A reaction lists an ordered collection of actions which may be shared by triggers
  4. A reaction may (but not must) alter the current state of the machine

Nothing yet implies parallel firing, but the groundwork to not block it is present. In particular, the idea that actions can occur without transitions is important for the parallel model.

Later articles will continue the process!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s