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.

Sunday, June 27, 2004

Automaton meets LOOP 

After I wrote the blog entry on the simple automaton macro I have been playing with, I got a couple of good comments back from astute readers. Bill Clagett wrote to show me his version of the macro which he had also been playing with. Bill had used LOOP instead of the mapping functions I used in my first version. Further, Bill gently pointed out that my first version used a (reduce #'append (mapcar f lst)) form, which is a very verbose way of saying (mapcan f lst). Doh! He was right.

Anyway, after correcting my first version to use MAPCAN, I also decided that enough was enough. I had been avoiding the LOOP macro for a while and just decided that I had to dive in, do the reading, and then start using it. On another one of my numerous plane rides, I pulled out my laptop and started going through the HyperSpec section on LOOP. I was pretty blown away by the power of the LOOP macro. There are so many nifty features that can really make your code short and sweet.

In particular, I was amazed at how easy it is to destructure a sublist as you're iterating over the top-level list. I had done a bunch of destructuring manually with CAR, CDR, CADR, and CDDR in the first version of the automaton macro. LOOP promised to make this much easier.

So, I finally rewrote a version of the macro, shown below. Thanks to Bill, both for his education about MAPCAN as well as giving me the encouragement to dive into LOOP. As a result, the macro is now six lines shorter than the first attempt. Notice how nicely the LOOP form destructures the nested list structure of the macro syntax and then collects the results back up for inclusion in the final macro expansion.

If LOOP has you scared (like it had me), two good references are the HyperSpec itself and an appendix of Peter Seibel's upcoming book, Practical Common Lisp, titled "LOOP for Black-Belts." I don't know that I have quite reached black-belt status yet, but I'm feeling a lot more comfortable with LOOP now.

(defmacro define-automaton (name states &key (stop 'stop) (debug nil))
  (let ((event-func (gensym "func")))
    `(defun ,name (,event-func)
	 ,@(loop for (state-name . transitions) in states
		 (list state-name
		       `(case (funcall ,event-func)
 			 ,@(loop for (match next . actions) in transitions
				 collecting (cons match
						  (append actions
							  (when debug
							    `((format t "Matched ~A. Transitioning to state ~A.~%" ,match ',next)))
							  `((go ,next))))))
		       `(go ,state-name)))

Update, 28-Jun: The macro as first posted had a slight error in it. The first LOOP form had been using a COLLECTING clause which caused an extra set of parenthesis in the expansion. The LOOP should have been using an APPENDING clause.

Post a Comment

Links to this post:

Create a Link

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