How Basic Common Lisp Techniques Can Improve Code Configurability, Maintainability, and Reuse

“Lisp programs inflate libraries with functions whose utility transcends the application that produced them. The list, Lisp’s native data structure, is largely responsible for such growth of utility. The simple structure and natural applicability of lists are reflected in functions that are amazingly non-idiosyncratic…. It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.” — Alan J. Perlis

You might have started out with Peter Seibel’s Practical Common Lisp. You thought of yourself as being an experienced coder, so you skimmed it quickly, mainly taking away the point that Lisp really is unusually expressive and powerful. But after sitting down at the REPL prompt you succeeded at only kludging together ugly imperative style programs. So you slowed down and worked through half or more of a more straight forward tutorial. This lead to a pet project that started innocently enough, but that soon spun out of control and got uglier and uglier as you took more and more shortcuts just to get things to work. Maybe you dipped into some more advanced books and solved some clever problems, but you want to start coding something real because you’re beginning to lose interest. As Duncan Kenzie said, “any time you have something that can give you good success early on, it helps to build momentum and get into more complex things.” Without something resembling a successful project, you’re liable to give up on Lisp and go off and tinker with Python or Ruby instead. This article is written in hopes of preventing such a fate for the would-be Lisp programmer.

What we’re going to do is demonstrate how the plain vanilla Common Lisp list can adapt to just about any data structure you can think of. We’re going to use a simple list to write pseudo-code that is designed to be as readable as possible– then we’ll build up on our core language elements until we can actually run our pseudo code. We’re going to do all the things that the Lisp experts have bragged about (and that you’ve maybe failed to achieve on your own) and we’re going to show that you don’t have to be a genius to make this work for you. In fact, the most difficult technique we’re going to use is recursion on trees and lists– something that most Lisp texts tend to confront you with fairly quickly anyway. We’ll see that while it may take us a little bit longer to work through a problem than it would, say, in a language that we’ve already mastered, it will all be worth it for the additional configurability we get in the process.

The Problem: Traveller World Generation

“The referee has the responsibility for mapping the universe before actual game play begins. The entire universe is not necessary immediately, however, as only a small portion can be used at any one time.” — Traveller Book 3

Whenever I’m experimenting with a new technique I like to do something completely and pointlessly fun. The less “real world” applicability, the better. (Of course, nine times out of ten, I end up applying the techniques I learn on a real project later on, anyway.) For this project we’ll dig back into the pencil and paper gaming scene of the late seventies and look at the world generation sequence of the first science fiction role playing game. The game Traveller debuted in 1977. It featured a generic space opera setting that was vaguely reminiscent of classic sci-fi works such as Dune and the Foundation series. Actually, it didn’t originally come with a fleshed out setting at all: the “referee” was supposed to randomly generate one for the players to explore. Back in the day, this meant hours of rolling dice and penciling in obscure symbols on retro-nerdy xerox copies of professional-looking interstellar “TAS forms.”

You can get an overview of the process by looking at this pseudo code snippet. Size represents the world’s planetary diameter in thousands of miles. You roll two six sided dice and subtract two to determine this property. (A zero here signifies a “world” that centers in and around an asteroid belt.) To determine the Atmosphere code for a world, roll 2d6, subtract 7, and add the value we determined for Size. Just as Atmosphere is influenced by Size, so is the Hydrographics code influenced by Atmosphere. Likewise, Government type is influenced by the Population code and Law Level is influenced by the Government type. Note that, the Population of a world is completely independent of the world’s environment. You can end up with an airless rock-ball with a population in the billions right next to a garden world with a population in the hundreds. While many Traveller players complain that such results are silly, others took great delight in attempting to come up with plausible explanations for such anomalies. In any event, referees are encouraged to throw out any results they don’t like, and there are only so many worlds that can be successfully managed in a real game anyway.

