From: Tim Bradshaw
Subject: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <ey3lnki24mj.fsf@todday.aiai.ed.ac.uk>
This is something I've been thinking about for a while, and I'm
wondering if anyone else thinks this is a reasonable argument.

One of the things Lisp (-family-languages) have is that the source
code of programs is represented as Lisp data -- specifically as
lists.  And we all know how powerful that is.

But lists are kind of the minimal sufficient structure for this --
it's seemed to me for a long time that it would really be better to
represent your source code as something richer, so you might have
`blocks' and `function-calls' or something, and these would be real
data types in the language (and you'd be able to say
(function-call-operator ...)).  You'd still have macros, but these
would work as transformations on these data types in a more
object-oriented way.  (Perhaps Dylan does this?).

That seemed to me like a generally much more modern way of doing
things, since it has a richer set of types.  It would make things like
code walkers much easier, and you could probably share these types
with the compiler too, so that would be a win perhaps.

But I think I was wrong.

The problem with having this whole bestiary of
sorts-of-things-in-the-language is that once you've defined them, then
you've defined what sorts of things you can have in the language.  And
you might be wrong, because there might be other sorts of things that
you can have in the language, or in some extension of it, which you
haven't thought of yet, and which it would now be hard to even
conceive of.  So although everything would be nicer in the short term,
you have really limited the way the language can develop because
you've limited the sorts of macros that can be written.

So although lists are only a minimally sufficient representation, they
are *also* the representation with minimal commitment, thus allowing
the most flexibility you can have.  So perhaps representing source
code as lists is exactly the right choice, in the long term.

Does that seem reasonable?

--tim

From: David Cooper
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <366D8CE0.3FE9C5E8@genworks.com>
Tim Bradshaw wrote:
> 
> So although lists are only a minimally sufficient representation, they
> are *also* the representation with minimal commitment, thus allowing
> the most flexibility you can have.  So perhaps representing source
> code as lists is exactly the right choice, in the long term.
> 
> Does that seem reasonable?
> 

Yes, it is reasonable. I think you hit the nail right on the 
head.
From: Steve Gonedes
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <m2ww42z0o2.fsf@KludgeUnix.com>
Tim Bradshaw <···@aiai.ed.ac.uk> writes:

< So although lists are only a minimally sufficient representation, they
< are *also* the representation with minimal commitment, thus allowing
< the most flexibility you can have.  So perhaps representing source
< code as lists is exactly the right choice, in the long term.

How low can you go? That is, at the lowest level available to a
programmer common lisp programs are represented as streams of data.
It's the function attached to the parenthesis character that returns a
list. Since this behavior can be changed at will, lisp programs can be
represented in any manner the programmer can imagine - flexability in
the utmost extreme!

< Does that seem reasonable?

After experiencing such flexability, it's almost become a requirement! :)
From: Eugene Zaikonnikov
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <913143711.778630@lxms.cit.org.by>
Tim Bradshaw wrote in message ...
[snip]
>So although lists are only a minimally sufficient representation, they
>are *also* the representation with minimal commitment, thus allowing
>the most flexibility you can have.  So perhaps representing source
>code as lists is exactly the right choice, in the long term.
>
>Does that seem reasonable?


Sometimes I thought of Lisp based on sets instead of lists. While set theory
equally powerful with lists algebra, it could be funny to use set operations
both on data and code.
Although I can't imagine convenient representation for such language.

--
     Eugene Zaikonnikov
From: Christopher Browne
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <74nkha$f1p$22@blue.hex.net>
On Tue, 8 Dec 1998 21:04:59 +0200, Eugene Zaikonnikov
<······@removeme.cit.org.by> wrote: 
>Tim Bradshaw wrote in message ...
>[snip]
>>So although lists are only a minimally sufficient representation, they
>>are *also* the representation with minimal commitment, thus allowing
>>the most flexibility you can have.  So perhaps representing source
>>code as lists is exactly the right choice, in the long term.
>>
>>Does that seem reasonable?
>
>Sometimes I thought of Lisp based on sets instead of lists. While set theory
>equally powerful with lists algebra, it could be funny to use set operations
>both on data and code.
>Although I can't imagine convenient representation for such language.

