When Domain Specific Languages Attack!

Posted on June 4, 2011 by Tommy McGuire
Labels: notation, lisp, books, programming language
Or, why I don't particularly like Common Lisp

Once upon a time, many years ago, Common Lisp was my favorite programming language. This was mostly when I was taking upper division classes at UT Austin, and mostly due to the AI faculty in the department, who were excellent teachers. In fact, I recall getting a laugh out of Ham Richards, when he read my answer to one of the questions on the final of the C++ class he was teaching: The question was on C++ operator precedence, and my answer included the comment, "I want my Lisp!"

Anyway, enough about that. I have recently been meandering through Land of Lisp: Learn to Program in Lisp, One Game at a Time!, by Conrad Barski (check out the sample chapter, with the most violent programming example ever put into a textbook). (I've been meaning to learn something about Clojure, and I had nothing better to do.) The book gets a big thumbs up. It is entertaining, the cartoons (especially those that go with the evolution simulation) are perfect, the games bring back a surprising number of memories, and I'm picking back up my Lisp. Fortunately or unfortunately, Barski uses Common Lisp, which is also bringing back some less pleasant memories.

What happens when an embedded domain-specific language escapes into the general language in which it is embedded? The DSL probably doesn't fit in with the general language, stylistically, syntactically, or semantically, and the result may not be very pretty.

One example that is less problematic involves parsing combinators; for one thing, parsers are usually isolated from the remainder of the program due to modularity concerns; for another, a parser isn't generally driving the remainder of the program.

On the other hand, Common Lisp has three more problematic DSLs:
The first of these is built for the generic settor, setf. The first argument to setf is a pattern, identifying a location in a data structure which is to be updated. This pattern can use the ever-present car and cdr, as well as things like structure field accessors. It does not allow all general programs, and I refuse to figure out what parts can be used, what cannot, and why.

The second and the third are the reason for this post. Barski admits loop and format are not pretty in the two chapters dedicated to them, and shows a single-function game in the chapter dedicated to the latter. This game, robots, is a third-person, avoid-the-monsters thing, that I recall as being reasonably entertaining. Without much ado, here's the code:
(defun robots ()
(loop named main with directions = '((q . -65) (w . -64) (e . -63) (a . -1)
(d . 1) (z . 63) (x . 64) (c . 65))
for pos = 544
then (progn (format t "~%qwe/asd/zxc to move, (t)eleport, (l)eave:")
(force-output)
(let* ((c (read))
(d (assoc c directions)))
(cond (d (+ pos (cdr d)))
((eq 't c) (random 1024))
((eq 'l c) (return-from main 'bye))
(t pos))))
for monsters = (loop repeat 10 collect (random 1024))
then (loop for mpos in monsters collect (if (> (count mpos monsters) 1)
mpos
(cdar (sort (loop for (k . d) in directions
for new-mpos = (+ mpos d)
collect (cons (+ (abs (- (mod new-mpos 64) (mod pos 64)))
(abs (- (ash new-mpos -6) (ash pos -6))))
new-mpos))
'<
:key #'car))))
when (loop for mpos in monsters always (> (count mpos monsters) 1))
return 'player-wins
do (format t "~%|~{~<|~%|~,65:;~A~>~}|"
(loop for p below 1024 collect (cond ((member p monsters)
(cond ((= p pos) (return-from main 'player-loses))
((> (count p monsters) 1) #\#)
(t #\A)))
((= p pos) #\@)
(t #\space))))))
If you can figure out what is going on there, you're a better man than I. Even if you're not a man.

My complaints: loop has absolutely nothing to do with the rest of CL, it has a very baroque interface, and enough features that I feel no urge to analyze or remember them all. format, on the other hand, is just simply loony.

I spent some time unraveling robots, and came up with this, which is more understandable but which still contains the complexity of loop and format:
(defparameter *directions* '((q . -65) (w . -64) (e . -63)
(a . -1) (d . 1)
(z . 63) (x . 64) (c . 65)))

(defparameter *initial-position* 544)

(defparameter *n-monsters* 10)

(defun initial-monsters () (loop repeat *n-monsters* collect (random 1024)))

(defun read-move ()
(format t "~%qwe/asd/zxc to move, (t)eleport, (l)eave:")
(force-output)
(read))

(defun monster-wrecked (mpos monsters) (> (count mpos monsters) 1))

(defun new-monster-position (pos mpos wrecked)
(labels ((player-distance (new-mpos) (+ (abs (- (mod new-mpos 64)
(mod pos 64)))
(abs (- (ash new-mpos -6)
(ash pos -6))))))
(let ((possible-moves (loop
for (k . d) in *directions*
for new-mpos = (+ mpos d)
collect (cons (player-distance new-mpos) new-mpos))))
(if (not wrecked) (cdar (sort possible-moves '< :key #'car)) mpos))))

(defun new-monster-positions (pos monsters)
(loop for mpos in monsters collect
(new-monster-position pos mpos (monster-wrecked mpos monsters))))

(defun all-monsters-wrecked (monsters)
(every (lambda (mpos) (monster-wrecked mpos monsters)) monsters))

(defun board-contents (pos monsters)
(loop for p below 1024 collect
(cond ((member p monsters) (if (monster-wrecked p monsters) #\# #\A))
((= p pos) #\@)
(t #\space))))

(defun robots ()
(loop named main
for pos = *initial-position* then
(let* ((c (read-move))
(d (assoc c *directions*)))
(cond (d (+ pos (cdr d)))
((eq 't c) (random 1024))
((eq 'l c) (return-from main 'bye))
(t pos)))
for monsters = (initial-monsters) then
(new-monster-positions pos monsters)
when (all-monsters-wrecked monsters) return 'player-wins
when (member pos monsters) return 'player-loses
do (format t "~%|~{~<|~%|~,65:;~A~>~}|" (board-contents pos monsters))))

Now, bizarro DSLs are not limited to Common Lisp (Olin Shivers, who also wrote scsh and more importantly the acknowledgements in its manual, wrote a paper about a suitably hideous version of loop in Scheme) but Common Lisp is the only example that I know about of several in one place, and of a culture that seems to really enjoy creating them.

Postscript

2000/07/24 Per Bother infects Scheme with a setf-alike.
active directory applied formal logic ashurbanipal authentication books c c++ comics conference continuations coq data structure digital humanities Dijkstra eclipse virgo electronics emacs goodreads haskell http java job Knuth ldap link linux lisp math naming nimrod notation OpenAM osgi parsing pony programming language protocols python quote quotes R random REST ruby rust SAML scala scheme shell software development system administration theory tip toy problems unix vmware yeti
Member of The Internet Defense League
Site proudly generated by Hakyll.