Design Patterns in Automated Programming


    From the theory of algorithms and automata, the concept of a finite state machine is known , which describes the behavior of an abstract model in terms of a finite set of states and events that initiate transitions between these states. Based on this theory, a fairly widespread paradigm of automaton programming was developed , using which the problem is solved in terms of finite automata - i.e. in terms of states and events. In explicit form, this paradigm is widely used in programming languages, when constructing lexers. However, you can find a huge number of examples of software systems, in a sense, implemented on the basis of this paradigm.

    This article discusses the features of using Visitor / Double Dispatch templates.and State when implementing a system based on a finite state machine. In addition, the article can be considered as a continuation of the series of publications on design patterns on Habrahabr .


    Motivation


    Automated 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 task of programming the behavior of the elevator in a multi-storey building turns into a very formalized model of the machine with the following states: “The elevator goes up”, “The elevator goes down”, “The elevator stands on floor N” and the events coming from the residents of the house: “The Down button is pressed on the N-th floor ”and“ Up button is pressed on the N-th floor ”.

    However, along with the obvious advantages of this approach, there is one small drawback - coding of such a system is a very unpleasant process, accompanied by the use of a large number of branches and transitions.

    To solve this problem, there are OOP and templates Visitor and State.

    Example


    Consider the following problem. Let it be required to design and implement a primitive car radio that supports two operating modes - “radio” and “CD player”. Switching between modes is carried out using the toggle switch on the control panel (see the figure at the beginning of the article). In addition, the radio supports the mechanism for switching 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 nested C branches can be found on Wikipedia . Consider its most significant area.

    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 extend. For example, adding a new state or event seems to be a very time-consuming operation, requiring the modification of a large amount of code. In addition, such a spaghetti code provokes the developer to duplicate certain sections (a situation is possible in which in different states the same event should be processed the same way).

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

    Thus, to add a new type of event or handler to the system, it is enough to implement the required class, the heir of the “Event” or “Handler” classes, 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 existing in the system;



    Of greatest interest in this diagram is the GramophoneHandler interface, which is both part of the Visitor structure (as the visitor itself) and the self-contained State structure (as the state for the Gramophone). Those. we can assume that in the considered example a kind of composition of two patterns is used.

    Implementation


    One of the options for using the system will look like this:

    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 options for external events that come 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 code above, the apply () method has the same implementation in all descendants. This is the main idea of ​​the template - a polymorphic definition of the type of event in the process of code execution. Those. the handle () method will be called on the handler, 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 like this:

    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, 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 pool = new LinkedList();
        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 implementation considered, the methods toogle (), nextTrack () and nextStation () have a 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 causing stream. 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, you should pay attention to the run () method, which implements the Event Loop idiom . In this case, the method contains two nested loops that ensure that the stream falls asleep in the absence of events in the queue. At the same time, adding each new event to the queue (see the dispatch () method) wakes it up.

    Conclusion


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

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

    Also popular now: