Subject: Re: Could CDR-coding be on the way back? From: Erik Naggum <erik@naggum.net> Date: 09 Dec 2000 22:00:21 +0000 Newsgroups: comp.lang.lisp,comp.arch Message-ID: <3185388021717094@naggum.net> * Per Bothner <per@bothner.com> | 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? #:Erik -- "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