The finite-state-machine Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The finite-state-machine Reference Manual

This is the finite-state-machine Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed Jun 15 04:02:41 2022 GMT+0.

Table of Contents


1 Introduction

#+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



2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 finite-state-machine

An intuitive implementation of a finite state machine.

Author

Isoraķatheð Zorethan <isoraqathedh.zorethan@gmail.com>

License

MIT

Version

1.0.0

Source

finite-state-machine.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


3.1.1 finite-state-machine/finite-state-machine.asd

Source

finite-state-machine.asd.

Parent Component

finite-state-machine (system).

ASDF Systems

finite-state-machine.


3.1.3 finite-state-machine/finite-state-machine.lisp

Dependency

package.lisp (file).

Source

finite-state-machine.asd.

Parent Component

finite-state-machine (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 info.isoraqathedh.finite-state-machine

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Generic functions

Generic Function: acceptingp (state-machine)

Check if the STATE-MACHINE is in an accepting state.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: acceptingp ((fsm finite-state-machine))
Generic Function: next-state (state-machine event)

Name the correct next state of STATE-MACHINE given event EVENT.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Generic Function: next-state! (state-machine event)

Move to the correct next state of STATE-MACHINE given event EVENT.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: next-state! ((state-machine finite-state-machine) event)
Generic Function: previous-state (state-machine)

Peek at the previous state.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: previous-state ((fsm finite-state-machine))
Generic Function: previous-state! (state-machine)

Return the machine to a previous state.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: previous-state! ((fsm finite-state-machine))
Generic Function: state (state-machine)

Return the current state of the machine.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: state ((fsm finite-state-machine))
Generic Function: (setf state) (state-machine)

Set the new state of the state-machine.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: (setf state) ((state-machine finite-state-machine))
Generic Function: statep (state-machine possible-state)

Check if a POSSIBLE-STATE is a state in STATE-MACHINE.

Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Methods
Method: statep ((fsm finite-state-machine) possible-state)

5.1.2 Standalone methods

Method: initialize-instance :after ((instance finite-state-machine) &key states start-state)
Source

finite-state-machine.lisp.

Method: print-object ((object finite-state-machine) stream)
Source

finite-state-machine.lisp.


5.1.3 Classes

Class: finite-state-machine
Package

info.isoraqathedh.finite-state-machine.

Source

finite-state-machine.lisp.

Direct methods
Direct slots
Slot: all-states
Initargs

:states

Readers

states-of.

Writers

(setf states-of).

Slot: accepting-states
Initargs

:accepting-states

Readers

accepting-states.

Writers

(setf accepting-states).

Slot: state-history
Readers

state-history.

Writers

(setf state-history).

Slot: state=-test
Initform

(function eql)

Initargs

:test

Readers

state=-test.

Writers

(setf state=-test).


5.2 Internals


Previous: , Up: Internals   [Contents][Index]

5.2.1 Generic functions

Generic Reader: accepting-states (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Reader Method: accepting-states ((finite-state-machine finite-state-machine))

automatically generated reader method

Source

finite-state-machine.lisp.

Target Slot

accepting-states.

Generic Writer: (setf accepting-states) (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Writer Method: (setf accepting-states) ((finite-state-machine finite-state-machine))

automatically generated writer method

Source

finite-state-machine.lisp.

Target Slot

accepting-states.

Generic Reader: state-history (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Reader Method: state-history ((finite-state-machine finite-state-machine))

automatically generated reader method

Source

finite-state-machine.lisp.

Target Slot

state-history.

Generic Writer: (setf state-history) (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Writer Method: (setf state-history) ((finite-state-machine finite-state-machine))

automatically generated writer method

Source

finite-state-machine.lisp.

Target Slot

state-history.

Generic Reader: state=-test (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Reader Method: state=-test ((finite-state-machine finite-state-machine))

automatically generated reader method

Source

finite-state-machine.lisp.

Target Slot

state=-test.

Generic Writer: (setf state=-test) (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Writer Method: (setf state=-test) ((finite-state-machine finite-state-machine))

automatically generated writer method

Source

finite-state-machine.lisp.

Target Slot

state=-test.

Generic Reader: states-of (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Reader Method: states-of ((finite-state-machine finite-state-machine))

automatically generated reader method

Source

finite-state-machine.lisp.

Target Slot

all-states.

Generic Writer: (setf states-of) (object)
Package

info.isoraqathedh.finite-state-machine.

Methods
Writer Method: (setf states-of) ((finite-state-machine finite-state-machine))

automatically generated writer method

Source

finite-state-machine.lisp.

Target Slot

all-states.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
A   G   I   M   N   P   S  
Index Entry  Section

(
(setf accepting-states): Private generic functions
(setf accepting-states): Private generic functions
(setf state): Public generic functions
(setf state): Public generic functions
(setf state-history): Private generic functions
(setf state-history): Private generic functions
(setf state=-test): Private generic functions
(setf state=-test): Private generic functions
(setf states-of): Private generic functions
(setf states-of): Private generic functions

A
accepting-states: Private generic functions
accepting-states: Private generic functions
acceptingp: Public generic functions
acceptingp: Public generic functions

G
Generic Function, (setf accepting-states): Private generic functions
Generic Function, (setf state): Public generic functions
Generic Function, (setf state-history): Private generic functions
Generic Function, (setf state=-test): Private generic functions
Generic Function, (setf states-of): Private generic functions
Generic Function, accepting-states: Private generic functions
Generic Function, acceptingp: Public generic functions
Generic Function, next-state: Public generic functions
Generic Function, next-state!: Public generic functions
Generic Function, previous-state: Public generic functions
Generic Function, previous-state!: Public generic functions
Generic Function, state: Public generic functions
Generic Function, state-history: Private generic functions
Generic Function, state=-test: Private generic functions
Generic Function, statep: Public generic functions
Generic Function, states-of: Private generic functions

I
initialize-instance: Public standalone methods

M
Method, (setf accepting-states): Private generic functions
Method, (setf state): Public generic functions
Method, (setf state-history): Private generic functions
Method, (setf state=-test): Private generic functions
Method, (setf states-of): Private generic functions
Method, accepting-states: Private generic functions
Method, acceptingp: Public generic functions
Method, initialize-instance: Public standalone methods
Method, next-state!: Public generic functions
Method, previous-state: Public generic functions
Method, previous-state!: Public generic functions
Method, print-object: Public standalone methods
Method, state: Public generic functions
Method, state-history: Private generic functions
Method, state=-test: Private generic functions
Method, statep: Public generic functions
Method, states-of: Private generic functions

N
next-state: Public generic functions
next-state!: Public generic functions
next-state!: Public generic functions

P
previous-state: Public generic functions
previous-state: Public generic functions
previous-state!: Public generic functions
previous-state!: Public generic functions
print-object: Public standalone methods

S
state: Public generic functions
state: Public generic functions
state-history: Private generic functions
state-history: Private generic functions
state=-test: Private generic functions
state=-test: Private generic functions
statep: Public generic functions
statep: Public generic functions
states-of: Private generic functions
states-of: Private generic functions

Jump to:   (  
A   G   I   M   N   P   S