Guide to Lisp, v1.20

388 views
Skip to first unread message

Pascal Costanza

unread,
Aug 27, 2002, 3:50:25 PM8/27/02
to
Hi everybody,

I have just released version 1.20 of my highly opinionated guide to Lisp
at http://www.pascalcostanza.de/lisp/guide.html. I have tried to
incorporate as much feedback as possible, and I have also tried to
include all the names of the people who provided the feedback in the
acknowledgement sections. (If you have any objections to being mentioned
there, please let me know.)

I think the guide has improved a lot because of this feedback, so I
would like to thank you all. I have also added a change log so that you
can quickly check for changes.

All the best,
Pascal

--
Pascal Costanza University of Bonn
mailto:cost...@web.de Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)

Adam Warner

unread,
Aug 27, 2002, 6:34:02 PM8/27/02
to
Pascal Costanza wrote:

> Hi everybody,
>
> I have just released version 1.20 of my highly opinionated guide to Lisp
> at http://www.pascalcostanza.de/lisp/guide.html. I have tried to
> incorporate as much feedback as possible, and I have also tried to
> include all the names of the people who provided the feedback in the
> acknowledgement sections. (If you have any objections to being mentioned
> there, please let me know.)
>
> I think the guide has improved a lot because of this feedback, so I
> would like to thank you all. I have also added a change log so that you
> can quickly check for changes.

I started reading it last night and am astonished at the depth of
information and links it contains. Thank you.

Regards,
Adam

Knut Arild Erstad

unread,
Aug 28, 2002, 9:03:09 AM8/28/02
to
[Pascal Costanza]
: Hi everybody,

:
: I have just released version 1.20 of my highly opinionated guide to Lisp
: at http://www.pascalcostanza.de/lisp/guide.html. I have tried to
: incorporate as much feedback as possible, and I have also tried to
: include all the names of the people who provided the feedback in the
: acknowledgement sections. (If you have any objections to being mentioned
: there, please let me know.)
:
: I think the guide has improved a lot because of this feedback, so I
: would like to thank you all. I have also added a change log so that you
: can quickly check for changes.

Excellent work. One comment to the car/cdr/mapcar point; you might not be
aware that there are in fact functions named "first" and "rest" that are
identical to "car" and "cdr".

Also, you might be interested in the book "Structure and Interpretation of
Computer Programs" by Abelson and Sussman, which is available online at
http://mitpress.mit.edu/sicp/full-text/book/book.html. IMHO it is one of
the best books on programming available. It uses Scheme, but even people
who don't like or don't use Scheme will benefit greatly from it.

--
Knut Arild Erstad

But if less is more, then just think how much more more will be.
-- from "Frasier"

Pascal Costanza

unread,
Aug 28, 2002, 9:41:01 AM8/28/02
to
Knut Arild Erstad wrote:
>
> [Pascal Costanza]
> : Hi everybody,
> :
> : I have just released version 1.20 of my highly opinionated guide to Lisp
> : at http://www.pascalcostanza.de/lisp/guide.html.

[...]

> Excellent work. One comment to the car/cdr/mapcar point; you might not be
> aware that there are in fact functions named "first" and "rest" that are
> identical to "car" and "cdr".

Yes, I am aware of these functions. However, they don't help you as a
Lisp newbie because you spend much more time on reading other people's
code than writing your own. I haven't seen example Lisp code that
actually used "first" and "rest".

Furthermore, when you learn a new language you also have to learn its
idiomatic use. There's no way around this.

> Also, you might be interested in the book "Structure and Interpretation of
> Computer Programs" by Abelson and Sussman, which is available online at
> http://mitpress.mit.edu/sicp/full-text/book/book.html. IMHO it is one of
> the best books on programming available. It uses Scheme, but even people
> who don't like or don't use Scheme will benefit greatly from it.

I also know this book but it is a book on programming in the first place
that just happens to use Scheme. If I want to learn a new language I
don't want to learn about computer science from scratch again.

Nevertheless, thanks for your comments. ;)

Espen Vestre

unread,
Aug 28, 2002, 9:48:45 AM8/28/02
to
Pascal Costanza <cost...@cs.uni-bonn.de> writes:

> I haven't seen example Lisp code that actually used "first" and "rest".

That's _really_ odd. I wonder how old the code you've been looking at is?
--
(espen)

Pascal Costanza

