Design patterns in automaton programming

From the theory of algorithms and automata, we know the concept of a finite automaton , which describes the behavior of some abstract model in terms of a finite set of states and events that initiate transitions between these states. On the basis of this theory, the now widely spread paradigm of automaton programming was developed, using which the problem is solved in terms of finite automata — that is, in terms of states and events. Explicitly, this paradigm is widely used in programming languages ​​when building lexers. However, you can find a huge number of examples of software systems, in some sense, implemented on the basis of this paradigm.

The article discusses the features of the use of templates Visitor / Double Dispatch and State in the implementation of the system based on the state machine. In addition, the article can be viewed as a continuation of the cycle of publications on Habrahabr design patterns .

Motivation

Automata programming is a very convenient and flexible tool that allows you to solve the problem in terms close to the concepts of the subject area. For example, the problem of programming elevator behavior in a multi-storey building turns into a very formalized model of an automaton with the following states: “Elevator goes up”, “Elevator goes down”, “Elevator stands on floor N” and events coming from the residents: “Down button pressed on the Nth floor ”and“ Up button is pressed on the Nth floor ”.
')
However, along with the obvious advantages of this approach, there is one small drawback - the coding of such a system is a very unpleasant process, accompanied by the use of a large number of branches and transitions.

OOP and Visitor and State patterns exist to solve this problem.

Example

Consider the following problem. Suppose you want to design and implement a primitive car radio that supports two modes of operation - “radio” and “CD player”. Switching between modes is performed using the toggle switch on the control panel (see the figure at the beginning of the article). In addition, the radio tape recorder supports the switching mechanism of radio stations or tracks (the “Next” button), depending on the set mode.

An excellent example of how this problem is solved on the basis of embedded branches (switch) of the C language can be viewed in Wikipedia . Consider his most significant section.

switch( state ) { case RADIO: switch(event) { case mode: /* Change the state */ state = CD; break; case next: /* Increase the station number */ stationNumber++; break; } break; case CD: switch(event) { case mode: /* Change the state */ state = RADIO; break; case next: /* Go to the next track */ trackNumber++; break; } break; } 

The code from the example is absolutely not readable and hard to expand. For example, adding a new state or event is a very laborious operation that requires modification of a large amount of code. In addition, such a spaghetti code provokes the developer to duplicate some sections (a situation is possible in which the same event should be treated the same in different states).

The Visitor template and its special case Double Dispatch is designed to solve this problem by separating the concepts of state and handler. In this case, the final implementation of the event processing algorithm is selected in the process of execution, based on two factors: the type of event and the type of handler (hence the name “Double Dispatching”).

Thus, to add a new type of event or handler to the system, you just need to implement the required class, the successor of the classes “Event” or “Handler”, respectively.

Class diagram

The main entities of the system:

• Gramophone - radio, which can turn on - enable (), turn off - disable () and receive events - dispatch (event);
• GramophoneEvent - the interface of possible events with one single method - apply (handler) to “apply” the handler to the event;
• GramophoneHandler - a handler interface that contains polymorphic methods (handle) for processing all events in the system;

The GramophoneHandler interface, which is at the same time part of the Visitor design (as the visitor itself) and the self-contained State construction (as a state for the Gramophone), is of the most interest in the considered diagram. Those. we can assume that in the considered example a kind of composition of two templates is used.

Implementation

One of the options for using the system will be as follows:

 public static void main(String args[]) { Gramophone gramophone = new Gramophone(); // it's CD by default gramophone.enable(); // start event loop gramophone.dispatch(new ToogleEvent()); // toogle to radio gramophone.dispatch(new NextEvent()); // next station gramophone.dispatch(new ToogleEvent()); // toogle to CD player gramophone.dispatch(new NextEvent()); // next CD track gramophone.disable(); // stop event loop } 

We describe the possible variants of external events coming to the system.

 /** * Events */ interface GramophoneEvent { void apply(GramophoneHandler handler); } class ToogleEvent implements GramophoneEvent { @Override public void apply(GramophoneHandler handler) { handler.handle(this); } } class NextEvent implements GramophoneEvent { @Override public void apply(GramophoneHandler handler) { handler.handle(this); } } 

In the above code, the apply () method has the same implementation in all descendants. This is the main idea of ​​the template - polymorphic definition of the type of event in the process of code execution. Those. the handler will call the handle () method depending on the type of the event itself (such as the this link).

In languages ​​that do not support polymorphism (for example, in JavaScript), you can encapsulate information about the type of event being processed in the method name. Then in our case the methods will look like handleNext (event) and handleToogle (event) and the calling code is:

 var NextEvent = function() { this.apply = function(handler) { handler.handleNext(this); } } 

The implementation of the possible states of the system is the following code. In our case, the state = handler.

 /** * Visitor */ interface GramophoneHandler { void handle(ToogleEvent event); void handle(NextEvent event); } class RadioHandler implements GramophoneHandler { private Gramophone gramophone; public RadioHandler(Gramophone gramophone) { this.gramophone = gramophone; } @Override public void handle(ToogleEvent event) { gramophone.toogle(new CDHandler(gramophone)); } @Override public void handle(NextEvent event) { gramophone.nextStation(); } } class CDHandler implements GramophoneHandler { private Gramophone gramophone; public CDHandler(Gramophone gramophone) { this.gramophone = gramophone; } @Override public void handle(ToogleEvent event) { gramophone.toogle(new RadioHandler(gramophone)); } @Override public void handle(NextEvent event) { gramophone.nextTrack(); } } 

Finally, we consider the implementation of the main class of the system - radio (Gramophone).

 /** * FSM (Finit-State-Machine) implementation */ class Gramophone implements Runnable { private GramophoneHandler handler = new CDHandler(this); private Queue<GramophoneEvent> pool = new LinkedList<GramophoneEvent>(); private Thread self = new Thread(this); private int track = 0, station = 0; private boolean started = false; public void enable() { started = true; self.start(); } public void disable() { started = false; self.interrupt(); try { self.join(); } catch (InterruptedException ignored) { } } public synchronized void dispatch(GramophoneEvent event) { pool.offer(event); notify(); } @Override public void run() { for (;!pool.isEmpty() || started;) { for (;!pool.isEmpty();) { GramophoneEvent event = pool.poll(); event.apply(handler); } synchronized (this) { try { wait(); } catch (InterruptedException ignored) { } } } } void toogle(GramophoneHandler handler) { this.handler = handler; System.out.println("State changed: " + handler.getClass().getSimpleName()); } void nextTrack() { track++; System.out.println("Track changed: " + track); } void nextStation() { station++; System.out.println("Station changed: " + station); } } 

In the considered implementation, the toogle (), nextTrack () and nextStation () methods have scope only inside the package. This is done in order to protect the system from direct external calls. Moreover, in real conditions it is recommended to additionally check the nature of the calling thread. For example, you can add the following verification code to each of the methods.

 void nextTrack() { if (Thread.currentThread() != self) { throw new RuntimeException(“Illegal thread”); } track++; System.out.println("Track changed: " + track); } 

In addition, attention should be paid to the run () method, which implements the Event Loop idiom. In this case, the method contains two nested loops that ensure that the stream goes to sleep in the absence of events in the queue. At the same time, adding each new event to the queue (see the dispatch () method) awakens it.

Conclusion

The article is not a promotion of the use of OOP and design patterns, but only reveals the features of the use of these tools to solve a specific problem.

The code for this example is available on GitHub . There you can also find examples of other patterns , about which several articles have already been written on Habrahabr .