Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.DFA

This package implements a DFA, Deterministic Finite Automaton (or Deterministic Finite State Machine). A DFA has a state. Our DFAs also have a set of slots. Each DFA is implemented as a class. Events are represented as generic functions called with the DFA instance as first argument (and optionnaly other arguments). They are specialized on each specific class of DFA they're applicable to. Example: (define-state-machine test-dfa :slots ((data :initarg :data :initform nil :accessor data)) :initial zero :states ((zero (:entry () (print `(entering zero))) (:exit () (print `(exiting zero))) (got-a (sym) (push (cons 'a sym) data)) (got-b (sym) (push (cons 'b sym) data) (go-to-state one sym))) (one (:entry (sym) (print `(entering one ,sym))) (:exit () (print `(exiting one))) (got-a (sym) (push (cons 'a sym) data)) (got-b (sym) (push (cons 'b sym) data) (go-to-state zero)))) :documentation "A test DFA") (defparameter *d* (make-test-dfa '())) prints: (entering zero) --> *d* (got-a *d* 'a) --> ((a . a)) (got-b *d* 'b) prints: (exiting zero) (entering one b) --> (entering one b) (got-a *d* 'a) --> ((a . a) (b . b) (a . a)) (slot-value *d* 'data) --> ((a . a) (b . b) (a . a)) License: AGPL3 Copyright Pascal J. Bourguignon 2012 - 2012 This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>

README:

FUNCTION

Private

COLLECT-EVENTS (STATES)

STATES: an A-list of state-name and events. Each event is a list containing the name of the event (a symbol), a lambda list, followed by the body of the event in that state. Returns the list of dfa-events and the list of dfa-entrexes collected from the STATES.

DFA-ENTREX-BODY (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DFA-ENTREX-LAMBDA-LIST (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DFA-ENTREX-NAME (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DFA-ENTREX-STATE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DFA-EVENT-LAMBDA-LIST (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DFA-EVENT-NAME (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

DFA-EVENT-STATE-BODY-MAP (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

GENERATE-ENTREX-METHOD (DFA-CLASS SLOT-NAMES STATE-NAMES ENTREX)

Generate the entrex method. DFA-CLASS: name of the DFA. The entrex method is named either ON-ENTRY or ON-EXIT and dispatches on the DFA class and the state name.

GENERATE-EVENT-METHOD (DFA-CLASS SLOT-NAMES STATE-NAMES EVENT)

Generate the event method. DFA-CLASS: name of the DFA.

SLOT-NAMES (SLOTS)

The list of names of slots.

STATE-NAMES (STATES)

The list of names of states.

Undocumented

COPY-DFA-ENTREX (INSTANCE)

COPY-DFA-EVENT (INSTANCE)

SETFDFA-ENTREX-BODY (NEW-VALUE INSTANCE)

SETFDFA-ENTREX-LAMBDA-LIST (NEW-VALUE INSTANCE)

SETFDFA-ENTREX-NAME (NEW-VALUE INSTANCE)

DFA-ENTREX-P (OBJECT)

SETFDFA-ENTREX-STATE (NEW-VALUE INSTANCE)

SETFDFA-EVENT-LAMBDA-LIST (NEW-VALUE INSTANCE)

SETFDFA-EVENT-NAME (NEW-VALUE INSTANCE)

DFA-EVENT-P (OBJECT)

SETFDFA-EVENT-STATE-BODY-MAP (NEW-VALUE INSTANCE)

MAKE-DFA-ENTREX (&KEY ((NAME DUM116) NIL) ((STATE DUM117) NIL) ((LAMBDA-LIST DUM118) NIL) ((BODY DUM119) NIL))

MAKE-DFA-EVENT (&KEY ((NAME DUM76) NIL) ((LAMBDA-LIST DUM77) NIL) ((STATE-BODY-MAP DUM78) NIL))

MACRO

Public

DEFINE-STATE-MACHINE (NAME &KEY SLOTS INITIAL STATES DOCUMENTATION)

Defines a DFA class named NAME with the given SLOTS. The CLAUSES define the states and transitions, that are implemented as generic functions on the DFA class.

Private

WITH-GO-TO-STATE ((DFA-VAR STATE-NAMES) &BODY BODY)

Execute the BODY in a context where GO-TO-STATE is defined as a macro to transition to a new state.

GENERIC-FUNCTION

Public

ON-ENTRY (DFA STATE &REST REST)

This generic function is called on entry into the state, ie. at the end of the transition, when the state has been updated. (Methods may further change the state). The REST arguments are those passed to the event.

ON-EXIT (DFA STATE &REST REST)

This generic function is called on exit from the state, ie. at the beginning of the transition, before the state changes. The REST arguments are those passed to the event.

SLOT-ACCESSOR

Public

DFA-STATE (DFA)

The The state of the DFA.

SETFDFA-STATE (NEW-VALUE OBJECT)

Set the The state of the DFA.

CLASS

Public

DFA

A base class for DFAs. A DFA has a state, and transitions from one state to another can be performed by event methods.

Private

DFA-ENTREX

Entrexes are on-Entry and on-Exit actions. They're implemented as normal functions specific to each DFA state.

DFA-EVENT

Events are implemeted as a method on the DFA objects. Each method dispatches on the state of the DFA.