Checkers Rules in Lisp

I've recently started trying to wrap my head around the beast that is Lisp. I have to say so far all the rumors are true -- just trying to program in it is enough to twist your brain into seeing problems in a whole new way.

So with that minor disclaimer, I offer you my first semi-useful chunk of Lisp code: a set of functions and macros to generate the valid checkers moves and jumps given a 2-dimensional grid representing the current position. I even exported the source from Emacs with syntax highlighting. Ooooh. Ahhhh.

(defvar board
  (make-array
   '(8 8)
   :initial-contents
   '(( 1  0  1  0  1  0  1  0)
     ( 0  1  0  1  0  1  0  1)
     ( 1  0  1  0  1  0  1  0)
     ( 0 -1  0  0  0  0  0  0)  ;; piece is out of place
     ( 0  0  0  0  0  0  0  0)  ;; to demonstrate jump
     ( 0  0  0 -1  0 -1  0 -1)
     (-1  0 -1  0 -1  0 -1  0)
     ( 0 -1  0 -1  0 -1  0 -1))))

(defvar *size* 8)
(defvar *red* 1)
(defvar *white* -1)
(defvar *empty* 0)
(defvar *red-piece* 1)
(defvar *white-piece* -1)
(defvar *red-king* 2)
(defvar *white-king* -2)

(defvar *side* *red*)

(defun get-p (x y)
  (aref board y x))

(defun set-p (x y p)
  (setf (aref board y x) p))

(defun is-my-piece (p)
  (= p *side*))

(defun is-my-king (p)
  (= p (* 2 *side*)))

(defun is-mine (p)
  (or (is-my-piece p) (is-my-king p)))

(defun is-opp (p)
  (is-mine (- p)))

(defun is-empty (p)
  (= p 0))