unread,
Aug 28, 2002, 10:25:17 AM8/28/02
to

I meant "first" and "rest" as a _general_ replacement for "car" and
"cdr". The papers and books I have seen and that I link to generally use
"car" and "cdr", so you have to understand what they mean. I have the
impression that many people still prefer the latter over the former, and
I agree.

See the fourth entry at http://www.paulgraham.com/arcfaq.html for a
rationale given more recently.

Knut Arild Erstad

unread,
Aug 28, 2002, 10:33:43 AM8/28/02
to
[Pascal Costanza]
:
: Yes, I am aware of these functions. However, they don't help you as a

: Lisp newbie because you spend much more time on reading other people's
: code than writing your own. I haven't seen example Lisp code that
: actually used "first" and "rest".

I actually use "first" and "rest" all the time when I'm working with
proper lists, and "car" and "cdr" when I'm working with some other
structure that happens to use conses (which is almost never). But you are
of course right that you need to learn them anyway.

: I also know this book but it is a book on programming in the first place


: that just happens to use Scheme. If I want to learn a new language I
: don't want to learn about computer science from scratch again.

When learning new paradigms, it is often useful to start from scratch. :)
And seriously, SICP has a wealth of ideas that should be of interest even
for experienced programmers.

Erik Naggum

unread,
Aug 28, 2002, 10:45:58 AM8/28/02
to
* Knut Arild Erstad

| Also, you might be interested in the book "Structure and Interpretation of
| Computer Programs" by Abelson and Sussman, which is available online at
| http://mitpress.mit.edu/sicp/full-text/book/book.html. IMHO it is one of
| the best books on programming available. It uses Scheme, but even people
| who don't like or don't use Scheme will benefit greatly from it.

I have just recently completed the first pass of two other MIT Press books.

Gerald Jay Sussman and Jack Wisdom with Meinhard E. Mayer: Structure and
Interpretation of Classical Mechanics, which uses Scheme to do exploratory
mathematics, and this is really exciting. Never quite got the hang of fluid
mechanics (I wrote much of the support software for a girlfriend who wrote
her thesis on turbulence in narrow tubes, but had no time to delve into the
reasoning behind the exploratory computations), but this enjoyable book lets
me toy with the world of classical mechanics in a way that is reminiscent of
the old text-based virtual reality-games.

Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi:
How to Design Programs; An Introductino to Programming and Computing, which
also uses Scheme as the teaching vehicle. I found it much a better book
than SICP 2, which I have yet to make a full pass through even thought I
bought it long ago with that express intention. Amazon.com's look inside
feature has ignored the preface, which I find unwise, because it sets the
stage excellently. I take the liberty under the fair use doctrine to quote
the first few paragraphs from it.

It goes against the grain of modern education to teach
children to program. What fun is there in making plans,
acquiring discipline in organizing thoughts, devoting
attention to detail and learning to be self-critical?

-- Alan Perlis, Epigrams in Programming

Many professions require some form of computer programming. Accountants program
spreadsheets and word processors; photographers program photo editors; musicians
program synthesizers; and professional programmers instruct plain computers.
Programming has become a required skill.

Yet programming is more than just a vocational skill. Indeed, good programming
is a fun activity, a creative outlet, and a way to express abstract ideas in a
tangible form. And designing programs teaches a variety of skills that are
important in all kinds of professions: critical reading, analytical thinking,
creative synthesis, and attention to detail.

We therefore believe that the study of program design deserves the same central
role in general education as mathematics and English. Or, put more succinctly,

*everyone should learn how to design programs*.

Of course, I'm an old fart and I ground my baby teeth on The Little Lisper
back in 1978 or so and consider Scheme to have great educational value, but
also serious dangers and drawbacks when the student does not realize that one
cannot hope to keep the baby teeth just because it is painful to replace them
with the real killer teeth. (roar) => t.

--
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

Jens Axel Søgaard

unread,
Aug 28, 2002, 11:02:10 AM8/28/02
to
Erik Naggum wrote:

> Matthias Felleisen, Robert Bruce Findler, Matthew Flatt,
> Shriram Krishnamurthi: How to Design Programs; An
> Introductino to Programming and Computing

For Pascal:

http://www.htdp.org

--
Jens Axel Søgaard

sv0f

unread,
Aug 28, 2002, 11:09:04 AM8/28/02
to
In article <3D6CD2ED...@cs.uni-bonn.de>, cost...@web.de wrote:

>Knut Arild Erstad wrote:
>> Excellent work. One comment to the car/cdr/mapcar point; you might not be
>> aware that there are in fact functions named "first" and "rest" that are
>> identical to "car" and "cdr".
>
>Yes, I am aware of these functions. However, they don't help you as a
>Lisp newbie because you spend much more time on reading other people's
>code than writing your own. I haven't seen example Lisp code that
>actually used "first" and "rest".

Perhaps a fair point, although a footnote containing this justification
would be informative.

>Furthermore, when you learn a new language you also have to learn its
>idiomatic use. There's no way around this.

I consider the over-use of CAR and CDR historical, not idiomatic.

When I see CAR and CDR in modern code, I interpret them as accessors
for the "cons" data structure. On the other hand, FIRST and REST imply
the presence of a "list" data structure. That lists are made up of
conses is an implementation detail.

So if you're goal is to convey idiomatic usage, and if my idioms are
representative, then you should explain CAR and CDR as part of the cons
family and FIRST and REST as part of the list family. Again, this
discussion could be placed in a footnote.

PS: Don't let this negative feedback on what point dissuade you.
I find your document excellent.

Christopher Browne

unread,
Aug 28, 2002, 12:51:42 PM8/28/02
to
Oops! Pascal Costanza <cost...@cs.uni-bonn.de> was seen spray-painting on a wall:

> Knut Arild Erstad wrote:
>>
>> [Pascal Costanza]
>> : Hi everybody,
>> :
>> : I have just released version 1.20 of my highly opinionated guide to Lisp
>> : at http://www.pascalcostanza.de/lisp/guide.html.
>
> [...]
>
>> Excellent work. One comment to the car/cdr/mapcar point; you might not be
>> aware that there are in fact functions named "first" and "rest" that are
>> identical to "car" and "cdr".

> Yes, I am aware of these functions. However, they don't help you as
> a Lisp newbie because you spend much more time on reading other
> people's code than writing your own. I haven't seen example Lisp
> code that actually used "first" and "rest".

> Furthermore, when you learn a new language you also have to learn its
> idiomatic use. There's no way around this.

Modern idiomatic use _is_ to use FIRST and REST. When I check code
into CVS at the end of a project, I try take a look at it with a view
to cleaning up code that has such undesirable idioms.

The ongoing use of CAR/CDR is kind of like the way occasional bits of
Middle English still pop their way into modern usage, or the way that
people use bits of Shakespearean-era English due to:
a) Quotes from Shakespeare, and
b) The fact that the King James Version of the Bible published in
the early 17th century is still in active use in the Protestant
church community.

I would simply encourage you to point out the presence of the modern
functions. That's not even the _important_ part.

What is _better_ to point out is that code that is filled with
car/cdr/caddr/cdar/... is often termed "cadaverous," which is
certainly a pun due to the congruence of letters in the word with the
letters in car/cdr.

"Cadaverous" code tends to be very messy to read and modify,
irrespective of whether you use car/cdr or first/rest, and the
presence of a lot of this stuff is suggestive of a novice programmer.
The more experienced you get, the less you should _need_ to use these
functions.

With more experience comes such things as:
-> Using more specialized data structures, like arrays, structures,
and CLOS class instances, where car/cdr simply don't apply;

-> Using destructuring operators to _describe_ the bindings that
you need, rather than fiddling around with the lists by hand;

