CSS 343: Assignment 5: Finite State Machine with Double Dispatch

This assignment is about implementing a finite state machine. There are several ways to implement a state machine, including switch/case statements and table lookup. You shall implement this machine using double dispatch, so carefully read the Notes section below and pay attention.

This gives 12 possible states, but some states are illegal

Door	Timer	Magnetron	Status
closed	unset	off	ok
opened	unset	off	ok
closed	set	off	ok
opened	set	off	ok
closed	running	off	illegal
opened	running	off	illegal
closed	unset	on	illegal
opened	unset	on	illegal!!
closed	set	on	illegal
opened	set	on	illegal!!
closed	running	on	ok
opened	running	on	illegal!!

Several events may be invalid depending on the state: you cannot open the door if it's already open; and the DING! cannot happen if the timer wasn't running. If input contains an invalid event, print "invalid event" followed by the event and the unchanged state.

The simulator will start in the state (closed, unset, off) and read events from standard input (cin) and write the state changes to standard output (cout). Output should be a tab-delimited record showing the event and the new state.

CLOSE_DOOR
DING
DING
SET_TIMER
DING
PRESS_CANCEL
CLOSE_DOOR
CLOSE_DOOR
OPEN_DOOR
CLOSE_DOOR
SET_TIMER
DING
CLOSE_DOOR
SET_TIMER
CLOSE_DOOR
DING
PRESS_CANCEL
DING
DING
OPEN_DOOR

         INITIAL	CLOSED	UNSET	OFF
invalid event
      CLOSE_DOOR	CLOSED	UNSET	OFF
invalid event
            DING	CLOSED	UNSET	OFF
invalid event
            DING	CLOSED	UNSET	OFF
       SET_TIMER	CLOSED	SET	OFF
invalid event
            DING	CLOSED	SET	OFF
    PRESS_CANCEL	CLOSED	UNSET	OFF
invalid event
      CLOSE_DOOR	CLOSED	UNSET	OFF
invalid event
      CLOSE_DOOR	CLOSED	UNSET	OFF
       OPEN_DOOR	OPEN	UNSET	OFF
      CLOSE_DOOR	CLOSED	UNSET	OFF
       SET_TIMER	CLOSED	SET	OFF
invalid event
            DING	CLOSED	SET	OFF
invalid event
      CLOSE_DOOR	CLOSED	SET	OFF
       SET_TIMER	CLOSED	SET	OFF
invalid event
      CLOSE_DOOR	CLOSED	SET	OFF
invalid event
            DING	CLOSED	SET	OFF
    PRESS_CANCEL	CLOSED	UNSET	OFF
invalid event
            DING	CLOSED	UNSET	OFF
invalid event
            DING	CLOSED	UNSET	OFF
       OPEN_DOOR	OPEN	UNSET	OFF

Submit your solution, Run script (which you may beg, borrow, or steal), and test cases to the usual place.

Notes

Dispatch is a term for how the language decides which function to call based on the data type (polymorphism).

C++ uses single dispatch, which means the function call is determined by the object:

#include <iostream>
using namespace std;

class Derived;

class Base {
public:
  virtual void Foo(Base *b, int count);
  virtual void Foo(Derived *d, int count);
};

class Derived : public Base {
public:
  virtual void Foo(Base *b, int count);
  virtual void Foo(Derived *d, int count);
};

void Base::Foo(Base *b, int count) {
  cout << "Called Base::Foo " << this << " with a Base* " << b << "\n";
  if (count == 0) {
    b->Foo(b, 1);
  }
}

void Base::Foo(Derived *d, int count) {
  cout << "Called Base::Foo on " << this << " with a Derived* " << d << "\n";
  if (count == 0) {
    d->Foo(d, 1);
  }
}

void Derived::Foo(Base *b, int count) {
  cout << "Called Derived::Foo on " << this << " with a Base* " << b << "\n";
  if (count == 0) {
    b->Foo(b, 1);
  }
}

void Derived::Foo(Derived *d, int count) {
  cout << "Called Derived::Foo on " << this << " with a Derived* " << d << "\n";
  if (count == 0) {
    d->Foo(d, 1);
  }
}

int main(int argc, char *argv[]) {
  Derived base;
  Derived arg;
  Base* base_ptr = &base;
  Base* arg_ptr = &arg;

  base_ptr->Foo(arg_ptr, 0);

  return 0;
}

Called Derived::Foo on 0x7fffee3d44c0 with a Base* 0x7fffee3d44d0
Called Derived::Foo on 0x7fffee3d44d0 with a Base* 0x7fffee3d44d0

The reason it behaves this way is base_ptr->Foo() invokes the Derived::Foo() version of Foo(), but calls Derived::Foo(Base*) despite the fact that arg_ptr points to a Derived object. Foo in turn calls a virtual function on the arg_ptr, which will still invokes the correct the virtual method of arg_ptr. Try it!

next_state = (current_state, event)->get_next_state();

Undaunted, we are going to do it anyway using the visitor pattern. You will create two abstract base classes State and Event. Each state will be a subclass of State and each event will be a subclass of Event.

It makes sense that there shall be exactly one instance of each state, so you will make the constructor private and have a static method that will return a pointer to the only instance of that class.

Use a map<const string, const Event* to get the event object for a corresponding input word. You do not need to make each event a singleton because you will only create a single instance at the time you create the map.

To implement the double dispatch, each state should have a virtual method get_next_state that takes an Event pointer argument. Since it is virtual, the appropriate function will be called for the state. get_next_state will in turn call event->get_next_state(this).

The magic here is that each event object will have an overloaded function for each class of state:

class SomeEvent : public Event {
public:
  //...
  State* get_next_state(State1* s);
  State* get_next_state(State2* s);
  //...
_;

This assignment is quite short. Once you figure out this double dispatch thing for one or two state transitions, the rest is essentially boilerplate. My solution is only about 230 lines (but I did use evil C preprocessor macro fu to reduce some of the repetition).

Assignment 5: Finite State Automaton with Double Dispatch

Notes