trystan.org

After using Lisp nearly every weekend for about 6 months now I feel I have a handle on the major features such as macros and the CLOS. Both are very interesting as macros provide a meta-programming facility missing from many languages and the CLOS is a very interesting take on OOP.

Even though most of my OOP experience in in C++, I was able to warm up to the CLOS and the notion of generic functions fairly quickly. An OOP zealot my criticize Lisp’s lack of strict data encapsulation but via explicit programming techniques in Lisp, i.e. writing your own accessors, one can communicate the intent of data hiding sufficiently. Also, let’s not forget that there are plenty of ways to break encapsulation in most other OO languages as well.

In general, the draw to Lisp for me is the reported flexibility and extendability of the language. I love programming by building abstractions and I don’t like a language that restricts how I choose to abstract a concept. After becoming quite advanced in C++ I ran into this issue often. Usually, it involved me banging my head against the type system that wouldn’t let me create the abstractions I wanted. With lisp being very lambda expression centric, this is less of an issue because you can build up abstractions via higher order functions and closures rather than types. As an aside, you can also achieve true data encapsulation this way. However, there are still some cases where type abstractions are preferable or neccessary over functional abstractions. But Lisp has a type system and the language is so damn flexible that I should be able to build whatever kind of abstraction I want right? Well, yes and no.

First, let me touch on my motivation for really wanting good user defined types. In many, if not most, situations I believe dynamic types are fine, even for large programs, as long as a facility exists to assert a certain type for a function that can only act on that type. Lisp has that facility. In many cases, you don’t care what the type is and it provides motivation to write elegant and general code that is safe for all types when possible. However, one place that I feel quite compelled to lock things down via type abstractions is at a package/module interface level. For instance, I may have a function that is exported from a package that is expecting another function as an argument. The argument function is defined by the user of the package but it must have a particular signature as expected by the package. Therefore, I want to define a type that represents the set of all functions with a particular signature. This can not be accomplished in Lisp, at least as far as I can tell.

But wait, isn’t this the most extensible language on the planet? Perhaps, but extending or replacing an entire type system is far from trivial. When I hit this wall, I said to myself “hmm, this must have bothered someone before. I bet there’re a bunch of type systems out there that I can just asdf into my Lisp environment.” Sadly, it seems it doesn’t bother people quite that much.

This brings us to a final comment about a language called Qi that is built on top of Lisp. It’s a 7k line or so Lisp program that implements new language features on Common Lisp. These features include pattern matching and…drum roll…an optional static type system. I have yet to delve into this language much but on the surface it looks very promissing.

My first foray into Lisp is finally producing some viewable results. The images below, click to enlarge, are mazes generated by a random, recursive, spatial subdivision algorithm implemented in common Lisp using an Eclipse/CUSP environment. The 2D mazes are rendered using the lispbuilder bindings to SDL. The implementation of the generation algorithm will produce data for mazes of any number of spatial dimensions. However, visualizing anything beyond 3D is challenging and the current code will only render 2D mazes. I have no plans to write visualization code for n-dimensional spaces. The ability to generate mazes in arbitrary dimensions was more or less just a ‘Lispy’ exercise.

The maze on the left is 80×80 cells and the other is 320×200 cells. Both are rendered on a 640×480 surface, hence the scaling. Diagonal moves are allowed in the mazes. All areas of the maze should be accessible from any starting point, usually via multiple paths. I intend to use these mazes an environments for experimenting with various AI agents. The Lisp source is available at http://code.google.com/p/compu-psy-research/.