Thursday, July 14, 2005


Lispy or not?

I just started making Lisp versions my cop and robber entries from the ICFP contest. I am aware that because other languages I use don't have anything like Lisp's macros, I tend not to use macros in Lisp. I am trying to change that.

When I was coding my parser in ocaml, I thought it was cool to use the match statement to parse the various lines, like this:

let parse_line line =
match Str.split (Str.regexp "[ \t]+") line with
"wsk\\" :: [] -> handle_wsk_start()
| "name:" :: name :: [] -> handle_name name
| "robber:" :: name :: [] -> handle_robber name
| "cop:" :: name :: [] -> handle_cop name
| "nod\\" :: [] -> handle_nodes_start()
| "nod:" :: name :: tag :: x :: y :: [] -> handle_node name (node_tag_of_string tag)
(int_of_string x) (int_of_string y)

Since I don't have match in Lisp, I wondered what would be a good way to do this in Lisp. I decided to do it with a macro. I keep a global hash table that maps keywords like "wsk\\" and "name:" to functions that handle the data for those keywords. I use a macro named defparse to create a function where instead of the name of the function, I supply the keyword name. Here is how I handle the "nod:" line for example:

(defparse "nod:" (name tag x# y#)
(push (make-instance 'node :name name :tag tag :x x# :y y#) *build-node-list*))

One of the interesting things here is that you are seeing the function that handles the line, not just my definition of what is on the "nod:" line. In the ocaml version, I had all the keywords in one big match statement and made them call separate functions. I could have implemented the functions in the match statements but I thought it might look ugly. I like the Lisp solution here because I define the line contents and the function in one place, but it isn't all cluttered with other line definitions.

There are a couple of things going on in defparse. First, it turns the function body into a lambda expression that is mapped in the global keyword hash table. Next, it looks for parameters whose names end in # and automatically converts them from string to integer. This is what the expansion of my (defparse "nod:" ...) looks like:

(LAMBDA (NAME TAG #:G4171 #:G4172)
(LET ((|X#| (PARSE-INTEGER #:G4171)) (|Y#| (PARSE-INTEGER #:G4172)))

Those #:G4171 and #:G4172 names are unique symbol names generated by the gensym function. A macro in Lisp is basically a function whose return value is code that will be compiled. This means that it blends in well with the language - there are a few syntactic differences having to do with quoting, but otherwise, you don't learn a separate macro language. One of the difficulties is that the macros run at compile time, so you can make use of all the functions you have defined (as far as I can tell, at least).

For the curious, here is my defparse macro:

(defmacro defparse (command param-list &body body)
(let* ((int-params (remove-if-not
#'(lambda (param)
(let ((ps (symbol-name param)))
(char= (elt ps (1- (length ps))) #\#))) param-list))
(param-map (mapcar #'(lambda (x) (cons x (gensym))) int-params))
(param-list-with-syms (mapcar
#'(lambda (param) (if (assoc param param-map) (cdr (assoc param param-map)) param))
(let-list (mapcar #'(lambda (pg) (list (car pg) (list 'parse-integer (cdr pg)))) param-map)))
`(setf (gethash ,command *command-handlers*)
(lambda ,param-list-with-syms
(let ,let-list ,@body)))))

The thing I am a bit curious about is whether this is a Lispy way to approach the problem. Would a Lisp pro nod his or her head at this, or start to gag?

Comments: Post a Comment

<< Home

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