In comp.lang.scheme Arthur Lemmens <alemm...@xs4all.nl> wrote:
> Kaz Kylheku wrote:
>> In Lisp, we have an imaginary CAR field of the NIL value. It does the >> same thing as imaginary numbers: it takes some contortions out of >> expressions operating on lists
> For a nice example of the consequences of not allowing (CAR NIL) and > distinguishing between NIL and false, see 'A SHORT BALLAD DEDICATED TO > THE GROWTH OF PROGRAMS' by Ashwin Ram. The first link I found is at > http://www.apl.jhu.edu/~hall/lisp/Scheme-Ballad.text.
Its also a piece of pretty shoddy poetry in which the author also manages to demonstrate his taste for bad programming. Not that (cdr (assq key a-list)) actually would have solved the posed problem, as it at most solves the second half...
* Sander Vesik <san...@haldjas.folklore.ee> | Well, depends on whetever you want to treat '() as a simple constant | or a recursive structure.
Why do those have to be exclusive options? In Common Lisp it is both, according as how you look at it. There is never any ambiguity unless you wish to look at nil with the eyes of Pablo Picasso.
-- 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.
* Dorai Sitaram wrote: > No, it cannot be a constant /cons/ cell, because > we must -- even in CL -- absolutely distinguish between > () and
It can be a constant cons cell, so long as the system knows the value of that constant. You can't fabricate a copy of it, because you can't get that copy to be the same identical object. In other words, it can't *only* be a cons whose car & cdr point back to itself, it also has to be a particular such cell (perhaps one that exists at a particular address, say).
> lest the meaningful activity of finding the last > cdr become ill-defined.
Finding the last cdr involves just walking down the cdr chain until you get to an object which is EQ to NIL, not simply to a cons which happens to point back to itself.
>> No, it cannot be a constant /cons/ cell, because >> we must -- even in CL -- absolutely distinguish between >> () and
>It can be a constant cons cell, so long as the system knows the value >of that constant. You can't fabricate a copy of it, because you can't >get that copy to be the same identical object. In other words, it >can't *only* be a cons whose car & cdr point back to itself, it also >has to be a particular such cell (perhaps one that exists at a >particular address, say).
>> lest the meaningful activity of finding the last >> cdr become ill-defined.
>Finding the last cdr involves just walking down the cdr chain until >you get to an object which is EQ to NIL, not simply to a cons which >happens to point back to itself.
Yeah, you're right. (And I meant to say last pair of course, not last cdr, because there are already pairs in CL that don't have a last cdr, but still have a last pair.)
Extending your proposal by just a smidg, I wonder what would be the downside to simply identifying any old cons whose car & cdr point to itself to be _an_ empty list.
There wouldn't be just one empty list anymore. Two empty lists need not be EQ, EQL, or even EQUAL. But that's OK, isn't it, as long we have NULL, which now becomes a more substantial predicate, rather than one that determines if its arg is EQ to a particular symbol?
* Dorai Sitaram wrote: > Extending your proposal by just a smidg, I wonder > what would be the downside to simply identifying any > old cons whose car & cdr point to itself to be _an_ > empty list. > There wouldn't be just one empty list anymore. Two > empty lists need not be EQ, EQL, or even EQUAL. > But that's OK, isn't it, as long we have NULL, which > now becomes a more substantial predicate, rather than > one that determines if its arg is EQ to a particular > symbol?
I think that the difference is probably that (a) it's nice to be able to say that NIL is unique, and (b) there are probably substantial efficiency gains. Lots of things that can now be implemented with a single instruction (compare against known value) need at least several.
One thing I wonder about is type. I'm not an implementor, but I sort of assume a reasonable approach would be rather than having a special typecode for NULL (which eats a code you could use for something else in every object in the world), it's actually just an ordinary cons (or whatever it is), and the typesystem does some fast (single instruction) check for `is this thing actually NIL?'. In fact, in any system where NIL is a distinct type (is '() a distinct type in Scheme?), using your proposal would be kind of weird: firstly the act of setting the car & cdr of a cons to point back to the object would change its type (hmm...), and secondly the type check would be nontrivial. I guess giving up the special type would be the right approach here.
I'd like to know what implementations do, actually.
Tim Bradshaw <t...@cley.com> writes: > I'd like to know what implementations do, actually.
Implementations need to take at least the following operations into account: symbolp, null, consp, listp, and the symbol and list accessors (car and cdr).
If you don't assign a tag to the null type, and let's say you give it the cons tag, you have to explicitly check for the nil value in symbolp (include nil), consp (exclude nil), and all the symbol accessors. This can be a substantial penalty.
What's typically done, I believe, is that null is assigned a tag such that it is congruent with the cons tag or symbol tag, modulo a simple operation. I.e that
(= (logand <null-tag> <x>) <cons-tag>)
and
(= (logand <null-tag> <y>) <symbol-tag>)
That was a terrible explanation. An example is probably much better. Assume three bits are assigned to type-tags.
cons-tag: #b010 symbol-tag: #b100 null-tag: #b110
Now, the type-predicate operations above can be implemented like this:
These operations can typically be implemented quite efficiently in machine-code, certainly so in x86.
Additionaly, it is important that the null-tag is congruent with the cons-tag modulo 4 (on a 32-bit architecture), such that car and cdr won't need a special case for nil (otherwise (car nil) and (cdr nil) would become non-aligned memory accesses). Ideally, the same relationship should be true for null-tag and the symbol-tag, but that's impossible if you're restricted to 3 tag-bits. So you still need to special-case nil in the symbol accessors.
I think there are even more reasons (than improved symbolp and consp) to prefer a separate null-tag, but I can't think of what it is right now.
d...@goldshoe.gte.com (Dorai Sitaram) writes: > Extending your proposal by just a smidg, I wonder > what would be the downside to simply identifying any > old cons whose car & cdr point to itself to be _an_ > empty list.
The following two things should be distinguished:
The list with no elements. All circular lists with one element.
The pair whose car and cdr are itself is a special case of the latter, it's a circular list with one element, which element is the list itself.
Sander Vesik <san...@haldjas.folklore.ee> wrote in message <news:1036011026.622577@haldjas.folklore.ee>... > In comp.lang.scheme Erann Gat <g...@jpl.nasa.gov> wrote: > > In article <1035857902.112...@haldjas.folklore.ee>, Sander Vesik > > <san...@haldjas.folklore.ee> wrote:
> >> Otherwise you would have to define '() as the immutable pair > >> which both "car" and "cdr" slots pointed to itself - imho not > >> nice at all.
> > Why? I always thought that approach was rather elegant myself.
> Well, depends on whetever you want to treat '() as a simple constant > or a recursive structure.
No it doesn't. It depends on what output you want from CAR in response to what inputs, to obtain some desired level of convenience.
Common Lisp has (car nil) => nil without at all defining nil to be some recursive structure.
Continuing with an earlier analogy, when mathematicians decided that (sqrt -1) made sense, they did not need to redefine the integer -1 as the area of some square whose length is (sqrt -1).
k...@ashi.footprints.net (Kaz Kylheku) writes: > No it doesn't. It depends on what output you want from CAR in response > to what inputs, to obtain some desired level of convenience.
> Common Lisp has (car nil) => nil without at all defining nil to be > some recursive structure.
But the structure just is whatever car and cdr return.
I don't care what the *implementation* of nil is. It's the *semantics* which are recursive here.
>> Extending your proposal by just a smidg, I wonder >> what would be the downside to simply identifying any >> old cons whose car & cdr point to itself to be _an_ >> empty list.
>The following two things should be distinguished:
>The list with no elements. >All circular lists with one element.
>The pair whose car and cdr are itself is a special case of the latter, >it's a circular list with one element, which element is the list >itself.
I am unable to see why not distinguishing an [sic] empty list and a circular list whose car is itself is any more of a problem than not distinguishing the empty list and a particular symbol?
Lists are fictions atop dotted pairs anyway -- anything could be the piece of grit called the empty list around the language, oyster-like, builds its lists. Choosing a pair whose car and cdr are itself has the merit of not requiring a special and/or arbitrary element, but also of having empty lists themselves be pairs, so we don't have the phenomenon of the empty list being the one list that is not a pair.
Tim Bradshaw asked about the representation of NIL and ():
> I'd like to know what implementations do, actually.
This message was cross-posted to both comp.lang.lisp and comp.lang.scheme.
The tradeoffs are different in Common Lisp and in Scheme. In Scheme, the empty list is just one of several miscellaneous objects that are usually represented by a non-pointer bit pattern that can be synthesized as an immediate operand. (Other miscellaneous objects include #f, #t, and the end-of-file object(s).) This makes the NULL? predicate into a single machine instruction, and does not make the PAIR? predicate or (safe versions of) the CAR and CDR operations any slower.
In Common Lisp, an immediate representation for NIL makes NULL fast without making PAIRP any slower, but CAR and CDR are likely to become slower if they have to add extra code to handle the NIL case. Thus NIL is more likely to be represented as a cons. To prevent NULL from having to fetch the canonical value of NIL from memory, NIL is often represented as a cons in low memory, so it both looks like a cons and can also be synthesized as an immediate operation. As Frode Vatvedt Fjeld explained, various tricks can be played to prevent ENDP, CONSP, and SYMBOLP from becoming much slower: usually only one instruction slower than they would be with Scheme's semantics.
>> >> Otherwise you would have to define '() as the immutable pair which >> >> both "car" and "cdr" slots pointed to itself - imho not nice at all.
>> > Why? I always thought that approach was rather elegant myself.
>> Well, depends on whetever you want to treat '() as a simple constant or >> a recursive structure.
> No it doesn't. It depends on what output you want from CAR in response > to what inputs, to obtain some desired level of convenience.
> Common Lisp has (car nil) => nil without at all defining nil to be some > recursive structure.
> Continuing with an earlier analogy, when mathematicians decided that > (sqrt -1) made sense, they did not need to redefine the integer -1 as > the area of some square whose length is (sqrt -1).
Another good example is #'concatenate 'string. This treats nil as an empty string even though nil is not of type string: (stringp nil) ==> nil
I would find #'concatenate 'string slightly more convenient if it also coerced characters to strings.
"Adam Warner" <use...@consulting.net.nz> writes: > Hi Kaz Kylheku,
> > Continuing with an earlier analogy, when mathematicians decided that > > (sqrt -1) made sense, they did not need to redefine the integer -1 as > > the area of some square whose length is (sqrt -1).
> Another good example is #'concatenate 'string. This treats nil as an empty > string even though nil is not of type string: (stringp nil) ==> nil
No it doesn't. It treats nil as an empty sequence, which it is, as it is a list of no elements.
(concatenate 'string "a" nil "b") -> "ab" (concatenate 'string "a" '(#\b #\c) "d") -> "abcd"
Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
> Tim Bradshaw asked about the representation of NIL and (): > > I'd like to know what implementations do, actually.
> This message was cross-posted to both comp.lang.lisp and comp.lang.scheme.
[ ... ]
> In Common Lisp, an immediate representation for NIL makes NULL fast > without making PAIRP any slower, but CAR and CDR are likely to become > slower if they have to add extra code to handle the NIL case. Thus > NIL is more likely to be represented as a cons. To prevent NULL from > having to fetch the canonical value of NIL from memory, NIL is often > represented as a cons in low memory, so it both looks like a cons and > can also be synthesized as an immediate operation. As Frode Vatvedt > Fjeld explained, various tricks can be played to prevent ENDP, CONSP, > and SYMBOLP from becoming much slower: usually only one instruction > slower than they would be with Scheme's semantics.
Why one instruction slower? What assumptions are you making?
I wrote: > As Frode Vatvedt > Fjeld explained, various tricks can be played to prevent ENDP, CONSP > and SYMBOLP from becoming much slower: usually only one instruction > slower than they would be with Scheme's semantics.
Duane Rettig asked:
> Why one instruction slower? What assumptions are you making?
With the tag bits in Fjeld's example, on most architectures, ENDP and CONSP would be just as fast as with Scheme's semantics, but SYMBOLP would be one instruction slower. SYMBOLP would still be much faster than it is in Larceny, so I obviously don't think one instruction is very significant here.
As you know, there are lots of other clever representations, each with its own advantages and disadvantages, so it's hard to generalize about this sort of thing.
> I wrote: > > As Frode Vatvedt > > Fjeld explained, various tricks can be played to prevent ENDP, CONSP > > and SYMBOLP from becoming much slower: usually only one instruction > > slower than they would be with Scheme's semantics.
> Duane Rettig asked: > > Why one instruction slower? What assumptions are you making?
> With the tag bits in Fjeld's example, on most architectures, ENDP and > CONSP would be just as fast as with Scheme's semantics, but SYMBOLP > would be one instruction slower.
Not at all. If you take Frode's sample tagging as cons = #b010, symbol = #b100, and nil = #b110, and if you consider imaginary low-level "l" operators as functions which operate on the bit values of their second arguments (rather than logand and =, which might be confused for operations on each lisp object's _value_), then
Of course, there are faster ways of doing one or the other of these operations, and on machines for which misaligned accesses are trapped, the chosen access can be done with no instructions at all (i.e., if cons access is chosen, then car/cdr can be done with a single instruction with no testing beforehand).
> SYMBOLP would still be much faster > than it is in Larceny, so I obviously don't think one instruction is > very significant here.
Agreed.
> As you know, there are lots of other clever representations, each > with its own advantages and disadvantages, so it's hard to generalize > about this sort of thing.
I completely agree, and that is why I questioned the assumption in your own generalization, which is not necessarily correct.
>> Another good example is #'concatenate 'string. This treats nil as an >> empty string even though nil is not of type string: (stringp nil) ==> >> nil
> No it doesn't. It treats nil as an empty sequence, which it is, as it > is a list of no elements.
> (concatenate 'string "a" nil "b") -> "ab" > (concatenate 'string "a" '(#\b #\c) "d") -> "abcd"
Thanks for fixing this misconception Christophe and Paul. I'm also pleased to learn another way to include characters in a string concatenation without having to call the string function: (string #\a) => "a"
Duane Rettig wrote: > Of course, there are faster ways of doing one or the other of these > operations, and on machines for which misaligned accesses are trapped, > the chosen access can be done with no instructions at all (i.e., if > cons access is chosen, then car/cdr can be done with a single instruction > with no testing beforehand).
As in Allegro Common Lisp on the SPARC, for example. Larceny uses the same representation, and the only reason a CAR or CDR takes more than one instruction in Larceny is that we wanted to avoid writing any trap handlers.
> > As you know, there are lots of other clever representations, each > > with its own advantages and disadvantages, so it's hard to generalize > > about this sort of thing.
> I completely agree, and that is why I questioned the assumption in > your own generalization, which is not necessarily correct.
Tim Bradshaw <t...@cley.com> writes: > One thing I wonder about is type. I'm not an implementor, but I sort > of assume a reasonable approach would be rather than having a special > typecode for NULL (which eats a code you could use for something else [...] > I'd like to know what implementations do, actually.
This has been discussed before (on comp.lang.lisp), actually. In amongst the meta-level "how's my politeness? Call 0800 22 55 33" discussion, you can sieve a reasonable amount of information about NIL handling in SBCL and Allegro CL from the archive at Google Groups
Christopher C. Stacy wrote: >>>>>> On 23 Oct 2002 14:03:03 -0700, Rich Demers ("Rich") writes: > > Personally, I have been looking hard at APL (one of the most > > powerful > Yeah, APL was the language I loved before I discovered Lisp! Common > Lisp has REDUCE; also check out the SERIES package by Dick Waters. > The thing about APL, though, is that a lot of its beauty is in the > syntax. Someone said, "APL is like a diamond, Lisp is like a ball of > mud.", the point being that Lisp is capable of retaining its Lispish > beauty while still absorbing other ideas, but APL's crystal lattice > shatters when you try to add things to it.
The quote in my collection says:
"APL is a flawless diamond, perfect, symmetrical, an irreducible whole. But add anything to it, and it's ruined. LISP is a bucket of mud; add anything to it, and it's still a bucket of mud."
Also there:
You hear a gunshot, and there's a hole in your foot, but you don't remember enough linear algebra to understand what happened. -- Shooting yourself in the foot: APL
You spend so much time playing with the graphics and windowing system that your boss shoots you in the foot, takes away your workstation, and makes you develop in COBOL on a character terminal. -- Shooting yourself in the foot: Smalltalk
Don't seem to have one for lisp or scheme.
-- : Bandwidth is no longer as expensive, so that's no excuse : anymore. It's not a matter of bandwidth any more, it's a matter of manners. -- Robert A. Uhl and Dave Brown, on .sigs, in the Monastery
Harri J Haataja wrote: > You hear a gunshot, and there's a hole in your foot, but you don't > remember enough linear algebra to understand what happened. > -- Shooting yourself in the foot: APL
> You spend so much time playing with the graphics and windowing system > that your boss shoots you in the foot, takes away your workstation, > and makes you develop in COBOL on a character terminal. > -- Shooting yourself in the foot: Smalltalk
> Don't seem to have one for lisp or scheme.
You shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds the gun with which you shoot yourself in the appendage which holds..
is the canonical Lisp version. The Scheme version is the same with the addition
...but none of the other appendages are aware of this happening.
Le Hibou -- Dalinian: Lisp. Java. Which one sounds sexier? RevAaron: Definitely Lisp. Lisp conjures up images of hippy coders, drugs, sex, and rock & roll. Late nights at Berkeley, coding in Lisp fueled by LSD. Java evokes a vision of a stereotypical nerd, with no life or social skills.
> The epiphany was this: the "liberal" use of nil (as false, as end of > list, as a nil-returning argument to CAR and CDR) is damn convenient. > I made the decision to take advantage of `(car nil) => nil' and so > forth in this program. The result was that the code accomplished > more, with less work. I wound up with algorithms that were perfectly > transparent, when read presuming that various values were not nil -- > but that also worked with nil. You could read the algorithm first, > presuming not-nil, and get the gist. Then you could ask "what happens > if such-and-such value is nil" and, much more often than not, the > Right Answer simply fell out of the same algorithm. Gosh the RnRS > authors are full of hot air in this area :-)
There is a similar stunt in Smalltalk with an object that is like nil (is in fact subclass of UndefinedObject) but accepts *any* message and quietly returns itself. You can get an implementation of this from my website: look for "void". This thing reduces many fairly complex algorithms to triviality for the same reason as expressed above.
