Can anyone tell me why lists in Lisp are singly-linked?
Wouldn't doubly-linked list make it easy to (destructively)
insert/remove from lists, given only a single element as reference, not
to mention making for efficient adding/reoving elemenst from both head
and tail of the list? Overhead should be minimal (one extra pointer per
element to maintain).
This would be useful...
Ben.
Ben (jvdvyah) wrote:
> Can anyone tell me why lists in Lisp are singly-linked?
I once touched on this issue in a discussion with a friend,
where I said:
> [...] I do think that the singly linked list lies at a
> sweet spot on the simplicity-versus-power plane.
What I mean by this is that the singly linked list is about
the simplest data structure that can still dynamically vary
in size, contain itself, and so on.
--
Aaron
On Sun, 29 Jul 2006, jvdvyah wrote:
> Can anyone tell me why lists in Lisp are singly-linked?
Because that's usually all that's needed.
> Wouldn't doubly-linked list make it easy to (destructively)
> insert/remove from lists, given only a single element as reference, not
> to mention making for efficient adding/reoving elemenst from both head
> and tail of the list?
I can trivially insert/remove from a singly-linked list given only a
single element as reference.
The only advantage a doubly-linked list gives me is that I can trivially
walk through the list backwards, and I can trivially insert/remove the
element in front of the reference element.
Sometimes that could be useful, but most times when I have a list, I don't
have a pressing need for those features.
Additionally, a singly-linked list gives me the ability to prepend to an
existing list without modifying it. It also means lists can share
structure. Neither of these are possible with a doubly-linked list.
> Overhead should be minimal (one extra pointer per element to maintain).
>
> This would be useful...
You could write it yourself. Here's a start:
(eval-when (:compile-toplevel :load-toplevel :execute)
(defstruct (dcons (:conc-name d)
(:constructor dcons (car cdr cdl))
(:predicate dconsp))
car
cdr
cdl)
(defmethod print-object ((dcons dcons) stream)
(princ "[" stream)
(do ((node dcons (dcdr node)))
((not node) nil)
(princ (dcar node) stream)
(when (dcdr node)
(princ " " stream)))
(princ "]" stream))
(defun dlist (&rest list)
(when list
(let* ((first-node (dcons (car list) nil nil))
(node first-node))
(dolist (item (cdr list))
(setf node (setf (dcdr node) (dcons item nil node))))
first-node)))
(defun dlist-reader (stream char)
`(dlist ,@(read-delimited-list #\] stream t)))
(defun error-reader (stream char)
(error "Syntax error, unexpected ~S." char))
(set-macro-character #\[ #'dlist-reader nil)
(set-macro-character #\] #'error-reader nil))
(print ['foo 'bar 'baz])
> Ben.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: LIst in Lisp are singly linked?
Date:
Message-ID: <87ac6ricsu.fsf@qrnik.zagroda>
Nathan Baum <···········@btinternet.com> writes:
> I can trivially insert/remove from a singly-linked list given only
> a single element as reference.
A doubly-linked list has a property that each occurrence of its
element is associated with an object (list node), and it can be
removed from the list in O(1) time given that object, without
disturbing other associations.
It's a nice property of various lists of "registered" items which
can be unregistered given a handle obtained at registration.
A singly-linked list doesn't have this property unless we accept
O(n) time for unregistering.
Pascal Costanza <··@p-cos.net> writes:
> It's a good idea to get used to such a programming style because it
> has a few advantages.
I agree to the principle, but this argument wasn't very convincing :-)
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
This is incorrect. If a doubly-linked list has 1,000,001 items and you
want
to access item 500,000, it takes time proportional to 500,000 starting
from either end.
Marcin 'Qrczak' Kowalczyk wrote:
> A doubly-linked list has a property that each occurrence of its
> element is associated with an object (list node), and it can be
> removed from the list in O(1) time given that object, without
> disturbing other associations.
+ ···············@yahoo.com:
[corrected your top posting]
| Marcin 'Qrczak' Kowalczyk wrote:
|> A doubly-linked list has a property that each occurrence of its
|> element is associated with an object (list node), and it can be
|> removed from the list in O(1) time given that object, without
|> disturbing other associations.
| This is incorrect. If a doubly-linked list has 1,000,001 items and
| you want to access item 500,000, it takes time proportional to
| 500,000 starting from either end.
You didn't read what he said. Given an object in the middle of the
list, you don't need to search for the object you already have. And
you have access to its prev and next pointers, so removing it takes
O(1) time just as he said.
Of course, the same is true for the singly linked list /provided/ you
also have the previous object in hand.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> + ···············@yahoo.com:
>
> [corrected your top posting]
>
> | Marcin 'Qrczak' Kowalczyk wrote:
> |> A doubly-linked list has a property that each occurrence of its
> |> element is associated with an object (list node), and it can be
> |> removed from the list in O(1) time given that object, without
> |> disturbing other associations.
>
> | This is incorrect. If a doubly-linked list has 1,000,001 items and
> | you want to access item 500,000, it takes time proportional to
> | 500,000 starting from either end.
>
> You didn't read what he said. Given an object in the middle of the
> list, you don't need to search for the object you already have. And
> you have access to its prev and next pointers, so removing it takes
> O(1) time just as he said.
>
> Of course, the same is true for the singly linked list /provided/ you
> also have the previous object in hand.
No, not exactly.
(delete 'c '(a b c d e))))
+-------------------------------------------+
| |
| |
| +---+---+ +--------+ |
| |cdr|car|-->| DELETE | |
| +---+---+ +--------+ |
| | |
| v |
| +---+---+ +---+---+ +-------+ |
| |cdr|car|-->|cdr|car|-->| QUOTE | |
| +---+---+ +---+---+ +-------+ |
| | | |
| | v |
| | +---+---+ +---+ |
| | |NIL|car|-->| C | |
| | +---+---+ +---+ |
| v |
| +---+---+ +---+---+ +-------+ |
| |NIL|car|-->|cdr|car|-->| QUOTE | |
| +---+---+ +---+---+ +-------+ |
| | |
| v |
| +---+---+ +---+---+ +---+ |
| |NIL|car|-->|cdr|car|-->| A | |
| +---+---+ +---+---+ +---+ |
| | |
| v |
| +---+---+ +---+ |
| |cdr|car|-->| B | |
| +---+---+ +---+ |
| | |
| v |
| +---+---+ +---+ |
| |cdr|car|-->| C | |
| +---+---+ +---+ |
| | |
| v |
| +---+---+ +---+ |
| |cdr|car|-->| D | |
| +---+---+ +---+ |
| | |
| v |
| +---+---+ +---+ |
| |NIL|car|-->| E | |
| +---+---+ +---+ |
+-------------------------------------------+
To delete the object C, you need to have a reference to the CONS whose
CDR is the CONS whose CAR is C.
In a doubly-linked list, you'd need to have a reference to the NODE
whose LABEL is C.
If you only have the object to delete from the list, in both cases,
you need to scan the list to find the node from which to do the
deletion.
Now you may consider structures such as:
(defstruct sl-person next name birthdate address mother father)
or:
(defstruct dl-person next previous name birthdate address mother father)
(or even CLOS objects with a sll or dll mixin),
but tell me, who are your next and previous persons?
More serriously, the big problem with this kind of structure is that
it prevents the same person structure to be put in more than one list.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
+ Pascal Bourguignon <···@informatimago.com>:
| Harald Hanche-Olsen <······@math.ntnu.no> writes:
|
|> [...] Given an object in the middle of the
|> list, you don't need to search for the object you already have. And
|> you have access to its prev and next pointers, so removing it takes
|> O(1) time just as he said.
|>
|> Of course, the same is true for the singly linked list /provided/ you
|> also have the previous object in hand.
|
| No, not exactly.
Er, I guess I didn't make clear is my use of the word "object" as
meaning whatever owns the "next" pointer (and "prev" in the first
case) , meaning the cons cell in the case of the standard Lisp list.
Sorry about that.
Your point concerning the problems with including those pointers in
the data object are of course well taken.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: LIst in Lisp are singly linked?
Date:
Message-ID: <87mzaryvah.fsf@qrnik.zagroda>
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> Of course, the same is true for the singly linked list /provided/ you
> also have the previous object in hand.
But then removing an element invalidates the handle of the next element.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: LIst in Lisp are singly linked?
Date:
Message-ID: <87k65vyv1i.fsf@qrnik.zagroda>
Harald Hanche-Olsen <······@math.ntnu.no> writes:
> Of course, the same is true for the singly linked list /provided/ you
> also have the previous object in hand.
But then removing an element invalidates the handle of the next element.
Actually I have used a singly-linked list for the "registered list"
construct, accepting the O(n) removal cost, because I wanted a
well-defined behavior of removing during traversal (and it turned out
that "iteration uses a snapshot from the beginning of the iteration"
was the only semantics which is both easy to describe and obtain).
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
+ Marcin 'Qrczak' Kowalczyk <······@knm.org.pl>:
| Harald Hanche-Olsen <······@math.ntnu.no> writes:
|
|> Of course, the same is true for the singly linked list /provided/ you
|> also have the previous object in hand.
|
| But then removing an element invalidates the handle of the next element.
Huh? What I had in mind is something like this - assuming for
simplicity that the list has an artificial list head (cons cell)
attached to its front, and disregarding any unpleasantness that might
happen due to messing with loop control variables:
(loop
with list = (list :ignore 1 2 3 4 5 6 7)
for prev = list then this
for this on (rest list)
when (oddp (first this))
do (setf (rest prev) (rest this)
this (rest this))
finally (return list))
=> (:ignore 2 4 6)
(I am fully aware that this can be written /much/ more briefly in CL.)
PS. I must apologize for getting involved in this now, as I will be
away from usenet for a couple weeks now - so I cannot follow up
further.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
Thanks all for your insights:
*Nathan*, thanks for the code: I will not pretend to understand it all
right away but I'll play around with it: looks like it may come in very
handy. Also, your point about not being able to share structure is well
taken: I hadn't though of that but should have as it's obvious the head
of a doubly-linked list cannot point back to more than one list
(similar for tail and pointing forward, etc.).
*Pascal*, given a handle to the cons cell referring to value "C" I
*can* remove it from the list in O(1) if it was doubly-linked. Not so
with singly-linked. Of course, if you only have the value of "C" and
not a reference to the controlling cell, then you can't do it in either
type of list, which is a point well-taken as it's an important
distinction., especially in Lisp where values seem to have a life of
their own :-)
*Martin*, removing an element does not necessarily invalidate
neighbouring elements. Since the list is double-linked you have direct
access to preceding and following elements, so if you remove an
element, you can change the forward reference of the preceding element
to point to the next element, and the backward reference of the
following element to point to the preceding element. All this is still
O(1) with doubly-linked lists.
*Aaron*, sinlgly-linked lists may well lie at the sweet spot of
performance vs. flexibility so that might well be the reason; I do not
know Lisp well enough to determine that. However, I can imagine
scenarios where being able to insert into or remove from the middle of
a list given only a reference to a single element of the list is an
overriding concern.
A follow-up question for all you gurus: how often does shared structure
occur in Lisp as an intended effect and how often as a side-effect of
common operations? If I'm going to use a doubly-linked list I need to
have seom idea of to what extent common Lisp idioms will break it.
Thanks all for your informed answers,
Ben.
Harald Hanche-Olsen schreef:
> + Marcin 'Qrczak' Kowalczyk <······@knm.org.pl>:
>
> | Harald Hanche-Olsen <······@math.ntnu.no> writes:
> |
> |> Of course, the same is true for the singly linked list /provided/ you
> |> also have the previous object in hand.
> |
> | But then removing an element invalidates the handle of the next element.
>
> Huh? What I had in mind is something like this - assuming for
> simplicity that the list has an artificial list head (cons cell)
> attached to its front, and disregarding any unpleasantness that might
> happen due to messing with loop control variables:
>
> (loop
> with list = (list :ignore 1 2 3 4 5 6 7)
> for prev = list then this
> for this on (rest list)
> when (oddp (first this))
> do (setf (rest prev) (rest this)
> this (rest this))
> finally (return list))
>
> => (:ignore 2 4 6)
>
> (I am fully aware that this can be written /much/ more briefly in CL.)
>
> PS. I must apologize for getting involved in this now, as I will be
> away from usenet for a couple weeks now - so I cannot follow up
> further.
>
> --
> * Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
> - It is undesirable to believe a proposition
> when there is no ground whatsoever for supposing it is true.
> -- Bertrand Russell
"jvdvyah" <···········@gmail.com> writes:
> *Pascal*, given a handle to the cons cell referring to value "C" I
> *can* remove it from the list in O(1) if it was doubly-linked. Not so
> with singly-linked. Of course, if you only have the value of "C" and
> not a reference to the controlling cell, then you can't do it in either
> type of list, which is a point well-taken as it's an important
> distinction., especially in Lisp where values seem to have a life of
> their own :-)
If you are to track the nodes instead of the values, in all your
operations with single-linked lists you can keep the previous node
instead of the current node, and archive O(1) in insert around the
current node or delete of the current node.
> A follow-up question for all you gurus: how often does shared structure
> occur in Lisp as an intended effect and how often as a side-effect of
> common operations?
You have to consider the use cases. Note that the first application
of lists in lisp is to hold the source code. The compiler doesn't
need to insert or delete parts of the source code. Actually,
inserting in the middle of a list, is almost never done, and deleting
an element from a list is rare too. Consequently, list tail sharing
can and do occur often in functional list manipulation code.
> If I'm going to use a doubly-linked list I need to
> have seom idea of to what extent common Lisp idioms will break it.
It will break none, since you will be using your own primitives.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
Thanks Pascal,
> If you are to track the nodes instead of the values, in all your
> operations with single-linked lists you can keep the previous node
> instead of the current node, and archive O(1) in insert around the
> current node or delete of the current node.
This is true but I may not always be able to do that; I've come across
many situations where both tracking the previous node in code and
searching the list sequentially were not practical.
> Actually,
> inserting in the middle of a list, is almost never done, and deleting
> an element from a list is rare too. Consequently, list tail sharing
> can and do occur often in functional list manipulation code.
Maybe so, I defer to your broader experience here.
> It will break none, since you will be using your own primitives.
True :-)
Thanks,
Ben.
Pascal Bourguignon wrote:
> "jvdvyah" <···········@gmail.com> writes:
> > *Pascal*, given a handle to the cons cell referring to value "C" I
> > *can* remove it from the list in O(1) if it was doubly-linked. Not so
> > with singly-linked. Of course, if you only have the value of "C" and
> > not a reference to the controlling cell, then you can't do it in either
> > type of list, which is a point well-taken as it's an important
> > distinction., especially in Lisp where values seem to have a life of
> > their own :-)
>
> If you are to track the nodes instead of the values, in all your
> operations with single-linked lists you can keep the previous node
> instead of the current node, and archive O(1) in insert around the
> current node or delete of the current node.
>
Does it work if the previous node was delete first?
(let* ((*list '())
(pair-a (insert-and-return-cons-pair *list* 'a))
(pair-b (insert-and-return-cons-pair *list* 'b))
(pair-c (insert-and-return-cons-pair *list* 'c)) ;;; now
*list* is A->B->C
(remove-using-pair pair-b) ;; pairs is cons of A -> B, remove
B from list.
(remove-using-pair pair-c) ;; This won't work because it is
cons of B->C, but B is already out of the list.
But it works in doubly-linked-list case because every delete operation
keeps other dcons pointer up to date. In case of singly-linked-list,
'remove' operation has no way of updating others cons pair.
"Pisin Bootvong" <··········@gmail.com> writes:
> Pascal Bourguignon wrote:
>> "jvdvyah" <···········@gmail.com> writes:
>> > *Pascal*, given a handle to the cons cell referring to value "C" I
>> > *can* remove it from the list in O(1) if it was doubly-linked. Not so
>> > with singly-linked. Of course, if you only have the value of "C" and
>> > not a reference to the controlling cell, then you can't do it in either
>> > type of list, which is a point well-taken as it's an important
>> > distinction., especially in Lisp where values seem to have a life of
>> > their own :-)
>>
>> If you are to track the nodes instead of the values, in all your
>> operations with single-linked lists you can keep the previous node
>> instead of the current node, and archive O(1) in insert around the
>> current node or delete of the current node.
>>
>
> Does it work if the previous node was delete first?
Well no, you'd have to keep track of this deletion and substitute the
new "previous". In effect, you'd be managing a dll node at this
point.
If you want to be able to delete all the items in O(1), you'd have to
keep the whole list in a dll, but then, either you know by name all
the nodes and keep O(1), or you don't and fallback to O(n).
> [...]
> But it works in doubly-linked-list case because every delete operation
> keeps other dcons pointer up to date. In case of singly-linked-list,
> 'remove' operation has no way of updating others cons pair.
You still have to find the nodes you want to delete.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"This machine is a piece of GAGH! I need dual Opteron 850
processors if I am to do battle with this code!"
Pascal Bourguignon wrote:
> "Pisin Bootvong" <··········@gmail.com> writes:
>
> > Pascal Bourguignon wrote:
> >> "jvdvyah" <···········@gmail.com> writes:
> >> > *Pascal*, given a handle to the cons cell referring to value "C" I
> >> > *can* remove it from the list in O(1) if it was doubly-linked. Not so
> >> > with singly-linked. Of course, if you only have the value of "C" and
> >> > not a reference to the controlling cell, then you can't do it in either
> >> > type of list, which is a point well-taken as it's an important
> >> > distinction., especially in Lisp where values seem to have a life of
> >> > their own :-)
> >>
> >> If you are to track the nodes instead of the values, in all your
> >> operations with single-linked lists you can keep the previous node
> >> instead of the current node, and archive O(1) in insert around the
> >> current node or delete of the current node.
> >>
> >
> > Does it work if the previous node was delete first?
>
> Well no, you'd have to keep track of this deletion and substitute the
> new "previous". In effect, you'd be managing a dll node at this
> point.
>
> If you want to be able to delete all the items in O(1), you'd have to
> keep the whole list in a dll, but then, either you know by name all
> the nodes and keep O(1), or you don't and fallback to O(n).
>
> > [...]
> > But it works in doubly-linked-list case because every delete operation
> > keeps other dcons pointer up to date. In case of singly-linked-list,
> > 'remove' operation has no way of updating others cons pair.
>
> You still have to find the nodes you want to delete.
>
I already have the dcons of the place I want to delete. That's O(1).
Did I misunderstand something?
If you kept the referent to a dcons in a dll, then you can delete that
node with O(1).
No matter how many distinct dcons references you kept, you can still
delete each of them from the dll with O(1) speed.
Then you said that by keeping the previous cons instead of the current
cons, you can archive O(1) in deletion.
I only point out that it was not a sound optimization. For one, you can
not kept two cons then delete both of them and still expect the
behavior to be correct if the node that was deleted first is a previous
node of the latter.
Or should the requirement to delete node with O(1) given the cons/dcons
reference of that node (previous node if you want) must also be
constrained by not being able to keep more than one reference before
hand?
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> "This machine is a piece of GAGH! I need dual Opteron 850
> processors if I am to do battle with this code!"
From: Pierpaolo BERNARDI
Subject: Re: LIst in Lisp are singly linked?
Date:
Message-ID: <op.tdi9dszvxbm8ci@eraora>
On Sun, 30 Jul 2006 23:45:43 +0200, jvdvyah <···········@gmail.com> wrote:
> how often does shared structure
> occur in Lisp as an intended effect and how often as a side-effect of
> common operations? If I'm going to use a doubly-linked list I need to
> have seom idea of to what extent common Lisp idioms will break it.
A short answer is that singly linked lists allow programming
in functional style, while doubly linked lists make programming
in functional style impossible.
Doubly linked lists appeal to programmers who don't yet grasp
the fundamentals of computing.
P.
--
Anything below this line is being added by the newsserver
From: Kent M Pitman
Subject: Re: LIst in Lisp are singly linked?
Date:
Message-ID: <u7j1uk1yw.fsf@nhplace.com>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> Nathan Baum <···········@btinternet.com> writes:
>
> > I can trivially insert/remove from a singly-linked list given only
> > a single element as reference.
>
> A doubly-linked list has a property that each occurrence of its
> element is associated with an object (list node), and it can be
> removed from the list in O(1) time given that object, without
> disturbing other associations.
Actually, as noted by another poster, it's only O(1) if you have a
pointer to the cell. But in a large number of cases, it's easy by
using a pair of pointers in the same traversal to do the same snap-out
with O(1) time and no extra data storage.
One reason the decision was made originally was that memory used to be
more expensive. But I think that's not the reason we've stayed with it.
You have to use lists for a while to understand the value of singly-linked
lists. They seem like lists that offer less service, but their true value
is that they can be shared. Lisp is full of structures that point into
one another, and when you doubly-link them, this becomes nearly impossible
since it suggests that it follows from the fact that something is conceptually
linked in one direction that it's conceptually linked in the other.
It's best to just use singly-linked lists for a while and see how
others use them before you decide that doubly-linked lists are the
right thing. There are just lots of data layouts done in Lisp that
most people probably don't do in other languages exactly because they
don't think much about the "list" having object identity in the same
way as some other class instance. They think of lists as
"lightweight" and other things as "heavyweight", and that's just not
always what you want.
That said, there are languages where lists are lightweight and other
objects are heavyweight where this works very well. I'm not saying
there is no computational value to that--I'm just saying "don't fight
the language". Languages evolve whole ecologies around their
operators, and the individual operators support others. If you make a
big change like the one that is implicitly suggested in "why aren't
they all doubly-linked", the effects can be non-obvious and often
not even pleasant.
> It's a nice property of various lists of "registered" items which
> can be unregistered given a handle obtained at registration.
> A singly-linked list doesn't have this property unless we accept
> O(n) time for unregistering.
"Registering" things is not the only things lists are made of. And
no, it's utterly false that O(n) time is required for "unregistering";
it's only required IF you insist on using a particular, pessimally
chosen set of storage layouts and operations. There are lots more
ways to store things and more ways to delete things, so this choice is
not properly analyzed.
jvdvyah wrote:
> Can anyone tell me why lists in Lisp are singly-linked?
>
> Wouldn't doubly-linked list make it easy to (destructively)
> insert/remove from lists, given only a single element as reference, not
> to mention making for efficient adding/reoving elemenst from both head
> and tail of the list? Overhead should be minimal (one extra pointer per
> element to maintain).
>
> This would be useful...
...but uses more memory, and doesn't buy you a lot when you program in a
mostly applicative style (without using side effects).
It's a good idea to get used to such a programming style because it has
a few advantages.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
(message (Hello 'jvdvyah)
(you :wrote :on '(29 Jul 2006 18:30:49 -0700))
(
j> Can anyone tell me why lists in Lisp are singly-linked?
CONS is the minimal fundamental building block. it's conceptual thing, not
just a data structure.
doubly-linked lists is merely a data structure, useful in some cases,
bringing overhead in other.
if you write in natural functional style in LISP, you won't need
doubly-linked lists.
btw you can see this conceptual CONS everywhere. for example, in RDF
Collections:
_:c1 rdf:first <ex:aaa> .
_:c1 rdf:rest _:c2 .
_:c2 rdf:first <ex:bbb> .
_:c2 rdf:rest rdf:nil .
this represents list (<ex:aaa> <ex:bbb>), _:c1 and _:c2 are blank nodes
represeting CONSes.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
First, when Lisp was created memory was in short supply only
32K of 36 bit words for both Lisp interpreter , compiler, and user's
program. Like in LISP 1.5, where the lisp system took 11K that
gives the user 22K. The overhead for a second link would have
limit the size of program to even smailler than they were.
In today, while memory size is not a problem, the extra link
would not cause a problem in the memory size but the extra
instruction code would slow down the execution of the program. And
today, speed is the master killer for all programs and languages. Most
people have stop using interpreter languages such as interpreted BASIC
because of the speed of executions. They use compiler type of languages.
And even though Lisp can be compiler, its code still includes and executed
by the interpreter code.
Why would any one want to use dual links that would slow
and execution of a program? So this question does not compute,
except for an excise in the classroom.
In <························@p79g2000cwp.googlegroups.com>, "jvdvyah" <···········@gmail.com> writes:
>Can anyone tell me why lists in Lisp are singly-linked?
>
>Wouldn't doubly-linked list make it easy to (destructively)
>insert/remove from lists, given only a single element as reference, not
>to mention making for efficient adding/reoving elemenst from both head
>and tail of the list? Overhead should be minimal (one extra pointer per
>element to maintain).
>
>This would be useful...
>
>Ben.
>
On Sun, 30 Jul 2006, anon wrote:
> First, when Lisp was created memory was in short supply only 32K of 36
> bit words for both Lisp interpreter , compiler, and user's program.
> Like in LISP 1.5, where the lisp system took 11K that gives the user
> 22K. The overhead for a second link would have limit the size of
> program to even smailler than they were.
>
> In today, while memory size is not a problem, the extra link would not
> cause a problem in the memory size but the extra instruction code would
> slow down the execution of the program. And today, speed is the master
> killer for all programs and languages. Most people have stop using
> interpreter languages such as interpreted BASIC because of the speed of
> executions.
They've stopped using interpreted languages such as BASIC because BASIC
sucks. They have, however, continued to use other interpreted languages.
It might also be noted that BASIC was originally a compiled language and
only later interpreted.
> They use compiler type of languages. And even though Lisp can be
> compiler, its code still includes and executed by the interpreter code.
I can't parse that.
> Why would any one want to use dual links that would slow and execution
> of a program?
Odd question. Why would anyone want to use bignums, they slow down
programs? Answer is: sometimes you *need* bignums. Similarly, sometimes
you *need* a data structure with the features of a doubly-linked list.
> So this question does not compute, except for an excise in the
> classroom.
>
> In <························@p79g2000cwp.googlegroups.com>, "jvdvyah" <···········@gmail.com> writes:
>
>> Can anyone tell me why lists in Lisp are singly-linked?
Ugh. Top-posting
anon wrote:
> In today, while memory size is not a problem, the extra link
> would not cause a problem in the memory size but the extra
> instruction code would slow down the execution of the program.
It's very doubtful. It would be good to profile reasonably complex
program with single-linked and
double-linked list. But I expect in one cases a better performance
would be for double-linked lists and better for
single-linked - in other.
> And
> today, speed is the master killer for all programs and languages. Most
> people have stop using interpreter languages such as interpreted BASIC
> because of the speed of executions.
Actually today Basic code can be compiled to native or byte code, but
it it still sucks even with OOP and .NET features (I mean one can
always find better (more suitable) language than Basic for any task).
>They use compiler type of languages.
You clearly mean "languages which have compilers to machine native code
or/and languages which better suited for native compilation". I saw
many developers which couldn't work with thought about not native
compiled code and they all liked C++ very much. But C++'s STL uses
double-linked lists sealed to object without many great features of
Lisp lists (easy sharing, dividing etc.). When I showed Lisp like
version of lists in C++ to colleague which is C++ fan, he said that he
couldn't understand why list is not encapsulated in single object ? I
answered that in spite of dangerous memory managment issues it could
greatly simplify some kind of operations where I wanted to
connect/disconnect parts of list in any place, build cycled lists and
so on. He is still unconvinced about Lisp way of doing things because
C++ is just another planet's language.
> And even though Lisp can be compiler, its code still includes and executed
> by the interpreter code.
It was funny sentence. IMHO Lisp can not be a compiler, because Lisp is
language or family of languages. And
how "iterpreter code" can execute something ? And most important WHY do
you think Lisp code must contain interpreted code ?
> Why would any one want to use dual links that would slow
> and execution of a program? So this question does not compute,
> except for an excise in the classroom.
Because somebody would want to walk fast through list items forward and
backward for some specific task.
anon wrote:
> They use compiler type of languages.
> And even though Lisp can be compiler, its code still includes and executed
> by the interpreter code.
Although Lisps almost always contain an interpreter it is not generally
used to execute very much code in a complete program. If you have a
lisp implementation that says it generates native code then it does
exactly that, it does not call the interpreter.
Some old Lisp implementations, like Lisp 1.5, did use the interpreter
this for constructs the compiler couldn't cope with. Modern Lisps
don't though.
On 2006-07-31, Rob Thorpe <·············@antenova.com> wrote:
> anon wrote:
>> They use compiler type of languages.
>> And even though Lisp can be compiler, its code still includes and executed
>> by the interpreter code.
>
> Although Lisps almost always contain an interpreter it is not
> generally used to execute very much code in a complete program. If
> you have a lisp implementation that says it generates native code
> then it does exactly that, it does not call the interpreter.
>
> Some old Lisp implementations, like Lisp 1.5, did use the
> interpreter this for constructs the compiler couldn't cope with.
> Modern Lisps don't though.
"Modern ..." Does "modern" mean the opposite of "old", or the
opposite of "primitive"? (Or both?)
I ask because most people seem to use the two senses interchangably,
and in this case, it ain't necessariy so. In particular, ABCL still
punts to the interpreter occasionally (I think mostly for CLOS?).
They're far from v1.0, though; I'm not throwing stones. But -- does
that make it something other than "modern"? Or just "not finished
yet"? :)
-- Larry
Larry Clapp wrote:
> On 2006-07-31, Rob Thorpe <·············@antenova.com> wrote:
> > anon wrote:
> >> They use compiler type of languages.
> >> And even though Lisp can be compiler, its code still includes and executed
> >> by the interpreter code.
> >
> > Although Lisps almost always contain an interpreter it is not
> > generally used to execute very much code in a complete program. If
> > you have a lisp implementation that says it generates native code
> > then it does exactly that, it does not call the interpreter.
> >
> > Some old Lisp implementations, like Lisp 1.5, did use the
> > interpreter this for constructs the compiler couldn't cope with.
> > Modern Lisps don't though.
>
> "Modern ..." Does "modern" mean the opposite of "old", or the
> opposite of "primitive"? (Or both?)
I meant old.
> I ask because most people seem to use the two senses interchangably,
> and in this case, it ain't necessariy so. In particular, ABCL still
> punts to the interpreter occasionally (I think mostly for CLOS?).
> They're far from v1.0, though; I'm not throwing stones. But -- does
> that make it something other than "modern"? Or just "not finished
> yet"? :)
I didn't know that, if I had I would have phrased it differently.
Any thing created by Bill Gates in the computer world sucks, BIG
TIME! This include the BASIC interpreter and all of his OS. Everybody knew
back in the 80's and early 90s. you want IBM PC DOS instead of MS-DOS.
And today you want a Hardware company modified version of XP, if you
stupid to still enough to use Windows. As for Basic, I used that language
because most people know it as an interpreter type of language. And I
still use Basic interpreter when I needs a one-time fast written code.
As for CLOS, "oop" died back in the 90s. It will just take a few
years for the average people to know this. An example is no one at
Microsoft or INTEL uses "oop" version of "c" aka "c++". They use
only the standard "c". One reason for the death of oop version of LIsp
aka Common LIsp is the overhead the object code generates. And a
second is the lack of a true interpreter functions. Plus, each version
of commun Lisp has its own sub-set of the language, except for the
elementary functions.
Also, I could fill a book of reasons why "common lisp" is not
even LISP. Just like a Cherry pie is not an Apple pie, even though
there is only one item that is different and the rest are the same. But it
is enough of a difference. And if you do not understand this then you do
not understand the idea of a why you would use LISP in the first place.
It just sound like there are few students or programmers who have
never put there code into a real world enviroment talking. Therefore they
just want to make trouble for those of us that do work in the field.
In <························@s13g2000cwa.googlegroups.com>, "Rob Thorpe" <·············@antenova.com> writes:
>Larry Clapp wrote:
>> On 2006-07-31, Rob Thorpe <·············@antenova.com> wrote:
>> > anon wrote:
>> >> They use compiler type of languages.
>> >> And even though Lisp can be compiler, its code still includes and executed
>> >> by the interpreter code.
>> >
>> > Although Lisps almost always contain an interpreter it is not
>> > generally used to execute very much code in a complete program. If
>> > you have a lisp implementation that says it generates native code
>> > then it does exactly that, it does not call the interpreter.
>> >
>> > Some old Lisp implementations, like Lisp 1.5, did use the
>> > interpreter this for constructs the compiler couldn't cope with.
>> > Modern Lisps don't though.
>>
>> "Modern ..." Does "modern" mean the opposite of "old", or the
>> opposite of "primitive"? (Or both?)
>
>I meant old.
>
>> I ask because most people seem to use the two senses interchangably,
>> and in this case, it ain't necessariy so. In particular, ABCL still
>> punts to the interpreter occasionally (I think mostly for CLOS?).
>> They're far from v1.0, though; I'm not throwing stones. But -- does
>> that make it something other than "modern"? Or just "not finished
>> yet"? :)
>
>I didn't know that, if I had I would have phrased it differently.
>
····@anon.org (anon) writes:
> Also, I could fill a book of reasons why "common lisp" is not
> even LISP. Just like a Cherry pie is not an Apple pie, even though
> there is only one item that is different and the rest are the same. But it
> is enough of a difference. And if you do not understand this then you do
> not understand the idea of a why you would use LISP in the first place.
Please, enlight us!
Could you just fill a paragraph why Common Lisp is not LISP?
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
This is pretty funny.
On Thu, 3 Aug 2006, anon wrote:
> Any thing created by Bill Gates in the computer world sucks, BIG
> TIME! This include the BASIC interpreter and all of his OS.
1. Bill Gates never created a BASIC interpreter.
2. Bill Gates never created an OS.
> Everybody knew back in the 80's and early 90s. you want IBM PC DOS
> instead of MS-DOS.
Which is odd, considering that up until the early 90's PC-DOS and
MS-DOS were nearly indistinguishable, since Microsoft and IBM shared the
source between each other.
> As for CLOS, "oop" died back in the 90s. It will just take a few
> years for the average people to know this.
I suppose we're fortunate we have above-average people like yourself to
keep us informed, eh?
> An example is no one at Microsoft or INTEL uses "oop" version of "c" aka
> "c++". They use only the standard "c".
Do you have any idea how stupid that makes you sound? Seriously.
> One reason for the death of oop version of LIsp aka Common LIsp is the
> overhead the object code generates.
Riiight.
> And a second is the lack of a true interpreter functions.
Well, I can't refute that. Mainly because it doesn't even mean anything.
> Plus, each version of commun Lisp has its own sub-set of the language,
> except for the elementary functions.
I'm missing the bit where this causes the death of Common Lisp?
> Also, I could fill a book of reasons why "common lisp" is not even LISP.
I'm pretty sure you couldn't. But how about you give us a short preview of
your magnum opus? I'm sure it would be highly... entertaining.
> Just like a Cherry pie is not an Apple pie, even though there is only
> one item that is different and the rest are the same. But it is enough
> of a difference.
They're both pies, however. If you're imagining that because Common Lisp
is not exactly the same as <insert name of some other Lisp dialect here>
it is not "a Lisp", you're sadly mistaken.
> And if you do not understand this then you do not understand the idea of
> a why you would use LISP in the first place.
Ah, I see. Anyone who disagrees with you is an idiot who shouldn't even be
using LISP in the first place.
> It just sound like there are few students or programmers who have
> never put there code into a real world enviroment talking. Therefore they
> just want to make trouble for those of us that do work in the field.
I agree wholeheartedly with every last word of that sentence.
It's possible we might not agree on *who* is out of touch with reality,
though.
On Thu, 3 Aug 2006 05:31:54 +0100, Nathan Baum
<···········@btinternet.com> wrote:
>1. Bill Gates never created a BASIC interpreter.
Sorry to bust your bubble ... Bill Gates (with Paul Allen) wrote the
first commercial BASIC interpreter for the Altair 8080. It was freely
copied and swapped and he made very little money from the venture.
That's what started his long campaign against software piracy.
>2. Bill Gates never created an OS.
True. He had essentially stopped hacking by the time DOS was born.
George
--
for email reply remove "/" from address
On Thu, 3 Aug 2006, George Neuner wrote:
> On Thu, 3 Aug 2006 05:31:54 +0100, Nathan Baum
> <···········@btinternet.com> wrote:
>
>> 1. Bill Gates never created a BASIC interpreter.
>
> Sorry to bust your bubble ... Bill Gates (with Paul Allen) wrote the
> first commercial BASIC interpreter for the Altair 8080. It was freely
> copied and swapped and he made very little money from the venture.
> That's what started his long campaign against software piracy.
I stand corrected. (It turns out I already knew that, but had completely
forgotten until you reminded me.) I was thinking of the later Microsoft
BASICs, which Bill had no direct hand in code.
>> 2. Bill Gates never created an OS.
>
> True. He had essentially stopped hacking by the time DOS was born.
>
>
> George
> --
> for email reply remove "/" from address
····@anon.org (anon) writes:
Send in the Billy Goats gruff...
> Any thing created by Bill Gates in the computer world sucks, BIG
> TIME! This include the BASIC interpreter and all of his OS. Everybody knew
> back in the 80's and early 90s. you want IBM PC DOS instead of MS-DOS.
> And today you want a Hardware company modified version of XP, if you
> stupid to still enough to use Windows. As for Basic, I used that language
> because most people know it as an interpreter type of language. And I
> still use Basic interpreter when I needs a one-time fast written code.
>
> As for CLOS, "oop" died back in the 90s. It will just take a few
> years for the average people to know this. An example is no one at
> Microsoft or INTEL uses "oop" version of "c" aka "c++". They use
> only the standard "c". One reason for the death of oop version of LIsp
> aka Common LIsp is the overhead the object code generates. And a
> second is the lack of a true interpreter functions. Plus, each version
> of commun Lisp has its own sub-set of the language, except for the
> elementary functions.
>
> Also, I could fill a book of reasons why "common lisp" is not
> even LISP. Just like a Cherry pie is not an Apple pie, even though
> there is only one item that is different and the rest are the same. But it
> is enough of a difference. And if you do not understand this then you do
> not understand the idea of a why you would use LISP in the first place.
>
> It just sound like there are few students or programmers who have
> never put there code into a real world enviroment talking. Therefore they
> just want to make trouble for those of us that do work in the field.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Casey Hawthorne
Subject: Re: LIst in Lisp are singly linked? Wouldn't removing an element be a destructive update -- an ephemeral data structure?
Date:
Message-ID: <ni9rc21ihl6hv0e3i84v3o3biuakmun1dn@4ax.com>
Wouldn't removing an element be a destructive update -- an ephemeral
data structure?
Doesn't functional programming need persistent data structures?
--
Regards,
Casey
From: Harald Hanche-Olsen
Subject: Re: LIst in Lisp are singly linked? Wouldn't removing an element be a destructive update -- an ephemeral data structure?
Date:
Message-ID: <pco64heuubp.fsf@shuttle.math.ntnu.no>
+ Casey Hawthorne <·················@istar.ca>:
| Wouldn't removing an element be a destructive update -- an ephemeral
| data structure?
|
| Doesn't functional programming need persistent data structures?
Short answer: Lisp is not a functional language. You can do
functional programming in Lisp, and it is indeed quite common to find
bits and pieces of programming in the functional style in any program.
But hardly anybody ever writes purely functional programs in Lisp.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
From: Pascal Bourguignon
Subject: Re: LIst in Lisp are singly linked? Wouldn't removing an element be a destructive update -- an ephemeral data structure?
Date:
Message-ID: <87u04yw4m1.fsf@thalassa.informatimago.com>
Casey Hawthorne <·················@istar.ca> writes:
> Wouldn't removing an element be a destructive update -- an ephemeral
> data structure?
>
> Doesn't functional programming need persistent data structures?
When you want to write in functional style, you use REMOVE instead of DELETE:
[17]> (let ((data (list 1 2 3 4 5))
(*print-circle* nil))
(print (list data
(remove 3 data))))
((1 2 3 4 5) (1 2 4 5))
((1 2 3 . #1=(4 5)) (1 2 . #1#))
[18]> (let ((data (list 1 2 3 4 5))
(*print-circle* nil))
(print (list data
(delete 3 data))))
((1 2 4 5) (1 2 4 5))
(#1=(1 2 4 5) #1#)
--
__Pascal Bourguignon__ http://www.informatimago.com/