Re: Lisp collections

From: Pascal Bourguignon (spam_at_mouse-potato.com)
Date: 09/23/04 

Date: 23 Sep 2004 10:22:14 +0200

cstacy@news.dtpq.com (Christopher C. Stacy) writes:

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

Obviously, in my sentence above, "lists" must be understood differently!
I have in mind: THE abstract data type I HAVE IN MIND.

That is: abstract data types in general, and the specific abstrat data
type I want.

The OP had in mind abstract data types too, to wit his note about interfaces:

> [1] Unordered, key can be anything. These are implemented using interfaces
> (like COM or java) on every class that wants to be a collection, including
> basic arrays and such. There's also a "list" interface, which is an ordered
> collection indexable with integers, and about as pervasive as the
> collection interface.

And in his case, the abstract data type he wanted did not map to the
ones provided by Common-Lisp, if at all.

The rest of my post extended the notion that in lisp, the abstract
data type of (cons a b) is not that of a list, but that of a pair, ie,
a record of two fields (T x T). (I use the term PAIR to insist on
that record-of-two-fields aspect of cons cells). And I tried to hint
that you should not hope to have Common-Lisp provide you with more
sophisticated abstract data type when you did not want to restrict you
to what it provides.

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

(defstruct single-linked-list (length 0) (head nil) (tail nil))

(defstruct single-linked-node node (next nil))

(defun prepend (sll item)
    (setf (single-linked-list-head sll)
          (make-singled-linked-node item (single-linked-list-head sll)))
    (when (null (single-linked-list-tail sll))
        (setf (single-linked-list-tail sll) (single-linked-list-head sll)))
    (incf (single-linked-list-length sll)))
    
(FIRST (prepend :a (prepend :b (make-single-linked-list))))
--> the proof that FIRST does not deal with list abstract data types.

That is, if what you want is more that what is provided by
Common-Lisp. Here I wanted an abstract data type that consisted of
singled linked lists in which the length, prepending and appending
could be computed in O(1). Since I could not satisfy myself with what
Common-Lisp provides, I could not use what it provides!

Another thing is that by restricting yourself to a given subset of the
Common-Lisp "primitives", YOU are actually building an abstract data
type over the basic PAIR data type of Common-Lisp.

For example, if you DECIDE to use only FIRST, NEXT, ENDP, LENGTH, you
are BUILDING a simple list data type.

If you DECIDE to use only FIRST, NEXT, you are BUILDING a circular
list data type.

If you DECIDE to use CAR, CDR, NULL, COPY-TREE, TREE-EQUAL, you are
BUILDING a binary tree data type.

If you DECIDE to use PUSH, POP, you are BUILDING a stack data type.

If you DECIDE to use FIRST, NEXT, NULL, NCONC, you are building a FIFO
data type.

If you DECIDE to use: INTERSECTION, UNION, MEMBER, PUSHNEW, and NULL,
you are BUILDING a set data type.

Actually, in all these cases, if you start with a given abstract data
type definition, you'll see that Common-Lisp only goes half the way,
and you have to provide a number of custom functions to implement
completely the abstract data type you want.

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

Yes. This is the proof that LISTP is not a predicate for a list
abstract data type.

> [...]
> I would say that Common Lisp includes several kinds of lists.

No. It includes a PAIR data type, over which other abstract data types
can be built, and for which a certain number of predefined helper
functions are provided by Common-Lisp. But Common-Lisp does not give
you any of THESE abstract data type YOU have in YOUR MIND!

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

No. It's quite easy to avoid any implementation decision. Just
expression yourself with _interfaces_. That's why abstract data types
are so important. Either you program low-level with what primitive
Common-Lisp provides you and indeed, you are commiting yourself to
these early decisions (you won't be able to AREF (in O(1)) if you've
built your sequence with CONS!), or you program with an interface:

(defun ordered-collection-prepend (oc item) ...)
(defun ordered-collection-nth (oc index) ...)
(defun ordered-collection-append (oc item) ...)
(defun ordered-collection-length (oc) ...)

First, it's easy enough to provide a "prototype" implementation with
the Common-Lisp primitives.

Then, it's easy enough to privde a new implementation following a late
implementation decision.

I should refer you to the first chapters of SICP...

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

Indeed, Common-Lisp has a basic sequence abstract data type: COPY-SEQ,
ELT, SUBSEQ, LENGTH, MAP, which is the union of two main data types:
lists and vectors, so you can program some of your algorithms without
early binding to lists or vectors. But this is only a strict minimum.
What if you're unsure of the type of your "indices"? You'd have to
build your own interface allowing you to later decide whether you
implement it with vectors, with hash-table, or with balanced binary
trees.

Just because Common-Lisp provides you with convenient low level
primitives (and much more than most of the other languages!) does not
mean that you don't have to implement your own interfaces and abstract
data types.

On the other hand, the fact that Common-Lisp provides this atomic PAIR
data type, that allow you to consider a data indifferently as a list,
a tree, a graph, a set, or whatever you build with it, allows you to
play tricks that you could not with strictly enforced abstract data
types. If you had to move your elements from one container class to
another, it would be much more inconvenient and much less efficient
than just using the function of your choice from the Common-Lisp
toolbox. But that means that you're not programming with abstract
data types anymore, you're programming in Lisp! 

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.

Relevant Pages

  • Re: Lisp collections
    ... do you think Lisp has a data type called a number? ... > that CONS,CAR,CDR,NULL implement the PAIR abstract data type. ... Your claim that "Lisp does not have lists" does not follow logically ...
    (comp.lang.lisp)
  • Re: SoA Vs OO
    ... data type, they are just functions that operate on a data type, and if ... When doing functional design, you start with what you want done. ... mostly it's lists and trees (there isn't much need felt ... so the subclass can't even access it. ...
    (comp.object)
  • Re: SoA Vs OO
    ... data type, they are just functions that operate on a data type, and if ... When doing functional design, you start with what you want done. ... mostly it's lists and trees (there isn't much need felt ... so the subclass can't even access it. ...
    (comp.programming)
  • Re: Definition of Abstract Data Type
    ... let me apologize for bringing this topic as it has been ... What is the actual definition of Abstract Data Type? ... there are no tigers in microprocessors; ...
    (comp.object)
  • Re: Normalisation
    ... be expressed as operations over a signature that consists only of domains described by an abstract data type and relations that contain in their fields only values from these domains. ... the RM part of a RDBMS. ... party that does have such knowledge. ...
    (comp.databases.theory)