Adam Richardson's Site

A Simple Finite State Machine with CLOS

Table of Contents

State Design Pattern

While reading the chapter on the State design pattern in Game Programming Patterns (Robert Nystrom) I was inspired to try to implement it in Common Lisp.

The State design pattern describes an object that changes its behavior based on some input.

While I was working on the text adventure game perplexer I definitely wanted to find a more succinct way of organizing rooms (states) and edges. This pattern seems to offer a very clean way to encapsulate all the logic needed for a given state.

Common Lisp Object System (CLOS)

I was introduced to CLOS in one of the awesome Kaveh808 Common Lisp lessons. My initial impressions were quite favorable as it reminded me of Objective-C. It seems like the reason for this resemblance is because both Objective-C and CLOS were influenced by Smalltalk.

To get a more complete understanding of CLOS I read the Object Reorientation chapters in the highly informative Practical Common Lisp (Peter Seibel).

Simple Finite State Machine

Before attempting to implement a the State pattern in lisp I wanted to design a simple finite state machine that I could test. I came up with the following states and transitions. The interface for the state machine will be a simple prompt asking the user for a number.

  • The initial state is alpha
  • The input for the state machine is integers
  • alpha will transition to beta when it receives an even integer
  • alpha will transition to gamma when it receives an odd integer
  • beta will transition to alpha when it receives three consecutive odd integers
  • beta will transition to gamma when it receives two consecutive even integers
  • gamma will transition to beta when it receives a negative integer
  • gamma will transition to alpha when it receives a multiple of 7

Diagramming the FSM

I wanted to use the opportunity to brush up on Graphviz and model the FSM. With a little trial and error, I think I got a pretty good diagram. The black node indicates that the node is the initial node.

fsm_diagram.png

Below is the dot file that made the above diagram. 

digraph fsm {
    rankdir="LR";
    node [fontname="Hack",
          fontsize="10",
          shape="circle"];
    alpha [style="filled",
           fontname="Hack Bold"
           fillcolor="black",
           fontcolor="white"];
    beta;
    gamma;
    edge [fontname="Hack",
          fontsize="10"];
    alpha->beta [label="even"];
    alpha->gamma [label="odd"];
    beta->alpha [label="3 odds"];
    beta->gamma [label="2 evens"];
    gamma->alpha [label="multiple of 7"];
    gamma->beta [label="negative value"];
}

Generic Functions and Methods

The first difference I noticed when learning CLOS compared to traditional OOP (C++/Java) is that methods are not part of classes. Instead methods are defined with the defmethod macro similar to normal functions. defmethod is the primary tool for polymorphism in Common Lisp. Multiple methods that have the same name can be defined, with each one specifying which class they correspond to. Each method needs to have the same number of arguments to be matched. When a method is called at run-time CLOS will evaluate which method to call based on the types of the parameters passed. Additionally, a defgeneric macro can be used to define an abstract / virtual version of the defmethod. This seems to be primarily useful for documentation as well as making the interface clear if users want to add their own defmethods.

There are lots of other exciting features possible with defmethods in CLOS including multiple dispatch.

Approach

When designing the FSM for this project, I wanted to make sure at least one of the states had its own internal sub-state. I think this really lends to using objects over pure functions and I think could be very useful (especially in the context of programming a game). I knew I wanted to make a separate class for each state. I was not sure if I needed a base class in this case and ended up not actually using one. Both the alpha and gamma states do not have any properties since they do not have any internal state. The beta state has two properties for counting the number of consecutive odds or evens.

The bulk of the state machine is implemented in a method named handle-input. This method will accept an input value that the user typed into the prompt and then do the conditional logic to decide if a state transition is needed.

Lastly there will need to be a state machine loop function that continually prompts the user for an input value and prints the current state.

Finite State Machine Common Lisp Implementation

(defgeneric handle-input (state input)
  (:documentation "Defines the behavior of a state for a given input
  value. Optionally returns a new state."))

(defclass alpha () ())

(defclass beta ()
  ((odd-count :accessor odd-count :initform 0)
   (even-count :accessor even-count :initform 0)))

(defclass gamma () ())

(defmethod handle-input ((state alpha) input)
  (when (numberp input)
    (cond ((evenp input)
           (make-instance 'beta))
          ((oddp input)
           (make-instance 'gamma)))))

(defmethod handle-input ((state beta) input)
  (when (numberp input)
    (cond ((evenp input)
           (setf (odd-count state) 0)
           (incf (even-count state)))
          ((oddp input)
           (setf (even-count state) 0)
           (incf (odd-count state))))

    (cond ((= (even-count state) 2)
           (make-instance 'gamma))
          ((= (odd-count state) 3)
           (make-instance 'alpha)))))

(defmethod handle-input ((state gamma) input)
  (when (numberp input)
    (cond ((< input 0)
           (make-instance 'beta))
          ((mod input 7)
           (make-instance 'alpha)))))

(defun state-machine ()
  (let ((state (make-instance 'alpha)))
    (do ((input nil (setf input (read))))
        ((eq input 'q))
      (let ((new-state (handle-input state input)))
        (when new-state
          (setf state new-state)))
      (format t "~&state: ~a~%? " state))))

Running the State Machine

Below is a capture from the REPL of running the finite state machine. One cool thing to note is that since beta is the only state that has an internal state you can see the address id remain the same between inputs. 

CL-USER> (state-machine)
state: #<ALPHA {10021607C3}>
? 2

state: #<BETA {100220AB23}>
? 4

state: #<BETA {100220AB23}>
? 8

state: #<GAMMA {100223EF73}>
? 35

state: #<ALPHA {100223F633}>
? 3

state: #<GAMMA {100223FD43}>
? -1

state: #<BETA {10022482A3}>
? 3

state: #<BETA {10022482A3}>
? 1

state: #<BETA {10022482A3}>
? -5

state: #<ALPHA {10022491F3}>
? q

NIL
CL-USER>

Conclusion

Recently I have trended away from using OOP when approaching problems. Preferring instead to use functional solutions where possible. CLOS is really interesting because it keeps code terse while also being very dynamic and flexible. CLOS (like a lot of Common Lisp) seems to be optimized around usability and ergonomics for the developer. Multiple dispatch also seems particularly useful for game programming. I am planning on implementing some small games in lisp in the future and I will definitely be using CLOS.