Books of Note

Practical Common
LispThe best intro to start your journey. Excellent coverage of CLOS.

ANSI Common
LispAnother great starting point with a different focus.

Paradigms of Artificial Intelligence
ProgrammingA superb set of Lisp examples. Not just for the AI crowd.

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


Comments:


Beautiful!

This is exactly what I have been looking for. Thanks!
 

Post a Comment


Links to this post:

Create a Link

This page is powered by Blogger. Isn't yours?