Sunday, November 25, 2007

Thoughts on Lisp: Things I don't like about lists

Lisp, of course, is named because it is a LISt Processing language. So I'll start right at the foundations with a list of things I don't like about Lisp's lists:

  1. "List" isn't a tagged type. A pair (known to Lisp as a cons) is a tagged type. "List" is a term for a pair that happens to obey a content requirement, specifically the second element of the pair is either another "list", or is empty.

  2. Lists don't have identity. A list is identified by its first pair. If you sort "a list", the reordered list may be identified by a different first pair than the unsorted list was.

  3. Two or more lists can share pairs. Now imagine what happens if you sort one of them.

  4. Lists are used where other data structures would be more efficient. In CL, for instance, association lists and property lists are both list structures representing key-value mappings. In CL, each has a distinct search function --- assoc for alists, getf for plists.

  5. Pair-based data-structures must be manually maintained. E.g., it's up to the programmer to maintain an alist such that it continues to fulfill the structural requirements of being an alist.

  6. Pair-based data-structures don't convey intent. Given a particular pair, it may just be a pair, it may be a list, it may be a property list, etc. It may have been intended to denote any of those, or something else --- a tree, an association list, etc. The pair itself doesn't describe the programmer's intent when it's sitting naked in the debugger.

  7. Syntactic poverty. This is the classic "too many parens" complaint. Lisp uses parentheses to denote all code constructs and sub-constructs. This makes Lisp harder to read than Algol-family languages. In part, this is because the meaning of each paren-delimited form is dependent upon its entire lexical context. And in part, this is because specialized syntax is helpful to the human reader, even if it's technically redundant.

  8. Lisp programs are represented as lists. This is why the code is fully-parenthesized: lists are denoted with parens. It is true that this makes Lisp easy to parse. But nobody is having much trouble parsing Python, either. I'm still conflicted about Lisp's structured macros --- that's for a later post --- but I'd like to see the next language that represents its code as data structures use a few more data structures for the representation.

  9. Lisp programs aren't really represented as lists anyhow. A Lisp program is represented as a collection of files. Within a file, yes, there are lists, but there are also comments and whitespace describing and structuring those lists. Code which has been literally reduced to a list is tremendously less readable than the original, commented, formatted source. It's an important distinction to make, but one that is often lost.

So what don't you like about lists in Lisp?

Coming up next...

Things other languages took from Lisp

Saturday, November 24, 2007

Thoughts on Lisp: Preface

Over the last few weeks, I've been making lists for myself. Things I like don't like about Lisp. Things I do like about Lisp. Things that I think are interesting and cool about Lisp, but which I still feel conflicted about. And so on. Over the next little while, I'm going to publish and embellish my lists in a series of posts.

Background

I first met Scheme in 1990. Since it was a big part of my computer science education, I encountered it frequently, and extensively, over the next several years. I came to really like Scheme.

As an Emacs user, I also came to write occasional snippets of Emacs Lisp (Elisp). I never came to like it, but I never did anything large in it, either.

Once or twice, I dabbled briefly in Common Lisp. Until 2006, I didn't do anything substantial with it. But in 2006, I got my chance, and I spent the next eighteen months working in CL.

I had been very excited about the chance to work with Common Lisp. Many of the smartest people I know were and are raving CL fans. Having banged my head against CL on my own without achieving enlightenment, I was hoping to achieve CL nirvana by CL immersion.

No such luck.

Instead, I wound up with a complicated, conflicted, love-hate relationship with Lisp in general. Which relationship will hopefully make this series more interesting than if I was just another unalloyed Lisp fan.

Audience

The intended audience for this series consists of two groups. The first target group is programmers who don't know Lisp, but are curious about it. By and large, the 'net is full of people who either love Lisp without reserve, or who freaked out about Lisp's heavy use of parentheses and never made it to the interesting parts. I hope I represent a more nuanced position.

The second target group is programmers who do know Lisp, and like thinking about how to make the next great Lisp dialect (Lisp 2010?) an improvement on its ancestors.

Specifically omitted are those people to whom some specific dialect of Lisp is the ultimate programming language, never to be improved upon. If you're one of them, stop reading. This series will only raise your blood pressure.

Assumptions and prejudices

My comments on Lisp are explicitly subjective. I'm not saying "this is good," or "that sucks." I'm saying "I like this", and "I don't like that." But to provide some hint of where I'm coming from, here are some of the assumptions that I tend to make:

  1. Code is read more often than it is written.
  2. The basic meaning of a code fragment should be context-independent.
  3. Correctness precedes performance. It's easy to be fast and wrong.
  4. The most important programming nowadays is done by teams.
  5. Development tools should be able to introspect on programs and their source.
  6. Expressivity is good. Clarity is better.
  7. Most clever hacks aren't smart. Most aren't good engineering, either.

Coming up next...

"Things I don't like about lists."