Pascal Costanza's Highly Opinionated Guide to Lisp

http://p-cos.net/lisp/guide.html
(v1.5, 17/2/2013, changelog.txt, old version)
Turkish translation by Hayrettin Gürkök:
http://ileriseviye.org/arasayfa.php?inode=costanza-lisp-guide.html

Copyright © 2002, 2004, 2005, 2013 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 pc@p-cos.net.


Part I: Background

I always wanted to be a lumberjack!
- Monty Python

1. Why am I writing this introduction?


I have originally written this section in August 2002. The situation I describe below is not so current anymore, but in order to keep the feel of this guide I have decided not to change the tense.


My current situation, as of 2002, 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.


Note that the situation has dramatically improved as of 2005. Peter Seibel has written a book about Common Lisp which was published in April 2005. You can also find it online at http://www.gigamonkeys.com/book/. It takes a very pragmatic approach and presents examples that are of more interest to a "modern" audience, like spam filters, mp3 libraries and html generation. Apart from that, the Lisp is continually growing which has a very positive effect on the information available throughout several channels.


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 that 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. (There are also other variants of Lisp out there, like Emacs Lisp and Lush, but they are rather limited domain-specific dialects.)

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 liberal.

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. When you find out that you do not like the one alternative you have opted for, give the other one also a try.)

Perhaps this is also a good place to explain how people use the names Lisp and Scheme. In a broad sense, Lisp usually refers to a family of languages that includes Common Lisp, Scheme, older dialects (not in use anymore) like MacLisp, InterLisp, Franz Lisp, and also newer ones like Arc and Goo. In a narrow sense, Lisp currently refers to Common Lisp and Common Lisp only, which specifically excludes Scheme! How broad and/or narrow the name Lisp is used depends on the person using it, and perhaps on the context. There exist a broad spectrum of people, including those who would generally exclude Scheme even in the broad sense as one extreme and those who include Dylan and even Python as another. (Personally, I prefer to be liberal and try to be explicit when it is important in a specific context.)


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 LispWorks 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!

The latter paper also includes a pretty complete bibliography on Lisp

(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.

(This paper makes hints about a follow-up paper but it has never been written nor published. So don't look for it: try to tie up the loose ends as an exercise. ;)

7. Available implementations

You can find a list of Common Lisp implementations at http://common-lisp.net/~dlw/LispSurvey.html. Many Lisp programmers prefer to use emacs or xemacs as a development environment for Lisp but I prefer more modern IDEs. (If you are interested in setting up an IDE with emacs, go for SLIME at http://common-lisp.net/project/slime/. There is also Lispbox, a pre-installed Emacs-based environment at http://common-lisp.net/project/lispbox/.)

Specific recommendations for Apple Macintosh (Mac OS X): LispWorks for Macintosh is an excellent IDE, with a Personal Edition that can be downloaded for free. Clozure Common Lisp also comes with a very good IDE, and can be obtained for free from the Apple App Store. I have not tried Allegro Common Lisp's IDE myself yet. CLISP, CMU CL, ECL, and SBCL are available for Mac OS X but miss IDEs, which is essential for me.

I use LispWorks for Macintosh on a regular basis. 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.

(The editors of this "HyperSpec" stress that this is not the definitive specification but just derived from the official ANSI document. However, I guess that this is only a legal issue and that you can most probably count on the HyperSpec. In fact, it is generated from the same TeX sources.)

(Beware: CLtL2 has appendices about the so-called "Series" macros and "Generators and Gatherers" that implement lazy iterators. These features were not included in ANSI Common Lisp. I haven't found a rationale why they were included in CLtL2 and dropped again in ANSI Common Lisp, but my guess is that they were too experimental. The "Series" macros can be found http://series.sourceforge.net as a separate library, though.)

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.

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 nearly $400 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.

Another excellent beginner's book is Peter Seibel's "Practical Common Lisp" available as a book or online at http://www.gigamonkeys.com/book/.

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. Nowadays, almost all implementations offer support for CLOS. (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 good rationale for some of the CLOS design decisions can be found in another paper.

Jeff Dalton provides a brief guide to CLOS (without the MOP) at http://www.aiai.ed.ac.uk/~jeff/clos-guide.html. A more comprehensive guide is provided by Nick Levine at http://cl-cookbook.sourceforge.net/clos-tutorial/index.html. A reference for the MOP that is similar in style to the ANSI HyperSpec can be found at http://www.alu.org/mop/. (Most of the external links on that page are broken but the reference itself works.)

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 quickly, but I still have to check this on my own.)


In the meantime, I have managed to learn LOOP and find it extremely useful. It takes some time but in my experience it pays off. Peter Seibel provides a good tutorial on LOOP in his book, but I still think my advice to guess and try it out is sufficient for most cases.


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 that 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 Lisp 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 https://groups.google.com/d/msg/comp.lang.lisp/wE7yOt434nw/DfTwFQEMQYQJ for the complete message that includes the following example. In the citation below, some bugs are corrected that were spotted by Jeff Caldwell.)

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 two widely used system construction facilities are ASDF (http://www.cliki.net/asdf) and MK-DEFSYSTEM (http://www.cliki.net/mk-defsystem). Additionally, some Common Lisp implementations come with their own system construction support. Allegro Common Lisp, LispWorks and CLISP offer Unicode support. CLIM is a platform-independent GUI library that is supported by some vendors, including Franz, LispWorks and Digitool. Most serious Common Lisp implementations offer support for sockets and more advanced networking facilities. CLISP offers support for fastgci. CL-XML is a library for dealing with XML stuff.

More recently (as of 2013), Quicklisp has started to provide an excellent collection of well-maintained libraries for almost all Common Lisp implementations, which should cover most of what you need in its more than 700 entries. Moreover, Quicklisp is incredibly easy to set up and use. Just give it a try!

So the basic message is: if you need some library, do a little search in Quicklisp or with DuckDuckGo 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. Scheme links

23. Copyright issues

Acknowledgements

Many thanks (in alphabetical order) to Tom Arbuckle (http://www.csis.ul.ie/staff/TomArbuckle/), Joe Bergin (http://csis.pace.edu/~bergin/) and Richard Gabriel (http://www.dreamsongs.com/) for providing lots of useful feedback on the draft version. Thanks to Seung Mo Cho for the Korean translation.

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

Valid HTML 4.0!