Thursday, June 01, 2006

 

Stealing it back

At Artima, Topher Cyll wrote an article called If It's Not Nailed Down, Steal It where he implements pattern matching, S-expressions and destructuring in Ruby, then uses this to implement a modified Logo interpreter (it uses "(" and ")" instead of "[" and "]"). The Logo interpreter outputs SVG files for rendering.

The interpreter interested me, and hey, Lisp already has the stuff he's stealing, so I thought I'd have a go at implementing the interpreter. I wanted to stick to "vanilla Common Lisp" as much as possible, in other words not pull in big pattern matching libraries, just stick to CLOS multiple dispatch.

Most of the "stealing back" is pretty straightforward, except for the "run" methods. It looks like the Ruby code can distinguish methods by variable arguments, where Lisp methods implementing a generic function must all have the same argument signature, even if the last argument is a &rest. Fortunately, the Ruby methods just distinguish by the command argument, and the rest is destructuring, so once we're in the dispatched run method we can destructure afterwards.

The next bump was chopping off the "command" argument from the remainder of the S-expression to call the next run, which left a single argument for the &rest, the argument being a list of the remaining arguments, so that had to be car'ed, and you had to remember to do it everywhere, etc. It's messy.

"apply" to the rescue. From the CLHS, "apply" uses a "spreadable argument list designator", which means it will turn (1 2 (3 4 5)) into (1 2 3 4 5) when it gets back to dispatching on the method. So
(apply #'run lg '(right 90 forward 10))

turns into
(run lg right 90 forward 10)

which will match on
(defmethod run ((lg logo) (command (eql 'right)) &rest args)

and "args" will have (90 forward 10) in it, ready for destructuring.

One feature of the Ruby version that I can't figure out how to duplicate is dispatching on nil, in other words when we're at the end of the program S-expression. It looks like the methods can catch it, but calling "run" or "apply #'run" won't throw it. What I came up with was inserting a special "stop" token at the end of the programs and stopping on it, or checking at the end of each method for an empty remainder before calling run again. I opted for the empty check. If there's a better solution I'd appreciate a comment to let me know.

This gives me methods such as

(defmethod run ((lg logo) (command (eql 'forward)) &rest args)
(destructuring-bind (distance &rest rest-args) args
(move lg distance)
(when rest-args (apply #'run lg rest-args))))

(defmethod run ((lg logo) (command (eql 'pendown)) &rest args)
(setf (pen lg) t)
(when args (apply #'run lg args)))

(defmethod run ((lg logo) (command (eql 'repeat)) &rest args)
(destructuring-bind (repeat-count code &rest rest-args) args
(dotimes (i repeat-count) (apply #'run lg code))
(when rest-args (apply #'run lg rest-args))))


This works, but looking at the code you can see a lot of boilerplate code. Like any Lisper, to me this code smelled like it needed a macro to make an internal DSL to help out with the external DSL. So with

(defmacro defrun ((logo-var command-symbol vars) &body body)
(let ((args (gensym))
(rest-args (gensym)))
`(defmethod run ((,logo-var logo) (command (eql ',command-symbol)) &rest ,args)
(destructuring-bind (,@vars &rest ,rest-args) ,args
,@body
(when ,rest-args (apply #'run ,logo-var ,rest-args))))))


the above methods turn into

(defrun (lg forward (distance)) (move lg distance))
(defrun (lg pendown ()) (setf (pen lg) t))
(defrun (lg repeat (repeat-count code)) (dotimes (i repeat-count) (apply #'run lg code)))

which is closer to the Ruby DSL.

logo-steal-when.lisp has the pre-macro version, and logo-steal-macro.lisp has the defrun'ned version. Happy stealing.

Comments:
I read your post and I thought I'd try my own way. After half an hour I came up with this (note that this actually allows CL to compile, not just interpret) (and note that some names/access methods aren't that well-chosen.. fun of hacks):

http://paste.lisp.org/display/20746
 
OK, this is a perfect place to bring this up. I've seen the "interpreter vs. compiler" examples in the literature, but I've never quite understood if the compilers would work with reading external files with DSL code in them or if they just work for the DSL that's already in the source code.
This was supposed to be for reading external Logo files; would the compiler work with that as well.

Either way, nice job with the macro characters.
 
Of course it would. See the CLHS for `READ', `EVAL', `COMPILE', `LOAD', and their relatives.

http://www.paulgraham.com/diff.html

See point 9.
 
Hey Richard,

That's very slick! I put a link to this post in the Artima discussion section for the article to help folks find their way here.

Toph
 
You wrote:
"The next bump was chopping off the "command" argument from the remainder of the S-expression to call the next run, which left a single argument for the &rest, the argument being a list of the remaining arguments, so that had to be car'ed, and you had to remember to do it everywhere, etc. It's messy."

Not necessarily, you can get by without APPLY even.

One way to do it is:
(defgeneric run-with-command (lg command args))

(defun run (turtle args)
(if (endp args)
turtle
(run-with-command turtle (first args) (rest args))))

and let the DEFLOGO macro generate methods for RUN-WITH-COMMAND.
 
Richard,

I see you are in GA. I wanted to make sure you had seen the following message:

http://www.lispniks.com/pipermail/gardeners/2006-September/001579.html

(Sorry to hijack your comments section but I don't know your email address.)

Thanks,
Erik.
 
b3ZMos Your blog is great. Articles is interesting!
 
A47NQT Please write anything else!
 
Wonderful blog.
 
Please write anything else!
 
actually, that's brilliant. Thank you. I'm going to pass that on to a couple of people.
 
Nice Article.
 
Post a Comment



<< Home

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