Does somebody have Common Lisp code to create a doubly-linked list and
to allow you to move back and forth through it deleting and inserting
things? It should be set up with an underlying implementation that
will make things efficient. Is there a way to ensure this, or should
I write it in C? I started typing up the following, but I'm wondering
whether I can even count on this as the basis for an efficient
approach:
(defstruct node
next
prev
key)
(defun make-dbly-linked-list (size)
(setq sentinel (make-node))
(setq prev-name 'sentinel)
(dotimes (i size)
(setq next-name (intern (format nil "elt-~D" i)))
(set next-name (make-node))
(setf (node-next (eval prev-name)) next-name)
(setf (node-prev (eval next-name)) prev-name)
(setq prev-name next-name))
(setf (node-next (eval prev-name)) 'sentinel)
(setf (node-prev sentinel) prev-name)
sentinel)
Is getting a next node by evaling some interned name about as
efficient as following a pointer in C? Alternatively, as long as I
have a limit on how big the list will ever grow, I could make an array
of that many nodes and use the array indices as the next and prev
values.
Ideally, I'd like to add an extra layer of convenience but do it with
a minimal amount of execution overhead. I'd like to be able to write
things the following way (without any eval's or what not):
(setq thelist (make-dbly-linked-list 100))
(setq firstnode (head thelist))
(setf (key firstnode) 3)
(setq nextnode (next firstnode))
(setq alsofirst (prev nextnode))
(setf (key nextnode) '(foo bar))
(delete nextnode)
(insert-key 5); would insert a node with key 5 onto the front of the list
; now firstnode (and alsofirst) would actually be the second node
Actually, for my application I don't need insertions. (In a general
package it would be nice to also have something like
(insert-key-after foo-node 2)
which would insert a node with key 2 after the node foo-node.)
--
Ronald I. Greenberg (Ron) ···@eng.umd.edu
In article <············@mojo.eng.umd.edu> ···@eng.umd.edu
(Ronald Greenberg) writes:
>
>Does somebody have Common Lisp code to create a doubly-linked list and
>to allow you to move back and forth through it deleting and inserting
>things?
> (stuff ommitted)
>Is getting a next node by evaling some interned name about as
>efficient as following a pointer in C?
You don't need to use EVAL and intern to intern symbols.
Notice that the normal list structure uses pointers.
For example, the list '(a b c) has "a" as the "car" of the first element,
the "cdr" of the list is the list (b c) etc.
To save space you might define node without explicit "keys". You'll
save 4 cells for every node.
Here's the code rewritten without using eval
(defstruct (node (:type list))
next
prev
key)
(defun make-dbly-linked-list (size)
(let (root
next-node
prev-node)
(setq root (make-node :key -1))
(setq prev-node root)
(dotimes (i size)
(setq next-node (make-node :key i))
(setf (node-next prev-node) next-node)
(setf (node-prev next-node) prev-node)
(setq prev-node next-node))
(setf (node-next prev-node) root)
(setf (node-prev root) prev-node)
root))
(defun print-node (node)
(format t "~s " (node-key node)))
(defun print-dbly-linked-list (root)
(let (node1)
(print-node root)
(setq node1 root)
(loop with node = node1
do (setq node (node-next node))
until (eq node root)
do (print-node node))))
? (setq list (make-dbly-linked-list 5))
#1=(#5=(#4=(#3=(#2=(#6=(#1# #2# 4) #3# 3) #4# 2) #5# 1) #1# 0) #6# -1)
? (print-dbly-linked-list list)
-1 0 1 2 3 4
As for adding/deleting nodes, a good reference is Donald Knuth
-Fundamental Algorithms- the volume on lists and sorting. The
problem you're trying to solve sounds suspiciously like a class
assignment.
From: Tom Pole
Subject: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <1993Feb18.161215.27176@evb.com>
>>(Ronald Greenberg) writes:
>>>
>>>Does somebody have Common Lisp code to create a doubly-linked list and
>>>to allow you to move back and forth through it deleting and inserting
>>>things?
>
... other good stuff
.................................................. > I was just
>hoping there might already exist some nice convenient, efficient
>Common Lisp package for manipulating (doubly) linked lists, given how
>fundamental they are.
... more good stuff
>............. But I would still say that given all the other fancy
>things that have been built into Common Lisp, it is somewhat
>incongruous to not have a doubly linked list data type with routines
>to efficiently do the following things:
>
>Ronald I. Greenberg (Ron) ···@eng.umd.edu
I have been avoiding this like the plague for years, but because of
this and other postings of late my guilt has overcome me.
I have been working in software reuse for about 4-5 years now, and
my work has run the gamut from reseach papers, to experimental
environments and tools, to (believe it or not) actual commercial
development of reuse tools and methods.
I have a library of Lisp that I always start and end each programming
project with (start = see if there's anything useful before writing the
spec and tying myself down, end = see what I can add to the library).
I know a lot of other Lisper's do the same, more so than any other
language I have had exposure to.
I think its time we use some of the very good stuff that the reuse
community has come up with, and apply it to a PD reuse library of
Lisp forms (I use the word form, because there are many reusable
assets: functions, constants, classes, macros, even code templates
that help programmers follow standardized coding practices).
Please respond if:
(1) You are willing to participate in the development of such a library.
This includes doing a little background reading on the non-technical
aspects of succesful reuse.
(2) You are willing to submit assets to the library.
(3) You want to use the library.
(4) You wish to start a flame war, but please use alternate email
address ········@bottom.of.sea or News group comp.dead.air
(5) You're not sure but you'd be willing to consider it.
One more point, about why data-structures probably should not be
included in the CL language spec. CL implementations are already
too big for commercial delivery's and great resources are being
consumed trying to find efficient ways of removing unused portions
of an image before delivery. I think it best that any non-universal
(or near universal) functionality or knowledge that is needed
by Lisper's should be avaiable to be _added_ to the image, not
another thing that may need to be removed.
I know there are ftp sites. etc. where lisp code may be found that
is reusable; that is not the only requuirement of succesful software
reuse. I would like to develop an environment available to Lisper's
that not only makes reuse possible, but available, cost-effective,
and something that management can support.
Thanks for your attention, let's see if we can get something
planned for if not implemented before LUV-93.
Thomas
--
Thomas Pole
From: Mark Kantrowitz
Subject: Re: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <C2pLC5.95C.1@cs.cmu.edu>
In article <······················@evb.com> ····@evb.com (Tom Pole) writes:
>I have a library of Lisp that I always start and end each programming
>project with (start = see if there's anything useful before writing the
>spec and tying myself down, end = see what I can add to the library).
>I know a lot of other Lisper's do the same, more so than any other
>language I have had exposure to.
>
>I think its time we use some of the very good stuff that the reuse
>community has come up with, and apply it to a PD reuse library of
>Lisp forms (I use the word form, because there are many reusable
>assets: functions, constants, classes, macros, even code templates
>that help programmers follow standardized coding practices).
The Lisp Utilities Repository collects stuff like this. If you'd like
to browse the contents, it's located by anonymous ftp at
ftp.cs.cmu.edu in the directory
/afs/cs.cmu.edu/user/mkant/Public/Lisp/
If you'd like to contribute files to the repository, send me email.
--mark
·····@cs.cmu.edu
From: Kent Sandvik
Subject: Re: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <sandvik-210293195009@17.201.32.75>
In article <············@cs.cmu.edu>, ······@cs.cmu.edu (Mark Kantrowitz)
wrote:
> The Lisp Utilities Repository collects stuff like this. If you'd like
> to browse the contents, it's located by anonymous ftp at
> ftp.cs.cmu.edu in the directory
> /afs/cs.cmu.edu/user/mkant/Public/Lisp/
What about a PD meta-browser that provides information and source
code over the net? IMHO such tools would eventually help concerning
acceptance of component related development work.
Think about it as a smart WAIS/meta-browser system that could find
out about libraries/components over the Internet.
Maybe someone has done something similar already, or is working on it?
Cheers,
Kent
---
·······@newton.apple.com. ALink: KSAND
Private activities on the Net, opinions are not Apple's, they are mine.
From: Stephen J Bevan
Subject: Re: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <BEVAN.93Feb24201853@panda.cs.man.ac.uk>
In article <····················@17.201.32.75> ·······@newton.apple.com (Kent Sandvik) writes:
In article <············@cs.cmu.edu>, ······@cs.cmu.edu (Mark Kantrowitz)
wrote:
> The Lisp Utilities Repository collects stuff like this. If you'd like
> to browse the contents, it's located by anonymous ftp at
> ftp.cs.cmu.edu in the directory
> /afs/cs.cmu.edu/user/mkant/Public/Lisp/
What about a PD meta-browser that provides information and source
code over the net? IMHO such tools would eventually help concerning
acceptance of component related development work.
Maybe, but there needs to be components to browse to make it
worthwhile. Most archives I've scanned (and submitted to) don't
really have enough in them to warrant a fancy interface. IMHO getting
people to submit to an archive is a much tougher job than extracting
information from it.
bevan
From: Jeff Dalton
Subject: Re: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <8461@skye.ed.ac.uk>
In article <······················@evb.com> ····@evb.com (Tom Pole) writes:
>
>I think its time we use some of the very good stuff that the reuse
>community has come up with, and apply it to a PD reuse library of
>Lisp forms
>I know there are ftp sites. etc. where lisp code may be found that
>is reusable; that is not the only requuirement of succesful software
>reuse. I would like to develop an environment available to Lisper's
>that not only makes reuse possible, but available, cost-effective,
>and something that management can support.
This is an execellent idea and, if nothing else, should at least
help people increase the reusability of code they want to make
available.
>Please respond if:
>
>(1) You are willing to participate in the development of such a library.
>This includes doing a little background reading on the non-technical
>aspects of succesful reuse.
>
>(2) You are willing to submit assets to the library.
>
>(3) You want to use the library.
All of the above. Can you suggest some likely-to-be-available
background reading?
-- jeff
From: Tom Pole
Subject: Re: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <1993Mar9.152833.12177@evb.com>
In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>In article <······················@evb.com> ····@evb.com (Tom Pole) writes:
>>
>>I think its time we use some of the very good stuff that the reuse
>>community has come up with, and apply it to a PD reuse library of
>>Lisp forms
>
... other stuff
>
>This is an execellent idea and, if nothing else, should at least
>help people increase the reusability of code they want to make
>available.
>
>All of the above. Can you suggest some likely-to-be-available
>background reading?
>
>-- jeff
Sorry guys, I promised the respondents to this original posting that I would
reply a list of references as well as some other information, but things
have really stacked up on me lately.
I'm chairing LUV-93 this year, and that is really getting first priority
after day-job responsibilities. It will be the end of March before I can
really get things going on the reuse-lib front.
Not to mention that I'm in the process of a day-time move, and will
be responding from a new email address in a couple of weeks.
I will try to put together some materials during lunch today and
post it either this afternoon or this evening.
If I may suggest, can we get a little discussion going anyway ?
What do you folk expect from a reuse lib of Lisp assets (note the word
asset, software is MUCH MUCH more than source code) ?
What services, standards, representation of assets, search mechanisms,
access do you want ?
What kind of functionality would you find useful to be available in the
library ?
Should we allow pointers in the PD library to Non-PD, commercially
available components ?
What incentives can we come up with to convince people to donate
(read "give away") the product of their sweat and ulcers ?
Thanks, Thomas
--
Thomas Pole
From: ····@evb.com (Tom Pole)
Newsgroups: comp.lang.lisp
Subject: Re: Reusable Lisp Library (was Efficient Linked Lists in Common Lisp?)
Date: 9 Mar 93 15:28:33 GMT
Organization: EVB Software Engineering, Inc.
Sorry guys, I promised the respondents to this original posting that I would
reply a list of references as well as some other information, but things
have really stacked up on me lately.
I will try to put together some materials during lunch today and
post it either this afternoon or this evening.
If I may suggest, can we get a little discussion going anyway ?
What do you folk expect from a reuse lib of Lisp assets (note the word
asset, software is MUCH MUCH more than source code) ?
Basically, I want a known repository of Lisp assets that I can search
through. While I agree with your idea that the assets are more than
source code, I think that we should follow the "worse is better"
strategy to the extent that we allow submissions of assets that are
nothing more than source code, minimal use documentation and an
abstract. If we want to build on that and develop standards to
promote interoperability and reuse, fine, but solve the problem one
step at a time.
What services, standards, representation of assets, search mechanisms,
access do you want ?
I think that good abstracts are the key to low-overhead searches. The
low quality of abstracts is currently a problem in both the MCL and
CLIM contrib libraries (as well as the stuff on comp.binaries.metc,
etc. I think that the only good solution is to have a librarian with
enough resources to devote to the task, pestering contributors for
descriptions and maybe even writing some.
There might be an even bigger problem associated with organizing the
library. Most contributions can be cut along several lines, including
the problem area being addressed, the implementation technique, and
the connections to the environment. Sometimes you want to search for
"all the CLIM-based tools", finding a class grapher and a color
editor, and sometimes you want to search for a "class grapher",
finding both the CLIM and Garget versions. There are also
platform-dependence issues which will need to be addressed given that
there is already a pretty big library of MCL-specific contributions
(some of which could possibly be made portable).
What kind of functionality would you find useful to be available in the
library ?
Anything that people build the might be reusable. The point is to
provide the infrastructure that allows people to easily make
contributions and find things that they can use.
Should we allow pointers in the PD library to Non-PD, commercially
available components ?
Yes.
What incentives can we come up with to convince people to donate
(read "give away") the product of their sweat and ulcers ?
Fame and glory, contributions from others, hope for the future.
From: Ronald Greenberg
Subject: Re: Efficient Linked Lists in Common Lisp?
Date:
Message-ID: <1lbgf5INNruq@mojo.eng.umd.edu>
I feel compelled to followup my own message based on e-mail I have
received. A few people have wondered why I would use eval, horrors!
Ok, sorry, eval certainly could be replaced by symbol-value. One
respondent indicated that symbol-value on his lisp system is about 4
times as slow as simple pointer following, but at least it's better
than eval. (Probably, the reason I slipped into eval is that
sometimes I fall back on the barebones things I learned when I first
learned Lisp from the "Lisp 1.5 Primer" rather than remembering all
the other nice Common Lisp things.)
But some people are mystified that there is any need for anything like
eval or symbol-value. Here are some of the comments:
You definitely don't want to get to a next node by calling EVAL. Just
use the NODE-NEXT function on your current node.
But honestly, I cannot understand why you are mixing together
symbols-as-pointer with your node-structures. Why don't you simply let
NEXT and PREV be pointers to other objects of type NODE????
In light of the length discussion on why Lisp isn't a mainstream
language, I find this message quite interesting. I'm very interested
in knowing what is it about Lisp that seduced you into using EVAL. In
C, nobody would ever think of doing this, presumably because EVAL does
not exist at all. But since in Lisp, everything is an object
reference, there is no need for EVAL at all.
Somebody even gave me code that gets rid of the eval type calls, but
calling this function causes an infinite loop; try it! The problem as
I see it is how to create and use a pointer in an efficient fashion.
(defstruct (node (:type list))
(next nil)
(previous nil)
(key nil))
(defun make-doubly-linked-list (size &key circular)
(let* ((root-node nil)
(prev-node nil)
(next-node nil))
(dotimes (i size)
(setq next-node (make-node :key i
:previous prev-node))
(when prev-node
(setf (node-next prev-node) next-node))
(setq prev-node next-node)
(unless root-node
(setq root-node next-node)))
(when circular
(setf (node-next next-node) root-node)
(setf (node-previous root-node) next-node))
root-node))
--
Ronald I. Greenberg (Ron) ···@eng.umd.edu
--
Ronald I. Greenberg (Ron) ···@eng.umd.edu
From: Ronald Greenberg
Subject: Re: Efficient Linked Lists in Common Lisp?
Date:
Message-ID: <1lbi7tINNshq@mojo.eng.umd.edu>
Aha, I'd better try to head of the potential avalanche of responses to
my complaint about an infinite loop. The following comment seems to
resolve the problem. For those of you who evidently knew what you
were talking about, but didn't think to mention *print-circle*, try to
remember this is the answer for problems like mine. Thanks for the
help.
Actually, my code doesn't go into an infinite loop. However, the
resulting structure is a circular structure, so the Lisp printer will
go into an infinite loop trying to print it.
Try evaluating the following form to see what I mean:
(let ((*print-circle* t))
(let ((dll (make-doubly-linked-list 5)))
(print dll) nil))
--
Ronald I. Greenberg (Ron) ···@eng.umd.edu
Date: Wed, 10 Feb 1993 13:10 EST
From: Ronald Greenberg <···@eng.umd.edu>
I feel compelled to followup my own message based on e-mail I have
received. A few people have wondered why I would use eval, horrors!
Ok, sorry, eval certainly could be replaced by symbol-value. One
respondent indicated that symbol-value on his lisp system is about 4
times as slow as simple pointer following, but at least it's better
than eval. (Probably, the reason I slipped into eval is that
sometimes I fall back on the barebones things I learned when I first
learned Lisp from the "Lisp 1.5 Primer" rather than remembering all
the other nice Common Lisp things.)
But some people are mystified that there is any need for anything like
eval or symbol-value. Here are some of the comments:
You definitely don't want to get to a next node by calling EVAL. Just
use the NODE-NEXT function on your current node.
But honestly, I cannot understand why you are mixing together
symbols-as-pointer with your node-structures. Why don't you simply let
NEXT and PREV be pointers to other objects of type NODE????
In light of the length discussion on why Lisp isn't a mainstream
language, I find this message quite interesting. I'm very interested
in knowing what is it about Lisp that seduced you into using EVAL. In
C, nobody would ever think of doing this, presumably because EVAL does
not exist at all. But since in Lisp, everything is an object
reference, there is no need for EVAL at all.
Somebody even gave me code that gets rid of the eval type calls, but
calling this function causes an infinite loop; try it! The problem as
I see it is how to create and use a pointer in an efficient fashion.
The following code does not go into an infinite loop, but since the
resulting object is circular, the Lisp printer will go into a loop
trying to print the object.
(defstruct (node (:type list))
(next nil)
(previous nil)
(key nil))
(defun make-doubly-linked-list (size &key circular)
(let* ((root-node nil)
(prev-node nil)
(next-node nil))
(dotimes (i size)
(setq next-node (make-node :key i
:previous prev-node))
(when prev-node
(setf (node-next prev-node) next-node))
(setq prev-node next-node)
(unless root-node
(setq root-node next-node)))
(when circular
(setf (node-next next-node) root-node)
(setf (node-previous root-node) next-node))
root-node))
In article <····················@SUMMER.SCRC.Symbolics.COM> ···@stony-brook.scrc.symbolics.com (Scott McKay) writes:
The following code does not go into an infinite loop, but since the
resulting object is circular, the Lisp printer will go into a loop
trying to print the object.
[...stuff...]
unless you set *print-circle* non-nil, of course.
which reminds of me something else i wanted to ask: does anyone have any
good ideas about how to implement efficient general circularity testing?
the fastest way i can think of is to use something like the gc's mark bit -
most likely REuse it, in fact. any better ways?
i'm also having trouble figuring out how to do #n= and #n#. i'll take the
example from the dpANSI standard:
((a b) . #1=(#2=(p q) foo #2# . #1#))
how the dickens do i handle #1#? on seeing #1= i surely can't just recursively
call read, since the second read will see #1# before it's defined. is there a
clean way to do this?
--
Hume Smith i make no apologies
··········@acadiau.ca for not using capitals.
······@bnr.ca everyone needs a vice...
From: Michael Greenwald
Subject: Re: *print-circle* (was Re: Efficient Linked Lists in Common Lisp?)
Date:
Message-ID: <michaelg.729453080@Xenon.Stanford.EDU>
······@bnr.ca (hume smith) writes:
>which reminds of me something else i wanted to ask: does anyone have any
>good ideas about how to implement efficient general circularity testing?
>the fastest way i can think of is to use something like the gc's mark bit -
>most likely REuse it, in fact. any better ways?
For generality, the mark bit (assuming the system has one) is a bad
idea: let's say another part of the system wants to overload it, too?
Another, more general, is to look up the stack (your own, obviously,
not the system) during object traversal each time you encounter a new
object. Unfortunately, this is O(n^2).
>i'm also having trouble figuring out how to do #n= and #n#. i'll take the
>example from the dpANSI standard:
> ((a b) . #1=(#2=(p q) foo #2# . #1#))
>how the dickens do i handle #1#? on seeing #1= i surely can't just recursively
>call read, since the second read will see #1# before it's defined. is there a
>clean way to do this?
I don't understand. I think I'm misunderstanding your question.
In the simple case above, why can't you call READ? Why not just use
the current value of #1# when you see it during the read? Why should
it make a difference that (cdddr #1#) is uninitialized --- you should
define #1# as soon as you see #1=, not when the value is complete,
otherwise you can never use #n for circular objects. This shouldn't
be any different than
(let* ((a (cons nil nil))
(b a))
...
(setf (cdr b) a))
When #1= points at a cons cell, it's simple --- there >are< some
slightly tricky questions when you think about interactions with #.
and #, or backquote and comma, but only slightly.
>--
>Hume Smith i make no apologies
>··········@acadiau.ca for not using capitals.
>······@bnr.ca everyone needs a vice...