-> Building functions that produce the results that are needed, where
it won't be _necessary_ to fiddle with list contents.
--
(concatenate 'string "cbbrowne" "@acm.org")
http://cbbrowne.com/info/linuxxian.html
Send messages calling for fonts not available to the recipient(s).
This can (in the case of Zmail) totally disable the user's machine and
mail system for up to a whole day in some circumstances.
-- from the Symbolics Guidelines for Sending Mail

Tim Bradshaw

unread,
Aug 28, 2002, 1:09:58 PM8/28/02
to
* Pascal Costanza wrote:
> Yes, I am aware of these functions. However, they don't help you as a
> Lisp newbie because you spend much more time on reading other people's
> code than writing your own. I haven't seen example Lisp code that
> actually used "first" and "rest".

I use them all the time. In fact I usually distinguish two cases: If
I'm using a cons as some kind of data structure which happens to be
convenient, I use CAR / CDR. If I'm thinking of it as an ordered
list, I use FIRST / REST.

I just did some rudimentary measurements: in ~21,000 lines of code I
have 146 calls to FIRST, 48 to CAR, 78 to REST and 100 to CDR (these
are calls that are trivially findable by fgrep, so I have missed #'car
&c). Almost all of this code is less than a year old.

--tim

Bulent Murtezaoglu

unread,
Aug 28, 2002, 1:20:37 PM8/28/02
to
>>>>> "TimB" == Tim Bradshaw <t...@cley.com> writes:
[...]
TimB> I use them all the time. In fact I usually distinguish two
TimB> cases: If I'm using a cons as some kind of data structure
TimB> which happens to be convenient, I use CAR / CDR. If I'm
TimB> thinking of it as an ordered list, I use FIRST / REST. [...]

Hmm, unlike others it never even occurs to me that first and rest are
there when I am writing code. I understand the above might be a good
habit to get into but I am curious how you guys made yourselves get into
this habit to start with?

cheers,

BM

Erik Naggum

unread,
Aug 28, 2002, 1:57:58 PM8/28/02
to
* Pascal Costanza <cost...@cs.uni-bonn.de>

| However, they don't help you as a Lisp newbie because you spend much more
| time on reading other people's code than writing your own. I haven't seen
| example Lisp code that actually used "first" and "rest".

Certainly a valid point, but I think it aids understanding nonetheless to
explain that `first´ and `rest´ are the "modern" versions of `car´ and `cdr´
and that other languages have `head´ and `tail´. The latter may have some
sexual connotations that may or may not make the reader remember things
better. Bumber sticker texts like "my other car is a cdr" may also help.
Anything to make people get used to these common words in Lisp code.

| Furthermore, when you learn a new language you also have to learn its
| idiomatic use. There's no way around this.

Very true.

| I also know this book but it is a book on programming in the first place
| that just happens to use Scheme. If I want to learn a new language I don't
| want to learn about computer science from scratch again.

Sometimes, the only way to learn something really well is to revert to the
state of mind of a novice and reawaken to the raw observations that you have
accumulated instead of relying on the conclusions you have reached from the
exogenous premises absorbed through teaching and bookish learning. (This
may trigger Zen receptors in some people. :)

I enjoy reading new introductory textbooks, because not only the does topic
evolve, pedagogical principles change, too. Different authors have different
angles on the same topic and approach abstractions along widely differing
paths. I read Apostol on Calculus and Analysis in high school, was forced
to use Edwards and Penney at the U of Oslo, but discovered that much had
happened from the first to the fifth edition, then went back to Courant and
John. I really enjoy helping other people grasp something difficult through
unexpected means, to get them out of their usual mode of thinking. Nothing
beats exposure to several different ways to explain the same concept to get
rid of artefacts of one style. The same applies to computer concepts, where
there are so many vastly different approaches to the same core ideas. The
ability to recognize the same thing in different clothing and shapes is like
being able to read both handwriting and print mirrored and rotated or the
ability to manipulate 3D objects in your head. It takes serious amounts of
practice, but, like juggling, teaches you something you could not explain
without knowing it. Computer programming is like the ablility or skill to
see what Picasso saw from all the different angles at once. If it is an art,
the crucial element of art is to look at things from an angle that produces
new insight or at least has that potential. The fall-out of reading lots of
textbooks at various levels is that you can actually recomment something to
people. "This is the best book I have read on <whatever>" has no merit if
you have only read one. The incredible chore of an academic education or
even a liberal education acquired on your own from reading something like
the Harvard Classics or Britannica's Great Books is that the whole point is
to acquire the ideas of many people and this is painfully time-consuming.

But if you only want one other person's ideas or are inclined to believe
only one set of ideas at a time, I hope it is not confused with education.

Tim Bradshaw

unread,
Aug 28, 2002, 2:14:53 PM8/28/02
to
* Bulent Murtezaoglu wrote:

> Hmm, unlike others it never even occurs to me that first and rest
> are there when I am writing code. I understand the above might be a
> good habit to get into but I am curious how you guys made yourselves
> get into this habit to start with?

I think that at some point I decided that I needed to think about when
to use lists and when to use other structures, and since then I've
tended to be fairly conscious about choice of structure - should I use
an alist, a hashtable, a list, a structure &c &c. One of the divisions
I make (which I realise is not actually there in the system) is
then between using a list and a cons. If I'm using a cons, I use CAR
/ CDR, if I'm using a list I use FIRST / REST.

And sometimes I'm using some other conceptual structure altogether,
even though it may implementationally be conses, and in that case I'll
generally have some other accessor functions (often defined as inlined
functions so I don't pay any cost).

There is one significant exception to all this - I tend to use CDDR
say, even for conceptual lists, rather than (rest (rest ...)), because
I find it easier. This is only true for the CD*R functions, not for
CA*R ones, where I'd use SECOND / ... / NTH.

--tim

Nils Goesche

unread,
Aug 28, 2002, 2:47:12 PM8/28/02
to
Bulent Murtezaoglu <b...@acm.org> writes:

> >>>>> "TimB" == Tim Bradshaw <t...@cley.com> writes:
> [...]
> TimB> I use them all the time. In fact I usually distinguish two
> TimB> cases: If I'm using a cons as some kind of data structure
> TimB> which happens to be convenient, I use CAR / CDR. If I'm
> TimB> thinking of it as an ordered list, I use FIRST / REST. [...]
>
> Hmm, unlike others it never even occurs to me that first and rest
> are there when I am writing code.

Same here. I learned the meaning of CAR and CDR right after SETQ. I
had no problems at all learning their meaning as a newbie. There is
lots of literature containing CAR and CDR, I think more than there is
that uses FIRST and REST. And I didn't like FIRST and REST at all
when I first met them. They look somewhat like an attempt to hide the
fact that lists are made up of cons cells, as if that was something
you have to keep secret from newbies. I sometimes consider switching
to the form of usage Tim describes, but frankly I doubt that I'll ever
do that. Taking the REST of a cons cell seems just unnatural to me.

Newbies have other problems. I think people should spend more time
thinking about how to explain things like binding, object identity,
read/compile/load time and call-by-value that are much harder to
understand than CAR and CDR, even if you gave them new names.

To me, traditional notations like CAR, CDR, RPLACA and friends are
part of the /charme/ of Lisp; I like it that you can take a text from
the sixties and understand the Lisp code in it. That is nothing to be
ashamed of, rather the opposite: Tradition is not something bad. Lisp
is so great /because/ so many smart people have been working on it for
/decades/.

And maybe it is time to mention that not /all/ code that uses lists is
automatically bad and ``cadaverous''; using a vector where a list is
the natural choice is just as dumb as doing it the other way around.

> I understand the above might be a good habit to get into but I am
> curious how you guys made yourselves get into this habit to start
> with?

I guess you'd have to make a conscious decision. The question is
whether you should. I think not.

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

PGP key ID 0x0655CFA0

Dorai Sitaram

unread,
Aug 28, 2002, 3:18:16 PM8/28/02
to
In article <87lm6qa...@cinifa.internal>,

I am a car/cdr user myself.

I might consider using first, second, ..., if
zeroth == car,
first == cadr,
second == caddr,
...

Erik Naggum

unread,
Aug 28, 2002, 3:24:31 PM8/28/02
to
* Bulent Murtezaoglu

| Hmm, unlike others it never even occurs to me that first and rest are there
| when I am writing code. I understand the above might be a good habit to get
| into but I am curious how you guys made yourselves get into this habit to
| start with?

I concur with differentiation according as the argument is a list or a tree.
If a list, `first´, `second´, `third´, ..., `tenth´, and `rest´ apply. If a
tree, `car´, `cdr´, `caar´, `cadr´, `cdar´, ... `cddddr´ apply. We see that
`first´, `car´, `rest´, and `cdr´ are the trivial or degenerate case.

Bill Clementson

unread,
Aug 29, 2002, 12:18:09 AM8/29/02
to
Pascal Costanza <cost...@cs.uni-bonn.de> writes:

> Espen Vestre wrote:
> >
> > Pascal Costanza <cost...@cs.uni-bonn.de> writes:
> >
> > > I haven't seen example Lisp code that actually used "first" and "rest".

FWIW, Peter Norvig's PAIP uses first/rest in preference to car/cdr in
much of his code.

--
Bill Clementson

Bruce Hoult

unread,
Aug 29, 2002, 6:10:07 AM8/29/02
to
In article <akiv2t$1it2b1$1...@ID-125932.news.dfncis.de>,
Christopher Browne <cbbr...@acm.org> wrote:

> With more experience comes such things as:
> -> Using more specialized data structures, like arrays, structures,
> and CLOS class instances, where car/cdr simply don't apply;
>
> -> Using destructuring operators to _describe_ the bindings that
> you need, rather than fiddling around with the lists by hand;
>
> -> Building functions that produce the results that are needed, where
> it won't be _necessary_ to fiddle with list contents.

-> using multiple value function returns.

-- Bruce

Wolfhard Buß

unread,
Aug 29, 2002, 6:41:01 AM8/29/02
to
Bulent Murtezaoglu <b...@acm.org> writes:

> Hmm, unlike others it never even occurs to me that first and rest are
> there when I am writing code. I understand the above might be a good

> habit to get into this habit to start with?

Lispers know, that a Lisp object is either an atom or a cons, i.e.
a data type with constructor cons, and accessors car and cdr, that
fulfils (1)-(3).

(car (cons <car> <cdr>)) => <car> (1)
(cdr (cons <car> <cdr>)) => <cdr> (2)

(cons (car <cons>) (cdr <cons>)) => <cons> (3)

Usually the data type list, with constructors list*, list, make-list
is implemented in terms of cons, such that a non-empty list is a cons
and vice versa, such that some Lispers even use cons to construct a
list, dare to use car and cdr to select the components of a list,
instead of the canonical accessors first and rest.
Allen calls "these representation-dependent coding tricks" dangerous.
Strachey calls them puns (according to Allen).

--
"I believe in the horse. The automobile is a passing phenomenon."
-- Kaiser Wilhelm II. (1859-1941)

Pascal Costanza

unread,
Aug 29, 2002, 9:36:35 AM8/29/02
to
Knut Arild Erstad wrote:
>
> [Pascal Costanza]

> : I have just released version 1.20 of my highly opinionated guide to Lisp
> : at http://www.pascalcostanza.de/lisp/guide.html.

[...]

> Excellent work. One comment to the car/cdr/mapcar point; you might not be
> aware that there are in fact functions named "first" and "rest" that are
> identical to "car" and "cdr".

After the many arguments for and against "first" and "rest" I have
slightly changed the wording of the paragraph in question. I think I
have found a good compromise - see version 1.22 of my guide.

(I still prefer "car" and "cdr" but I can relate to your arguments.)

Fred Gilham

unread,
Aug 29, 2002, 12:34:18 PM8/29/02
to

wb...@gmx.net (Wolfhard Buß) writes:
> Usually the data type list, with constructors list*, list, make-list
> is implemented in terms of cons, such that a non-empty list is a
> cons and vice versa, such that some Lispers even use cons to
> construct a list, dare to use car and cdr to select the components
> of a list, instead of the canonical accessors first and rest. Allen
> calls "these representation-dependent coding tricks" dangerous.
> Strachey calls them puns (according to Allen).

I know what you're getting at, but in this case I think you are wrong,
because of the way the Lisp specification defines a list:

list n. 1. a chain of conses in which the car of each cons is an
element of the list, and the cdr of each cons is either the next
link in the chain or a terminating atom. See also proper list,
dotted list, or circular list. 2. the type that is the union of
null and cons. (From the hyperspec glossary.)

So a list IS a chain of conses; its required to be implemented that
way.

I think we're at the fuzzy boundary between the abstract and its
concrete implementation, and I'm not quite sure what to say about it.

(side note)
Once (a long time ago now) I took a class on recursive programming.
The class used scheme. One time the professor asked how we could
specify the behavior of a certain construct. I, being a novice at
this sort of thing, said, ``Just define it as whatever the interpreter
says it is!'' ;-)

--
Fred Gilham gil...@csl.sri.com
Communism is a murderous failure.
Socialism is communism with movie stars.

Wolfhard Buß

unread,
Aug 29, 2002, 2:24:21 PM8/29/02
to
wb...@gmx.net (Wolfhard Buß) writes:
> Usually the data type list, with constructors list*, list, make-list
> is implemented in terms of cons, such that a non-empty list is a
> cons and vice versa, such that some Lispers even use cons to
> construct a list, dare to use car and cdr to select the components
> of a list, instead of the canonical accessors first and rest. Allen
> calls "these representation-dependent coding tricks" dangerous.
> Strachey calls them puns (according to Allen).

Fred Gilham <gil...@snapdragon.csl.sri.com> writes:
> I know what you're getting at, but in this case I think you are wrong,
> because of the way the Lisp specification defines a list:
>
> list n. 1. a chain of conses in which the car of each cons is an
> element of the list, and the cdr of each cons is either the next
> link in the chain or a terminating atom. See also proper list,
> dotted list, or circular list. 2. the type that is the union of
> null and cons. (From the hyperspec glossary.)
>
> So a list IS a chain of conses; its required to be implemented that
> way.

Right. Common Lisp requires the data type list to be implemented in
terms of cons.

Wolfhard Buß

unread,
Sep 3, 2002, 11:10:53 AM9/3/02
to
Fred Gilham <gil...@snapdragon.csl.sri.com> writes:

> I know what you're getting at, but in this case I think you are wrong,
> because of the way the Lisp specification defines a list:
>
> list n. 1. a chain of conses in which the car of each cons is an
> element of the list, and the cdr of each cons is either the next
> link in the chain or a terminating atom. See also proper list,
> dotted list, or circular list. 2. the type that is the union of
> null and cons. (From the hyperspec glossary.)
>
> So a list IS a chain of conses; its required to be implemented that
> way.

Clarification:

Lispers are prepared to deal with objects that are either atomic or
constructed, i.e. of type cons with constructor cons and selectors
car and cdr. Cons is a data type that fulfills (1)-(3).

(car (cons <car> <cdr>)) => <car> (1)
(cdr (cons <car> <cdr>)) => <cdr> (2)

(cons (car <cons>) (cdr <cons>)) => <cons> (3)

Usually the data type (proper) list, with constructors list*, list,
make-list is implemented in terms of cons and the empty list, such
that non-empty lists are cons; such that some Lispers even use cons


to construct a list, dare to use car and cdr to select the components
of a list, instead of the canonical accessors first and rest.

Allen calls "these representation-dependent coding tricks" dangerous.
Strachey calls them puns (according to Allen).

Erik Naggum

unread,
Sep 3, 2002, 1:04:16 PM9/3/02
to
* Wolfhard Buß

| Allen calls "these representation-dependent coding tricks" dangerous.

Does he have any alternatives in mind? Common Lisp has made a trade-off in
this regard where the general mechanisms depend on run-time type information
to make their decisions and compilers generally do not rewrite calls based
on available type information. This is in sharp distinction to statically
typed languages, where syntactically identical access mechanisms may be used
independent of the types, but with only abstractly similar semantics.

Some Scheme courses I have seen construct an abstraction barrier between the
lower-level access functions and the abstract names for their accessors.
This may have its merits, but I found it needlessly verbose and error-prone.
Common Lisp offers defstruct with a `:type´ argument that may be used to
construct lists with accessors. Is that something Allen would prefer?

Fred Gilham

unread,
Sep 3, 2002, 2:41:52 PM9/3/02
to

wb...@gmx.net (Wolfhard Buß) writes:


To begin with, I suppose I should say that I pretty much agree that
if you are handling a datum that you are thinking of as a List, that
is, an instance of the abstract data type List, you should probably
use first and rest.

Nevertheless, it's not the case that

Usually the data type (proper) list, with constructors list*,
list, make-list is implemented in terms of cons and the empty

list....

In fact, it should be

The data type (proper) list, with constructors list*,
list, make-list is ALWAYS implemented in terms of cons and the
empty list....

The standard defines a lisp list as a chain of conses.

Again I'm not quite sure how to navigate here. I'm uncomfortable with
calling the use of `car' and `cdr' a `representation-dependent coding
trick', since there's a canonical representation for this data type
and as a result these are well defined operations on that data type.
(The reason I'm continuing this thread is that I'm hoping someone will
help me resolve my fuzziness about this stuff.)

I also feel no compunction about using `car' and `cdr' (and friends)
when accessing a datum that I'm not thinking of as a list of
homogeneous elements. Though, as some have argued, I do find myself
tending to use them in wrapper functions or macros.

The above argument seems like a call to make list-related functions
primitives in Lisp and to make the list data type incommensurate with
conses.

--
Fred Gilham gil...@csl.sri.com
"If I'm going to get paged at 3 in the morning, I'd like it to at
least be my fault, and I'd also like a fighting chance of fixing the
problem." -- Tim Moore, arguing for professional open-source tools

Reply all
Reply to author
Forward
0 new messages