To write a program to take care of all of this is pretty trivial. All we need is a way to pull the rule expressions out of our pseudo-code list. Once we have the expression, we need to massage it so that the “2d”‘s are replaced with randomly generated die-rolls and the field references are replaced with their current value. Once we’ve made such a pass over our expression list, were left with a simple arithmetic problem. Writing a recursive function to perform that calculation is pretty straight forward, and once we put all of these pieces together in our create-world routine, we have a working proof of concept. The following code snipped from the REPL prompt demonstrates our program in action:

CL-USER> (get-rule (third *worlds*))
(|2D| – 7 + ATMOSPHERE)
CL-USER> (massage (get-rule (third *worlds*)) ‘(1 2 3 4 5 6))
(11 – 7 + 2)
CL-USER> (massadd *)
(6)
CL-USER> (create-world)
(2 5 6 3 6 2)

We’re glossing over a few details here, but if you have a little experience working with Lisp then you should have a pretty good idea of how to implement the above. The get-rule function returns a list containing everything after the -> symbol in an item from our list of pseudo-code expressions. The massage function is a little trickier. While it’s trivial to replace occurrences of |2D| with the results of simulated die rolls, to substitute the correct numbers for the reference Atmosphere we’re going to need to pass along a list such as (1 2 3 4 5 6) above representing each of the world code values. The code will have to pull the correct value from the list and then substitute it for the ATMOSPHERE tag. Massadd moves through the list replacing occurrences of [0-9] [+-] [0-9] with an integer. The create-world function starts with a blank world description (0 0 0 0 0 0) and then cycles through each position replacing it with the results of evaluating massage and massadd with the corresponding line of pseudo code. Simple!

Notice that everything we’re doing is in terms of cycling through lists. Everything we do can be conceived of in terms of abstract operations on lists. Each function that we write to accomplish the above is fairly straight-forward… but this a completely alien approach when compared with how we tend to do things in more imperative languages.

There’s More To It Than That

Okay, it’s actually a little more complicated than what I’ve described so far. This is the seventies, we’re talking about here! This is RPG’s, even…. You aren’t having real fun unless you’re rolling dice and looking things up on charts and tables. (See this pseudo code file for a better idea of what we’re dealing with.) For Starport type and for checking for the existence of Bases and Gas Giants, we need to roll two dice and look up the result on a chart. To find out the TechLevel, we need to cross reference most of our World codes on a table and add up the values. There’s probably a more concise way to phrase this, but this was about as simple as I could make it. I came up with a simple way to inline all but two of these tables with their respective rules. The :choose directive takes a number parameter and returns the nth item on a list. The :table directive does the same thing in a more verbose (and more flexible) manner by looking up a value in an associative list. Also, we’re going to have to make sure that some of our world codes fall within a specified range.

CL-USER> (masschoo ‘(:choose 5 [ABCDEFGHIJ]))
(E)
CL-USER> (massage ‘(1d + :choose Size + 1 [22111000000]) ‘(A 2 0 0 0 0 0 0 0 0 0 0))
(4 + :CHOOSE 2 + 1 [22111000000])
CL-USER> (massadd *)
(4 + :CHOOSE 3 [22111000000])
CL-USER> (masschoo *)
(4 + 1)
CL-USER> (massadd *)
(5)

In the above example we see the new masschoo fuction demonstrated from the REPL prompt. First we “choose” the fifth item from a string contained inside square brackets. Then we step by step break down a more complex piece of pseudo-code step by step. First we “massage” the die roll and substitute a 2 for the Size tag. Next we replace the 2 + 1 with a 3 using our previously written massadd function. Then we choose the third item from our string of results. And finally we “massadd” the resulting list to get our final result of a 5. Note that the massadd and masschoo functions are easily tested from the REPL prompt and that it’s trivial to come up with test cases that prove they work correctly. And now that we have them worked out, they are so generic that they could easily be applied to totally different projects. If you’re still wondering when you’re going to get around to experiencing the much-vaunted benefits of code reuse in your OOP applications, then maybe Lisp can provide you with a model for achieving it a lot sooner!

