The finite-state-machine Reference Manual

Table of Contents

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 3.0 "Montgomery Scott" on Fri Jun 26 10:34:56 2020 GMT+0.


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

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



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

2 Systems

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


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

2.1 finite-state-machine

Author

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

License

MIT

Description

An intuitive implementation of a finite state machine.

Version

1.0.0

Source

finite-state-machine.asd (file)

Components

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

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


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 finite-state-machine.asd

Location

finite-state-machine.asd

Systems

finite-state-machine (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 finite-state-machine/package.lisp

Parent

finite-state-machine (system)

Location

package.lisp

Packages

info.isoraqathedh.finite-state-machine


Previous: , Up: Lisp files   [Contents][Index]

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

Dependency

package.lisp (file)

Parent

finite-state-machine (system)

Location

finite-state-machine.lisp

Exported Definitions
Internal Definitions

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

4 Packages

Packages are listed by definition order.


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

4.1 info.isoraqathedh.finite-state-machine

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

Writer

(setf state) (generic function)

Methods
Method: state (FSM finite-state-machine)
Generic Function: (setf state) NEW-STATE STATE-MACHINE

Set the new state of the state-machine.

Package

info.isoraqathedh.finite-state-machine

Source

finite-state-machine.lisp (file)

Reader

state (generic function)

Methods
Method: (setf state) NEW-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 (file)

Methods
Method: statep (FSM finite-state-machine) POSSIBLE-STATE

Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Classes

Class: finite-state-machine ()
Package

info.isoraqathedh.finite-state-machine

Source

finite-state-machine.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: all-states
Initargs

:states

Readers

states-of (generic function)

Writers

(setf states-of) (generic function)

Slot: accepting-states
Initargs

:accepting-states

Readers

accepting-states (generic function)

Writers

(setf accepting-states) (generic function)

Slot: state-history
Readers

state-history (generic function)

Writers

(setf state-history) (generic function)

Slot: state=-test
Initargs

:test

Initform

(function eql)

Readers

state=-test (generic function)

Writers

(setf state=-test) (generic function)


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

5.2 Internal definitions


Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Generic functions

Generic Function: accepting-states OBJECT
Generic Function: (setf accepting-states) NEW-VALUE OBJECT
Package

info.isoraqathedh.finite-state-machine

Methods
Method: accepting-states (FINITE-STATE-MACHINE finite-state-machine)

automatically generated reader method

Source

finite-state-machine.lisp (file)

Method: (setf accepting-states) NEW-VALUE (FINITE-STATE-MACHINE finite-state-machine)

automatically generated writer method

Source

finite-state-machine.lisp (file)

Generic Function: state-history OBJECT
Generic Function: (setf state-history) NEW-VALUE OBJECT
Package

info.isoraqathedh.finite-state-machine

Methods
Method: state-history (FINITE-STATE-MACHINE finite-state-machine)

automatically generated reader method

Source

finite-state-machine.lisp (file)

Method: (setf state-history) NEW-VALUE (FINITE-STATE-MACHINE finite-state-machine)

automatically generated writer method

Source

finite-state-machine.lisp (file)

Generic Function: state=-test OBJECT
Generic Function: (setf state=-test) NEW-VALUE OBJECT
Package

info.isoraqathedh.finite-state-machine

Methods
Method: state=-test (FINITE-STATE-MACHINE finite-state-machine)

automatically generated reader method

Source

finite-state-machine.lisp (file)

Method: (setf state=-test) NEW-VALUE (FINITE-STATE-MACHINE finite-state-machine)

automatically generated writer method

Source

finite-state-machine.lisp (file)

Generic Function: states-of OBJECT
Generic Function: (setf states-of) NEW-VALUE OBJECT
Package

info.isoraqathedh.finite-state-machine

Methods
Method: states-of (FINITE-STATE-MACHINE finite-state-machine)

automatically generated reader method

Source

finite-state-machine.lisp (file)

Method: (setf states-of) NEW-VALUE (FINITE-STATE-MACHINE finite-state-machine)

automatically generated writer method

Source

finite-state-machine.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   L  
Index Entry  Section

F
File, Lisp, finite-state-machine.asd: The finite-state-machine․asd file
File, Lisp, finite-state-machine/finite-state-machine.lisp: The finite-state-machine/finite-state-machine․lisp file
File, Lisp, finite-state-machine/package.lisp: The finite-state-machine/package․lisp file
finite-state-machine.asd: The finite-state-machine․asd file
finite-state-machine/finite-state-machine.lisp: The finite-state-machine/finite-state-machine․lisp file
finite-state-machine/package.lisp: The finite-state-machine/package․lisp file

L
Lisp File, finite-state-machine.asd: The finite-state-machine․asd file
Lisp File, finite-state-machine/finite-state-machine.lisp: The finite-state-machine/finite-state-machine․lisp file
Lisp File, finite-state-machine/package.lisp: The finite-state-machine/package․lisp file

Jump to:   F   L  

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

A.2 Functions

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

(
(setf accepting-states): Internal generic functions
(setf accepting-states): Internal generic functions
(setf state): Exported generic functions
(setf state): Exported generic functions
(setf state-history): Internal generic functions
(setf state-history): Internal generic functions
(setf state=-test): Internal generic functions
(setf state=-test): Internal generic functions
(setf states-of): Internal generic functions
(setf states-of): Internal generic functions

A
accepting-states: Internal generic functions
accepting-states: Internal generic functions
acceptingp: Exported generic functions
acceptingp: Exported generic functions

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

M
Method, (setf accepting-states): Internal generic functions
Method, (setf state): Exported generic functions
Method, (setf state-history): Internal generic functions
Method, (setf state=-test): Internal generic functions
Method, (setf states-of): Internal generic functions
Method, accepting-states: Internal generic functions
Method, acceptingp: Exported generic functions
Method, next-state!: Exported generic functions
Method, previous-state: Exported generic functions
Method, previous-state!: Exported generic functions
Method, state: Exported generic functions
Method, state-history: Internal generic functions
Method, state=-test: Internal generic functions
Method, statep: Exported generic functions
Method, states-of: Internal generic functions

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

P
previous-state: Exported generic functions
previous-state: Exported generic functions
previous-state!: Exported generic functions
previous-state!: Exported generic functions

S
state: Exported generic functions
state: Exported generic functions
state-history: Internal generic functions
state-history: Internal generic functions
state=-test: Internal generic functions
state=-test: Internal generic functions
statep: Exported generic functions
statep: Exported generic functions
states-of: Internal generic functions
states-of: Internal generic functions

Jump to:   (  
A   G   M   N   P   S  

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

A.3 Variables

Jump to:   A   S  
Index Entry  Section

A
accepting-states: Exported classes
all-states: Exported classes

S
Slot, accepting-states: Exported classes
Slot, all-states: Exported classes
Slot, state-history: Exported classes
Slot, state=-test: Exported classes
state-history: Exported classes
state=-test: Exported classes

Jump to:   A   S  

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

A.4 Data types

Jump to:   C   F   I   P   S  
Index Entry  Section

C
Class, finite-state-machine: Exported classes

F
finite-state-machine: The finite-state-machine system
finite-state-machine: Exported classes

I
info.isoraqathedh.finite-state-machine: The info․isoraqathedh․finite-state-machine package

P
Package, info.isoraqathedh.finite-state-machine: The info․isoraqathedh․finite-state-machine package

S
System, finite-state-machine: The finite-state-machine system

Jump to:   C   F   I   P   S