wagner@iaoobelix.UUCP (07/15/87)
[ National lineeater week... ]
In some cases, list creation can be optimized not to create a number of single
conses but one large vector which comprises a piece of the entire list (this
technique is usually referred to as CDR-Coding). The Symbolics manuals will
probably give you some hints on that.
An alternative representation of arbitrary n-ary structures (i.e. structures
holding n components) is possible with closures. Closures provide a
well-defined interface to a somehow opaque data structure (see various LISP
introductions or the FranzLISP Manual for an explanation).
Juergen Wagner, (USENET) ...seismo!unido!iaoobel!wagner
("Gandalf") Fraunhofer Institute IAO, Stuttgartlarus@dill.Berkeley.EDU.berkeley.edu (James Larus) (07/17/87)
Luddy Harrison (of the Center for Supercomputing Research & Development at the Univ. of Illinois) has done some very nice work on using vector-like structures to store lists. The purpose of this work is to make fast, concurrent reduction operations possible on multiprocessors. It has other advantages in that certain common operations, such as APPEND, become very fast and efficient. It's main disadvantage is that RPLACA and RPLACD are outlawed because they screw up the structure-sharing. Luddy argues that a lot of cases in which these operations were previously necessary for efficiency reasons are not as important, i.e., NCONC is unnecessary when APPEND is almost constant-time. There is a paper in the 1986 Parallel Processing Conf. and a couple of tech. reports on this work. /Jim
tdavis@athena.mit.edu (Timothy L. Davis) (07/17/87)
{}
I think the style & "readability" wins of "writing out the parse tree", which
is really what lisp syntax is all about, could be combined with less esoteric
data structures, a la C's malloc() and free(), to produce VERY optimized
code. There should be no need for run-time garbage collection.
Does anyone know if it is possible to write a lisp (or SCHEME)
pre-processor which will eliminate the need for garbage collection by
inserting (free ..) in the approprate places? A starting point would be
lexically-scoped Scheme, no side-effects, and no global or fluid bindings.
If that is too hard (or proven impossible), how about a pre-processor to add
>most< of the needed (free ...) statements, so that the garbage collector need
not hardly ever be called? The compiler could even flag unfreeable variables
and let the programmer specify their disposal explicitly.
I know many of the lisp hackers out there may think I don't understand the lisp
philosophy; I do, but let's leave garbage collection to rapid prototyping,
and develop good compilers to automatically transform those prototypes into
the products (software, parallel-ware, VLSI, etc.) of the future.
Tim Davis tdavis@athena.mit.edu
60 Wadsworth #19A ...mit-eddie!mit-athena!tdavis
Cambridge, MA 02142