Good News, Bad News, How to Reinvent the Wheel!

It seems like every project has one thing that is completely unanticipated. You know… the kind of nightmares that cause you to reflexively multiply all of your coding estimates by a factor of 5. (Check out this pseudo code file to see what we really needed to be able to work with from the start.)  In this case, just as I thought I had completed my project in record time (and with hardly any short-cuts or kludges even) I reread the rules and to find out that I’d missed some essential logic in the pseudo code. I actually needed to be able to handle conditional logic in the same style with which I’ve dealt with table look ups and die rolls…. Now if I’d known I was going to do this much work, I probably would not have started the project quite this way. I don’t know what I’d have done… maybe I wouldn’t have started the project at all. Anyways, I decided to suck it up and hack through the problem anyway. I just about ended up doubling the code size for the project in the process, but I think some of that is due to the fact that I was reinventing the wheel in places. Maybe if I was more familiar with the built-in functions of Common Lisp, then I might have had an easier time.

CL-USER> (massif ‘(:if [ 0 = 0 ~ 5 ~ 42 ]))
(5)
CL-USER> (massif ‘(:if [ 2 = 0 ~ 5 ~ 42 ]))
(42)
CL-USER> (massif ‘(:if [ 2 = 0 ~ 0 ~ 5 – 7 + 6 :if [ 6 ranges from 3 to 8 ~ – 4 ] ]))
(5 – 7 + 6 :IF [ 6 RANGES FROM 3 TO 8 ~ – 4)
CL-USER> (massif *)
(5 – 7 + 6 – 4)
CL-USER> (massadd *)
(0)
CL-USER> (massif ‘( (:if [ 2 <= 5 ~ AA ] :if [ 3 = 6 ~ BB ] :if [ 7 in ‘[2579] ~ CC ]) ))
((AA CC))

Here we see my (perhaps half-baked) list oriented “embedded if” concept in action. I wanted to avoid introducing nested parentheses to the pseudo code due to all the hard feelings they seem to generate in non-lispers. I used the ~ character to represent the argument separator. So the first example expresses “if 0 equals 0 then return 5 otherwise return 42.” Of course, we may need to return expressions… and we may even need to return expressions containing more :if directives. Finally, we may need to return a list of items, with each item associated with their own conditional that determines whether or not the show up in the list. Coding all of this didn’t require any advanced techniques beyond the usual recursion on lists and trees, but it did require a lot of tedious work to get a function that could handle all of the various cases. Whenever I expend this much effort on something like this I always assume I’m overlooking something obvious, but the time it would take to figure out what that was exactly might (in this case anyway) take longer to figure out than it would to just follow my original premises to their logical conclusion. Not as pretty as I would like, but you can always expect a few rough edges when you’re trying to pick up a new language.

Here we have a demo of the final program:

CL-USER> (create-world)
(B 8 8 1 8 6 4 – 5 ~ S G (RI))
CL-USER> (create-world)
(A 4 5 0 4 3 0 – 12 ~ S G (NI PO DE))

In that last result there, you can see the that we have a Starport code of A, Size 4, Atmosphere 5, Hydrographics 0, Population code 4, Government code 3, Law level 0, Tech level 12… there’s no Naval Base, but there is a Scout Base and a Gas Giant. Finally we have Trade codes Ni, Po, and De. Each position in the list corresponds to a result derived from a line of pseudo-code.

Conclusion

Lets take a quick look at what we got using this approach to solve our problem. (Here’s the complete code listing.) First, the program logic for the overall thrust of the application fits neatly into a single screen. This is extremely handy if you want to attempt to keep the entire program in your head at once. (Note that habits developed while working with relational databases and modern OOP languages work against this outcome: those tools train you to break each piece up into their own separate table or code file.) The pseudo code practically eliminates the need for code comments to document what’s going on. Not only are we at the opposite extreme of Perl’s notorious “right once read never” methodology, but we can also make complex changes to the behavior of the application without writing new functions. We can add new “properties” to our world objects without modifying any class definitions and we can open up our program to customization– even to people with an innate fear of parentheses! Finally, the list processing routines can be reused in completely different applications. In fact, the bulk of our code is more like abstract utilities than anything else.

So we have realized most of the promises of the Lisp advocates. Paul Graham was right when he said that “in Lisp, you don’t just write your program down toward the language, you also build the language up toward your program.” And notice that we could do it without using the hard-core techniques like closures and macros that get all the press. We could do it just using recursion and the built-in features of the humble list. The key to our approach was not to think of our processes in terms of tables or objects or any other abstraction… but to instead try to express the problem as closely as possible to a natural pseudo-code notation. We then built up our language to the point where we could actually execute the pseudo code. While it was challenging to work out a few of the list processing routines, integrating our new language elements into the pseudo-code interpreter turned out to be a snap.

This approach may not be suited to everything you might want to code, but if readability, code reuse, and configurability are really important to you, this might be the way to go. At any rate, programming this way is a lot more fun!

Okay… questions anybody? Yes… you over there in the “I grok Spock” shirt….

“But what about speed and efficiency?”

It may appear inefficient to make so many passes across each “rule” list in this example. If speed matters, what we can do is alter our approach somewhat by developing a macro that transforms a pseudo code rule into a function. These could then be compiled at run time, and our code will run about as fast as if it were all written directly in Lisp.

Yes. Thank you. Okay, you over there with the trendy Buddy Holly glasses….

“What’s the next step in developing the application?”

Assuming that the premise of this program is not insane, the next step would be to write a set of thorough unit tests for our existing language elements. Once we have the functions working correctly for all of the oddball cases, then we should look at adding some additional elements that improve the expressiveness of our custom pseudo code language. In particular, I would like to have a :table directive that could process more complicated table look ups. (I don’t like having to have a separate associative list defined for the Government Tech and Starport Tech modifiers tables.) Another thing to do is to carefully read the Common Lisp specification to help eliminate anywhere that I’m inadvertently reinventing the wheel. We’ll want to look at our functions and try to determine if there’s a way to make any of them even more generic than they already are so that when we pull them out into a utility file they’ll be more useful in other programs. Finally, we’ll want to look at other world generation procedures and see if they can be implemented in our pseudo code without having to extend the language anymore. Once we get that far, we know we’ve accomplished something.

Okay… you in the turtle neck there….

“Yeah, uh, can’t I program in a similar style in the language I aleady use?”

Yes you can. I’ve coded similar applications in other languages myself. The thing is, I started by googling for a utility that could evaluate strings into code. It took me maybe a few minutes to extend the application with my own “instant if” function and things like that… but there’s still this chunk of code there that I shamelessly munged off of someone else and that I might not completely understand. In other languages you’re much more likely to hack out a kludgey mess that only works well for a single class of problems– so unless you’re really good you’ll lose out in the code reuse department. When you work with Common Lisp, you get a code evaluator out of the box for free and you’re working with the overall idiom of the language. You might spend a little more time working through some of your custom functions, but you end up with something that is completely transparent, understandable, and generically applicable.

Attempting this in other languages, there is a tendency to create applications in which you have an evaluator that’s tacked onto (and hardwired for) a bunch of other code. Notice that the way we worked here, we didn’t end up with an evaluator that was tacked on to a bunch of other stuff. The evaluator was our program. Once you begin to think in these terms, you can begin to develop applications which blur the lines between “data” and “code logic” in a much more creative manner. It is this property that makes coding in Lisp so much fun.

Update 8/30/07: A lisp hacker has rewritten my code to take advantage of more of the language’s native features– eliminating a great deal of code in the process. While the new iteration of the pseudo-code might be less non-lisper friendly than what I would prefer, you can still see a few places where I coded a function that already existed in the language.

Update 8/31/07: I respond to feedback on this article here.