I would think that moving to sets takes us a bit below the "minimal"
requirements. 

Lists provide you the ability to do two things:

a) Group together related things, and
b) Indicate a sequence.

Sets provide the former ability, but do not provide the ability to
indicate sequence, e.g. - to indicate "this comes first, and that comes
next."

It thereby denies the ability to indicate the start and end of a
computation.  

In order to indicate sequence, you need to add some additional
structure, perhaps some additional set of associations indicating
explicitly required orderings.  That requires adding additional sets and
emulating lists, which probably adds back more complexity than you got
rid of by moving to "simpler" sets. 

I'd suggest that this issue is pretty deep; the study of parallel
computing largely represents attempts to break that assumption of
sequence, with varying degrees of success. 
-- 
"I will not send lard through the mail" ^ 100 -- Bart Simpson
········@hex.net- <http://www.ntlug.org/~cbbrowne/langlisp.html>
From: Barry Margolin
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <tcJb2.12$wF5.722@burlma1-snr1.gtei.net>
In article <·············@blue.hex.net>,
Christopher Browne <········@hex.net> wrote:
>I'd suggest that this issue is pretty deep; the study of parallel
>computing largely represents attempts to break that assumption of
>sequence, with varying degrees of success. 

So does logic programming, right?  However, IIRC, Prolog is sensitive to
the order in which terms are entered into the logic database, as well as
the order of subexpressions within a term -- this was a concession to
reality.

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
From: Erik Naggum
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <3122163252938555@naggum.no>
* Tim Bradshaw <···@aiai.ed.ac.uk>
| But lists are kind of the minimal sufficient structure for this -- it's
| seemed to me for a long time that it would really be better to represent
| your source code as something richer, so you might have `blocks' and
| `function-calls' or something, and these would be real data types in the
| language (and you'd be able to say (function-call-operator ...)).  You'd
| still have macros, but these would work as transformations on these data
| types in a more object-oriented way.  (Perhaps Dylan does this?).

  this is actually what SGML does.  SGML has "named parentheses".  think
  about it.  it is a monumentally wrong way to go.

| That seemed to me like a generally much more modern way of doing things,
| since it has a richer set of types.  It would make things like code
| walkers much easier, and you could probably share these types with the
| compiler too, so that would be a win perhaps.

  yup.  all the good old SGML propaganda comes back to life with this one.

| But I think I was wrong.

  yup.  and your argumentation is very close to what I used when I finally
  made up my mind that SGML would be way too costly to ever give any return
  on investment, either mine or in general.  sadly, I haven't seen any hard
  evidence that I'm wrong yet.

| The problem with having this whole bestiary of sorts-of-things-in-the-
| -language is that once you've defined them, then you've defined what
| sorts of things you can have in the language.  And you might be wrong,
| because there might be other sorts of things that you can have in the
| language, or in some extension of it, which you haven't thought of yet,
| and which it would now be hard to even conceive of.  So although
| everything would be nicer in the short term, you have really limited the
| way the language can develop because you've limited the sorts of macros
| that can be written.

  yup.  very good.  you have argued excellently against SGML's DTD concept
  without (I hope!) having suffered the pain of dealing with updates and
  changing requirements.

  incidentally, HTML "solved" this problem by requiring unknown elements
  (that's what the stuff with start-tag, contents, and end-tags is actually
  called) should cause the contents to be in-lined in the containing
  element, recursively.  this, of course, was the single most idiotic thing
  HTML could ever have done.  that _one_ decision led to the decision to
  use _comments_ for script languages, because there was no way to say "if
  you don't now this element, ignore it" -- there could have been, but they
  blew that chance, and that comments were such a crummy place to put
  things led to all kinds of other mind-bogglingly stupid ideas, like CSS.

  if you need an example of how horrible a language that names all it
  substructure components would be, take a good long look at SGML and HTML
  and XML, especially at how they are actually used in real life.  I trust
  I don't need to tell you to go away and never look back.

[ explanation elided ]
| Does that seem reasonable?

  yup.  sure does to me.

#:Erik
-- 
  The Microsoft Dating Program -- where do you want to crash tonight?
From: David Steuber "The Interloper
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <366febdd.700456873@news.newsguy.com>
On 08 Dec 1998 12:35:32 +0000, Tim Bradshaw <···@aiai.ed.ac.uk>
claimed or asked:

% Does that seem reasonable?

It seems very reasonable.

The thing that got me interested in Lisp was that I wanted to have a
scripting language / extension language embedded into a software
project.  I am not a veteran of interpreter or compiler
implementation, so ease of implementation was a big factor for me.

With Lisp's simple structure, it seemed like the ideal language to
use.  However, I am also lazy.  So lazy that I didn't even want to
code the interpreter or compiler.  I came to this group, poked and
prodded, and came away with the idea of getting CMUCL.

The compiler and interpreter are there, royalty free.  Not only that,
but as I continued to look at the language, I began to realize how
powerful it was.  I started to reconsider my original implementation
language choices: C++ or Java.  Lisp is just more expressive, although
I don't quite grok it yet.

This lead me to a Trinity.  I could write the core of my project in
CMUCL.  By providing a well documented API, others could add what ever
extensions they needed using CMUCL.  Finally, the coup de tat, the
file format could be Lisp itself.

The front end GUI component, when built, would really be fancy
dressing for a Lisp code generator.

My project is still very much in the vapor ware stage of early
planning.  I've been side tracked by many things lumped into the
category of life.  But I still visit this news group regularly to see
what further insight I can gain from the sages who shed their wisdom
here.

If I am not mistaken, the list can be used to implement pretty much
any other data structure that is in use in computer science and
engineering.  Simple is powerful.

--
David Steuber (ver 1.31.3a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.

May the source be with you...
From: Kellom{ki Pertti
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <xfzbtld3iky.fsf@kuovi.cs.tut.fi>
········@david-steuber.com (David Steuber "The Interloper") writes:
> If I am not mistaken, the list can be used to implement pretty much
> any other data structure that is in use in computer science and
> engineering.  

Provided that you ignore access time issues.
-- 
Pertti Kellom\"aki, Tampere Univ. of Technology, Software Systems Lab
From: David Steuber "The Interloper
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <36705d01.794956707@news.newsguy.com>
On 09 Dec 1998 09:01:01 +0200, Kellom{ki Pertti <··@kuovi.cs.tut.fi>
claimed or asked:

% ········@david-steuber.com (David Steuber "The Interloper") writes:
% > If I am not mistaken, the list can be used to implement pretty much
% > any other data structure that is in use in computer science and
% > engineering.  
% 
% Provided that you ignore access time issues.

I'm not suggesting one should implement all data structures with
lists.  Only that one can.

I reserve the right to use arrays, hashes, etc as the situation
warrants.  Lisp gives these things as built in types too.

--
David Steuber (ver 1.31.3a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.

May the source be with you...
From: Christopher Browne
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <74r8h9$b7i$5@blue.hex.net>
On 09 Dec 1998 09:01:01 +0200, Kellom{ki Pertti <··@kuovi.cs.tut.fi> wrote:
>········@david-steuber.com (David Steuber "The Interloper") writes:
>> If I am not mistaken, the list can be used to implement pretty much
>> any other data structure that is in use in computer science and
>> engineering.  
>
>Provided that you ignore access time issues.

Using lists, one can construct trees, and a whole variety of those data
structures that, in C/Pascal, would be represented using pointers.  An
extra cons or two is needed to build doubly-linked lists, with not
dramatically more overhead than one gets in C/Pascal. 

Since lists can contain references to other lists, as well as a variety
of "objects" including (I'm referencing Scheme here) pairs, ints, lists,
characters, strings, symbols, and boxes, this provides the ability to
implement pretty much any of the data structures that are pointer-based. 

The other *major* data structure that is commonly used that is not
readily (e.g. - efficiently) represented as a small number of list
conses is the "array" aka "vector." Its availability thereby gives us
ways of getting at all those O(1) algorithms. 

Since it's only certain array-oriented operations that are O(1), with
the *substantial* downside that some other operations head to O(n)
(exhaustive hash searches and "array lengthening" being common
examples), it should *not* be assumed that vectorizing everything would
be beneficial. 

The Lisp "typical assumption" of "everything a list" is different from
the not uncommon "everything an array" assumption that is particularly
characteristic of BASIC; neither is forcibly preferable, except for the
consideration that it is likely easier to implement weird data
structures using lists in Lisp than it is to do the equivalent using
arrays in BASIC... 

-- 
Actually, typing random strings in the Finder does the equivalent of
filename completion.  (Discussion in comp.os.linux.misc on the
intuitiveness of commands: file completion vs. the Mac Finder.)
········@ntlug.org- <http://www.hex.net/~cbbrowne/langlisp.html>
From: Per Bothner
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <74scqp$afd$1@rtl.cygnus.com>
In article <············@blue.hex.net>,
Christopher Browne <········@hex.net> wrote:
>Since it's only certain array-oriented operations that are O(1), with
>the *substantial* downside that some other operations head to O(n)
>(exhaustive hash searches and "array lengthening" being common
>examples),

Array lengthening is on average O(1) (per element) if you do it right,
(i.e. when it is full, double the space.  (You *still* save space
compared to linked lists!)

I don't understand your point about "exhaustive hash searches".

> it should *not* be assumed that vectorizing everything would
> be beneficial.

Vectorizing everything would be beneficial.  Vectorizing
*almost* everything would be even more beneficial ...
-- 
	--Per Bothner
Cygnus Solutions     ·······@cygnus.com     http://www.cygnus.com/~bothner
From: Christopher B. Browne
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <slrn7757qv.mjr.cbbrowne@godel.brownes.org>
On 11 Dec 1998 16:19:37 -0800, Per Bothner <·······@cygnus.com> posted:
>In article <············@blue.hex.net>,
>Christopher Browne <········@hex.net> wrote:
>>Since it's only certain array-oriented operations that are O(1), with
>>the *substantial* downside that some other operations head to O(n)
>>(exhaustive hash searches and "array lengthening" being common
>>examples),
>
>Array lengthening is on average O(1) (per element) if you do it right,
>(i.e. when it is full, double the space.  (You *still* save space
>compared to linked lists!)

Possibly so...

>I don't understand your point about "exhaustive hash searches".

Hash tables require O(1) operations for inserts and for searches for
*specific keys.* If you only have a partial key, it takes O(n) operations,
as you will have to scan the whole table.

>> it should *not* be assumed that vectorizing everything would
>> be beneficial.
>
>Vectorizing everything would be beneficial.  Vectorizing
>*almost* everything would be even more beneficial ...

I'm a little less optimistic.  Vectorizing all the right things would be
extremely beneficial.  Vectorizing everything has more ambiguous results...

-- 
Those who do not understand Unix are condemned to reinvent it, poorly. 	
-- Henry Spencer          <http://www.hex.net/~cbbrowne/lsf.html>
········@hex.net - "What have you contributed to Linux today?..."
From: Per Bothner
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <74ughf$ilo$1@rtl.cygnus.com>
In article <·······················@godel.brownes.org>,
Christopher B. Browne <········@hex.net> wrote:
>Hash tables require O(1) operations for inserts and for searches for
>*specific keys.* If you only have a partial key, it takes O(n) operations,
>as you will have to scan the whole table.

Yes - and why is this a "downside" to using vectors insteads of lists?

-- 
	--Per Bothner
Cygnus Solutions     ·······@cygnus.com     http://www.cygnus.com/~bothner
From: Christopher B. Browne
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <slrn776k74.usb.cbbrowne@godel.brownes.org>
On 12 Dec 1998 11:35:11 -0800, Per Bothner <·······@cygnus.com> posted:
>In article <·······················@godel.brownes.org>,
>Christopher B. Browne <········@hex.net> wrote:
>>Hash tables require O(1) operations for inserts and for searches for
>>*specific keys.* If you only have a partial key, it takes O(n) operations,
>>as you will have to scan the whole table.
>
>Yes - and why is this a "downside" to using vectors insteads of lists?

Hash tables are a special case of vectors, thus sharing some properties,
unfortunately including the one that you can't do better than O(n) for
approximate searches.

If the data was in some sort of order, whether as a sorted array, or
expressed as an n-ary tree (which nicely maps onto lists...), then one can
generally do better, getting something like O(log n) searches.

The overall point is that different data structures have different
properties with respect to how rapidly one may access data.  And lists
aren't as bad as one might expect...

-- 
Those who do not understand Unix are condemned to reinvent it, poorly. 	
-- Henry Spencer          <http://www.hex.net/~cbbrowne/lsf.html>
········@hex.net - "What have you contributed to Linux today?..."
From: Kelly Murray
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <ku2z1t85h.fsf@www.intellimarket.com>
>From: ·······@cygnus.com (Per Bothner)
> Array lengthening is on average O(1) (per element) if you do it right,
> (i.e. when it is full, double the space.  (You *still* save space
> compared to linked lists!)

This is a good point, that since linked lists take double the space of
a vector, "wasting" up to half a vector with empty space is still
a space improvement, and perhaps more important the locality of
reference for the same space usage is *much* better with the vector,
since all the elements are packed together in the top of the vector.

This is an interesting issue for me, since space and locality
becomes a concern when dealing with a persistent object store,
where doubling the space doesn't mean 1mb vs 2mb, but 1gb vs 2gb,
and the real chance of not fitting the data into available
physical memory has serious performance implications.

Common Lisp has vector-push-extend, and by using LOOP it isn't
too painful to change representations, though I wish it didn't
even need any change (i.e. loop for x in list  == loop for x across vector)
and may very well implement a new LOOP implementation that supports
this.

To take it even further, I think we need a collection data type
that is a very generalized data type, and LOOP will iterate
through this as well (loop for x in collection),
and furthermore, adding query-language type constraints
(loop for x in collection where (> (person.age x) 40)
   do ..)

-Kelly Murray    ···@intellimarket.com
From: Tim Bradshaw
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <ey3pv9tppdz.fsf@haystack.aiai.ed.ac.uk>
* David Steuber "The Interloper" wrote:
> If I am not mistaken, the list can be used to implement pretty much
> any other data structure that is in use in computer science and
> engineering.  Simple is powerful.

Well, that's really right only in a bad sense, and it's a classic Lisp
mistake to assume it's right in any other sense.  The problem is lists
have O(n) access time for the nth slot, and this is crippling if you
really want something with O(1) access time, like an array.  I suspect
that a great deal of the `lisp is slow' mythology comes from people
using lists when they want some vector/array type structure really.
Fortunately this isn't so prevalent now I think (at least, we have no
problem making people understand it when we teach).

--tim
From: Reini Urban
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <366e9aab.28656786@judy>
Tim Bradshaw <···@aiai.ed.ac.uk> wrote:
>* David Steuber "The Interloper" wrote:
>> If I am not mistaken, the list can be used to implement pretty much
>> any other data structure that is in use in computer science and
>> engineering.  Simple is powerful.

>Well, that's really right only in a bad sense, and it's a classic Lisp
>mistake to assume it's right in any other sense.  The problem is lists
>have O(n) access time for the nth slot, and this is crippling if you
>really want something with O(1) access time, like an array.  I suspect
>that a great deal of the `lisp is slow' mythology comes from people
>using lists when they want some vector/array type structure really.
>Fortunately this isn't so prevalent now I think (at least, we have no
>problem making people understand it when we teach).

that was exactly my first argument when i read your first posting.
having vectors and allowing vectors of vectors as primitives instead of
linked lists would greatly increase efficiency and would enable some
"forward looking" in the interpreter, but would probably complicate
implementation and language design.
e.g. some kind of smallest pre-allocated vector size must be defined in
the language (say init-size=10 or 1000) and some typical reallocation
sizes must be given. (say 10*init-size). if the whole vector is copied
on reallocation or if chunks are just linked together then is the
question.
i would favour the second to enable the simpliest gc scheme and easy
exceptions (just jump to a known vector element).

so primitives would be (setnth) and (getnth) which guarantee O(1) for
vectors lower than init-size atomic elements and need reallocation on
overflow => O(1+c).
the cons/car/cdr/atom paradigm is enhanced to setnth/getnth/atomnth.

implementing set theory would be much more efficient then.
pointer arithmetic would be well-defined.

it would be no problem to represent code as well as data with vectors
only. arguments could be picked in random order and the order of
evaluation must be undefined then as in scheme. (restricting to
side-effect free arguments)

i only cannot think of some typical and useful examples now...
primitives, special functions, atomic values, and such

(defun eval (expr nth env)
  (cond ((atomnth nth expr)    (value-of (getnth nth) env))
        ((primitivep nth expr) (apply-primitive (getnth nth) env))
        ...

i feel completely weird now!
immediate access to ALL the code and data at once? 
or immediate access just to the chunk of the current expression?
should getnth/setnth 
1) be extended by relative access such as (getnth nth [expr]), 
2) use absolute values, as in a early basic without subroutines, thus
(getnth nth) or 
3) allow only (getnth nth expr).

smoke comes out of my left ear, i have to stop and think about it.
isn't this not just another interpretated assembler?
---
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
From: Kent M Pitman
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <sfw3e6puspv.fsf@world.std.com>
Reini Urban <······@sbox.tu-graz.ac.at> writes:

> >The problem is lists
> >have O(n) access time for the nth slot, and this is crippling if you
> >really want something with O(1) access time, like an array.

Big-O notation is meaningful mostly where there are numbers large enough
for it to matter.  The overhead of accessing an array header can be enough
that nth or certainly cadr and caddr may be faster than or at least
competitive aref in some implementations unless at least you have heavily
declared your code and maybe even then.

> that was exactly my first argument when i read your first posting.
> having vectors and allowing vectors of vectors as primitives instead of
> linked lists would greatly increase efficiency 

Also, I think it was Dick Waters who once said that "Functions that have
more than ten arguments have too few."  This is really an observation about
short term memory and it says that if you get more than 10 args, you're
probably forgetting something because the task of remembering for sure that
you've done a complete enumeration is materially harder.  This is one reason
that keyword args are very popular for situations with a lot of args, such
as the function WRITE.  And neither &rest nor &key arguments necessarily
access better with with aref than with cons references, since most reasonable
programs accessing them will need to iterate over them not randomly access
them and iterating sequentially over a list isn't terrible speed-wise (modulo
paging issues, which for cons cells sequentially allocated and never rplacd'd
is also likely.)

Further, for very small lists it's not even clear that arrays are more
space efficient because of header overhead.

> and would enable some
> "forward looking" in the interpreter, but would probably complicate
> implementation and language design.

Yes, that's right.  But (I seem to be quoting myself a lot today--I
guess these are just things on my mind) as I said at my recent talk at
the lisp conference, sometimes the enabling feature of a design isn't
the technical decision it's the fact of the decision itself.  That is,
I think the enabling power of Lisp in code-manipulation is not that it
could represent itself (since most languages can) or the fact that it
chose the most efficient representation (since there is room to
quibble on that) but rather that it just made a decision and it said
"this decision is done and will no longer be subject of debate". The
mere power of not wasting the community's time debating "best
representation" is so much more valuable than fussing over what's the
most efficient thing that I STRONGLY recommend that this discussion be
treated as suspect not for its technical content so much as for its
implicit assumption that it is ever a good idea to go back revisit a
point upon which so much technology has been built.

If you made a new language, it's worth considering.  Postscript, for
example, uses what seem to me to be the equivalent of "arrays" to as
chunks of code.  MOO takes the alternate approach of offering the list
abstraction but using what are really vectors internally to implement
them (copying where necessary to extend things).  These are good design
trade-offs in the context of making a new language.  But once the language
is made, stability and lack of confusion is key.

> it would be no problem to represent code as well as data with vectors
> only. arguments could be picked in random order and the order of
> evaluation must be undefined then as in scheme. (restricting to
> side-effect free arguments)

Of course, since the language requires semantic preprocessing before
execution, there's nothing that keeps you from processing lists into
vectors when they're to be interpreted.  You have to walk over the
code for macros, etc. anyway.  (Whether you do it lazily or all at
once, the effect is the same: you could still produce an alternate
data structure that you actually executed, so performance speed is not
affected by the choice of user-representation.  And programs that
modify their source program structure while executing are pretty
ill-defined in CL, so it's not like making a separate data structure
affects that much.)
From: Kelly Murray
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <366EBF49.1C462187@IntelliMarket.Com>
Source code as lists works well, it simplifies things greatly,
particularly writing macros and implementing the interpreter,
and some parts of the compiler. 

However, as you need more information about the code, 
then the problem becomes the same as any other application,
in which case the use of Objects becomes useful.
Certainly the compiler converts source code lists into objects
(probably defstructs in all current implementations?)

Also take a look at XREF, which I believe ACL includes as part
of its implementation, which represents information about source
code.  

Using XREF type implementation, one might be able to do
incremental updates while still using statically optimized code.
e.g after you change a class definition you can efficiently
find and recompile all the functions in which the inlined slot access
was used.  This is what Lucid's ill-fated C++ Cadillac IDE
was trying to do for C++, bring the kind of interactive, incremental
development they knew worked for lisp.

With a Lisp OODB, and a web browser UI, this is an exciting prospect
for the next generation of IDE where Lisp can be at the forefront.

At this point, then one could have a source-code editor that
isn't just text-based, but a "structure" based one, ala XEROX,
(or viaweb!), at which points lists themselves may not be
ideal for an internal representation.  

And to take it to yet another level, you can then add in
comments, references, dependencies, documentation as part of the source
code with clickable links that tie it all together.
Remember HyperCard?  What was that 10 years ago?

Clearly none of this is any great new idea, its just nobody has
pulled it all together and made it all work, which of course
is a very long and hard job with little prospect for a ROI.

-Kelly Murray  ···@intellimarket.com
From: Christopher Browne
Subject: Re: Lisp source code as lists (rather than something richer)
Date: 
Message-ID: <74nl6g$fdc$5@blue.hex.net>
On Wed, 09 Dec 1998 16:17:16 GMT, Reini Urban <······@sbox.tu-graz.ac.at> wrote:
>Tim Bradshaw <···@aiai.ed.ac.uk> wrote:
>that was exactly my first argument when i read your first posting.
>having vectors and allowing vectors of vectors as primitives instead of
>linked lists would greatly increase efficiency and would enable some
>"forward looking" in the interpreter, but would probably complicate
>implementation and language design.

This means that each "sublist" builds a new vector. 

Upside: Large linear lists benefit from easy random access. 

Downside: consing gets a whopping lot more expensive, as every operation
requires resizing a vector to add the element.  Methinks this is the
"killer," as cons gets used so much.  (Practical upshot is probably to
have a strategy to pre-allocate space, and extend vectors by increasing
amounts if it looks like they're growing fast; this nonetheless adds
overhead...)

"Irrelevant" side: There will be lots of small vectors generated, which
will neither be greatly assisted by the use of vectors, nor greatly
injured thereby.  Iterative code that exhaustively reads through a
vector will not be made faster. 

>implementing set theory would be much more efficient then.

Ah.  But sets aren't ordered.  Vectors more forcibly enforce ordering
than lists.  It's not obvious that sets get more efficient. 

Of course, Lisp already has arrays, and Scheme already has vectors.  
I'm not up to the task, but I expect it wouldn't be *too* nasty hard to
macro together critical Scheme functions to use vectors rather than
lists, and thereby see how feasible it is.
-- 
"sic transit discus mundi"
(From the System Administrator's Guide, by Lars Wirzenius)
········@ntlug.org- <http://www.ntlug.org/~cbbrowne/langlisp.html>