Saturday, June 12, 2004
Basic automaton macro
After getting my dosage of The Swine Before Perl, I figured I would code up a macro to generate a basic automaton. This really shows the power of Lisp on a number of levels. First, the macro:
(defmacro define-automaton (name states &key (stop 'stop) (debug nil) ) (let ((event-func (gensym "func"))) `(defun ,name (,event-func) (tagbody ,@(reduce #'append (mapcar (lambda (state) (let ((state-name (car state)) (transitions (cdr state))) (list state-name `(case (funcall ,event-func) ,@(mapcar (lambda (trans) (let ((match (car trans)) (next (cadr trans)) (actions (cddr trans))) (cons match (append actions (when debug `((format t "Matched ~A. Transitioning to state ~A.~%" ,match (quote ,next)))) `((go ,next)))))) transitions)) `(go ,state-name)))) states)) ,stop))))
This allows you to define a state machine like this:
(define-automaton look-for-lisp ((start ('l found-l) ('x stop)) (found-l ('i found-i) ('l found-l) (otherwise start)) (found-i ('s found-s) ('l found-l) (otherwise start)) (found-s ('p start (format t "Found LISP~%") (return-from look-for-lisp t)) ('l found-l) (otherwise start))))
Each state has a name and a set of transitions. Each transition includes an input to match, a next state to transition to when that input appears, and a set of forms that should be executed when that transition occurs. In this case, we include forms only when we match the final "P" symbol in the input. STOP is a default stop state which exits the machine with a NIL return value. You can override the name of the default stop state if it clashes with a another state name (handy if you're programming traffic signal state machines, for instance). Finally, you can return from the machine at any time with a RETURN-FROM form.
The macro expands the previous state machine definition to the following code that uses a TAGBODY to define states. Basically, the current state is held in the program counter. This makes a very fast state machine for doing something like scanning an input stream. Each state first calls the function passed to the state machine to retrieve the next input and then uses CASE to dispatch to the next event.
(DEFUN LOOK-FOR-LISP (#:|func3231|) (TAGBODY START (CASE (FUNCALL #:|func3231|) ((QUOTE L) (GO FOUND-L)) ((QUOTE X) (GO STOP))) (GO START) FOUND-L (CASE (FUNCALL #:|func3231|) ((QUOTE I) (GO FOUND-I)) ((QUOTE L) (GO FOUND-L)) (OTHERWISE (GO START))) (GO FOUND-L) FOUND-I (CASE (FUNCALL #:|func3231|) ((QUOTE S) (GO FOUND-S)) ((QUOTE L) (GO FOUND-L)) (OTHERWISE (GO START))) (GO FOUND-I) FOUND-S (CASE (FUNCALL #:|func3231|) ((QUOTE P) (FORMAT T "Found LISP~%") (RETURN-FROM LOOK-FOR-LISP T) (GO START)) ((QUOTE L) (GO FOUND-L)) (OTHERWISE (GO START))) (GO FOUND-S) STOP))
We can then use the state machine like this:
CL-USER> (look-for-lisp #'read) l i s p Found LISP T CL-USER> (look-for-lisp #'read) x NIL CL-USER> (look-for-lisp #'read) l i p l i s p Found LISP T CL-USER> (look-for-lisp #'read) l i l i s p Found LISP T CL-USER> (look-for-lisp #'read) l i s x x NIL
One of the neat things about Lisp is how easily you can do incremental debugging by passing in functions like READ and then just using all the Lisp machinery to do most of your work for you.
Now, this macro also has a debugging mode. Simply add the :DEBUG keyword to the definition and you're in business:
(define-automaton look-for-lisp ((start ('l found-l) ('x stop)) (found-l ('i found-i) ('l found-l) (otherwise start)) (found-i ('s found-s) ('l found-l) (otherwise start)) (found-s ('p start (format t "Found LISP~%") (return-from look-for-lisp t)) ('l found-l) (otherwise start))) :debug t) CL-USER> (look-for-lisp #'read) l Matched L. Transitioning to state FOUND-L. i Matched I. Transitioning to state FOUND-I. s Matched S. Transitioning to state FOUND-S. p Found LISP T
Links to this post: