Re: Lisp collections

From: Christopher C. Stacy (cstacy_at_news.dtpq.com)
Date: 09/23/04 

Date: Thu, 23 Sep 2004 05:43:37 GMT

Kenny Tilton <ktilton@nyc.rr.com> writes:
> Lisp does not have lists, it has nil and cons structures

That's a very odd thing to say about a language whose name is
an abbreviation for LISt Processing, and I don't get your point.
(I hope the remainder of my reply here is something that others
will find somehow useful; it's written mostly for them.)

If a programming language specification talks about a data type,
includes functional abstractions for dealing with that data type,
and even has a type predicate named for it, I would say that the
language "includes" the data type.

For example, The Common Lisp Hyperspec talks about lists,
and specifically defines "list", "proper list", "improper list",
"dotted list", "circular list", and so on.

Common Lisp includes the following functions that deal with lists:
LIST, LIST*, MAKE-LIST, COPY-LIST, LIST-LENGTH, NTH, NTHCDR, FIRST,
REST, SECOND thru TENTH, LAST, BUTLAST, NBUTLAST, TAILP, ENDP, NCONC,
NRECONC, APPEND, REVAPEND, LDIFF, PUSH, PUSHNEW, POP, and of course
MEMBER, and COPY-ALIST. (To make my point about "lists" being in
the language, I have omitted here the numerous and powerful generic
sequence functions, which work on both lists and vectors.)

In Lisp, a list is a traditional "linked list" structure, consisting
entirely of nodes which are "cons cells". There are no backpointers.
A list does not have any header or other encapsulation - each node
can be viewed as the beginning of a (sub) list.

One thing to watch out for is that the predicate function LISTP
returns T not only for a "proper list", but also for any cons.
LISTP also returns T for NIL, the empty list.
It is only discriminating between cons-or-nil and everything else.
Note that the function CONSP returns false for the empty list.

The building block nodes, "conses", are also used to implement some
other data structures in Lisp (such as "sets"), and you can use them
for any lone or composite "pair" type of structure that you invent.
The language also includes "association lists" (ASSOC, ACONS, PAIRLIS)
"property lists" (GET), trees (COPY-TREE, TREE-EQUAL), and more.
You can also hack conses themselves, using RPLACA and RPLACD.
What might be confusing about the list data type is that its implementation
is exposed as mostly being a conventional use of a more primitive data type,
and that lists need not be "proper" (NIL terminated) in all cases.
I would say that Common Lisp includes several kinds of lists.

One of the often-cited strengths of Lisp is that you can make
decisions about your program design later, rather than sooner.
But you are forced to make certain implementation decisions early on.
Lists can be indexed into, but that's linear time. Vectors have a
"fill pointer" feature that allows them to be dynamically adjusted
(eg. adding a new element) while preserving constant time, but such
arrays doesn't support splicing like lists do. Hash tables also have
iteration, but might not be quite what you had in mind and are maybe
expensive overkill. Lisp does have some "mapping" and "sequence"
functional abstractions that allow you to gloss over the implementation
details of iterating over both (1D) arrays and lists. But you do have
to choose which kind of data structure you had in mind before you can
create the data. There isn't really a generic "collection" data type.

This discussion was started when a C# programmer inquired about generic
collections that allow you to switch representations; he was under the
misapprehension that Lisp programmers generally just used lists to store
things, and then maybe switched to arrays if performance was unacceptable.
But of course, that's not how we do things. Programmers really do have
some early idea of how they will be accessing any given "collection".
If they don't know whether they will need to access the collection
through a key value, whether key is a numeric index or something else,
and whether constant-time is important or not, then I bet things are so
vague in their mind that they will end up re-designing and re-writing
a bunch of code. Such a program is pretty messed up algorithmicaly:
it's not just a matter of changing some data access expressions.
And if you're going through that exercise, Lisp already lets you do
all that same re-writing without having to declare the data type.
In fact, in Lisp, you probably got better feedback sooner about how
confused you were, due to the obvious need to make certain decisions,
and due to the ability to get your experimental/prototype code fragments
running more quickly than in C# or JAVA. So having an unspecified type
of "collection" would not really have been such a helpful idea, after all!

Common Lisp is certainly not a perfect language (although I find it
almost always "better" for most of my purposes), but what this whole
discussion about features reiterates to me is that Lisp has drawn its
lines in different places than languages that have been designed for
mass marketing. Lisp is a good language for beginners to learn _first_,
but it can be harder for programmers coming from most other language
cultures. My other favorite language (well over a quarter century ago,
just before I discovered Lisp) was APL, and the similarities in culture
(clashes) and in communities have always struck me as remarkable.

The "Lisp way" is not obvious to most people, even experienced programmers.
I was a very experienced programmer (in several langauges) when I first
learned Lisp, and it still seemed pretty strange in a number of ways.
I figured out FORTRAN and some others all by myself, but I was lucky
enough to have the best wizards tutor me for my introduction to both
APL and Lisp. Still, I remember writing some thinly veiled FORTRAN
programs with parenthesis, early on. Really understanding Lisp well
enough to seriously appreciate it to the point where one can make
insightful comparisons to other programming languages really takes
a while. Of course, that's what programmers (of all experience levels)
coming from other languages naturally try to do immediately when learning
or investigating Lisp. (It's unfortunately that so many of them on the net
are really annoyingly arrogant in their ignorance. I bet they would behave
better in person, at least to your face.) Anyway, as some of these newer
languages adopt some of Lisp's individual features (such as automatic
storage management), more meaningful comparions become even harder for newbies
to make. Maybe having all those scary parenthesis isn't a bad thing - while
they may bring to mind weird myths that belie the commonalities with other
languages, they also suggest that Something Different May Be Going On Here.
Maybe that gets people to think harder, if they're capable of thinking at all.

Relevant Pages

  • Re: Cons cell archaic!?
    ... Lisp can use other, alternative representations ... of lists, without cons. ... what exactly each of these jargons means is ... pretty much dependent on the language now. ...
    (comp.lang.lisp)
  • Re: LISPPA
    ... >> of arbitrary objects in a programming language. ... I'm puzzled by the statement that "Pure functional Lisp ... lists of arbitrary-typed elements has to be functional. ...
    (comp.lang.lisp)
  • Re: Lisp for the C21
    ... Language design is not about necessity. ... and the need for variadic functions goes ... Every functional language I remember has lists as matter of course, ... OCaml can do almost the same thing as Lisp does with &rest and that is ...
    (comp.lang.functional)
  • Re: Cons cell archaic!?
    ... How would the implementation of a Lisp without a using cons look like? ... the irregularity in its often cited regular syntax. ... Lisp at core is based on functional programing on lists. ...
    (comp.lang.lisp)
  • Re: PEP 318: Cant we all just get along?
    ... Paul Morrow wrote: ... >> including any such implicit magic in the language. ... > you feel about the way we can create/manipulate lists and dictionaries ... really good reason, we shouldn't make programmers ...
    (comp.lang.python)