## cl-simple-fsm

2020-02-18

No Description

### Upstream URL

### Author

### License

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