Re: grow list by tail, pointer example recipe -- please comment
- From: jaycx1.3.calrobert@xxxxxxxxxxxxxxxxxxxxxxx (Robert Maas, http://tinyurl.com/uh3t)
- Date: Thu, 05 Jun 2008 02:27:15 -0700
From: Mirko.Vuko...@xxxxxxxxx
OK Robert, is this better?
Proposed addition to the CL recipes starts here - it is in emacs'
muse mode that will be converted to HTML and all the * are part of
markup and NOT variable names.
I'm not familiar with muse mode, so I don't know if I'll be able to
read your marked-up-text carefully enough to detect mistakes.
The procedure described in this note involves list surgery,
Hmm, that's a cute term to denote directly modifying the internal
workings of data structures that already have been built and which
might have multiple viewers (thus side-effects of such
modifications would be shared to all such viewers). I hope that
somewhere previously you defined what you mean by "surgery".
Hey, looky what I found in WikiPedia! Sushruta, around 600 BC,
wrote a text on surgery, in particular describing rhinoplasty. His
technique, used to reconstruct noses that were amputated as a
punishment for crimes, is practiced almost unchanged in technique
to this day. Excerpted from: <http://en.wikipedia.org/wiki/Surgery#History>
Hmm, I wonder if anesthesia is analagous to freezing all other
processes by declaring a "critical section" of code when making a
set of related modifications in shared data?
and we will have to look at the internals of list representation
in lisp.
Note that we're looking *only* at an abstract or idealized
representation of the internals. We're not looking directly at the
internals, such as how pointers are represented (absolute address,
relative address, address divided by four, tag bits in addition to
the address, etc.) and how the heap is laid out in RAM.
Some earlier versions of Lisp had ways to obtain the machine
address that a pointer represents (converted to a boxed integer
value), and given a (boxed) integer could do the inverse of
manufacturing a pointer with that address. For example, I seem to
recall in MacLisp there was MAKNUM that converted a pointer into a
boxed integer, and MUNKAM or somesuch to convert back. I'm pretty
sure ANSI-CL doesn't provide any such facility, so the true innerds
are pretty much invisible to users and application programmers.
Briefly, lists are stored as a series of cons cells.
That's not quite said well IMO. Maybe "chain" would be better than
"series" in that sentence. But the next sentence clarifies, so it's
not a fatal misstatement.
The car of each cell points to the stored element, and the cdr to
the next cons cell.
Yes, but note the possibility that some implementations may store
some values directly in the half-CONS-cell, rather than point to
value elsewhere. You might include a footnote to this effect,
saying that this is possible only when (1) the value requires less
storage than half a CONS pair, so that the value and some tag bits
can share that half-CONS-pair, and when (2) the semantics of
ANSI-CL prohibit modification (surgery) of the value in-place such
that side effects could be shared, and when (3) the semantics of
ANSI-CL allow violation of the EQ rule, that a value is always EQ
to itself. IIRC this possibility applies *only* to a limited range
of integers (typically integers within some small interval around
zero) and some characters (typically just US-ASCII, or standard
characters), and again it's an option if the implementation would
do this optimization or not. In Steele's CLtL1, this discussion is
at the bottom of page 77 and continuing to the top of page 78. The
corresponding text from the HyperSpec is here:
<http://www.isr.ist.utl.pt/library/docs/HyperSpec/Body/f_eq.htm>
An implementation is permitted to make ``copies'' of characters and
numbers at any time. The effect is that Common Lisp makes no guarantee
that eq is true even when both its arguments are ``the same thing'' if
that thing is a character or number.
If you're writing an online file, it'd probably be good to link to that.
CL-USER> (setq *list1* (list 1 3 5 7 9))
(1 3 5 7 9)
CL-USER> (sdraw *list1*)
[*|*]--->[*|*]--->[*|*]--->[*|*]--->[*|*]--->NIL
| | | | |
v v v v v
1 3 5 7 9
Hey, that's a nifty function. Do you have the source openly
available? Do you have a CGI demo whereby somebody can enter some
commands to build a list structure and then request such a diagram
to be displayed?
One thing is *not* nifty about it: It always shows the next CONS
cell consecutively to the right, which could mislead the novice to
believe these lists are in consecutive memory locations. I think
(strong opinion!!) that *before* you draw the very first such
left-to-right linked list, you draw how memory might *really* be
laid out, for example:
__________________________<<__________________________
/ \
->[*|*]->NIL [*|*] |
| | | |
V V | |
9 1 | |
/ -------------->[*|*]--\ |
/-----<<-------- / ________ | | |
| / / \ V | |
\->[*|*]------>>----/ ->[*|*] | 5 | ^
| | | \___________/ ^
V V \ |
3 7 ------->>----------/
(all the rest of the diagram represents memory which is part of
other unrelated objects)
(the traces wander all around to avoid crassing)
(if we were willing to have lines cross, we could draw more direct
links to show pointers going directly from one place to another:)
[*|*]->NIL [*|*]
| <- |//
V --- //V
9 --- // 1
-//- --------->[*|*]
// -<<<< >------- __----- |
V/ --->>>><<<---- <- V
[*|*]--- [*|*] 5
| |
V V
3 7
(but it would be very hard to follow the arrows that way)
Actually, for newbies, before you draw *any* arrow diagrams, you should
IMO show an actual hypothetical memory dump, like this:
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 32 04 NIL 38 74
1
2
3 9 1
4 7E 7A
5
6
7 A4 4E AA 02 5
8
9
A 3 7
Then describe how the top of the list is at location 08, where
first part (CAR) points to location 38 where the number 1 is found,
and second part (CDR) points to location 74 where the next CONS
pair is found. (Continue to describe in detail how the two-digit
numbers interpreted as memory addresses allow finding the next CONS
cell or the current number. Then repeat exactly the same picture
but with arrows overlaying it to show links from CDR parts to next
CONS pair. Then erase the hexadecimal numbers, replace them by
[*|*] notation, to show just the CONS pairs and links from one
place to another. Then redraw the arrows to avoid crossing. Then
rearrange the memory cells to show them in a nice linear diagram
the way your sdraw function draws them. That way the newbie really
understands that really in RAM these linked lists might jump all
over memory, and *that* is why you really need the CDR pointer to
tell you where to find the next cell in the chain. (If they were
always in consecutive memory locations, you wouldn't need a pointer
to find the next element. But that layout of memory would be an
ARRAY, not a linked list.)
There are some variations on the storage theme. For example,
small integers may be stored in the car, instead of having a
pointer to them.
Actually they can be stored in the CDR too, at the end of a dotted
list. But in this context, you're talking about only proper lists,
so that wouldn't occur. I suggest a footnote here to say that,
namely that they can be stored in the CDR just the same, but then
it wouldn't be a proper list so it's not relevant to this
discussion here.
(Splitting my reply here. More another day.)
.
- Prev by Date: Re: grow list by tail, pointer example recipe -- please comment
- Next by Date: Re: Lisp, 50th Birthday
- Previous by thread: Re: grow list by tail, pointer example recipe -- please comment
- Next by thread: Re: grow list by tail, pointer example recipe -- please comment
- Index(es):
Relevant Pages
|
