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
turns into
which will match on
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
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
the above methods turn into
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.
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.
