Anybody has an experience implementing custom containers in Lisp ?
Is it possible or just have to be built in?
I am specifically interested in circularly-doubly-linked list.
"fireblade" <········@YAHOO.COM> writes:
> Anybody has an experience implementing custom containers in Lisp ?
Yes.
> Is it possible or just have to be built in?
Yes.
> I am specifically interested in circularly-doubly-linked list.
Good. Any problem?
--
__Pascal Bourguignon__ http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
Thanks for your re's guys but actually i was interested to see some
code here.
My experience comes from C++/Basic background (+ some Pascal and C#)
but i'm relatively new to Lisp (read less than a year).
It's not an easy task making a container in C++ but when standard
library doesn't provide it , you just have to do it yourself.
Also you could look at C++ library .h and .cpp files and got an idea
what to change (Though they are heavily optimized )
So if anybody has some code to post i would be very gratefull.
Thanks
Bobi
From: Christopher C. Stacy
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <u64y748y7.fsf@news.dtpq.com>
"fireblade" <········@YAHOO.COM> writes:
> Thanks for your re's guys but actually i was interested to see some
> code here.
> My experience comes from C++/Basic background (+ some Pascal and C#)
> but i'm relatively new to Lisp (read less than a year).
> It's not an easy task making a container in C++ but when standard
> library doesn't provide it , you just have to do it yourself.
> Also you could look at C++ library .h and .cpp files and got an idea
> what to change (Though they are heavily optimized )
> So if anybody has some code to post i would be very gratefull.
People think you're trying to get them to do your homework,
and are waiting for you to show your own work, first.
Well i'm student of economics (finances to be specific) so nobody
at my faculty doesn't even know what Lisp is ,homework about Lisp
you must be joking.
Also i don't want you doing my projects , i won't learn anything
that way, i just need a clue how any kind of List is implemented.
With C++ i would see at standard library, C# /VB - Net framework
and Mono.About Lisp i just don't know where to start .
>From all the books i read never seen somebody doing something
low level like that . Probably List dissection is the closest thing
but that's just not it.
Bobi
From: Christopher C. Stacy
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <uzmvj2sgl.fsf@news.dtpq.com>
You should start by reading an introductory textbook on Lisp.
A good one just came out the other day.
Which one ?
I allready went throgh:
Gentle Introduction - Touretzky
Loving Lisp - Watson
Practical CL -Seibel
On Lisp - Graham (I stacked at Macros returning functions, the
material was too advanced for me will continue once i gather more
experience)
As reference i use the hyperspec coming with Lispworks .
All the way is high-level programming ,using built in singly-linked
lists, arrays , hash tables ...
So If you have anything specific am eager to hear.
From: Christopher C. Stacy
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <u8y33gsur.fsf@news.dtpq.com>
"fireblade" <········@YAHOO.COM> writes:
> Which one ?
> I allready went throgh:
> Gentle Introduction - Touretzky
> Loving Lisp - Watson
> Practical CL -Seibel
> On Lisp - Graham (I stacked at Macros returning functions, the
> material was too advanced for me will continue once i gather more
> experience)
> As reference i use the hyperspec coming with Lispworks .
>
> All the way is high-level programming ,using built in singly-linked
> lists, arrays , hash tables ...
>
> So If you have anything specific am eager to hear.
Did you encounter something called DEFSTRUCT?
From: Jacek Generowicz
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <m2acnj88gy.fsf@genera.local>
"fireblade" <········@YAHOO.COM> writes:
> i'm not planning to do any OO here,
Oh yes you are, even if you do not realize it yet.
"fireblade" <········@YAHOO.COM> writes:
> With C++ i would see at standard library,
And if you did, you would see that C++ containers are implemented with
classes.
Yes correct , built the deck around class with array , mebers ,
functions.
It looks like that i'm missing the pointers , bad habits die hard.
Ok thanks everybody, especially Pascal for the code
will play with it and see how it works
See you later
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <REM-2005may02-002@Yahoo.Com>
> From: "fireblade" <········@YAHOO.COM>
> About Lisp i just don't know where to start . From all the books i
> read never seen somebody doing something low level like that .
Go back to those books and look specifically at the description of the
return value from CONS, the kind of two-pointer container it is.
(Ignore what that kind of container is called in the book because it's
probably either a misnomer or a circular definition, make up your own
descriptive name for that kind of object and tell me what name you
picked.) Then look at the definition of proper-list and dotted-list,
and try to draw diagrams of how these are really CDR-chains of those
things from CONS.
*after* you've done the above, look at:
http://www.rawbw.com/~rem/StandardPair.AsciiArt.txt
How does it compare with what you visualized?
How does what you called it compare with what I call it?
More generally, what do you think of this?
http://www.rawbw.com/~rem/LispDiagrams.html
·······@Yahoo.Com (Robert Maas, see http://tinyurl.com/uh3t) writes:
> More generally, what do you think of this?
> http://www.rawbw.com/~rem/LispDiagrams.html
You may conceptualize the vector of anything as you've done, but in
practice, the implementations may rather like put it like:
+---+--------+---+------------+---+
| H |char:#\[| H |fixnum:65536| H |
+-|-+--------+-|-+------------+-|-+
| | |
| | |
| | v
| | +-----------+------+------+
| | |complex-R-R|9.2275|-1.472|
| | +-----------+------+------+
| |
| v
| +----+-----------------+
| |real|2.718281828459045|
| +----+-----------------+
|
v
+---------+--+-+
|ratio-F-F|22|7|
+---------+--+-+
--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962:DO20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <REM-2005jun25-005@Yahoo.Com>
> From: Pascal Bourguignon <···@informatimago.com>
> You may conceptualize the vector of anything as you've done, but in
> practice, the implementations may rather like put it like:
(Snip very nice implementation-specific diagram)
The question between your diagram and mine is appropriateness for the
audience. If somebody is going to delve into the innerds of one
specific implementation, then knowing the exact way the data is
organized in actual RAM is important, so your diagram or something like
it would be the best way to visualize the structures to get an overview
prior to looking at the actual code that deals with these structures.
But for a beginner who wants to stick to the API, write portable code,
and needs to know what's possible and what's impossible and what's
efficient vs. not efficient, the key desired properties of a diagram
are:
- It must show the different parts of a structure.
- It must show which parts are mutable vs. which are immutable.
- It must show which operations are efficient (such as picking a field
out of an array or record, and performing indirect-addressing to follow
a link/pointer in the forward direction). All other operations are then
assumed to be inefficient, such as searching a large structure to find
a matching element (moderately inefficient) or searching all of RAM to
find any object that points to the given object (very inefficient).
- Anything shown must express something observable via the API.
- It must *not* show the specifics of anything that is invisible from
the API, such as tag bits that identify different kinds of objects or
pointers, or different regions of memory that hold different kinds of
objects (as in BIBOP storage management).
I'm trying to find an optimal diagram system for showing beginners what
they are dealing with via the API. So if you find any place I might
improve my diagram system, especially a more clear way of showing
mutable vs. immutable fields, that would be useful. Currently I'm
leaning toward showing a pointer whenever it can be mutated and showing
in-place referenced data when it is immutable. But I don't really like
that in the case of fixed-precision byte arrays which are mutable but
most definitely are done by in situ data rather than pointers, so an
alternative notational convention in diagrams of mutable-element
specific-type arrays would be useful.
Quoting the OP:
<<i'm student of economics (finances to be specific) ...
i just need a clue how any kind of List is implemented. ...
About Lisp i just don't know where to start>>
I assumed he doesn't yet know how to program Lisp down at the level of
CARs and CDRs, nor how to estimate what things can be done with lists,
so a portable diagram showing just the general idea of the structures
sufficient to write low-level CAR/CDR code, would be what he wanted.
Then later if he is interested in some particular implementation, then
your detailed implementation-specific diagram might be a useful
follow-on. But he just said "lisp" in general, not some specific
version of lisp, so probably my diagram first, right? Or did I
misunderstand the OP's immediate need?
·······@Yahoo.Com (Robert Maas, see http://tinyurl.com/uh3t) writes:
> [...]
> But for a beginner who wants to stick to the API, write portable code,
> and needs to know what's possible and what's impossible and what's
> efficient vs. not efficient, the key desired properties of a diagram
> are:
> - It must show the different parts of a structure.
> - It must show which parts are mutable vs. which are immutable.
> - It must show which operations are efficient [...].
> - Anything shown must express something observable via the API.
> - It must *not* show the specifics of anything that is invisible from
> the API, such as tag bits that identify different kinds of objects or
> pointers, or different regions of memory that hold different kinds of
> objects (as in BIBOP storage management).
Tag bits are somewhat visible in the API:
(type-of 48)
(type-of #\0)
(type-of "48")
(type-of '(4 . 8))
etc...
You'll want to abstract them and draw typed cells (type;value).
> I'm trying to find an optimal diagram system for showing beginners what
> they are dealing with via the API. So if you find any place I might
> improve my diagram system, especially a more clear way of showing
> mutable vs. immutable fields, that would be useful. Currently I'm
> leaning toward showing a pointer whenever it can be mutated and showing
> in-place referenced data when it is immutable.
You'd need an arrow every time two objects are EQ.
But this is implementation dependant, so you could pedagogically
ignore EQ and use an arrow every time two objects are EQL.
Then vectors would always contain pointers. For example, the vector
"AAA" could be drawn as:
+------+---+---+---+
|string| * | * | * |
+------+-|-+-|-+-|-+
| | | +----+-+
+-->+-->+-->|char|A|
+----+-+
> But I don't really like
> that in the case of fixed-precision byte arrays which are mutable but
> most definitely are done by in situ data rather than pointers, so an
> alternative notational convention in diagrams of mutable-element
> specific-type arrays would be useful.
> [...]
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <REM-2005jun29-008@Yahoo.Com>
> From: Pascal Bourguignon <···@informatimago.com>
> Tag bits are somewhat visible in the API:
> (type-of 48)
> (type-of #\0)
> (type-of "48")
> (type-of '(4 . 8))
> etc...
> You'll want to abstract them and draw typed cells (type;value).
Here's what i get:
CMU Common Lisp 18b, running on shell.xxx.com
Send questions and bug reports to your local CMU CL maintainer,
or to ··········@cons.org. and ·········@cons.org. respectively.
Loaded subsystems:
Python 1.0, target Intel x86
CLOS based on PCL version: September 16 92 PCL (f)
* (type-of 48)
FIXNUM
* (type-of #\0)
BASE-CHAR
* (type-of "48")
(SIMPLE-BASE-STRING 2)
* (type-of '(4 . 8))
CONS
I don't see any tag bits visible through the API. Perhaps you do on
whatever CL implementation you're using. Perhaps visibility of such is
implementation-dependent.
One thing that might be reasonble for me to do in my diagrams is to
carefully call type-of on any object I want to diagram, and copy the
return value verbatim into the header of the individual object, and
distinguish between immediate values and handles to heap objects, such
as:
FIXNUM:[47]
BASE-CHAR:[R]
H
|
|
V
SIMPLE-BASE-STRING:
+---+---+
| 4 | 8 |
+---+---+
H
|
|
V
CONS:
+-----+-----+
| | |
| H | H----------->FIXNUM:[47]
| | | |
+--|--+-----+
|
|
V
SINGLE-FLOAT:[3.1415926535]
However there are a couple things I don't like about that:
(1) The internal data types are implementation dependent, like the
number 32798451 might be an immediate FIXNUM on one system but a handle
to a heap-allocated BIGNUM on another system.
(2) The API is orthogonal to such implementation variations. Numbers
(integers, reals) are immutable regardless of whether they are
immediate or handle-to-heap-object. Arithmetic on integers yields
FIXNUM or BIGNUM values depending on the size of the result, not
depending on the mathematical value or the specific parameter types
going into the arithmetic function.
(3) For beginners, some of the arcane historical jargon such as CONS is
mysterious and confusing, when I and all my students (so-far) agree
that "Standard Pair" is much more meaningful to describe a car-cdr pair
than "CONS" is. Likewise we agree a metaphor of a coathanger "mobile"
with a left side and a right side, with other stuff hanging from each
side of the coathanger, is more meaningful than CAR and CDR.
Accordingly I think I'll avoid both arcane jargon and internal
representations when initially teaching the API. I'll pretend like
*all* integers are in fact BIGNUMs or equivalent, immutable objects on
the heap. Perhaps I should mention in my sample diagrams that for some
small values of integers, both positive and negative near zero, on some
implementations the actual numeric value might be encoded directly in
the handle rather than allocated on the heap, hence the handle is
actually a pseudo-handle. But for all practical purposes (except
watching GC statistics) all integers might as well be heap BIGNUMs. So
I'll stick to showing a handle pointing to an INTEGER:[value]. So my
main effort toward change will be in makeing sure I clearly use
different notation, somehow, for mutable vs. immutable objects/values.
For example, I want to clearly distinguish between strings which are
literal constants or names of symbols, which are supposed to be
immutable even if the implementation doesn't enforce that, caveat
emptor will bite you, vs. strings created by make-string or format or
read-line etc. which are freely mutable without any bad conseqences.
Hmm, I might also wish, in advanced beginner lessons, to clearly
distinguish between extendable vectors/strings and fixed-size objects.
Maybe this notation would be good:
(make-array '(5) :element-type 'BASE-CHAR :initial-element #\q
:adjustable t :fill-pointer t)
H
|
|
V
BASE-STRING:
+---+---+---+---+---+--
| q | q | q | q | q |...
+---+---+---+---+---+--
(make-array '(7) :element-type 'BASE-CHAR :initial-element #\q
:adjustable nil :fill-pointer 5)
H
|
|
V
BASE-STRING:
+---+---+---+---+---+--...--+
| q | q | q | q | q | ... |
+---+---+---+---+---+--...--+
Hmm, I did (vector-push-extend #\w h2) several times on that latter,
and it shouldn't have gotten past 7, but it did, why? Bug in CMUCL?
> You'd need an arrow every time two objects are EQ.
I'll ignore that, because I like the next idea better.
> But this is implementation dependant, so you could pedagogically
> ignore EQ and use an arrow every time two objects are EQL.
I agree. I think I'll say that EQ is used to tell whether the mutable
objects referenced by different handles are in fact the same or
different objects on the heap. If they are the same object, then making
a change inside that one object via either of the two handles will
obviously affect what is seen via the other handle to the same object.
An object can be visibly mutable, such as a standard pair or a vector,
or innerdly mutable, such as a symbol or OO-object.
For example of visibly mutable:
* (setq h1 (make-string 5 :initial-element #\q))
"qqqqq"
* (setq h2 h1)
"qqqqq"
* (setq h3 (make-string 5 :initial-element #\q))
"qqqqq"
* (eq h1 h2)
T
* (eq h1 h3)
NIL
* (eq h2 h3)
NIL
* (setf (elt h1 1) #\-)
* (setf (elt h2 2) #\*)
* (setf (elt h3 3) #\+)
* h1
"q-*qq"
* h2
"q-*qq"
* h3
"qqq+q"
For example of innerdly mutable:
* (setq s1 (make-symbol "foo"))
#:|foo|
* (set s1 "How should I know?")
"How should I know?"
* (setq s2 s1)
#:|foo|
* (setq s3 (make-symbol "foo"))
#:|foo|
* (set s3 "How should I know?")
"How should I know?"
* (setq syms (list s1 s2 s3))
(#:|foo| #:|foo| #:|foo|)
* (mapcar #'symbol-value syms)
("How should I know?" "How should I know?" "How should I know?")
* (eq s1 s2)
T
* (eq s1 s3)
NIL
* (eq s2 s3)
NIL
* (set s1 42)
42
* (setf (get s2 'altval) 7)
7
* (setf (get s3 'whatever) "yeah")
"yeah"
* syms
(#:|foo| #:|foo| #:|foo|)
;No visible change there.
;But deep down inside the innerds of the symbols:
* (mapcar #'symbol-value syms)
(42 42 "How should I know?")
* (mapcar #'(lambda (s) (get s 'altval)) syms)
(7 7 NIL)
* (mapcar #'(lambda (s) (get s 'whatever)) syms)
(NIL NIL "yeah")
I think examples like that would make the purpose of EQ, for handles to
mutable objects, apparent.
As for immutable objects: I'll just say there's no need for it in that
case since you aren't going to be able to modify the object so the
question of whether modifications are shared through different views
(handles) is moot. As a matter of fact, if you use EQ on mutable
objects that are created separately, interned symbols will be EQ if
they have the same name and are in the same package, otherwise the
objects will not be EQ (is that exactly correct?). By comparison, if
you use EQ on characters or integers that were created separately, or
even if you directly copy the handle as I did above, for example (setq
n1 5) (setq n1 n2), they might be EQ or they might not, and the EQ-ness
might change from moment to moment as you enter/leave bindings, so it's
best not to use EQ at all between integers or characters to avoid
confusion. If you use EQ on any other immutable objects created
separately, I have no idea if they'll be EQ or not.
* (setq f1 (expt 5.3 1.02))
5.4797583
* (setq f2 (expt 5.3 1.02))
5.4797583
* (eq f1 f2)
NIL
(defun testeq () (let ((f1 5.4) (f2 5.4)) (eq f1 f2)))
TESTEQ
* (testeq)
T
*
(defun testeq ()
(let ((f1 (expt 5.3 1.02)) (f2 (expt 5.3 1.02))) (eq f1 f2)))
TESTEQ
* (testeq)
NIL
* (symbol-function 'testeq)
#<Interpreted Function TESTEQ {9046E79}>
* (compile 'testeq)
* (testeq)
T
* (symbol-function 'testeq)
#<Function TESTEQ {9065CA1}>
So not-compiled it returns NIL, compiled it returns T. How's that for
confusing to beginner? Don't use EQ except on mutable objects, such as
standard-pairs and symbols, and you won't be confused by how EQ works.
> Then vectors would always contain pointers. For example, the vector
> "AAA" could be drawn as:
> +------+---+---+---+
> |string| * | * | * |
> +------+-|-+-|-+-|-+
> | | | +----+-+
> +-->+-->+-->|char|A|
> +----+-+
No. Only for mutable objects, where EQ is well defined, do I always
draw arrows (from handle/pointer to object). (Note: I like "handle"
instead of "pointer" for two reasons: It fits the coathanger/mobile
metaphor better, and these things in LISP are usually tagged, so they
aren't simple memory-address pointer-values as in C. Unfortunately
Macintosh jargon uses the term "handle" to mean something different,
which I won't discuss here. But an absolute beginner at programming,
trying to learn Lisp as a first language, surely hasn't studied the
innerds of Macintosh system-API-level toolbox traps with their stack
parameters and OS traps with their extremely fragile parameter blocks,
and the relevant storage management of pointers and handles, so Mac
jargon won't be a problem here.)
Note your phrase 'the vector "aaa"' is ambiguous: Does it mean a
general vector whose elements happen to be characters at the moment, or
an extendable vector of element-type declared to be restricted to
BASE-CHAR, or a fixed-size but elt-mutable string, or an immutable
string? You did identify it of type "string", which might eliminate
general vectors, but that fact might be implementation dependent.
As a general rule, any container whose elements are restricted to be
what is called a "primitive type" in Java, i.e. a fixed-precision
in-place value, not a handle to a value elsewhere, I'd write without
any arrow, whereas a containe whose elements are declared to be some
kid of heap object or which are not declared any type hence are by
default general, I'd always use arrows.
Note the slight conflict between the convention that general type
element of container which is handle on *any* heap object whatsoever,
even an immutable object, uses arrow, and the convention that arrows
are used only when pointing at mutable objects. I haven't completely
resolved this notational dilemma yet. Suggestions consistent with both
my proposed conventions are welcome so long as they are API-specific
and implementation-portable.
OT response to your sig:
> Nobody can fix the economy. Nobody can be trusted with their finger
> on the button. Nobody's perfect. VOTE FOR NOBODY.
Actually there needs to be somebody in control of key assets, such as
the military weapons systems, the border, the essential infrastructure
such as water and power. IMO the optimum solution is to have most such
admistrators watched 24/7, fully auto-audited, every action recorded in
multiple backup copies, etc., so *if* they do something really nasty we
can hold them accountable, no more situations like 18 minutes missing
from Nixon tape crap. In case of military actions such as movements of
troops and planning for an attack, record all actions for later release
after a reasonable "embargo" period, just like news releases about
scientific research papers being published and scientific press
conferences. For anything else, immediate real-time public disclosure.
Where the Geneva conventions disallow public exposure, such as
publishing photos of prisoners of war, keep full record but keep it
secret indefinitely until needed by international tribunal to
investigate alleged abuse of prisoners. Encryption of data, with
immediate public disclosure of any attempt to decrypt, should prevent
violation of Geneva conventions.
Back on topic, just barely: Lisp would be an ideal programming language
for implementing all the control algorithms for such monitoring. No
buffer overrun problems, for example, if all the software, even down to
the level of TCP/IP, uses Lisp storage management and Lisp-API
functions/methods, not a single line of C anywhere.
·······@Yahoo.Com (Robert Maas, see http://tinyurl.com/uh3t) writes:
>> From: Pascal Bourguignon <···@informatimago.com>
>> Tag bits are somewhat visible in the API:
>> (type-of 48)
>> (type-of #\0)
>> (type-of "48")
>> (type-of '(4 . 8))
>> etc...
>> You'll want to abstract them and draw typed cells (type;value).
>
> Here's what i get:
> CMU Common Lisp 18b, running on shell.xxx.com
> Send questions and bug reports to your local CMU CL maintainer,
> or to ··········@cons.org. and ·········@cons.org. respectively.
> Loaded subsystems:
> Python 1.0, target Intel x86
> CLOS based on PCL version: September 16 92 PCL (f)
> * (type-of 48)
> FIXNUM
> * (type-of #\0)
> BASE-CHAR
> * (type-of "48")
> (SIMPLE-BASE-STRING 2)
> * (type-of '(4 . 8))
> CONS
>
> I don't see any tag bits visible through the API.
I see two tag bits:
FIXNUM 00
BASE-CHAR 01
SIMPLE-BASE-STRING 10
CONS 11
> Perhaps you do on
> whatever CL implementation you're using. Perhaps visibility of such is
> implementation-dependent.
>
> One thing that might be reasonble for me to do in my diagrams is to
> carefully call type-of on any object I want to diagram, and copy the
> return value verbatim into the header of the individual object, and
> distinguish between immediate values and handles to heap objects, such
> as:
>
> FIXNUM:[47]
^^^^^^_______here, you're writting two tag bits.
> BASE-CHAR:[R]
>
> H
> |
> |
> V
> SIMPLE-BASE-STRING:
> +---+---+
> | 4 | 8 |
> +---+---+
>
> H
> |
> |
> V
> CONS:
> +-----+-----+
> | | |
> | H | H----------->FIXNUM:[47]
> | | | |
> +--|--+-----+
> |
> |
> V
> SINGLE-FLOAT:[3.1415926535]
>
>
> However there are a couple things I don't like about that:
> (1) The internal data types are implementation dependent, like the
> number 32798451 might be an immediate FIXNUM on one system but a handle
> to a heap-allocated BIGNUM on another system.
Of course you can abstract and call them all INTEGER.
> [...]
> (3) For beginners, some of the arcane historical jargon such as CONS is
> mysterious and confusing, when I and all my students (so-far) agree
> that "Standard Pair" is much more meaningful to describe a car-cdr pair
> than "CONS" is. Likewise we agree a metaphor of a coathanger "mobile"
> with a left side and a right side, with other stuff hanging from each
> side of the coathanger, is more meaningful than CAR and CDR.
Beginners stop being beginners once they know CONS, CAR and CDR.
These names are good because you don't attach any meaning to them.
(Well, perhaps Americans do see a Dodge when they read CAR?)
Their meaning is abstractly defined:
(car (cons x y)) =eq= x
(cdr (cons x y)) =eq= y
(cons (car c) (cdr c)) =equal= c
we could as well name them f g and h.
>> Then vectors would always contain pointers. For example, the vector
>> "AAA" could be drawn as:
>> +------+---+---+---+
>> |string| * | * | * |
>> +------+-|-+-|-+-|-+
>> | | | +----+-+
>> +-->+-->+-->|char|A|
>> +----+-+
> [...]
> Note your phrase 'the vector "aaa"' is ambiguous: Does it mean a
> general vector whose elements happen to be characters at the moment, or
> an extendable vector of element-type declared to be restricted to
> BASE-CHAR, or a fixed-size but elt-mutable string, or an immutable
> string? You did identify it of type "string", which might eliminate
> general vectors, but that fact might be implementation dependent.
I should have written 'a vector "AAA"', but since I was considering
one instance of a vector "AAA"...
But indeed, in some cases, what is represented (printed) as "AAA"
would more complex.
> [...]
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
Pascal Bourguignon <···@informatimago.com> writes:
> I see two tag bits:
>
> FIXNUM 00
> BASE-CHAR 01
> SIMPLE-BASE-STRING 10
> CONS 11
No, you only think you do. In SBCL, the following returns 7:
(let ((count 0))
(do-all-symbols (s (ceiling (log count 2)))
(when (typep (find-class s nil) 'built-in-class)
(incf count))))
I happen to know there are not 7 tag bits in SBCL.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Pascal Bourguignon <···@informatimago.com> writes:
>
>> I see two tag bits:
>>
>> FIXNUM 00
>> BASE-CHAR 01
>> SIMPLE-BASE-STRING 10
>> CONS 11
>
> No, you only think you do. In SBCL, the following returns 7:
>
> (let ((count 0))
> (do-all-symbols (s (ceiling (log count 2)))
> (when (typep (find-class s nil) 'built-in-class)
> (incf count))))
>
> I happen to know there are not 7 tag bits in SBCL.
Of course.
What we're just expliciting here is that lisp values are typed.
Whether a given implementation uses what's strictly technically called
"tag bits", or any other mean to tag a value with a type is irrelevant
to Robert's purpose, if I've understood well. However, he'll be
wanting to _tag_ his represented values with these types.
--
__Pascal Bourguignon__ http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <REM-2005jul27-018@Yahoo.Com>
> From: Pascal Bourguignon <···@informatimago.com>
> What we're just expliciting here is that lisp values are typed.
Well that's true. That's what makes Lisp so very much better than C and
somewhat better than Perl in that all the types can be distinguished
from each other at runtime, so you can freely mix different types in a
collection (linked-list, array, etc.) without getting confused as to
what type each object is when you later map/traverse/iterate/enumerate
through the collection to process all the individual values. The only
major deficiency is that the empty list and the false value are exactly
the same object, a pun that is useful most of the time but occasionally
it's a pain.
> Whether a given implementation uses what's strictly technically
> called "tag bits", or any other mean to tag a value with a type is
> irrelevant to Robert's purpose, if I've understood well.
Yes. I want to teach people computer programming in as much of a
language-independent way as possible, so not only do I avoid specifics
about how CMUCL or ELISP build objects at the machine level, but I also
avoid as much as possible anything whatsoever that isn't very nearly
the same in all versions of Lisp and also in Java and C and Perl and
PHP etc. etc. The only exception I make is for linked lists, where
other languages simply don't have any way to represent constants in
source code, so I use the Lisp notation, and later show how much of a
pain it is to do the same thing in any other language known to me.
Other than lists, I include only three other data types, strings,
numbers, and symbols (used only as names of variables and names of
functions during early lessons, no property lists since other languages
don't have property lists attached to symbols). Only the most basic
kinds of strings, without any special language-dependent notation such
as \n, are discussed. Numbers are treated very lightly, as integers and
common fractions and decimal fractions, no mention of "float" as the
internal name for decimal fractions. When Lisp shows that one integer
is a FIXNUM and another is a BIGNUM, I treat that lightly.
> However, he'll be wanting to _tag_ his represented values with these
> types.
Only with the abstract types that help the beginning student learn the
basics of computer programming, distinguishing strings from numbers for
example, showing explicit conversion from one to the other when it's
needed for accomplishing some useful larger task.
When I'm drawing diagrams, the most important distinctions are between:
- Mutable extendable objects.
- Mutable but fixed-size objects.
- Immutable objects.
I still haven't decided on the best notation for that distinction in
the case of strings which could be in any one of the three classes.
"fireblade" <········@YAHOO.COM> writes:
> Thanks for your re's guys but actually i was interested to see some
> code here.
> My experience comes from C++/Basic background (+ some Pascal and C#)
> but i'm relatively new to Lisp (read less than a year).
> It's not an easy task making a container in C++ but when standard
> library doesn't provide it , you just have to do it yourself.
> Also you could look at C++ library .h and .cpp files and got an idea
> what to change (Though they are heavily optimized )
> So if anybody has some code to post i would be very gratefull.
;;****************************************************************************
;;FILE: dll.lisp
;;LANGUAGE: Common-Lisp
;;SYSTEM: Common-Lisp
;;USER-INTERFACE: NONE
;;DESCRIPTION
;;
;; A doubly-linked list.
;;
;;AUTHORS
;; <PJB> Pascal Bourguignon <···@informatimago.com>
;;MODIFICATIONS
;; 2005-04-28 <PJB> Clean-up.
;; 2004-03-01 <PJB> Created.
;;BUGS
;;LEGAL
;; GPL
;;
;; Copyright Pascal Bourguignon 2004 - 2005
;;
;; This program is free software; you can redistribute it and/or
;; modify it under the terms of the GNU General Public License
;; as published by the Free Software Foundation; either version
;; 2 of the License, or (at your option) any later version.
;;
;; This program is distributed in the hope that it will be
;; useful, but WITHOUT ANY WARRANTY; without even the implied
;; warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
;; PURPOSE. See the GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public
;; License along with this program; if not, write to the Free
;; Software Foundation, Inc., 59 Temple Place, Suite 330,
;; Boston, MA 02111-1307 USA
;;****************************************************************************
(DEFPACKAGE "COM.INFORMATIMAGO.COMMON-LISP.DLL"
(:DOCUMENTATION
"This module exports a double-linked list type.
This is a structure optimized insertions and deletions in any place,
each node keeping a pointer to both the previous and the next node.
The stub keeps a pointer to the head of the list, and the list is
circularly closed (the tail points to the head).
Copyright Pascal Bourguignon 2001 - 2005
This package is provided under the GNU General Public License.
See the source file for details.")
(:USE "COMMON-LISP")
(:EXPORT
;; lists:
"DLL" "DLL-FIRST-NODE" "DLL-LAST-NODE"
"DLL-EMPTY-P" "DLL-LENGTH"
"DLL-EQUAL" "DLL-COPY" "DLL-APPEND" "DLL-NCONC"
;; items:
"DLL-CONTENTS" "DLL-NTH" "DLL-POSITION"
"DLL-FIRST" "DLL-LAST"
;; nodes:
"DLL-NODE" "DLL-NODE-NEXT" "DLL-NODE-PREVIOUS" "DLL-NODE-ITEM"
"DLL-NODE-NTH" "DLL-NODE-POSITION"
"DLL-INSERT" "DLL-DELETE"
))
(IN-PACKAGE "COM.INFORMATIMAGO.COMMON-LISP.DLL"
(defstruct (dll (:conc-name %DLL))
(first nil)
(last nil))
(defstruct dll-node
(previous nil)
(next nil)
(item nil))
(defun dll (&rest list)
(let ((dlist (make-dll))
(current nil))
(map nil (lambda (item) (setf current (dll-append dlist current item))) list)
dlist))
(defun dll-first-node (dlist) (%dll-first dlist))
(defun dll-last-node (dlist) (%dll-last dlist))
(defun dll-empty-p (dlist)
(null (%dll-first dlist)))
(defun dll-length (dlist)
(do ((len 0 (1+ len))
(current (%dll-last dlist) (dll-node-previous current)))
((null current) len)))
(defun dll-nth (dlist index)
(do ((i 0 (1+ i))
(current (%dll-first dll) (dll-node-next current)))
((or (null current) (= i index))
(when current (dll-node-item current)))))
(defun dll-position (dlist index &key (test (function eql)))
(do ((i 0 (1+ i))
(current (%dll-first dll) (dll-node-next current)))
((or (null current) (funcall test (dll-node-item current) item))
(when current i))))
(defun dll-node-position (dlist index &key (test (function eql)))
(do ((i 0 (1+ i))
(current (%dll-first dll) (dll-node-next current)))
((or (null current) (funcall test (dll-node-item current) item))
(when current i))))
(defun dll-equal (&rest dlls)
(or
(null dlls)
(null (cdr dlls))
(and
(let ((left (first dlls))
(right (second dlls)))
(and
(equal (dll-node-item (%dll-first left))
(dll-node-item (%dll-first right)))
(equal (dll-node-item (%dll-last left))
(dll-node-item (%dll-last right)))
(do ((lnodes (dll-node-next (%dll-first left))
(dll-node-next lnodes))
(rnodes (dll-node-next (%dll-first right))
(dll-node-next rnodes)))
((or (eq lnodes (%dll-last left))
(eq rnodes (%dll-last right))
(not (equal (dll-node-item lnodes) (dll-node-item rnodes))))
(and (eq lnodes (%dll-last left))
(eq rnodes (%dll-last right)))))
(dll-equal (cdr dlls)))))))
(defun dll-copy (dll)
(do ((new-dll (make-dll))
(src (%dll-first dll) (dll-node-next src))
(dst nil))
((null src) new-dll)
(setf dst (dll-insert new-dll dst (dll-node-item src)))))
(defun dll-append (&rest dlls)
(apply (function dll-nconc) (mapcar (function dll-copy) dlls)))
(defun dll-nconc (&rest dlls)
"
PRE: No dll appears twice in dlls.
DO: Extract the nodes from all but the first dll,
and append them to that first dll.
"
(if (null dlls)
(make-dll)
(do ((result (do ((dll (pop dlls) (pop dlls)))
((%dll-first dll) dll)))
(dlls dlls (cdr dlls))
(dll))
((null dlls) result)
(setf dll (car dlls))
(let ((first (%dll-first dll)))
(unless (null first)
(setf (dll-node-previous first) (%dll-last result)
(dll-node-next (%dll-last result)) first
(%dll-last result) (%dll-last dll)
(%dll-first dll) nil
(%dll-last dll) nil))))))
(defun dll-contents (dlist)
"
RETURN: A new list containing the items of the dll.
"
(do ((current (%dll-last dlist) (dll-node-previous current))
(result ()))
((null current) result)
(push (dll-node-item current) result)))
(defun dll-first (dlist)
(unless (dll-empty-p dlist) (dll-node-item (%dll-first dlist))))
(defun dll-last (dlist)
(unless (dll-empty-p dlist) (dll-node-item (%dll-last dlist))))
(defun DLL-NODE-NTH (dlist index)
(do ((i 0 (1+ i))
(current (%dll-first dlist) (dll-node-next current)))
((or (null current) (= i index)) current)))
(defun dll-node-position (dlist node)
(do ((i 0 (1+ i))
(current (%dll-first dlist) (dll-node-next current)))
((or (null current) (eq current node))
(if (eq current node) i nil))))
(defun dll-insert (dlist node item)
"
DO: Insert a new node after node, or before first position when (null node).
RETURN: The new node.
"
(let ((new-node nil))
(cond
((dll-empty-p dlist)) ;; first item
(setf new-node (make-dll-node :item item))
(setf (%dll-first dlist) new-node
(%dll-last dlist) (%dll-first dlist)))
((null node) ;; insert before first
(setf new-node (make-dll-node :previous nil
:next (dll-first-node dlist)
:item item))
(setf (dll-node-previous (%dll-first dlist)) new-node
(%dll-first dlist) new-node))
((not (dll-node-position dlist node))
(error "Node not in doubly-linked list."))
(t
(setf new-node (make-dll-node :previous node
:next (dll-node-next node)
:item item))
(if (dll-node-next node)
(setf (dll-node-previous (dll-node-next node)) new-node)
(setf (%dll-last dlist) new-node))
(setf (dll-node-next node) new-node)))
new-node)
(defun dll-extract-node (dlist node)
(if (eq (dll-first-node dlist) node)
(setf (%dll-first dlist) (dll-node-next node))
(setf (dll-node-next (dll-node-previous node)) (dll-node-next node)))
(if (eq (dll-last-node dlist) node)
(setf (%dll-last dlist) (dll-node-previous node))
(setf (dll-node-previous (dll-node-next node)) (dll-node-previous node)))
dlist)
(defun dll-delete (dlist node)
(unless (or (null node) (dll-empty-p dlist)
(not (dll-node-position dlist node))) ;; Note O(N)!
(dll-extract-node dlist node))
dlist)
(defun dll-delete-nth (dlist index)
(dll-extract-node dlist (dll-node-nth idlist index)))
;;;; dll.lisp -- -- ;;;;
--
__Pascal Bourguignon__ http://www.informatimago.com/
In deep sleep hear sound,
Cat vomit hairball somewhere.
Will find in morning.
>>>>> "PJB" == Pascal Bourguignon <···@informatimago.com> writes:
[...]
PJB> ;;****************************************************************************
PJB> ;;FILE: dll.lisp
PJB> ;;LANGUAGE: Common-Lisp
PJB> ;;SYSTEM: Common-Lisp
PJB> ;;USER-INTERFACE: NONE
PJB> ;;DESCRIPTION
PJB> ;;
PJB> ;; A doubly-linked list.
[... snip ...]
I notice that none of the accessors (DLL-CONTENTS, DLL-NTH, DLL-FIRST,
DLL-LAST) are setf-able. Is that for a specific reason (technical,
aesthetics, ...) or just not needed for your purpose?
Holger
Holger Duerer <········@gmx.net> writes:
>>>>>> "PJB" == Pascal Bourguignon <···@informatimago.com> writes:
>
> [...]
>
> PJB> ;;***********************************************************
> PJB> ;;FILE: dll.lisp
> PJB> ;;LANGUAGE: Common-Lisp
> PJB> ;;SYSTEM: Common-Lisp
> PJB> ;;USER-INTERFACE: NONE
> PJB> ;;DESCRIPTION
> PJB> ;;
> PJB> ;; A doubly-linked list.
> [... snip ...]
>
> I notice that none of the accessors (DLL-CONTENTS, DLL-NTH, DLL-FIRST,
> DLL-LAST) are setf-able. Is that for a specific reason (technical,
> aesthetics, ...) or just not needed for your purpose?
>
> Holger
Well, here where we manage distinctly the list and the nodes.
Perhaps we should remove the dll header, and just refer one of the
node to refer to the dll.
Anyway, you can do:
(setf (dll-node-item (dll-first dll)) 'new-value)
Most of the time, you'd be walking the dll holding a node, eg.:
(loop for node = (dll-first dll) then (if (must-advance)
(dll-node-next node)
(dll-node-previous node))
while node
do (setf (dll-node-item node) (new-value (dll-node-item node))))
Otherwise there's nothing that prevents adding DEFSEFs.
--
__Pascal Bourguignon__ http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <REM-2005may02-001@Yahoo.Com>
> From: "fireblade" <········@YAHOO.COM>
> I am specifically interested in circularly-doubly-linked list.
Presumably you know about CONS and RPLACA and RPLACD?
Exercise #1: Using only CONS, build a structure that has room to store
three external pointers.
Exercise #2: Using multiple instances of that 3-external-pointer
structure, build a 2-way-linked list. For example, with parameters
A,B,C,D containing four external pointers, build a 2-way-linked-list of
circumference 4 that holds copies of those four external pointers.
Both those exercises should be trivial. (Just describe in English how
you would use CONS together with some temporary variables to build that
4-loop.)
Exercise #3: You now have a fifth external pointer F. (Can't use E
because in CL that's a built-in constant, sigh.) Describe how you would
use RPLACA and RPLACD to enlarge the 4-loop to make a 5-loop where F
was just after D.
Once you've completed those exercises, to get a feel for the kinds of
structure building that would occur, write a specification of the
functions you *really* want to include in your package. (For example,
you probably don't want a function that takes exactly four values and
builds a 2-way-circular list pointing to those four values. Instead you
might want a function that takes an ordinary list of arbitrary length
and maps it over to a 2-way-circular list of the same length containing
the same values in the same sequence. And/or you might want a function
that creates a 2-way-circular list of circumference 1, and a function
that appends one new element to an existing 2wcl.)
·······@Yahoo.Com (Robert Maas, see http://tinyurl.com/uh3t) writes:
> (Can't use E because in CL that's a built-in constant, sigh.)
No, it isn't.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Implementing custom containers in Lisp
Date:
Message-ID: <REM-2005jun29-011@Yahoo.Com>
> From: Kalle Olavi Niemitalo <···@iki.fi>
> > (Can't use E because in CL that's a built-in constant, sigh.)
> No, it isn't.
Hmm, I checked and you're correct. I really thought I remembered from
back when I first started using CMUCL here in late 2000. I could be
mistaken, or maybe CMUCL had it a constant by mistake which has since
been fixed. I do remember that when I first started using it here it
had three bugs I discovered (sleep of floating point > 1 never sleeps
at all, one of the format directives in ERROR and CERROR etc. was
non-implemented, and a certain case of mixing lexical and special
variable by same name causes reference to wrong variable two levels
deep in function call), and one of them (the ERROR format bug) was
fixed since I discovered it, so maybe E was fixed too and I didn't
discover it until you told me. Let me check if the version I'm using
now is the same version as back then ...
% whereis lisp
lisp: /usr/local/bin/lisp /usr/local/man/man1/lisp.1.gz
% ls -l /usr/local/bin/lisp
576 -rwxr-xr-x 1 root wheel 579696 Mar 11 2001 /usr/local/bin/lisp*
Yeah, confirmed new version since I started using it.
And just now I confirmed the sleep bug is still there, so a magic
genie didn't patch it:
* (time (sleep 2))
Evaluation took:
2.01 seconds of real time
* (time (sleep 2.0))
Evaluation took:
0.0 seconds of real time
Has the sleep-of-float bug been fixed in the latest version my ISP
hasn't yet installed here? It was simple for me to program around it:
;Bug in CMU-CL: (sleep n) where N is a floating pointer number 1.0 or larger
; returns immediately without sleeping at all. To get around the bug:
(defun cl-sleep (n)
(cond ((and (floatp n) (>= n 1.0))
(multiple-value-bind (int frac) (floor n)
(sleep int) (sleep frac)))
(t (sleep n))))