Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the finite-state-machine Reference Manual, version 1.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 15:19:50 2021 GMT+0.
| • Introduction | What finite-state-machine is all about | |
| • Systems | The systems documentation | |
| • Files | The files documentation | |
| • Packages | The packages documentation | |
| • Definitions | The symbols documentation | |
| • Indexes | Concepts, functions, variables and data types |
#+Title: finite-state-machine
An intuitive implementation of a finite state machine.
* Operation
** Creating a state machine
First, create your state machine, and store it somewhere.
#+BEGIN_SRC lisp
(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)))
#+END_SRC
(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:
#+BEGIN_SRC lisp
(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))
#+END_SRC
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.
** Transitions
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.
#+Name: state-transition-method
#+BEGIN_SRC lisp
(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)))
#+END_SRC
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~:
#+BEGIN_SRC lisp
(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")
#+END_SRC
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.
* Things to do [0/4]
** TODO Transition table
There will be a way to more succinctly represent the transition table
so that code like [[state-transition-method]] don't have to be written.
** TODO Encompassing 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 machine
and its transitions at once; and
- ~with-state-machine~, which creates a state machine
lasting for the body of the macro.
** TODO Reconsider history
Finite state machines don't have history. It may be better to remove them.
** TODO Built-in tokens
Consider creating ~tokenised-finite-state-machine~,
which contains within it the list of tokens that it recognises.
* License
MIT
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The finite-state-machine system |
Isoraķatheð Zorethan <isoraqathedh.zorethan@gmail.com>
MIT
An intuitive implementation of a finite state machine.
1.0.0
finite-state-machine.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files |
| • The finite-state-machine.asd file | ||
| • The finite-state-machine/package.lisp file | ||
| • The finite-state-machine/finite-state-machine.lisp file |
Next: The finite-state-machine/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
finite-state-machine.asd
finite-state-machine (system)
Next: The finite-state-machine/finite-state-machine․lisp file, Previous: The finite-state-machine․asd file, Up: Lisp files [Contents][Index]
finite-state-machine (system)
package.lisp
Previous: The finite-state-machine/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
finite-state-machine (system)
finite-state-machine.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The info.isoraqathedh.finite-state-machine package |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions | ||
| • Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported generic functions | ||
| • Exported classes |
Next: Exported classes, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
Check if the STATE-MACHINE is in an accepting state.
finite-state-machine.lisp (file)
Name the correct next state of STATE-MACHINE given event EVENT.
finite-state-machine.lisp (file)
Move to the correct next state of STATE-MACHINE given event EVENT.
finite-state-machine.lisp (file)
Peek at the previous state.
finite-state-machine.lisp (file)
Return the machine to a previous state.
finite-state-machine.lisp (file)
Return the current state of the machine.
finite-state-machine.lisp (file)
(setf state) (generic function)
Set the new state of the state-machine.
finite-state-machine.lisp (file)
state (generic function)
Check if a POSSIBLE-STATE is a state in STATE-MACHINE.
finite-state-machine.lisp (file)
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
finite-state-machine.lisp (file)
standard-object (class)
:states
states-of (generic function)
(setf states-of) (generic function)
:accepting-states
accepting-states (generic function)
(setf accepting-states) (generic function)
state-history (generic function)
(setf state-history) (generic function)
:test
(function eql)
state=-test (generic function)
(setf state=-test) (generic function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal generic functions |
Previous: Internal definitions, Up: Internal definitions [Contents][Index]
automatically generated reader method
finite-state-machine.lisp (file)
automatically generated writer method
finite-state-machine.lisp (file)
automatically generated reader method
finite-state-machine.lisp (file)
automatically generated writer method
finite-state-machine.lisp (file)
automatically generated reader method
finite-state-machine.lisp (file)
automatically generated writer method
finite-state-machine.lisp (file)
automatically generated reader method
finite-state-machine.lisp (file)
automatically generated writer method
finite-state-machine.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index | ||
| • Function index | ||
| • Variable index | ||
| • Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | F L |
|---|
| Jump to: | F L |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | (
A G M N P S |
|---|
| Jump to: | (
A G M N P S |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | A S |
|---|
| Jump to: | A S |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | C F I P S |
|---|
| Jump to: | C F I P S |
|---|