Pascal Costanza's Highly Opinionated Guide to Lisp

http://www.pascalcostanza.de/lisp/guide.html
(v1.23, 2/9/2002, changelog.txt)

Copyright © 2002 Pascal Costanza. All rights reserved. Permission to copy, transmit, and store this work, unmodified and in its entirety, is granted.

You can use this document as an online reference or print it out. All links are represented as explicit URLs that will be retained when printed. Please send any kind of feedback to costanza@web.de.


Part I: Background

I always wanted to be a lumberjack!
- Monty Python

1. Why am I writing this introduction?

My current situation is as follows. I have worked with the Java programming language for the last seven years, mainly in projects in which extensions to the Java programming language have been developed. Before that I have mainly used languages from the Wirth family (mainly Modula-2 and Oberon), so in the beginning I was quite happy with some of the advantages that Java has over the latter languages.

During the past year I have come to realize that Java is still a very (indeed extremely) limited programming language, so I started to look at alternatives. Because of my involvement with the Feyerabend project (http://www.dreamsongs.com/Feyerabend/Feyerabend.html), Lisp naturally came about as one of those alternatives. (Richard Gabriel started the Feyerabend project, and he was also one of the people that kicked off the Common Lisp standardization in the beginning of the 1980's.)

Although there are a lot of nice programming languages available (for example, in alphabetical order: gbeta, Objective CAML, Python, Ruby), I have quickly got the impression that Lisp is, in some sense, the mother of all languages. The main reason for this statement is that Lisp includes a complete theory of computation by treating code and data uniformly. (This is more powerful than "just" being Turing-complete. For more information, see the section on the "Technical Background of Lisp" below.) This effectively means that there are no (conceptual) restrictions whatsoever in Lisp: if you can do something in any one language, you can also do it in Lisp. Furthermore, Lisp checks all types at runtime, so no static type system can get in your way.

You can rightfully generalize these observations and state the following: the mindset of Lisp asserts that expressive power is the single most important property of a programming language. Nothing should get in your way when you want to use that power. A programming language should not impose its view of the world on the programmer. It is the programmer who should be able to adapt the language to his/her needs, and not the other way around.

This has a great appeal to me and so I have decided that Lisp is the language of my choice. However, there is a drawback when you decide to start looking at Lisp more seriously: there are no really good introductions into the language available on the net that suited my needs - or at least I haven't found them. Of course, there are some introductions available, but either they are too low-level and try to teach programming for the very beginners, or they are too academic and only touch theoretically interesting topics. What I would have liked to see is an introduction that provides you with enough background information in order to understand the concepts and then gets you going as quickly as possible. (Something like "Lisp for experienced programmers".)

Because I haven't found anything I have had to work through the available stuff on my own. Now, I would like to present a summary of what I have found out in order to ease things for other people.

Why is this introduction called "highly opinionated"? Lisp is a complex language, or rather a family of languages. There cannot be "the one definitive guide" to Lisp. What I present here is what I would have liked to have seen in the first place. Other people probably prefer a different approach. I don't want to write an introduction that provides everything for everyone. I only want to present information that is useful for people like me. At least, this is the material that worked for me, so it might suit other people as well.

Especially, this is not something like "Common Lisp for Dummies in 21 days". You may need several iterations of the material presented here or elsewhere until you actually get the feel of the "Common Lisp experience". (...but I don't have to stress that you need a lot more than 21 days to master any serious language, right? ;)

2. General introduction

Lisp has a long history. It was invented in the 1950's and has continually developed and been improved over the decades. At several stages there have been various dialects of Lisp, so Lisp is indeed not a single language but rather a family of languages. (If you think of languages like C, C++, Objective C, Java and C# as being languages of the same "C-like" family of languages, then you'll be quite close.)

In the 1980's and 1990's, two main dialects established themselves as the only widely available and usable dialects: Common Lisp and Scheme. Scheme was invented in the 1970's by Gerald Jay Sussman and Guy L. Steele as a result of trying to understand object-orientation and incorporate it into Lisp. Scheme essentially introduced lexical closures (as a generalization of objects) and continuations (as a generalization of function calls and message passing) at the conceptual level, and "extreme" optimization of tail calls and tail recursions at the technical level. The nice thing about Scheme is that it is a beautiful diamond with properties that appeal mainly to academics who are looking for truth and beauty (i.e. minimality and orthogonality). However, it misses many practical things that you need in every-day programming and that would spoil the conceptual beauty.


See the following links if you are interested in explanations for some of the terms mentioned above.


At the end of the 1970's, several variants of Lisp were in use. Common Lisp started as a remedy for an exaggerated diversification - a unified version of Lisp with the goal of integrating the advantages of the several Lisps that existed at this time and avoiding the disadvantages. Furthermore, Common Lisp was a big step forward because it also incorporated the lessons learned from Scheme. (Lexical scoping made its way into Common Lisp. Continuations were not included because they turned out to be too complicated for practical use. Optimization of tail recursions didn't need to be standardized because it was a natural progression to use it as an implementation technique.)