;; (multi-loop ((for y from 0 to 7)
;;              (for x from 0 to 7))
;;             (print (list x y)))
(defmacro multi-loop (loop-clauses body)
  (if (null loop-clauses)
      body
      (let ((clause (car loop-clauses)))
        `(loop ,@clause do
            (multi-loop ,(cdr loop-clauses) ,body)))))

;; (each-square (x y p) body)
(defun %each-square (f)
  (multi-loop
   ((for y from 0 below *size*)
    (for x from 0 below *size*))
   (let ((p (get-p x y)))
     (if (= (mod (+ x y) 2) 0)
         (funcall f x y p)))))

(defmacro each-square ((x y p) body)
  `(%each-square (lambda (,x ,y ,p) ,body)))

;; (each-square-for-side (x y p) body)
(defun %each-square-for-side (f)
  (multi-loop
   ((for y from 0 below *size*)
    (for x from 0 below *size*))
   (let ((p (get-p x y)))
     (if (and (= (mod (+ x y) 2) 0)
              (is-mine p))
         (funcall f x y p)))))

(defmacro each-square-for-side ((x y p) body)
  `(%each-square-for-side (lambda (,x ,y ,p) ,body)))

;; (each-jump-from x y (mx my nx ny) body)
(defun %each-jump-from (x y f)
  (let ((p (get-p x y)))
    (multi-loop
     ((for dy in (if (is-my-king p)
                     (list *side* (- *side*))
                     (list *side*)))
      (for dx in (list *side* (- *side*))))
     (let ((mx (+ x dx))
           (my (+ y dy))
           (nx (+ x dx dx))
           (ny (+ y dy dy)))
       (if (and (>= nx 0)
                (< nx *size*)
                (>= ny 0)
                (< ny *size*)
                (is-opp (get-p mx my))
                (is-empty (get-p nx ny)))
           (funcall f mx my nx ny))))))

(defmacro each-jump-from (x y (mx my nx ny) body)
  `(%each-jump-from ,x ,y (lambda (,mx ,my ,nx ,ny) ,body)))

;; (each-move-from x y (nx ny) body)
(defun %each-move-from (x y f)
  (let ((p (get-p x y)))
    (multi-loop
     ((for dy in (if (is-my-king p)
                     (list *side* (- *side*))
                     (list *side*)))
      (for dx in (list *side* (- *side*))))
     (let ((nx (+ x dx))
           (ny (+ y dy)))
       (if (and (>= nx 0)
                (< nx *size*)
                (>= ny 0)
                (< ny *size*)
                (is-empty (get-p nx ny)))
           (funcall f nx ny))))))

(defmacro each-move-from (x y (nx ny) body)
  `(%each-move-from ,x ,y (lambda (,nx ,ny) ,body)))

;; display all moves from this position
(each-square-for-side
 (x y p)
 (each-move-from
  x y
  (nx ny)
  (print (list x y nx ny p))))

;; display all jumps from this position
(each-square-for-side
 (x y p)
 (each-jump-from
  x y
  (mx my nx ny)
  (print (list x y mx my nx ny p))))

Lisp, Agility, Readability

I recently had the opportunity to witness a curious dialogue on the mailing list for a local user group I participate in. The original poster, a public devotee and evangelist for Agile development practices, posted an announcement to the group for an upcoming Lisp workshop. A responder immediately threw down the gauntlet – How can you possibly be advocating Lisp as a development language, when Agile is so much about code readability? Doesn't Lisp encourage some of the most unreadable code on the planet? Doesn't Lisp stand for “Lots of Irritating Superfluous Parentheses?” Doesn't Lisp ... ?

I thought about this challenge for a minute, and had an immediate sense of both the rightness and wrongness of it. After all, haven't we all beaten our heads against the wall for days trying to debug some Rails code, only to realize that the answer was buried deep in some “magic” meta-programming hook? Or spent the afternoon hunting down the documentation for some obscure method that's throwing an annoying runtime exception, only to discover that our framework kindly generated it for us at compile time based on some esoteric configuration parameter? Lisp programs seem to represent the pinnacle of this kind of self-generating, self-manipulating metacode, and they can be damned hard to wrap your head around.

At the same time, isn't it hard to beat that sublime feeling of joy you experience when you write that minimal amount of declarative code, and everything Just Works? When you can alter some piece of metacode at the global level to effect an entire architectural change, without touching a single line of code throughout your entire application? Surely there is something deeply right about these kinds of abstractions that allow us to communicate at the level of meaning, as opposed to mechanics – to separate the why of a piece of software from the how.

It struck me then that we operate under two very different senses of the word “readability,” often slipping and sliding back and forth between the two without realizing it. To caricature them down to their essence, allow me to call them mechanical readability, and semantic or intentional readability. Mechanical readability is achieved when a piece of code clearly communicates what it does, whereas semantic or intentional readability is achieved when a piece of code clearly communicates what it means. And there's the rub – clearly these two concerns are constraining us constantly, tugging at each other from opposite directions, nearly always forcing us to sacrifice one for the other in any given instance. What's the answer? Can they be harmonized into some greater concern that preserves them both?

I don't think they can be harmonized exactly, but I do think there is a bit of sound earned wisdom that applies here – a jewel in the crown of the software developer's craft. Without trying to be too scientific or dogmatic about it, it might go something like this:

• When addressing lower layers of abstraction, strive for mechanical readability.
• When addressing higher layers of abstraction, strive for semantic readability.
• Within a given layer of abstraction, strive to decouple the mechanical and intentional concerns as much as possible.

So where does that leave us as far as Lisp's alleged agility? Well, in truth, Lisp actually does address mechanical concerns far better than you might think. But its ability to express the semantic level of software is where it clearly shines. The temptation is to become obsessed with the semantic approach, to the point of obfuscation of the plain, simple mechanical tasks your software needs to perform. This is possibly the greatest temptation programmers face when given powerful meta-programming facilities. There's nothing quite so frustrating as having to work within forced abstractions.

However, don't assume a more “straightforward” mechanical style will clarify your code either. The reason your DSL doesn't flow well enough, or map onto your domain well enough, might not be that it's too abstract. It might just be the wrong abstraction. The semantic realm is a very conceptual, philosophical sort of beast. You won't write better abstractions by learning more about technological wizardry, but by practicing the dark art of simple, clear thinking.

Ultimately, it's the right ideas that set really great software apart.