Some Lisp suggestions

Posted on June 17, 2011 by Tommy McGuire
Labels: data structure, software development, notation, lisp, programming language
I am most definitely not a Lisp guru, but after finishing Land of Lisp, I have a couple of suggestions that might reduce the general imperviousness of Lisp code. In my opinion, most of the antipathy towards Lisp's parentheses is a red herring; those parentheses merely express the structure of the code---which is present but implicit in any code---while the actual problem is that the code is bad, a problem which is exacerbated by the explicit structure.

defstruct is your friend! Use it!

Allegedly, J.B.S. Haldane once described what a lifetime of biology had taught him about God as "an inordinate fondness for beetles". One thing that frequently bothers me about code in untyped languages in general, but specifically in Lisp, is an excessive focus on representations of data, rather than the structure of data. Rather than identifying and building on an abstract data structure, the programmer will simply put the components of data into a hash table or a list and access the components using raw hash or list functions.

For example, this is a function for Land of Lisp; below I rewrote the function using defstruct to reify the game tree (tree-node) and moves (attacking-move and passing-move). I also slapped some color on the two functions to emphasize the corresponding functions.
(defun limit-tree-depth (tree depth)
(list (car tree)
(cadr tree)
(if (zerop depth)
(lazy-mapcar (lambda (move)
(list (car move)
(limit-tree-depth (cadr move) (1- depth))))
(caddr tree)))))

(defun limit-tree-depth (tree depth)
(labels ((limit-depth-move (move)
(let* ((next-tree (limit-tree-depth (get-tree move) (1- depth))))
(if (passing-move-p move)
(make-passing-move :tree next-tree)
(make-attacking-move :src (attacking-move-src move)
:dst (attacking-move-dst move)
:tree next-tree)))))
(make-tree-node :player (tree-node-player tree)
:board (tree-node-board tree)
:moves (if (zerop depth)
(lazy-mapcar #'limit-depth-move
(tree-node-moves tree))))))

Now, the first function is markedly shorter than the second (although part of that is my apparent fondness for large names). However, unless you are fond of remembering that the car of one kind of list identifies a player in a node of the game tree, while the list of subsequent moves is the caddr, and the car of another kind of list identifies the aggressor and defender of a move (and implicitly whether it is an attacking move or a passing move), I respectfully suggest that the second might be preferable. In fact, a significant chunk of the length difference is that I have used different structures for the passing move (which only has the subsequent game tree node) and the attacking move (which also has the attacking and defending board positions).

Abstraction is good, too.

There are those in the functional programming community who identify function with abstraction. If I understand them correctly, they use the two words interchangeably. I believe that is a very grave mistake, since it would mean that the lambda expression in the first example is, in some sense, the same as the use of the limit-depth-move function. As for me, if I had to identify abstraction with a single technique, I would link it to naming; to my mind, the first lambda expression is an implementation detail that clutters up the building of the moves of the new game tree node, while the second version (as hideous as the labels construct is) provides the function as an identifiable, named, meaningful chunk.

If you compare typical Lisp code with typical code in a language from the ML family, I think you'll find that Lisp code has more functions built of multiple steps, and greater nesting, than the ML code; ML code will more likely use let or where to break out identifiable functions and values. As a result, in my opinion, the ML code is consistently easier to read.

After some further thought, I suspect the emphasis on representations is a result of working top-down to design the program. Further, I am almost positive that the more complex code and lack of abstraction are also a symptom of the same approach. Top-down design tends to be fine down to a certain level, at which point the code appears "simple enough". Further work, however, makes the code more complex but without redesigning the existing structure. A bottom-up approach almost calls for the identification of abstractions for working with the next level of code. (On the other hand, a bottom-up approach usually requires more work, since it involves traveling towards a destination without being sure of the best direction. Also, it can suffer from the same problem at the other end of the program, where the higher structure of the code seems simple enough until it needs elaboration to complete the solution.)

I do not want to pick on Land of Lisp unfairly. It is a very good, and entertaining, book. The code examples are, overall, very clean and nice. However, reading it reminded me of the difficulties I have had with other Lisp (and other dynamically-typed code) in the past.

[Edit: Typo and second-to-last paragraph fixed due to comments from reddit. Thanks!]
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 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.