Subject: Re: Could CDR-coding be on the way back?
From: Erik Naggum <>
Date: 09 Dec 2000 22:00:21 +0000
Newsgroups: comp.lang.lisp,comp.arch
Message-ID: <>

* Per Bothner <>
| I have an even more efficient and radical idea:  Don't use lists.

  Oh, Christ!  We've been there, done that, about a million times.

| They are almost always the wrong data structure.  Use arrays.  Arrays
| are available and efficient in Lisp, Scheme, Java, C++, Fortran, etc
| etc.

  Yes, so they are.  Available.  Arrays are also extremely inefficient
  where lists are not the wrong data structure.  Hence, use lists _and_
  arrays, as appropriate.  Lisp programmers are not the idiots you think
  they are, Per.  They figure out when it makes sense to use arrays even
  if you don't and need to reduce the problem to silliness.

| If it is important to be able to insert/delete in the middle of
| a sequence, you might consider using a list.

  If your data structures nest, use lists.

  If your data structures have unpredictable structure, use lists.

  If you need to maintain uniformity of type for the "rest" after
  processing an initial portion of the data structure, use lists.  (If
  you think this only applies to recursion, which it seems you do, you
  really must think more carefully about algorithm design with arrays
  and why displaced arrays or passing _pairs_ (sorry, data structures in
  small arrays, of course) of the array and the index won't cut it.)

  If you need to manipulate the structure of the data structure in any
  way, not just insert/delete, use lists.  (Flattening, pairing, etc.)

  If after much headache and painfully idiotic programming mistakes, you
  discover that your array implementation really must use two elements
  per "array", one data and one "next", you have reinvented the cons.
  Congratulations!  Welcome to the wisdom of 40 years of language design!

| I am talking about standard Lisp-style lists implemented using pairs.
| There is a better case to be made for chaining objects together using
| link slot in a more complex objects.  At least in that case you're not
| allocating a separate cons cell for each link.

  It is just insane to add "link" slots to more complex objects when you
  can separate and abstract out the container concept from the containee.

  Who cares about allocating separate cons cells?  Simple arrays have to
  be more than four elements long to take less space than the equivalent
  list using cons cells.  Specialized arrays may have to be much longer.
  The allocation for cons cells is extremely efficiently implemented in
  all Lisp implementations.  Using your stupid arrays-for-lists would of
  course force some super-clever implementation of exponent-of-2-sized
  arrays that double in size as they are used _and_ move around all the
  time (destroying object identity unless you waste even _more_ space on
  their already inefficient implementation), but people have been there,
  many times over, and they have _returned_ to lists, implemented via
  cons cells, when that has been the most intelligent solution.

  What we have left after so many years of using lists _and_ arrays
  _and_ structures _and_ clos objects _and_ databases, etc, is that
  there is not a single argument left for using anything _but_ lists
  where lists are used.  If you want to teach novices to use arrays, at
  least don't make the misguided Scheme-style argument that alternatives
  to the obvious and the most natural must be chosen because it somehow
  more divine to use recursion, oops, I meant arrays.

  You've done so much good work.  How come you don't know simple things?
  "When you are having a bad day and it seems like everybody is trying
   to piss you off, remember that it takes 42 muscles to produce a
   frown, but only 4 muscles to work the trigger of a good sniper rifle."
								-- Unknown