So this gives a hint of what to look for when you consider using Lisp today. If you want to do practical "real-world" things you should choose Common Lisp. If you mainly want to do academic research and, for example, want to experiment with continuations, you could also opt for Scheme. Both languages are still in use today and have a strong support from their respective user communities.

I have decided to use Common Lisp for several reasons. Some of them will pop out during the course of this introduction. What I don't like about Scheme is that it is a "right-thing" language that has strong notions about how things should be done. Common Lisp seems to be far more flexible.

However, many publications and descriptions of Scheme also make sense for Common Lisp - for example, descriptions of what lexical closures are - so I have nevertheless included some references to Scheme in the following sections.

(In essence, my message is as follows: it doesn't really matter if you choose Common Lisp or Scheme, it only depends on your specific needs. So just let your gut feelings guide you. In fact, both languages are flexible enough to be used both in research and in the "real world". However, the bulk of my introduction deals with Common Lisp, so if you opt for Scheme you have to look for other places to find introductory material. See the links section below for some pointers.)


A note on how to work through this material: I have tried to make it natural to read this text sequentially. Of course, you are free to skip sections and especially switch back and forth between part I and II. However, some of the later sections require you to have been exposed at least to some example Lisp code. The text includes enough pointers for that purpose.


3. "Executive summaries" of Common Lisp

A good one-page overview of what Common Lisp offers can be found at http://www.lisp.org/table/objects.htm. This description focusses on object-oriented features of CLOS (the Common Lisp Object System that is part of Common Lisp) but also gives a good summary of the functional and imperative features of Common Lisp.

The Common Lisp Language Overview by Xanalys is another good summary to be found at http://www.lispworks.com/products/lisp-overview.html.

4. Some first obstacles

Lisp's history is different from that of other programming languages, especially those of the Algol and C family. Therefore, the Lisp community has developed different notions and terminology at various levels. Here are some clarifications to avoid confusion.

5. History of Lisp

It's remarkable that there is extensive information available about the whole history of Lisp, including Common Lisp and Scheme, in two very well-written papers. At some stages, these two papers even read like crime novels - highly recommended!

(Please don't confuse these with other papers about the history of Lisp by Herbert Stoyan which I have found hard to read and in my opinion come to strange conclusions.)

6. Technical background of Lisp

As I stated before, Lisp includes a complete theory of computation by treating code and data uniformly - and this is one of the main features that makes Lisp so powerful. There are two papers I can recommend that give you a good explanation of what this actually means. (They deal with the concept of "meta-circular interpreters" - don't let the term frighten you, it's not as complicated as it sounds.) IMHO, you should at least read the first one to be able to really appreciate the power of Lisp.

...and, by the way, this article also gives a good description of the basic ("primitive") forms in Lisp.

If you like "The Roots of Lisp" and would like to learn more about meta-circular interpreters you can read a deep discussion and vision of how far you can get with them in the following paper. Alongside, you will learn useful facts about lexical closures, dynamic binding, and the like.

7. Available implementations

You can find a long list of Common Lisp implementations at http://www.lisp.org/table/systems.htm. However, this list doesn't seem to have been updated in a while. Here is a list of implementations to consider IMHO, in alphabetical order.

I have taken a closer look at only some of these implementations and there are probably other ones out there. Many Lisp programmers prefer to use emacs or xemacs as a development environment for Lisp but I prefer more modern IDEs, so this has surely restricted my search space. (No need to argue, this is just an irrational, subjective matter of taste.)

Specific recommendations for Apple Macintosh: PowerLisp is a free version that is good to play around with in order to get a taste of Common Lisp. However, it misses some features from the ANSI standard and runs only in classic mode, and there are no plans to port it to Mac OS X. Macintosh Common Lisp is obviously more advanced and the people at Digitool are generous and supportive enough to let you try out MCL for 30 days. CLISP is available for Mac OS X but misses an IDE, which is essential for me. Franz, Inc. are about to provide an IDE with Allegro Common Lisp for Mac OS X some time in the future but have no fixed plans, so don't hold your breath.

I have opted for Macintosh Common Lisp, especially because this system also has a nice and supportive user community built around the MCL mailing list. (However, this is not a product endorsement -  please check out your requirements on your own!)

Part II: An eclectic self-study guide

NOBODY expects the Spanish Inquisition! Our chief weapon is suprise...surprise and fear...fear and surprise.... Our two weapons are fear and surprise...and ruthless efficiency.... Our *three* weapons are fear, surprise, and ruthless efficiency...and an almost fanatical devotion to the Pope.... Our *four*...no... *Amongst* our weapons.... Amongst our weaponry...are such elements as fear, surprise.... I'll come in again....
- Monty Python

In this part of the introduction I mainly give hints and references that should help you in getting to know the several facets of Common Lisp. (That is, I'm mainly talking about its standard library.)

8. Reference material

In every-day programming, you usually need some reference material to be able to look up function definitions, syntax clarifications, and so on. Some people prefer books and some prefer online material.

The current Common Lisp standard is specified as an ANSI standard that has been released in 1995 and is the definitive source for Common Lisp. However, it is hard to read because it mainly only gives the specs and, for example, doesn't provide good rationale.

At the beginning of the 1990's, Guy L. Steele edited the second edition of the book "Common Lisp the Language" that was a report on the then-current state of Common Lisp standardization, which is quite close to ANSI Common Lisp. (This edition superceded the first edition from the 1980's and so is generally referred to as CLtL2. The first edition - just CLtL - shouldn't be used anymore.) Although CLtL2 misses some features from ANSI Common Lisp - there are also some minor differences - it can be generally recommended as an introduction because it has the big advantage that it provides good descriptions beyond a mere specification. This greatly eases your understanding of the material. Still it is highly recommended to have the ANSI specs at hand in order to find out about the exact details of particular definitions. Furthermore, the ANSI document contains a very useful glossary of terms.

Fortunately, both ANSI Common Lisp and CLtL2 are available online as HTML (and PDF/PS) documents and can even be downloaded (including the HTML versions) for use on your computer. Here are the links.

If you prefer printed matter, you have to put a little effort into getting some. CLtL2 seems to be out of print but you could try to obtain a used copy at Ebay. It's also still available at some (online) bookstores, like Amazon. You may also try to buy it at the publisher's website at http://www.bh.com/digitalpress/.

The ANSI document is available at http://global.ihs.com/, but I don't expect it to be particularly handy and/or useful because it has over 1000 pages. Furthermore at $368 it's really expensive.

Paul Graham's "ANSI Common Lisp" (see below) is a good book but I don't find it useful for reference purposes. Usually I prefer printed specifications (like the Java language specification) but in the case of Common Lisp, the electronic versions are just fine.

9. The very basics

Paul Graham has written a good book on ANSI Common Lisp called "ANSI Common Lisp". It is a good read and fortunately, the author has made the first two chapters available on his homepage. I can especially recommend the second chapter because it quickly gives you a good hands-on experience of what programming in Common Lisp is like.

If you like his style you might consider buying the book by following the links on that page.

Most of the information you need afterwards should be fairly easy to look up in CLtL2 and/or the ANSI specs. See below for some information that is a little harder to obtain IMHO.


In order to completely understand the remaining sections of part II you should have read either "The Roots of Lisp" (http://www.paulgraham.com/rootsoflisp.html) or "ANSI Common Lisp Chapter 2" (http://www.paulgraham.com/lib/paulgraham/acl2.txt) by now, or you should have been exposed at least to example Lisp code in some other ways.


10. More advanced basics

Sooner or later you will have to deal with the following issues that involve some minor issues.

11. Macros

Common Lisp's macro feature is one of the highlights of this language - it is a very powerful means to write your own programming language constructs beyond mere functions.

Macros are usually considered an advanced topic because of their power and because they are seemingly hard to understand. However, I have found them to be conceptually quite simple and easy to write.

A very good description of macros and how to use them can be found in the book "On Lisp" by Paul Graham. It is out of print, but can be downloaded for free from the following URL.

Here are some cautions and notes by me.

12. Object-oriented features (CLOS)

The Common Lisp Object System (CLOS) is part of ANSI Common Lisp. However, since it was a late addition to the standard, some vendors have taken their time to implement it. For example, PowerLisp does not provide full coverage of CLOS. Still, almost all implementations offer support for CLOS by now. (Some vendors praise this as an outstanding feature of their respective Common Lisp implementation and I have found that confusing at some stages. Strictly speaking, a Common Lisp system cannot claim to implement the ANSI standard if it doesn't include a full implementation of CLOS.)

CLOS offers full object-orientation with classes, subclassing, multiple inheritance, multi-methods and before-, after- and around advices. This already goes very well beyond the features offered by other object-oriented programming languages.

Furthermore, a so-called "Meta-Object Protocol" (MOP) has been added that allows for inspection and manipulation of class hierarchies and method dispatch at runtime. The Meta-Object Protocol is not part of the ANSI Common Lisp standard, but has become a de-facto standard because most CLOS/MOP implementations were derived from the same sources. (CLOS and MOP are not separate entities, as for example the Java language and its reflection API, but the MOP can rather be understood as a proper superset of CLOS.)

An excellent overview of CLOS and the Meta-Object Protocol can be found in the following paper.

A reference for MOP that is similar in style to the ANSI HyperSpec can be found at http://www.lisp.org/mop/. (Most of the external links on that page are broken but the reference itself seems to work.)

Barry Margolin has given a good rule of thumb on comp.lang.lisp:

An elaborate (and impressive) example of what you can do with the Meta-Object Protocol can be found in the following paper.

Some additional notes:

13. The LOOP facility

The so-called LOOP facility is another standard feature of Common Lisp that allows you to express iterations in a style that is similar in spirit to Algol/Wirth languages. Here is an example of a loop that prints ten stars.

(loop for i from 1 to 10
      do (format t "*"))

Again, CLtL2 is a good source of information. However, you will quickly notice that there is a vast number of possibilities and combinations of different styles. My impression is that it doesn't make sense to learn all the details because this would take far too long. The goal of the LOOP facility obviously was to allow for some kind of "natural" English-like expressions of iterations, and there are examples where this definitely eases the understanding of source code. (It is also a nice example of a domain-specific language embedded in Common Lisp for the domain of iteration.)

Here is another, more interesting example of the LOOP facility (due to Matthew Danish).

(defun fibonacci (n)
   (loop for a = 1 then (+ a b)
         and b = 0 then a ;  stepping in parallel
         repeat n
         collect b))

Seemingly, the intended way to use the LOOP facility is to just "guess" a way to express an iteration and see if it works. If it doesn't you can either look up the specifics in CLtL2 or the ANSI specs, or go back to a more Lispy way of expressing iterations and recursions (with do, dotimes, mapcar, and the like).

However, this is just my guess, I don't know about the actual intentions of the LOOP facility's designers. (Some claim that the details can be learned very quicly, but I still have to check this on my own.)

14. Conditions

Conditions are more or less what exceptions are for Java-like languages. However, conditions are much more powerful because, for example, condition handlers can direct the Lisp runtime system to just continue execution at the place where a condition was raised. This might seem strange at first when you are used to exception handling because, hey, an exception always means that there is a problem, doesn't it? Well, in Common Lisp conditions can also be signalled when there is no problem but, for example, multi-threaded code needs to be synchronized or other code needs to be notified of special events or whatever you might think of as useful. Furthermore, some conditions that signal real problems can be fixed on the fly, either interactively or programmatically.

So just as the models of most object-oriented programming languages turn out to be special cases of CLOS, Java's exception handling is again a special case of Common Lisp's far more general Condition system.

An excellent overiew of condition handling in Common Lisp, along with some interesting historical tidbits can be found in the following paper.

Some notes:

15. Advanced programming techniques

I have already mentioned Paul Graham's book "On Lisp" in conjunction with macro programming. This book deals with many other advanced programming techniques for Common Lisp, like creation of utility functions, higher-order functions, database access, simulation of Scheme-like continuations, multiple processes, non-determinism, parsing, logic programming, and object-orientation. (However, the bulk of this book deals with macros.)

I repeat the link for convenience.

16. Packages

Java has a nice module system that allows you to bundle classes into packages that are to some degree shielded from each other. Furthermore, the package structure is reflected in a matching file- and directory structure, possibly hidden in zip- or jar files. This allows for simple but detailed handling of classpaths that define where to look for classes that can be loaded by the Java runtime on demand.

Common Lisp offers a package system that allows for bundling definitions (including, of course, classes) as well. However, there is no mapping whatsoever to some kind of file- and/or directory structure. The package system in Common Lisp only deals with how definitions are arranged at runtime inside the Lisp environment.

In fact, Common Lisp's package system is more powerful than that because it more generally allows you to group symbols into packages. Because definitions in Common Lips are always accessed via symbols, the ability to bundle definitions is just a special case of the more general package concept. Here is a nice example of what else you can do with packages in Common Lisp, given by Kent M. Pitman in comp.lang.lisp. (See http://makeashorterlink.com/?E3B823F91 for the complete message that includes the following example.)

So Common Lisp's package system deals with bundling of symbols and, hence, allows for bundling definitions as a "side effect", but does not deal with searching and loading of system parts at all. In Common Lisp terminology, the latter task is called "system construction".

So please don't get confused in this regard. Java's packages and Common Lisp's packages just happen to have the same name but are used for different purposes (with some overlaps).

Common Lisp only defines rudimentary support for system construction (the functions "load" and "require" - see CLtL2 and the ANSI specs). Please see the next section for some more information on this issue.

17. What is missing?

The ANSI Common Lisp standard was finalized in 1994 and published in 1995. That was at a time when Java was just around the corner but hadn't yet been made publicly available. That was also before the commercial rise of the Internet. It's clear that in the last seven years programming support has progressed in several directions. Unfortunately, the "official" standardization of Common Lisp has not continued in the meantime. Many things are not included in ANSI Common Lisp that are by now taken for granted in other, more fashionable programming languages. Among these features are: a proper module ("system construction") facility, Unicode support, a platform-independent GUI library, sockets and TCP/IP, XML, WebServices, and so on (add your favorite feature here).

However, the Lisp world hasn't stood still in the meantime - just because something is not specified in the ANSI Common Lisp standard this doesn't mean that it doesn't exist.

The Common Lisp Open Code Collection (http://clocc.sourceforge.net/) offers a system construction facility as a free add-on for ANSI Common Lisp, among other things. Allegro Common Lisp and CLISP offer Unicode support. CLIM is a platform-independent GUI library that is supported by some vendors, including Franz, Xanalys and Digitool. Most serious Common Lisp implementations offer support for sockets and more advanced networking facilities. CL-XML is a library for dealing with XML stuff.

So the basic message is: if you need some library, do a little research with Google and you might find something that you can use. Also check out some of the links provided below.

Part III: Links

The television screen is the retina of the mind's eye.
Therefore, the television screen is part of the physical structure of the brain.
Therefore, whatever appears on the television screen emerges as raw experience for those who watch it.
Therefore, television is reality, and reality is less than television.
- Professor O'Blivion in Videodrome, by David Cronenberg

Here is a list of useful and/or interesting links. Some, but not all of them have already been mentioned in the text above.

18. Personal websites

19. Common Lisp References

20. Background information

21. Repositories, link collections, software

22. Some Common Lisp vendors

23. Scheme links

24. Copyright issues




Acknowledgements

Many thanks (in alphabetical order) to Tom Arbuckle (http://www.cs.uni-bonn.de/~arbuckle/), Joe Bergin (http://csis.pace.edu/~bergin/) and Richard Gabriel (http://www.dreamsongs.com/) for providing lots of useful feedback on the draft version.

Further thanks for even more feedback go to Paolo Amoroso, Marco Antoniotti, Tim Bradshaw, Christopher Browne, Thomas F. Burdick, Wolfhard Buß, Bill Clementson, Matthew Danish, Biep Durieux, Knut Aril Erstad, Frode Vatvedt Fjeld, John Foderaro, Paul Foley, Erann Gatt, Martti Halminen, Bruce Hoult, Arthur Lemmens, Barry Margolin, Erik Naggum, Nicolas Neuss, Duane Rettig, Dorai Sitaram, Aleksandr Skobelev, Thomas Stegen, Gene Michael Stover, sv0f, Raymond Toy and Espen Vestre. (Many of them are active participators in comp.lang.lisp.)

Valid HTML 4.0!