finite-state-machine

An intuitive implementation of a finite state machine.

1Operation

1.1Creating a state machine

First, create your state machine, and store it somewhere.

  (defvar *state*
    (make-instance 'info.isoraqathedh.finite-state-machine:finite-state-machine
                   :states (list :start
                                 :sign
                                 :pre-decimal-point-digit
                                 :decimal-point
                                 :post-decimal-point-digit
                                 :reject)
                   :accepting-states (list :pre-decimal-point-digit
                                           :post-decimal-point-digit)))

(All unqualified symbols are in common-lisp or the package that this system uses, info.isoraqathedh.finite-state-machine.)

Alternatively, you can subclass finite-state-machine if you wish to make many of the same machine and give them an identity:

  (defclass decimal-recogniser (finite-state-machine)
    ()
    (:default-initargs
     :states (list :start
                   :sign
                   :pre-decimal-point-digit
                   :decimal-point
                   :post-decimal-point-digit
                   :reject)
     :accepting-states (list :pre-decimal-point-digit
                             :post-decimal-point-digit)))

  (defvar *state* (make-instance 'decimal-recogniser))

You must provide make-instance a list of states, or it will complain. If you don't provide a starting state via :start-state, then the first one is automatically selected as the start state. If you don't provide any :accepting-states, this is acceptable but a little bit silly.

The states can be anything you feel is appropriate, but if the default comparison function #'eql is inadequate, you may want to set :test to compare them with each other. For simplicity, choose keywords.

1.2Transitions

The next step is to define some transitions.This is done by adding methods to next-state,which takes in the state machine (with its current state) and an event.

What that event is can again be anything you desire, as long as you can specify it as a specialiser on the method. If you do use a one-off state machine as above, then you should use an eql specialiser for your methods.

  (defmethod next-state ((machine decimal-recogniser) (event character))
    (ecase (state machine)
      (:start
       (case event
         ((#\+ #\-) :sign)
         ((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9) :pre-decimal-point-digit)
         (#\. :decimal-point)
         (t :reject)))
      (:sign
       (case event
         ((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9) :pre-decimal-point-digit)
         (#\. :decimal-point)
         (t :reject)))
      (:pre-decimal-point-digit
       (case event
         ((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9) :pre-decimal-point-digit)
         (#\. :decimal-point)
         (t :reject)))
      ((:decimal-point :post-decimal-point-digit)
       (case event
         ((#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9) :post-decimal-point-digit)
         (t :reject)))
      (:reject :reject)))

After that, you can run the machine on a particular sequence (here, a string). To check if the machine is in an accepting state, use acceptingp:

  (defun decimal-number-p (to-check)
    (loop with recogniser = (make-instance 'decimal-recogniser)
          for c across to-check
          do (next-state! recogniser c)
          finally (return (acceptingp recogniser))))

  (decimal-number-p "123.45")
  (decimal-number-p "-123")
  (decimal-number-p "bogus")

Note we have used next-state! here, which automatically sets the next state on the original object.

For best results, consider a token class that lists out all objects that can change the state of the machine as the event.

2Things to do [0/4]

2.1TODOTransition table

There will be a way to more succinctly represent the transition tableso that code like state-transition-method don't have to be written.

2.2TODOEncompassing macros

All of these should have some way to wrap them all around as one coherent whole.Candidates are:

• define-state-machine, which defines a state machineand its transitions at once; and
• with-state-machine, which creates a state machinelasting for the body of the macro.

2.3TODOReconsider history

Finite state machines don't have history. It may be better to remove them.

2.4TODOBuilt-in tokens

Consider creating tokenised-finite-state-machine,which contains within it the list of tokens that it recognises.

3License

MIT