Lisp collections
Chris Capel
flexible array/collection feature. Let me describe the .NET ArrayList class.
It's built over a fixed-length array that's reallocated and copied when you
add elements over the maximum length. You access the elements through an
index, like a normal array. You can add any object as a member, and remove
an object based on the object itself or its index. You can get the number
of members in the array, and do various resizing things on it.
Has anyone written a library for this in Lisp?
I hear a lot that in Lisp, you should use lists, and then switch to arrays
when you need performance. But it seems to me that lists don't offer many
of the features of the ArrayList (or even Lisp arrays). For one, there's the
the whole structure issue that means you can't change the first element of
a list referenced by a symbol without having the symbol. For two, you can't
easily add elements to the end without writing a util function (though
there is push--but there again is the structure issue). For three, CAR,
CDR, and CONS. I don't want to think about those. I don't want a binary
tree of cons cells. I don't even want a list. What is a list variable? A
variable whose value is a cons cell whose cdr points to nil or another cons
cell. No, no, no. I want a collection of objects. I want an ArrayList. I
want /abstraction/.
What sort of solution do people use in this situation?
Granted, lisp arrays are a good start. Fill-pointer offers about the same
thing as an array-list, except for the automatic resizing when you fill up
the currently allocated space. And the functions have funny names, too.
OK, now for the big picture. .NET has the idea of "collections"[1], about
the same as a Lisp sequence, I guess, only it's more consistently used. In
C#, any collection (really, any IEnumerable, but ICollection implements
that) can be iterated over using a "foreach". Why can't you do this in
Lisp? Because the basic types aren't CLOSsy enough. Can you iterate over
any sequence? It seems to me that list, hashtable, and vector types ought
to inherit from enumerable-collection, and foreach should be a generic
method on that. (A hashtable would return a key-value pair for every
iteration.) MAPCAR and friends should be defined in terms of this generic
"collection" idea, so they wouldn't be limited to lists. You could still
get a guaranteed enumeration order, but the order would be a property of
the type's enumerator. I'm sure there are other ways to make this idea more
pervasive than it currently seems to be in Lisp.
Just to be clear, I'm not advocating changing the language or the standard.
And I know that a lot of this can be taken care of with the consistent use
of a few good macros and a class or two. And I know that I could be
completely wrong. I'm just comparing what I know to what I'm learning. So,
am I alone in this dim opinion of Lisp collections?
Chris Capel
[1] Unordered, key can be anything. These are implemented using interfaces
(like COM or java) on every class that wants to be a collection, including
basic arrays and such. There's also a "list" interface, which is an ordered
collection indexable with integers, and about as pervasive as the
collection interface.
Adam Warner
> Coming from a C# background, one thing I've begun to miss in lisp is a nice,
> flexible array/collection feature. Let me describe the .NET ArrayList class.
>
> It's built over a fixed-length array that's reallocated and copied when you
> add elements over the maximum length.
(defparameter *a* (make-array 3 :adjustable t :fill-pointer t
:initial-element nil))
*a* => #(nil nil nil)
> You access the elements through an index, like a normal array.
(aref *a* 2) => nil
> You can add any object as a member
(vector-push-extend 3 *a*)
*a* => #(nil nil nil 3)
>, and remove an object based on the object itself or its index.
(remove 3 *a*) => #(nil nil nil)
> You can get the number of members in the array
(length *a*) => 4
> , and do various resizing things on it.
Refer ADJUST-ARRAY.
> Has anyone written a library for this in Lisp?
It's built it. You are likely to pay a performance price for expressly
adjustable arrays.
Regards,
Adam
Chris Capel
>> You can add any object as a member
>
> (vector-push-extend 3 *a*)
>
> *a* => #(nil nil nil 3)
Ah! I had missed that function. And knowing that remove is destructive for
vectors is very useful. Thanks!
Chris Capel
Adam Warner
> Coming from a C# background, one thing I've begun to miss in lisp is a
> nice, flexible array/collection feature. Let me describe the .NET
> ArrayList class.
>
> It's built over a fixed-length array that's reallocated and copied when
> you add elements over the maximum length.
By the way, if this is the specification of the ArrayList class then it is
junk. An implementation should be permitted to extend the array using a
constant time algorithm. By your description the cost of extending the
array is proportional to the original size of the array. That's a poor
abstraction.
Regards,
Adam
Chris Capel
>>, and remove an object based on the object itself or its index.
>
> (remove 3 *a*) => #(nil nil nil)
I don't see any function to remove an object based on its index. Is there
such a thing for vectors or sequences?
Chris Capel
Chris Capel
I'm not sure that the particular implementation I mentioned was part of the
specification. I only recall somewhere that it was described that way. Of
course, a simple conceptual model is useful in situations like these, no
matter how it's implemented. But I do know that fixed-length arrays are
involved, because the ArrayList class is implemented in pure .NET IL, and
.NET doesn't have native adjustable arrays.
Although I'm curious--is there a constant time algorithm for this sort of
thing? /Primae facie/, it seems impossible.
Chris Capel
Adam Warner
REMOVE isn't destructive. Consult the HyperSpec. I'm sorry my example was
misleading.
For deleting the data at an index position you can write the function
yourself. Copy the remaining data after the deleted data from its original
position to the deleted position and decrement the fill pointer by the
number of elements deleted. If the data you are deleting is near the end
of the array then only a small amount of data will have to be copied.
Regards,
Adam
Peter Seibel
And use MAP-INTO to copy the data rather than looping and copying the
elements yourself; there's at least a chance the implementation will
have implemented MAP-INTO to use bulk copying primitives where
possible.
-Peter
--
Peter Seibel pe...@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Chris Capel
> REMOVE isn't destructive. Consult the HyperSpec. I'm sorry my example was
> misleading.
Yeah, I guess I did misread your example a bit.
I had read the section on REMOVE, but I assumed that the implementation
would need to implement it that way--silly, because it couldn't and be
conformant. But I imagine pretty much every implementation does DELETE that
way.
You see, these destructive semantics are important. Very non-functional in
spirit, but very useful in many situations. The CL spec seems to lack in
destructive alternatives to pure functions pretty often. That's a nice
thing in general (better than having the language push an imperative style
on you), but it makes having a simple, stateful collection of objects that
stays put when you change it rather difficult.
I suppose it'd be straightforward to implement a class that defines all
these functions on an array and takes care of that stuff for you. I think
it'd end up looking quite a bit different from a normal array. But it'd be
kind of hard to make it efficient.
Chris Capel
Adam Warner
> I don't see any function to remove an object based on its index. Is there
> such a thing for vectors or sequences?
How's this? (untested)
(defun delete-range (adj-vec start &optional end)
(let ((len-vec (length adj-vec)))
(unless end (setf end len-vec))
(loop for start-i from end to (1- len-vec)
for new-i from start do
(setf (aref adj-vec new-i) (aref adj-vec start-i)))
(adjust-array adj-vec (- len-vec (- end start)) :fill-pointer t)))
Regards,
Adam
Vassil Nikolov
What's wrong with
(setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
to destructively delete the i-th element of v, or
(setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
for a range?
---Vassil.
--
Vassil Nikolov <vnik...@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
Adam Warner
> Although I'm curious--is there a constant time algorithm for this sort of
> thing? /Primae facie/, it seems impossible.
Counterexample: (make-hash-table) using integers as a key.
It's only impossible when you impose constraints upon how arrays may be
implemented. If the adjustable array _must_ be stored as a contiguous
ordinary array then you have no options. If the adjustable array can be
implemented as pointers to contiguous vectors (with say 1MB of elements
each) then you can add a pointer to another contiguous vector at a
constant cost. Lookup is also constant (there's just another level of
indirection). Even if the vector of pointers turned out to be too small
the cost of building a larger pointer of vectors would be low.
Regards,
Adam
Adam Warner
> And use MAP-INTO to copy the data rather than looping and copying the
> elements yourself; there's at least a chance the implementation will
> have implemented MAP-INTO to use bulk copying primitives where
> possible.
Thanks for the hint Peter!
Regards,
Adam
Adam Warner
> Adam Warner <use...@consulting.net.nz> writes:
>
>> Hi Chris Capel,
>>
>>> I don't see any function to remove an object based on its index. Is there
>>> such a thing for vectors or sequences?
>>
>> How's this? (untested)
>>
>> (defun delete-range (adj-vec start &optional end)
>> (let ((len-vec (length adj-vec)))
>> (unless end (setf end len-vec))
>> (loop for start-i from end to (1- len-vec)
>> for new-i from start do
>> (setf (aref adj-vec new-i) (aref adj-vec start-i)))
>> (adjust-array adj-vec (- len-vec (- end start)) :fill-pointer t)))
>
>
> What's wrong with
>
> (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
>
> to destructively delete the i-th element of v, or
>
> (setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
>
> for a range?
Nice idea. It would suck if DELETE-IF turned out to be a synonym for
REMOVE-IF (which is conforming by my reading of the HyperSpec).
Regards,
Adam
Adam Warner
> Although I'm curious--is there a constant time algorithm for this sort of
> thing? /Primae facie/, it seems impossible.
Counterexample: (make-hash-table) using integers as a key.
It's only impossible when you impose constraints upon how arrays may be
implemented. If the adjustable array _must_ be stored as a contiguous
ordinary array then you have no options. If the adjustable array can be
implemented as pointers to contiguous vectors (with say 1MB of elements
each) then you can add a pointer to another contiguous vector at a
constant cost. Lookup is also constant (there's just another level of
indirection). Even if the vector of pointers turned out to be too small
the cost of building a larger vector to hold more pointers would be low.
Regards,
Adam
Wade Humeniuk
> I don't see any function to remove an object based on its index. Is there
> such a thing for vectors or sequences?
(defun delete-ref (sequence position)
(let ((marker (load-time-value (make-symbol "MARKER"))))
(delete marker (progn (setf (elt sequence position) marker)
sequence))))
Wade
Kalle Olavi Niemitalo
> I don't see any function to remove an object based on its index.
> Is there such a thing for vectors or sequences?
I think that can be done with DELETE-IF.
(defparameter *a* (vector 'I 'do 'not 'have 'much 'time))
;; => *A*
(delete-if (constantly t) *a* :start 4 :count 1)
;; => #(I DO NOT HAVE TIME)
This is not guaranteed to modify the vector *A*, but in SBCL
0.8.14.9 it apparently does; SB-KERNEL:SHRINK-VECTOR works
even though the vector is not otherwise adjustable.
*a*
;; => #(I DO NOT HAVE TIME)
(array-has-fill-pointer-p *a*)
;; => NIL
(adjustable-array-p *a*)
;; => NIL
Eric Daniel
> Counterexample: (make-hash-table) using integers as a key.
The hash table must still be coiped once it's full.
> It's only impossible when you impose constraints upon how arrays may be
> implemented. If the adjustable array _must_ be stored as a contiguous
> ordinary array then you have no options. If the adjustable array can be
> implemented as pointers to contiguous vectors (with say 1MB of elements
> each) then you can add a pointer to another contiguous vector at a
> constant cost. Lookup is also constant (there's just another level of
> indirection). Even if the vector of pointers turned out to be too small
> the cost of building a larger vector to hold more pointers would be low.
That's still O(n).
I'm pretty sure that you have to pick between constant time extension and
constant time access, but you can't have both. But I can't think of a
proof right now.
--
Eic Daniel
Adam Warner
>> It's only impossible when you impose constraints upon how arrays may be
>> implemented. If the adjustable array _must_ be stored as a contiguous
>> ordinary array then you have no options. If the adjustable array can be
>> implemented as pointers to contiguous vectors (with say 1MB of elements
>> each) then you can add a pointer to another contiguous vector at a
>> constant cost. Lookup is also constant (there's just another level of
>> indirection). Even if the vector of pointers turned out to be too small
>> the cost of building a larger vector to hold more pointers would be low.
>
> That's still O(n).
>
> I'm pretty sure that you have to pick between constant time extension and
> constant time access, but you can't have both. But I can't think of a
> proof right now.
With:
(a) A vector that can hold 4096 pointers.
(b) Contiguous vectors holding 1MB elements each.
You can address 4GB elements without even adjusting the size of the vector
of pointers.
To extended the array you add a pointer to a newly allocated contiguous
vector of 1MB elements. This is constant time extension.
To access an element by index you work out how many times the index is
greater than 1MB to get the index into the array of pointers. The
remainder is the index into the relevant contiguous vector. This is
constant time access.
Regards,
Adam
Pascal Costanza
> OK, now for the big picture. .NET has the idea of "collections"[1], about
> the same as a Lisp sequence, I guess, only it's more consistently used. In
> C#, any collection (really, any IEnumerable, but ICollection implements
> that) can be iterated over using a "foreach". Why can't you do this in
> Lisp? Because the basic types aren't CLOSsy enough. Can you iterate over
> any sequence? It seems to me that list, hashtable, and vector types ought
> to inherit from enumerable-collection, and foreach should be a generic
> method on that. (A hashtable would return a key-value pair for every
> iteration.) MAPCAR and friends should be defined in terms of this generic
> "collection" idea, so they wouldn't be limited to lists. You could still
> get a guaranteed enumeration order, but the order would be a property of
> the type's enumerator. I'm sure there are other ways to make this idea more
> pervasive than it currently seems to be in Lisp.
"Pure" object-oriented single-inheritance languages have to squeeze
everything into class hierarchies. In Lisp, this is not necessary. When
you take a closer look at collection hierarchies, you will notice that
there are unimplemented methods that throw exceptions, etc. So these
hierarchies aren't really hierarchies. Not all methods work on all
classes. Therefore, it's ok to have specialized functions that work,
say, only for lists.
The LOOP macro is pretty complete in allowing iteration over the data
structures that Common Lisp provides. Extensible LOOP implementations
allow you to add your own data structures.
> Just to be clear, I'm not advocating changing the language or the standard.
> And I know that a lot of this can be taken care of with the consistent use
> of a few good macros and a class or two. And I know that I could be
> completely wrong. I'm just comparing what I know to what I'm learning. So,
> am I alone in this dim opinion of Lisp collections?
You seem to be a newcomer to Lisp. There's a transition time in which
you expect things to work like they did in other languages. Soon you
will expect things to work like they do in Lisp elsewhere. ;)
Pascal
--
Pascal Costanza University of Bonn
mailto:cost...@web.de Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)
Pascal Costanza
> And use MAP-INTO to copy the data rather than looping and copying the
> elements yourself; there's at least a chance the implementation will
> have implemented MAP-INTO to use bulk copying primitives where
> possible.
What about REPLACE?
Eric Daniel
>
> With:
>
> (a) A vector that can hold 4096 pointers.
> (b) Contiguous vectors holding 1MB elements each.
>
> You can address 4GB elements without even adjusting the size of the vector
> of pointers.
>
> To extended the array you add a pointer to a newly allocated contiguous
> vector of 1MB elements. This is constant time extension.
But! But! It's only constant up to 4 billion elements! After that you need
to extend and reallocate the main vector, which is a non-constant time
operation. You may say, 4GB is the practical upper limit for memory,
so it doesn't matter. But in that case, at a minimum of 1MB per array,
these arrays will hardly be practical.
You can reduce the size of the 1MB contiguous vectors to say, 1KB.
Now you can fit a reasonable number of arrays in memory, but in that
case you will hit the O(n) behavior sooner. Increasing the main
vector's size pushes that limit back, but again at the cost of wasted
memory. Etc etc etc.
Now, I *can* imagine your solution used in specific problems where you
know how many chunks you are likely to allocate, and what their optimal
size should be. To go back to the thread's topic, this might be a neat
thing to add to a collection library.
--
Eric Daniel
Adam Warner
>> With:
>>
>> (a) A vector that can hold 4096 pointers.
>> (b) Contiguous vectors holding 1MB elements each.
>>
>> You can address 4GB elements without even adjusting the size of the vector
>> of pointers.
>>
>> To extended the array you add a pointer to a newly allocated contiguous
>> vector of 1MB elements. This is constant time extension.
>
> But! But! It's only constant up to 4 billion elements! After that you need
> to extend and reallocate the main vector, which is a non-constant time
> operation. You may say, 4GB is the practical upper limit for memory,
> so it doesn't matter. But in that case, at a minimum of 1MB per array,
> these arrays will hardly be practical.
Erik even after 4GB of elements the vector of pointers can be expanded by
copying a mere 4kB of data. For almost every purpose the difference in
time between allocating a new 1MB vector and allocating a new 1MB vector +
allocating and copying a few kB of pointers would be negligible.
Though I don't have to be charitable. I can make the initial size of the
vector of pointers 1MB of elements. Then you can address up to 1TB of
elements without even having to allocate a new copy of the vector of
pointers.
Imagine what I could do with another level of indirection :-)
"All problems in Computer Science can be solved by another level of
indirection."
Regards,
Adam
Joe Marshall
> Coming from a C# background, one thing I've begun to miss in lisp is a nice,
> flexible array/collection feature.
There is no reason to miss this. Lisp has it.
> Let me describe the .NET ArrayList class.
>
> It's built over a fixed-length array that's reallocated and copied when you
> add elements over the maximum length. You access the elements through an
> index, like a normal array. You can add any object as a member, and remove
> an object based on the object itself or its index. You can get the number
> of members in the array, and do various resizing things on it.
>
> Has anyone written a library for this in Lisp?
When creating an array, specify that the array is adjustable.
> I hear a lot that in Lisp, you should use lists, and then switch to arrays
> when you need performance.
You should use lists when lists are the natural way to represent the
data in question. You should use arrays when arrays are the natural
way to represent the data in question.
> But it seems to me that lists don't offer many of the features of
> the ArrayList (or even Lisp arrays). For one, there's the
> the whole structure issue that means you can't change the first element of
> a list referenced by a symbol without having the symbol.
(define *foo* (list 'a 'b 'c))
(define (change-first-element list)
(setf (first list) 'x))
(change-first-element *foo*)
*foo*
> (x b c)
> For two, you can't easily add elements to the end without writing a
> util function (though there is push--but there again is the
> structure issue).
True. If you want to do this, do not use a list.
> For three, CAR, CDR, and CONS. I don't want to think about those.
And who is making you?
(first '(a b c))
> a
(rest '(a b c))
> (b c)
(defun prepend (element list)
(cons element list))
(prepend 'x '(b c))
> (x b c)
> I don't want a binary tree of cons cells.
Then don't make one.
> I don't even want a list.
Ok... So don't make one of those. Problem solved.
> What is a list variable?
I give up.
> A variable whose value is a cons cell whose cdr points to nil or another cons
> cell. No, no, no.
You are conflating the value of a variable with the definition of the
implementation of a data type.
> I want a collection of objects. I want an ArrayList. I want /abstraction/.
Make up your mind. Clearly an `ArrayList' is an object has a number
of behaviors common to both arrays and lists. This is not an
abstraction, but an implementation. If you want a simple collection
of objects, you want something like a SET. It just so happens that
Common Lisp provides a number of primitives that give just this
behavior:
MEMBER
INTERSECTION
ADJOIN
SET-DIFFERENCE
SET-EXCLUSIVE-OR
SUBSETP
UNION
Notice that the ArrayList collection *doesn't* provide operations
analagous to intersection, difference, exclusive or, or subsetp.
> What sort of solution do people use in this situation?
It depends on the specifics. In one project I use I have *several*
different kinds of sets, each with its own advantages and
disadvantages. For small sets where performance is unimportant, the
simple list-oriented functions suffice. For larger sets where the
`universe' is fixed, I use bitmaps. For larger sets where performance
is important, but other constraints restrict the use of hash tables, I
use ordered sets based on red-black trees.
> Granted, lisp arrays are a good start. Fill-pointer offers about the same
> thing as an array-list, except for the automatic resizing when you fill up
> the currently allocated space.
Adjustable arrays resize just fine.
> And the functions have funny names, too.
Macros. I happen to think the `IsFoo' style of naming predicates is
ugly, but it seems that I'm SOL when it comes to C#.
> OK, now for the big picture. .NET has the idea of "collections"[1], about
> the same as a Lisp sequence, I guess, only it's more consistently
> used. In C#, any collection (really, any IEnumerable, but
> ICollection implements that) can be iterated over using a "foreach".
> Why can't you do this in Lisp?
Why, indeed. You can.
> Because the basic types aren't CLOSsy enough. Can you iterate over
> any sequence?
MAP
> It seems to me that list, hashtable, and vector types ought
> to inherit from enumerable-collection, and foreach should be a generic
> method on that. (A hashtable would return a key-value pair for every
> iteration.) MAPCAR and friends should be defined in terms of this generic
> "collection" idea, so they wouldn't be limited to lists. You could still
> get a guaranteed enumeration order, but the order would be a property of
> the type's enumerator. I'm sure there are other ways to make this idea more
> pervasive than it currently seems to be in Lisp.
Sure. The LOOP macro and the SERIES package do this sort of thing.
> Just to be clear, I'm not advocating changing the language or the standard.
> And I know that a lot of this can be taken care of with the consistent use
> of a few good macros and a class or two. And I know that I could be
> completely wrong. I'm just comparing what I know to what I'm learning. So,
> am I alone in this dim opinion of Lisp collections?
No, a number of dim people share this opinion.
Chris C apel
> What's wrong with
>
> (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
>
> to destructively delete the i-th element of v, or
>
> (setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
>
> for a range?
What's wrong is that you have to have the symbol. A collection
shouldn't be tied to its symbol. A collection should be fully
available wherever it's available at all--when you pass it around,
when you change it, no matter where. Without this property a
collection isn't nearly as useful to me. I believe Adam's function has
that property. (Thanks, Adam.)
Which serves my point, that Common lisp is built so much around
non-destructive (immutable object like) semantics that it's sometime
much more difficult to write any other code. I [often] want my
collections/arrays/lists to be mutable!
Chris Capel
Chris C apel
Ahh, but what happens when you want to remove element five out of ten?
After you remove it, you expect the fifth element to be what the sixth
was. That would make removing a really slow operation.
So adding elements is virtually constant. Referencing is still
constant (but maybe slower--either you have a complicated hash
function or poor hash performance (because the keys are contiguous)).
But removing from the middle takes a lot longer (though still linear),
because you have to look up N elements in a hash instead of shifting N
bytes. I guess you pick the model that suits your algorithm.
Chris Capel
Marcin 'Qrczak' Kowalczyk
> Which serves my point, that Common lisp is built so much around
> non-destructive (immutable object like) semantics that it's sometime
> much more difficult to write any other code. I [often] want my
> collections/arrays/lists to be mutable!
IMHO it's good that it has non-destructive operations on collections,
but it's bad that it doesn't distinguish mutable collections from
immutable collections, and that it doesn't have a unified interface
for collections other than an incomplete one for sequences.
A true immutable collection doesn't force to think about aliasing of
parts of its structure. A true resizable sequence allows to shrink it
to 0 elements or expand it from 0 elements. A Lisp list is neither
because it tries to be both.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Chris C apel
> Chris Capel wrote:
>
> > OK, now for the big picture. .NET has the idea of "collections"[1], about
> > the same as a Lisp sequence, I guess, only it's more consistently used. In
> > C#, any collection (really, any IEnumerable, but ICollection implements
> > that) can be iterated over using a "foreach". Why can't you do this in
> > Lisp? Because the basic types aren't CLOSsy enough. Can you iterate over
> > any sequence? It seems to me that list, hashtable, and vector types ought
> > to inherit from enumerable-collection, and foreach should be a generic
> > method on that. (A hashtable would return a key-value pair for every
> > iteration.) MAPCAR and friends should be defined in terms of this generic
> > "collection" idea, so they wouldn't be limited to lists. You could still
> > get a guaranteed enumeration order, but the order would be a property of
> > the type's enumerator. I'm sure there are other ways to make this idea more
> > pervasive than it currently seems to be in Lisp.
>
> "Pure" object-oriented single-inheritance languages have to squeeze
> everything into class hierarchies. In Lisp, this is not necessary. When
> you take a closer look at collection hierarchies, you will notice that
> there are unimplemented methods that throw exceptions, etc. So these
> hierarchies aren't really hierarchies. Not all methods work on all
> classes. Therefore, it's ok to have specialized functions that work,
> say, only for lists.
>
> The LOOP macro is pretty complete in allowing iteration over the data
> structures that Common Lisp provides. Extensible LOOP implementations
> allow you to add your own data structures.
It's OK for Lisp to be different. But being able to treat certain kind
of collection as having a minimal, common set of properties makes it
easy to write functions dealing with just those aspects of what a
collection /is/. That way collections that don't fit entirely into the
mold can still be used in some places. It's about separating the
implementation of the collection from its representation, and letting
the programmer have a simpler conceptual model of working with it.
LOOP may be nice, but the functionality it encapsulates should
probably be much more orthogonal. Instead of LOOP having an iterator
for various built-in types, there should be a generic iterator-concept
(probably a superclass) that can be used by *anything*. There should
be a collection concept that inherits that (that supports count, and
copying, as well as iterators). There should be a list concept that
inherits from the collection that supports indexing, adding, and
removing.
I'm sorry if I've repeated myself, but I just don't see how lisp
offers this level of abstraction from the data structures of its
collections.
> You seem to be a newcomer to Lisp. There's a transition time in which
> you expect things to work like they did in other languages. Soon you
> will expect things to work like they do in Lisp elsewhere. ;)
But until then, I think I need some convincing. Lisp is a much better
language than C# in general, but there are two are three things about
the Framework library that I think CL could use. It's nice that CL
will allow this to be done is a really useful and neat way, but I do
think it needs to be done. I'm unhappy with Lisp collections. I just
can't see myself ever seeing the power in the current system.
I think that, while Lisp is a much higher-level language than most
.NET languages, Lisp collections are lower-level than .NET
collections. That's the core of my argument. All the primitives are
there, but they need to be organized, fleshed out, and made more
consistent.
Chris Capel
Duane Rettig
> In article <pan.2004.09.21...@consulting.net.nz>, Adam Warner wrote:
> >
> > With:
> >
> > (a) A vector that can hold 4096 pointers.
> > (b) Contiguous vectors holding 1MB elements each.
> >
> > You can address 4GB elements without even adjusting the size of the vector
> > of pointers.
> >
> > To extended the array you add a pointer to a newly allocated contiguous
> > vector of 1MB elements. This is constant time extension.
>
> But! But! It's only constant up to 4 billion elements! After that you need
> to extend and reallocate the main vector, which is a non-constant time
> operation. You may say, 4GB is the practical upper limit for memory,
> so it doesn't matter. But in that case, at a minimum of 1MB per array,
> these arrays will hardly be practical.
Once you have reached that many elements, you are working in a 64-bit
lisp anyway (or else in great pain in a 32-bit lisp). Once you get
to a 64-bit lisp, though, your tries can be larger anyway, as your
array sizes themselves can be larger.
--
Duane Rettig du...@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Pascal Costanza
Chris C apel wrote:
> It's OK for Lisp to be different. But being able to treat certain kind
> of collection as having a minimal, common set of properties makes it
> easy to write functions dealing with just those aspects of what a
> collection /is/. That way collections that don't fit entirely into the
> mold can still be used in some places. It's about separating the
> implementation of the collection from its representation, and letting
> the programmer have a simpler conceptual model of working with it.
Sure, in theory this sounds very nice. I can only see one or two
operations, though, that would benefit from such a generality and that
are currently missing in Common Lisp. The one is a generalized derefence
operation (combining aref, gethash, assoc, getf, and so on), and the
other one I don't remember anymore. ;)
It's trivial to implement these two operations as a generic function.
Just a few lines of code. That's all. The important point here is: Since
you don't need to squeeze such generic functions into a class hierarchy,
you don't have a real problem here. In Java and C#, when you don't have
a method in a class, you basically lose. Not so in Common Lisp (or, for
example, Smalltalk and Objective-C that also allow you to add methods
after the fact).
Note that AspectJ and the likes don't help because you cannot add
methods into the core API, only to your own classes. The same thing
probably also for partial types in C#.
So again, just add the few generic functions that you personally would
like to see in your code and you're done. (Another important lesson that
takes time to grasp is that there is no need to force your own
preferences on others!)
> LOOP may be nice, but the functionality it encapsulates should
> probably be much more orthogonal. Instead of LOOP having an iterator
> for various built-in types, there should be a generic iterator-concept
> (probably a superclass) that can be used by *anything*. There should
> be a collection concept that inherits that (that supports count, and
> copying, as well as iterators). There should be a list concept that
> inherits from the collection that supports indexing, adding, and
> removing.
>
> I'm sorry if I've repeated myself, but I just don't see how lisp
> offers this level of abstraction from the data structures of its
> collections.
Go ahead and try to implement such a collection API. Make sure that it
provides the same functionality that is already offered by Common Lisp's
data structures. I have tried to do that as a Gedankenexperiment in the
past and I have come to the conclusion that a) it's too hard because the
features don't really fit in a hierarchy and b) it's probably not worth
it because there is no real gain here. However, I don't know how to
communicate that experience, so either you have to live through that
same experience or someone else can explain this better than I can. (Of
course, maybe you do come up with a workable solution, and I would be
very happy about such a result.)
>>You seem to be a newcomer to Lisp. There's a transition time in which
>>you expect things to work like they did in other languages. Soon you
>>will expect things to work like they do in Lisp elsewhere. ;)
>
> But until then, I think I need some convincing. Lisp is a much better
> language than C# in general, but there are two are three things about
> the Framework library that I think CL could use. It's nice that CL
> will allow this to be done is a really useful and neat way, but I do
> think it needs to be done. I'm unhappy with Lisp collections. I just
> can't see myself ever seeing the power in the current system.
>
> I think that, while Lisp is a much higher-level language than most
> .NET languages, Lisp collections are lower-level than .NET
> collections. That's the core of my argument. All the primitives are
> there, but they need to be organized, fleshed out, and made more
> consistent.
In my Java past (until about 2.5 years ago) I have tried the JGL (which
I have been told is modeled after the C++ STL library), the Java
Collection API and the C# collection API. JGL was very good, the Java
Collection API ok (and the first example of Sun acting like Microsoft, -
they didn't just adopt the JGL without any good technical reasons), and
the C# collection API was just total shit. If you really take it
seriously to program against interface and not against concrete classes,
the C# design just didn't work because you always had to cast things
around just to get at that particular operation you just need. It may
work well with concrete classes, but then what's the point?
(Of course, this was a very early version of C# and maybe they have
improved the design in the meantime. Or I just didn't get it. I don't
really care anymore...)
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
Christopher C. Stacy
> Vassil Nikolov <vnik...@poboxes.com> wrote in message news:<lzd60gz...@janus.vassil.nikolov.names>...
> > What's wrong with
> >
> > (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
> >
> > to destructively delete the i-th element of v, or
> >
> > (setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
> >
> > for a range?
>
> What's wrong is that you have to have the symbol.
> A collection shouldn't be tied to its symbol.
What symbol are you talking about?
Eric Daniel
>
> I think that, while Lisp is a much higher-level language than most
> .NET languages, Lisp collections are lower-level than .NET
> collections. That's the core of my argument. All the primitives are
> there, but they need to be organized, fleshed out, and made more
> consistent.
Exactly. So why isn't anybody doing it? My guess is that a generic
collection isn't as useful as it seems. Most of the time your specific
tradeoffs will make the use of an array, list, hash table, etc. the
more natural choice. And it really doesn't take long to get familiar
with the Lisp primitives, so by the time someone knows enough Lisp to
write their collection library, they realize that they don't really need
it.
Anyway in case you haven't learned about generic functions yet, here is
how you could implement a generic access-by-index function on an array,
list, and hash table:
(defgeneric by-idx (collection index))
(defmethod by-idx ((collection list) (index number))
(nth index collection))
(defmethod by-idx ((collection vector) (index number))
(aref collection index))
(defmethod by-idx ((collection hash-table) index)
(gethash index collection))
Other operations left as an exercise to the reader :-)
--
Eric Daniel
Arthur Lemmens
>> > What's wrong with
>> > > (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
>> > > to destructively delete the i-th element of v, or
>> > > (setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
>> > > for a range?
>>
>> What's wrong is that you have to have the symbol. A collection shouldn't be tied to its symbol.
>
> What symbol are you talking about?
He probably means the variable V.
Arthur
Chris Capel
> In my Java past (until about 2.5 years ago) I have tried the JGL (which
> I have been told is modeled after the C++ STL library), the Java
> Collection API and the C# collection API. JGL was very good, the Java
> Collection API ok (and the first example of Sun acting like Microsoft, -
> they didn't just adopt the JGL without any good technical reasons), and
> the C# collection API was just total shit. If you really take it
> seriously to program against interface and not against concrete classes,
> the C# design just didn't work because you always had to cast things
> around just to get at that particular operation you just need. It may
> work well with concrete classes, but then what's the point?
Are you talking about the ArrayList indexer returning its members as
"objects"? This doesn't have anything to do with the collection API itself.
It's the staticly typed nature of the langauge. In Lisp, you don't need to
cast things to treat them as having a certain type, so this problem goes
away.
Chris Capel
Peter Seibel
> Peter Seibel wrote:
>
>> And use MAP-INTO to copy the data rather than looping and copying the
>> elements yourself; there's at least a chance the implementation will
>> have implemented MAP-INTO to use bulk copying primitives where
>> possible.
>
> What about REPLACE?
Er, yeah. That's good too. ;-)
-Peter
--
Peter Seibel pe...@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Chris Capel
(defparameter *my-list* (list 1 2 3))
(defun do-something ()
(remove-at 1 *my-list*))
(defun remove-at (index list)
(setq list (delete-if (lambda (ignored) t) list :start index :count 1)))
(do-something)
*my-list* ==> (1 2 3)
Chris Capel
Pascal Costanza
No, I am talking about programming against interfaces which means that I
don't use the ArrayList type directly but some more abstract interface.
That's the recommended practice in those statically typed OO languages,
but it doesn't work in C# becaues the interfaces are too small-grained.
So you keep switching between different interfaces to uncover the
different methods that you actually need. On the other hand, when you
use the ArrayList type directly to circumvent this problem you don't
really take advantage of the class hierarchy.
I don't really remember all the details anymore. As I said, maybe things
have changed or I just didn't get it at that time. But it doesn't really
matter. CLOS centers around generic functions instead of classes and
that's clearly the better approach to OOP in my opinion - the lesser
need to squeeze a collection API into a hierarchy is just one of many
examples that turn out much simpler because of that approach.
Will Hartung
news:69d0f981.04092...@posting.google.com...
> Which serves my point, that Common lisp is built so much around
> non-destructive (immutable object like) semantics that it's sometime
> much more difficult to write any other code. I [often] want my
> collections/arrays/lists to be mutable!
You're confusing things.
Arrays in CL are no different from arrays in pretty much any other language.
Including C#. C#'s arrays work and operate the same way.
There is no reason why you can not construct a collection hierarchy similar
to C# or Java in CL using CLOS. These will be as mutable as you want them to
be, and they'll be just as expensive to use as Collections in C#.
Idiomatically, however, because of built-in Lists, among other things,
typically something like Collections have not been necessary in CL.
In all of my java code, 99% of my use of ArrayList is to collect objects,
and then, later, iterate over them. I pretty much never need to access the
"nth element". Normally, I need to simply access the "next element".
The mechanics of doing this in CL is to either use this idiom with (push
...) and (nreverse ...):
(let ((l (list)))
(dotimes (i 10)
(push i l))
(nreverse l))
(0 1 2 3 4 5 6 7 8 9)
or use LOOP and COLLECT, and let it work out the details.
(loop for i from 0 below 10
collect i)
(0 1 2 3 4 5 6 7 8 9)
Then, to iterate over the list, you have several facilities available: MAP*,
DOLIST, LOOP, etc.
So, the real problem here is not what CL can or cannot do or does or does
not have. The problem is that you're trying to write C# using CL, and this
will cause you endless grief. Because CL is designed to write CL. While with
enough force and pure determination you can make CL have more C# like
facilities, the energy to do so is better and more efficiently spent in
learning the CL constructs and idioms, because with those you won't have to
fight every other construct in CL that doesn't know about the new things you
introduce, or every utility library available.
So, simply put, CL doesn't have a Collections hierarchy like C# because it
simply doesn't need one. It already has these facilities and more, they're
just organized differently, and more organic in their presentation because
they evolved and mutated under the searing pressure of the hot hammers,
keyboards and forges of folks writing enormous bits of software rather than
designed out of whole cloth from a clean slate.
So, again, while CL is more than capable of adopting those C# idioms, it is
probably easier to change the programmer than the language.
Regards,
Will Hartung
(wi...@msoft.com)
Steven E. Harris
> I'm pretty sure that you have to pick between constant time
> extension and constant time access, but you can't have both.
The type std::dequeน in the Standard C++ Library offers both. It's
usually implemented as a vector of blocks. Extension requires no
copying of elements, though the block vector may need occasional
extension, depending on how the vector is stored.
Constant-time access is provided with one extra level of indirection:
the target index is hashed into the block vector (index / block size),
finding the block containing the target element (index % block size).
Footnotes:
น http://www.dinkumware.com/manuals/reader.aspx?b=p/&h=deque.html
--
Steven E. Harris
Steven E. Harris
> Instead of LOOP having an iterator for various built-in types, there
> should be a generic iterator-concept (probably a superclass) that
> can be used by *anything*.
That's one aspect of LOOP that repeatedly surprises and frustrates me:
it imposes a distinction between walking lists and vectors, by way of
the "in" and "across" keywords. It would have been nice if one of
those two (probably "across") accepted a sequence instead.
--
Steven E. Harris
Matthew Danish
> What's wrong is that you have to have the symbol. A collection
> shouldn't be tied to its symbol. A collection should be fully
> available wherever it's available at all--when you pass it around,
> when you change it, no matter where. Without this property a
> collection isn't nearly as useful to me. I believe Adam's function has
> that property. (Thanks, Adam.)
You're confused on a number of points. The so-called ``collection'' is
not ``tied'' to a symbol any more than any other object is. First,
objects are bound to variables, generally, not symbols. Symbols are
used to name variables, but they are not the same thing. Second, the
list does not have to be bound to a variable, it could be bound to a
place; and you use SETF there. Third, this SETF can be macroed away.
Fourth, this ``property'' you are speaking of is an additional level of
indirection which is what the Java/C#/C++/etc libraries do. The mistake
with this view is to consider a list to be a ``collection'' like any
other. A list is not just a bag of objects to be accessed by key; it's
a very specific way of structuring data that has certain properties that
cannot be exploited through a generic ``collection'' interface.
Naturally, some operations can and do operate on the general notion of
sequences; but these operations still must take into account the
different properties of lists.
If you desire a ``list'' data-structure that behaves like an Java
collection, then by all means go ahead and create the extra indirection
for yourself.
Vassil Nikolov
> Chris Capel wrote:
>
>
>> I don't see any function to remove an object based on its index. Is there
>> such a thing for vectors or sequences?
>
> (defun delete-ref (sequence position)
> (let ((marker (load-time-value (make-symbol "MARKER"))))
> (delete marker (progn (setf (elt sequence position) marker)
> sequence))))
...but beware of specialized vectors that cannot hold symbols.
---Vassil.
--
Vassil Nikolov <vnik...@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
Chris Capel
> Pascal Costanza <cost...@web.de> writes:
>
>> Peter Seibel wrote:
>>
>>> And use MAP-INTO to copy the data rather than looping and copying the
>>> elements yourself; there's at least a chance the implementation will
>>> have implemented MAP-INTO to use bulk copying primitives where
>>> possible.
>>
>> What about REPLACE?
>
> It can't be used to delete an element from a sequence, though (which
> is being discussed).
(replace arr1 arr1 :start1 index :start2 (1+ index))
(adjust-array arr1 (1- (length arr1)))
That ought to delete the item at the INDEX position, if I'm reading the
hyperspec correctly.
Chris Capel
Chris Capel
> (adjust-array arr1 (1- (length arr1)))
Or "(vector-pop arr1)", if it has a fill pointer.
Chris Capel
Chris Capel
> So, the real problem here is not what CL can or cannot do or does or does
> not have. The problem is that you're trying to write C# using CL, and this
> will cause you endless grief. Because CL is designed to write CL. While
> with enough force and pure determination you can make CL have more C# like
> facilities, the energy to do so is better and more efficiently spent in
> learning the CL constructs and idioms, because with those you won't have
> to fight every other construct in CL that doesn't know about the new
> things you introduce, or every utility library available.
>
> So, simply put, CL doesn't have a Collections hierarchy like C# because it
> simply doesn't need one. It already has these facilities and more, they're
> just organized differently, and more organic in their presentation because
> they evolved and mutated under the searing pressure of the hot hammers,
> keyboards and forges of folks writing enormous bits of software rather
> than designed out of whole cloth from a clean slate.
Yeah, just like all the wonderful, consistent, orthogonal function names in
the standard, right? I'll give you that CL's sequence facilities are fully
capable. And that they're organic, in that they followed an evolutionary
design, which made them more suited to programs, and programmers, than
something that was designed in a clean-room, like most mainstream
languages' frameworks.
But evolution produces onions--appendices. I don't know enough about CL to
really put my finger on what it is about sequences, in a convincing way at
least, but I believe that the onion's at a pretty low level. It produces
about the same inconvenience as the strange function names in CL. (Can you
tell me what SETF stands for, anyway?) And they're forgotten about as
quickly by people practicing the language--they become reflex, they become
part of the unconscious mind.
That doesn't mean they're good. It just means they're really not worth
changing. It takes the beginner longer to learn them, but the beginner gets
the advantage of being able to read lots of existing code, and writing code
that existing programmers can understand more readily. So it's not worth
changing until you're already ripping out and replacing the guts of the
language anyway (like, say, Arc).
In the meantime, I think there should be a special tutorial that helps the
beginner understand the full breadth of CL's sequnce facilities, and how
they can use CLOS to make manipulating sequences easier. And I think I
should be the one to write it, (unless it already exists, and no one in
this long thread has linked to it...) once I have some more experience, but
before I forget what it is about them that needs explaining.
Chris Capel
Paul F. Dietz
> (Can you tell me what SETF stands for, anyway?)
The 'F' macros apply to places. SETF sets them.
Simple, no?
Paul
Peter Seibel
> In the meantime, I think there should be a special tutorial that
> helps the beginner understand the full breadth of CL's sequnce
> facilities, and how they can use CLOS to make manipulating sequences
> easier. And I think I should be the one to write it, (unless it
> already exists, and no one in this long thread has linked to it...)
> once I have some more experience, but before I forget what it is
> about them that needs explaining.
Before you write your own tutorial, perhaps you could take a look at:
<http://www.gigamonkeys.com/book/collections.html>
and:
<http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html>
and send me some comments about what you like and what you don't like.
Vassil Nikolov
> Vassil Nikolov wrote:
>
>> Pascal Costanza <cost...@web.de> writes:
>>
>>> Peter Seibel wrote:
>>>
>>>> And use MAP-INTO to copy the data rather than looping and copying the
>>>> elements yourself; there's at least a chance the implementation will
>>>> have implemented MAP-INTO to use bulk copying primitives where
>>>> possible.
>>>
>>> What about REPLACE?
>>
>> It can't be used to delete an element from a sequence, though (which
>> is being discussed).
That response of mine was inappropriate---sorry about that, I
cancelled it shortly after posting, but of course cancelling an
article does not really make it disappear...
> (replace arr1 arr1 :start1 index :start2 (1+ index))
> (adjust-array arr1 (1- (length arr1)))
>
> That ought to delete the item at the INDEX position, if I'm reading the
> hyperspec correctly.
(Well, it is still necessary to set ARR1 to the value returned by
ADJUST-ARRAY, besides what you pointed out, that the above is not
suitable for vectors with fill pointers.)
Vassil Nikolov
> [...]
> Can you tell me what SETF stands for, anyway?
I'm probably too dumb not to be able to recognize a rhetorical
question, but... SET Field.
Chris Capel
Oh, I see. Like GETF, INCF, DECF, and PUSHF. Heh. Yeah, section 5.1.1.1.
Chris Capel
Vassil Nikolov
> Hi Vassil Nikolov,
>
>> Adam Warner <use...@consulting.net.nz> writes:
>>
>>> Hi Chris Capel,
>>>
>>>> I don't see any function to remove an object based on its index. Is there
>>>> such a thing for vectors or sequences?
>>>
>>> How's this? (untested)
>>>
>>> (defun delete-range (adj-vec start &optional end)
>>> (let ((len-vec (length adj-vec)))
>>> (unless end (setf end len-vec))
>>> (loop for start-i from end to (1- len-vec)
>>> for new-i from start do
>>> (setf (aref adj-vec new-i) (aref adj-vec start-i)))
>>> (adjust-array adj-vec (- len-vec (- end start)) :fill-pointer t)))
>>
>>
>> What's wrong with
>>
>> (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
>>
>> to destructively delete the i-th element of v, or
>>
>> (setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
>>
>> for a range?
>
> Nice idea. It would suck if DELETE-IF turned out to be a synonym for
> REMOVE-IF (which is conforming by my reading of the HyperSpec).
That would be (at least, roughly speaking) the same case as the
vector not being actually adjustable, in which case the call to
ADJUST-ARRAY in DELETE-RANGE would have to copy the vector, too.
By the way, if DELETE-RANGE has to assume that ADJ-VEC has a fill
pointer, perhaps it can just decrement the fill pointer, instead of
calling ADJUST-ARRAY?
Vassil Nikolov
Well, GETF is not part of this company. There are also SHIFTF,
ROTATEF, etc. (And PUSH does not have a trailing 'F' in the name.)
Marcin 'Qrczak' Kowalczyk
> Chris C apel wrote:
>> What's wrong is that you have to have the symbol. A collection
>> shouldn't be tied to its symbol. A collection should be fully
>> available wherever it's available at all--when you pass it around,
>> when you change it, no matter where. Without this property a
>> collection isn't nearly as useful to me. I believe Adam's function has
>> that property. (Thanks, Adam.)
>
> You're confused on a number of points. The so-called ``collection''
> is not ``tied'' to a symbol any more than any other object is.
It is tied if you treat it as a mutable collection. You can't prepend
an element without changing the variable.
You could embed it in a first-class variable, e.g. in a one-element
structure. Then the structure itself would represent the collection,
it would be independent from the variable it's bound to. But it would
be less convenient because there are no functions which treat such
structure as a whole as a collection - you would have to get & set
its field, or write wrappers for all functions (CL doesn't allow to
extend the set of collection types accepted by standard functions).
> Fourth, this ``property'' you are speaking of is an additional level
> of indirection which is what the Java/C#/C++/etc libraries do.
No. They provide a function "prepend an element in place" wich doesn't
require rebinding the place the collection is stored in. (And other
functions, it's just an example.)
> The mistake with this view is to consider a list to be a
> ``collection'' like any other. A list is not just a bag of objects
> to be accessed by key; it's a very specific way of structuring data
> that has certain properties that cannot be exploited through a
> generic ``collection'' interface.
Well, this is basically the complaint: that the interface of
collections in CL is limited. There is no collection with operation
"prepend an element in place", you have to write your own.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Pascal Bourguignon
> Chris Capel <ch....@iba.nktech.net> writes:
>
> > [...]
> > Can you tell me what SETF stands for, anyway?
>
>
> I'm probably too dumb not to be able to recognize a rhetorical
> question, but... SET Field.
I'd bet on: SET Form
or: SET reFerence
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
mikel
> ch...@ibanktech.net (Chris C apel) writes:
>
>
>>Instead of LOOP having an iterator for various built-in types, there
>>should be a generic iterator-concept (probably a superclass) that
>>can be used by *anything*.
I don't think there is any advantage in involving a class unless you
happen to want to reuse something someone else already wrote. Iteration
is a protocol. If you want to be able to iterate over something, the
right solution is to implement an iteration protocol for it (or to use
an object for which an iteration protocol is implemented).
I think Dylan got this right: there is a defined iteration protocol. Any
object you like may be iterated over, so long as there are methods
specialized for it for each generic function in Dylan's iteration
protocol. It doesn't matter at all what the object inherits from.
Common Lisp's sequence functions predate (and influenced) Dylan's
iteration protocol, and are arguably less elegantly worked-out. But you
could implement the iteration protocol for sequences (and anything else
you like) if that's really something you feel you need.
Pascal Bourguignon
> > The mistake with this view is to consider a list to be a
> > ``collection'' like any other. A list is not just a bag of objects
> > to be accessed by key; it's a very specific way of structuring data
> > that has certain properties that cannot be exploited through a
> > generic ``collection'' interface.
>
> Well, this is basically the complaint: that the interface of
> collections in CL is limited. There is no collection with operation
> "prepend an element in place", you have to write your own.
Well, actually there is no lisp data structure in lisp!
What there is, is pairs. You can use pairs to implement small records
with two fields, trees of various sorts, association lists, double
linked lists, sets, and even lists. Common-Lisp provides some of these
abstractions, you provide the rest.
But given that Common-Lisp does not provide you with a full fleshed
list abstract type, you have to implement it yourself anyway. What I
don't understand, is why people who expect more want to use pairs to
implement lists?
And remember that pairs are used more to build trees (it was invented
to hold the syntactic trees of the programs = s-expressions) than
lists.
Pascal Costanza
Chris Capel wrote:
> Yeah, just like all the wonderful, consistent, orthogonal function names in
> the standard, right? I'll give you that CL's sequence facilities are fully
> capable. And that they're organic, in that they followed an evolutionary
> design, which made them more suited to programs, and programmers, than
> something that was designed in a clean-room, like most mainstream
> languages' frameworks.
This happens in all languages that are actually used in practice. I
don't think there is a way to avoid that. Guy Steele has to say
something about this in his paper "Growing a Language". (Google for it.)
> That doesn't mean they're good. It just means they're really not worth
> changing. It takes the beginner longer to learn them, but the beginner gets
> the advantage of being able to read lots of existing code, and writing code
> that existing programmers can understand more readily. So it's not worth
> changing until you're already ripping out and replacing the guts of the
> language anyway (like, say, Arc).
It's not only about understanding each other, it's also about taking the
notion of reusability seriously. OOP was supposed to solve reusability
issues, but what we get is a new OOP language every few years, and we
basically have to start from scratch again. There are few languages that
are designed in a way that "old" code can actually be reused.
Marcin 'Qrczak' Kowalczyk
> But given that Common-Lisp does not provide you with a full fleshed
> list abstract type, you have to implement it yourself anyway. What I
> don't understand, is why people who expect more want to use pairs to
> implement lists?
They don't insist on using pairs. They want to use lists in the sense
of fully mutable sequences. Preferably without implementing them
themselves from scratch, and without creating yet another API for
collections - CL already has some collection API, it's a pity that
it's non-extensible.
> And remember that pairs are used more to build trees (it was invented
> to hold the syntactic trees of the programs = s-expressions) than
> lists.
They *are* lists. These are pairs used to represent lists used to
represent trees. Well, they usually are - dotted pairs which are not
lists do happen, they are very rare in program source - mostly for
literals.
Alan Crowe
> That's one aspect of LOOP that repeatedly surprises and
> lists and vectors, by way of the "in" and "across"
> keywords. It would have been nice if one of those two
> (probably "across") accepted a sequence instead.
Agreed. It is all the more surprising when you notice that
MAP mixes `in' and `across'
(map 'vector #'list '(a b c) #(1 2 3))
=> #((A 1) (B 2) (C 3))
(map 'list #'vector '(a b c) #(1 2 3) '("1" "2" "3"))
=> (#(A 1 "1") #(B 2 "2") #(C 3 "3"))
(map nil (lambda(&rest x)(format t "~&~{~s ~}" x ))
'(a b c)
#(\1 \2 \3)
(list 'x 'y 'z)
(vector 1 2 3))
A |1| X 1
B |2| Y 2
C |3| Z 3
NIL
MAP-INTO also copes
Alan Crowe
Edinburgh
Scotland
szymon
> [.....]
> (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
(setq v (delete-if (constantly t) v :start i :count 1))
Regards, Szymon.
Will Hartung
"Chris Capel" <ch....@iba.nktech.net> wrote in message
news:10l1q3i...@corp.supernews.com...
> Yeah, just like all the wonderful, consistent, orthogonal function names
in
> the standard, right? I'll give you that CL's sequence facilities are fully
> capable. And that they're organic, in that they followed an evolutionary
> design, which made them more suited to programs, and programmers, than
> something that was designed in a clean-room, like most mainstream
> languages' frameworks.
You also need to appreciate that CL is a language of compromise and
diplomacy. It never had a clean slate to start with. CL is the result of
having competing vendors, implementations, and users locked up in rooms over
several years so they could come to some kind of understanding to defragment
what the overall Lisp language had become. A lot of the stuff in CL is there
for backward compatability to legacy source code. There are structures and
idioms that CL supports that are simply not used at all in modern CL
programming but was routine Back In The Day. This legacy is both a Feature
and a Bug.
> But evolution produces onions--appendices. I don't know enough about CL to
> really put my finger on what it is about sequences, in a convincing way at
> least, but I believe that the onion's at a pretty low level. It produces
> about the same inconvenience as the strange function names in CL. (Can you
> tell me what SETF stands for, anyway?) And they're forgotten about as
> quickly by people practicing the language--they become reflex, they become
> part of the unconscious mind.
And I agree that the apparent arbitrariness of the structures in the
language can be a bit of a hurdle for newcomers. For me, it was LAMBDA. WTH
is LAMBDA? It took the absolutely most basic of Scheme books to get me over
that hurdle, mostly because it didn't really use it until late and used a
different set of functions to do the same thing. I would see LAMBDA and my
mind would just freeze and stop processing. Error. Does not Grok.
But, as you said, now that it's essentially unconscious, I know what it is
and wouldn't dream of using the functions/macros of the book I learned it
from instead of LAMBDA.
> That doesn't mean they're good. It just means they're really not worth
> changing. It takes the beginner longer to learn them, but the beginner
gets
> the advantage of being able to read lots of existing code, and writing
code
> that existing programmers can understand more readily. So it's not worth
> changing until you're already ripping out and replacing the guts of the
> language anyway (like, say, Arc).
The reason it is taking you longer to learn is because of your exposure to
Collection frameworks and your struggle to map them on top of the primitives
that Lisp provides. You're struggling to pound that square peg into the
round hole, and it sort of almost fits in a cockeyed way, but not quite.
You will find that Collections are not that only square peg that you bring
to the Lisp world.
In C#, your Collections are all basicly high level objects, rather than
primitives. Pretty much every language on the planet only has arrays as a
primitive type.
CL has two primitive collections: arrays and lists. It's only "high level"
collection is Hashtable, which some may argue isn't quite high enough level,
but anyway.
Also, since most lanaguages don't have the ability of something like
(vector-push-extend ...), you end up having to implement all but the most
primitive functions into high level objects wrapping the primitive, native
arrays or using a Node structure and dynamic memory for lists.
But CL doesn't have that problem. It's primitives are rich enough that they
provide most everything that a Collection hierarchy provides without being
wrapped in high level objects. Since they're not wrapped, you lost the
entire hierarchy. Rather you have the ad hoc incremental evolutionary
"design" that you see today.
LOOP is a Great Consolidator that helps hide that issue as it works equally
well (if not identicially) on arrays, lists, and hashtables.
Now, in CL, each structure has their own way of accessing elements. But this
is true of Collections as well. While, yes, you CAN use collection.get(n) on
a LinkedList, you don't because it's horrible. But you can't use get(n) on a
Hashtable, you need to use get("n") (or something else). So, all the
Collection hierarchy really gives you is good access to common iteration:
Iterator i = collection.iterator().
But, LOOP basically provides that for you anyway.
No doubt someone got sick of the exact problem you're having, particularly
with multiple ways of iteration, and the result was the LOOP facility. Note,
and this is key, the result of that frustration was NOT a consolidated
Collection hiearchy. Rather, a (very) sophisticated macro that helped shroud
the details of iteration.
In most languages, functions and/or objects are the only means of
abstraction. CL offers macros as well. If, perhaps, CL only had CLOS
available, a Collection hierarchy would have evolved.
And granted, the CL primitives aren't as rich as what can be in a Collection
hierarchy. For example, you can have identically behaving Collections save
that one is synchronized and the other not unsynchronized. But I'd argue
that really less of an issue than it sounds to me. Certainly not a crippling
issue.
> In the meantime, I think there should be a special tutorial that helps the
> beginner understand the full breadth of CL's sequnce facilities, and how
> they can use CLOS to make manipulating sequences easier. And I think I
> should be the one to write it, (unless it already exists, and no one in
> this long thread has linked to it...) once I have some more experience,
but
> before I forget what it is about them that needs explaining.
Truth is, I wouldn't approach it that way. Rounding the corners of your
square peg may seem to make it fit in the hole better, but it really
doesn't. What you'll end up with is gaps around the peg and that shows you
don't fully understand the topic.
I know it is difficult to not bring a peg to the party at all, but,
truthfully, the party is a lot more fun when you leave the pegs at home and
take a step back while trying to learn and adopt CL. Arrays and Lists are
fundamental to CL, and the better you appreciate them in their native forms,
the better you'll be able to leverage CL in general, as well as other folks
code (who have also jumped this hurdle).
Learn how you must, but writing C# in Lisp ends up with both bad C# and bad
Lisp, and will lead to bad habits.
Regards,
Will Hartung
(wi...@msoft.com)
szymon
> LOOP may be nice, but the functionality it encapsulates should
> probably be much more orthogonal. [.............]
If you want orthogonality try SERIES package.
[ http://sourceforge.net/projects/series/ ]
Matthew Danish
generic sequence iteration form is a good question.
--
;;;; Matthew Danish -- user: mrd domain: cmu.edu
;;;; OpenPGP public key: C24B6010 on keyring.debian.org
Kenny Tilton
Paraphrasing my old geometry teacher, there is no room for "usually" in
strict definitions.
Lisp does not have lists, it has nil and cons structures which latter
might or might not consist of cars pointing to a Lisp object and cdrs
pointing only to nil or a similarly populated cons. That is a spec, not
a built-in datatype.
My 2c, anyway.
kenny
--
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
szymon
>
> <http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html>
>
you wrote:
"[...] Finally, the functions MAPC and MAPL are control constructs
disguised as functions--they simply return their first list argument so
they are only useful when the side effects of the mapped function do
something interesting. [...]"
I think you should provide example (maybe examples) here.
my example (too simple?):
CL-USER> (defvar lst (list 1 2 3 4 5))
==> LST
CL-USER> (mapl (lambda (l) (rplaca l (+ 10 (car l)))) lst)
==> (12 13 14 15 16)
CL-USER> lst
==> (12 13 14 15 16)
Regards, Szymon.
szymon
> CL-USER> (defvar lst (list 1 2 3 4 5))
>
> ==> LST
>
> CL-USER> (mapl (lambda (l) (rplaca l (+ 10 (car l)))) lst)
>
> ==> (12 13 14 15 16)
I intend this of course... MAP-INTO is hopeless in this case...
szymon
> I intend this of course... MAP-INTO is hopeless in this case...
Btw, in some (other) cases[*] I'm using MAP-INTO instead of MAPL:
;; ---------------------------------------------------[ too long...
(mapl (lambda (l) (rplaca l (gensym))) (make-list 5))
==> (#:G1496 #:G1497 #:G1498 #:G1499 #:G1500)
;; ---------------------------------------------------[ imho nice...
(map-into (make-list 5) #'gensym)
==> (#:G1501 #:G1502 #:G1503 #:G1504 #:G1505)
Regards, Szymon.
[*] GENSYM, RANDOM, ...
szymon
> Peter Seibel wrote:
>
>>
>>
>> <http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html>
>>
>>
>
> you wrote:
>
> "[...] Finally, the functions MAPC and MAPL are control constructs
> disguised as functions--they simply return their first list argument so
but this list can be changed, see my example.
I'm sorry I should send one post, not 4. *too much* booze... *hick*
Vassil Nikolov
> Vassil Nikolov <vnik...@poboxes.com> writes:
>
>> Chris Capel <ch....@iba.nktech.net> writes:
>>
>> > [...]
>> > Can you tell me what SETF stands for, anyway?
>>
>>
>> I'm probably too dumb not to be able to recognize a rhetorical
>> question, but... SET Field.
>
> I'd bet on: SET Form
> or: SET reFerence
I am fairly sure SET Field was what the name meant when invented,
and SET Form is a latter-day reinterpretation (not sure how
popular).
Unfortunately, I don't have references to original sources (from the
mid-1970s?); here are three (not necessarily a representative
sample) that I found during the time I had to spend searching:
http://groups.google.com/groups?selm=201%40mirror.UUCP
http://groups.google.com/groups?selm=sfwsmt3ya36.fsf%40shell01.TheWorld.com
http://groups.google.com/groups?selm=3092758408130571%40naggum.no
Christopher C. Stacy
> Lisp does not have lists, it has nil and cons structures
That's a very odd thing to say about a language whose name is
an abbreviation for LISt Processing, and I don't get your point.
(I hope the remainder of my reply here is something that others
will find somehow useful; it's written mostly for them.)
If a programming language specification talks about a data type,
includes functional abstractions for dealing with that data type,
and even has a type predicate named for it, I would say that the
language "includes" the data type.
For example, The Common Lisp Hyperspec talks about lists,
and specifically defines "list", "proper list", "improper list",
"dotted list", "circular list", and so on.
Common Lisp includes the following functions that deal with lists:
LIST, LIST*, MAKE-LIST, COPY-LIST, LIST-LENGTH, NTH, NTHCDR, FIRST,
REST, SECOND thru TENTH, LAST, BUTLAST, NBUTLAST, TAILP, ENDP, NCONC,
NRECONC, APPEND, REVAPEND, LDIFF, PUSH, PUSHNEW, POP, and of course
MEMBER, and COPY-ALIST. (To make my point about "lists" being in
the language, I have omitted here the numerous and powerful generic
sequence functions, which work on both lists and vectors.)
In Lisp, a list is a traditional "linked list" structure, consisting
entirely of nodes which are "cons cells". There are no backpointers.
A list does not have any header or other encapsulation - each node
can be viewed as the beginning of a (sub) list.
One thing to watch out for is that the predicate function LISTP
returns T not only for a "proper list", but also for any cons.
LISTP also returns T for NIL, the empty list.
It is only discriminating between cons-or-nil and everything else.
Note that the function CONSP returns false for the empty list.
The building block nodes, "conses", are also used to implement some
other data structures in Lisp (such as "sets"), and you can use them
for any lone or composite "pair" type of structure that you invent.
The language also includes "association lists" (ASSOC, ACONS, PAIRLIS)
"property lists" (GET), trees (COPY-TREE, TREE-EQUAL), and more.
You can also hack conses themselves, using RPLACA and RPLACD.
What might be confusing about the list data type is that its implementation
is exposed as mostly being a conventional use of a more primitive data type,
and that lists need not be "proper" (NIL terminated) in all cases.
I would say that Common Lisp includes several kinds of lists.
One of the often-cited strengths of Lisp is that you can make
decisions about your program design later, rather than sooner.
But you are forced to make certain implementation decisions early on.
Lists can be indexed into, but that's linear time. Vectors have a
"fill pointer" feature that allows them to be dynamically adjusted
(eg. adding a new element) while preserving constant time, but such
arrays doesn't support splicing like lists do. Hash tables also have
iteration, but might not be quite what you had in mind and are maybe
expensive overkill. Lisp does have some "mapping" and "sequence"
functional abstractions that allow you to gloss over the implementation
details of iterating over both (1D) arrays and lists. But you do have
to choose which kind of data structure you had in mind before you can
create the data. There isn't really a generic "collection" data type.
This discussion was started when a C# programmer inquired about generic
collections that allow you to switch representations; he was under the
misapprehension that Lisp programmers generally just used lists to store
things, and then maybe switched to arrays if performance was unacceptable.
But of course, that's not how we do things. Programmers really do have
some early idea of how they will be accessing any given "collection".
If they don't know whether they will need to access the collection
through a key value, whether key is a numeric index or something else,
and whether constant-time is important or not, then I bet things are so
vague in their mind that they will end up re-designing and re-writing
a bunch of code. Such a program is pretty messed up algorithmicaly:
it's not just a matter of changing some data access expressions.
And if you're going through that exercise, Lisp already lets you do
all that same re-writing without having to declare the data type.
In fact, in Lisp, you probably got better feedback sooner about how
confused you were, due to the obvious need to make certain decisions,
and due to the ability to get your experimental/prototype code fragments
running more quickly than in C# or JAVA. So having an unspecified type
of "collection" would not really have been such a helpful idea, after all!
Common Lisp is certainly not a perfect language (although I find it
almost always "better" for most of my purposes), but what this whole
discussion about features reiterates to me is that Lisp has drawn its
lines in different places than languages that have been designed for
mass marketing. Lisp is a good language for beginners to learn _first_,
but it can be harder for programmers coming from most other language
cultures. My other favorite language (well over a quarter century ago,
just before I discovered Lisp) was APL, and the similarities in culture
(clashes) and in communities have always struck me as remarkable.
The "Lisp way" is not obvious to most people, even experienced programmers.
I was a very experienced programmer (in several langauges) when I first
learned Lisp, and it still seemed pretty strange in a number of ways.
I figured out FORTRAN and some others all by myself, but I was lucky
enough to have the best wizards tutor me for my introduction to both
APL and Lisp. Still, I remember writing some thinly veiled FORTRAN
programs with parenthesis, early on. Really understanding Lisp well
enough to seriously appreciate it to the point where one can make
insightful comparisons to other programming languages really takes
a while. Of course, that's what programmers (of all experience levels)
coming from other languages naturally try to do immediately when learning
or investigating Lisp. (It's unfortunately that so many of them on the net
are really annoyingly arrogant in their ignorance. I bet they would behave
better in person, at least to your face.) Anyway, as some of these newer
languages adopt some of Lisp's individual features (such as automatic
storage management), more meaningful comparions become even harder for newbies
to make. Maybe having all those scary parenthesis isn't a bad thing - while
they may bring to mind weird myths that belie the commonalities with other
languages, they also suggest that Something Different May Be Going On Here.
Maybe that gets people to think harder, if they're capable of thinking at all.
Tayssir John Gabbour
> In the meantime, I think there should be a special tutorial that
helps the
> beginner understand the full breadth of CL's sequnce facilities, and
how
> they can use CLOS to make manipulating sequences easier. And I think
I
> should be the one to write it, (unless it already exists, and no one
in
> this long thread has linked to it...) once I have some more
experience, but
> before I forget what it is about them that needs explaining.
You might be interested in looking at the back of Graham's ANSI CL,
which contains a nice little reference for all these operations,
categorized well.
Also, I remember some PHP docs which were wiki-like. Maybe it makes
sense to do this on a wiki, and you or others may make more in-depth
pages on a specific item.
MfG,
Tayssir
Pascal Bourguignon
> Kenny Tilton <kti...@nyc.rr.com> writes:
> > Lisp does not have lists, it has nil and cons structures
>
> That's a very odd thing to say about a language whose name is
> an abbreviation for LISt Processing, and I don't get your point.
> (I hope the remainder of my reply here is something that others
> will find somehow useful; it's written mostly for them.)
Obviously, in my sentence above, "lists" must be understood differently!
I have in mind: THE abstract data type I HAVE IN MIND.
That is: abstract data types in general, and the specific abstrat data
type I want.
The OP had in mind abstract data types too, to wit his note about interfaces:
> [1] Unordered, key can be anything. These are implemented using interfaces
> (like COM or java) on every class that wants to be a collection, including
> basic arrays and such. There's also a "list" interface, which is an ordered
> collection indexable with integers, and about as pervasive as the
> collection interface.
And in his case, the abstract data type he wanted did not map to the
ones provided by Common-Lisp, if at all.
The rest of my post extended the notion that in lisp, the abstract
data type of (cons a b) is not that of a list, but that of a pair, ie,
a record of two fields (T x T). (I use the term PAIR to insist on
that record-of-two-fields aspect of cons cells). And I tried to hint
that you should not hope to have Common-Lisp provide you with more
sophisticated abstract data type when you did not want to restrict you
to what it provides.
> If a programming language specification talks about a data type,
> includes functional abstractions for dealing with that data type,
> and even has a type predicate named for it, I would say that the
> language "includes" the data type.
>
> For example, The Common Lisp Hyperspec talks about lists,
> and specifically defines "list", "proper list", "improper list",
> "dotted list", "circular list", and so on.
>
> Common Lisp includes the following functions that deal with lists:
> LIST, LIST*, MAKE-LIST, COPY-LIST, LIST-LENGTH, NTH, NTHCDR, FIRST,
> REST, SECOND thru TENTH, LAST, BUTLAST, NBUTLAST, TAILP, ENDP, NCONC,
> NRECONC, APPEND, REVAPEND, LDIFF, PUSH, PUSHNEW, POP, and of course
> MEMBER, and COPY-ALIST. (To make my point about "lists" being in
> the language, I have omitted here the numerous and powerful generic
> sequence functions, which work on both lists and vectors.)
>
> In Lisp, a list is a traditional "linked list" structure, consisting
> entirely of nodes which are "cons cells". There are no backpointers.
> A list does not have any header or other encapsulation - each node
> can be viewed as the beginning of a (sub) list.
(defstruct single-linked-list (length 0) (head nil) (tail nil))
(defstruct single-linked-node node (next nil))
(defun prepend (sll item)
(setf (single-linked-list-head sll)
(make-singled-linked-node item (single-linked-list-head sll)))
(when (null (single-linked-list-tail sll))
(setf (single-linked-list-tail sll) (single-linked-list-head sll)))
(incf (single-linked-list-length sll)))
(FIRST (prepend :a (prepend :b (make-single-linked-list))))
--> the proof that FIRST does not deal with list abstract data types.
That is, if what you want is more that what is provided by
Common-Lisp. Here I wanted an abstract data type that consisted of
singled linked lists in which the length, prepending and appending
could be computed in O(1). Since I could not satisfy myself with what
Common-Lisp provides, I could not use what it provides!
Another thing is that by restricting yourself to a given subset of the
Common-Lisp "primitives", YOU are actually building an abstract data
type over the basic PAIR data type of Common-Lisp.
For example, if you DECIDE to use only FIRST, NEXT, ENDP, LENGTH, you
are BUILDING a simple list data type.
If you DECIDE to use only FIRST, NEXT, you are BUILDING a circular
list data type.
If you DECIDE to use CAR, CDR, NULL, COPY-TREE, TREE-EQUAL, you are
BUILDING a binary tree data type.
If you DECIDE to use PUSH, POP, you are BUILDING a stack data type.
If you DECIDE to use FIRST, NEXT, NULL, NCONC, you are building a FIFO
data type.
If you DECIDE to use: INTERSECTION, UNION, MEMBER, PUSHNEW, and NULL,
you are BUILDING a set data type.
Actually, in all these cases, if you start with a given abstract data
type definition, you'll see that Common-Lisp only goes half the way,
and you have to provide a number of custom functions to implement
completely the abstract data type you want.
> One thing to watch out for is that the predicate function LISTP
> returns T not only for a "proper list", but also for any cons.
Yes. This is the proof that LISTP is not a predicate for a list
abstract data type.
> [...]
> I would say that Common Lisp includes several kinds of lists.
No. It includes a PAIR data type, over which other abstract data types
can be built, and for which a certain number of predefined helper
functions are provided by Common-Lisp. But Common-Lisp does not give
you any of THESE abstract data type YOU have in YOUR MIND!
> One of the often-cited strengths of Lisp is that you can make
> decisions about your program design later, rather than sooner.
> But you are forced to make certain implementation decisions early on.
No. It's quite easy to avoid any implementation decision. Just
expression yourself with _interfaces_. That's why abstract data types
are so important. Either you program low-level with what primitive
Common-Lisp provides you and indeed, you are commiting yourself to
these early decisions (you won't be able to AREF (in O(1)) if you've
built your sequence with CONS!), or you program with an interface:
(defun ordered-collection-prepend (oc item) ...)
(defun ordered-collection-nth (oc index) ...)
(defun ordered-collection-append (oc item) ...)
(defun ordered-collection-length (oc) ...)
First, it's easy enough to provide a "prototype" implementation with
the Common-Lisp primitives.
Then, it's easy enough to privde a new implementation following a late
implementation decision.
I should refer you to the first chapters of SICP...
> This discussion was started when a C# programmer inquired about generic
> collections that allow you to switch representations; he was under the
> misapprehension that Lisp programmers generally just used lists to store
> things, and then maybe switched to arrays if performance was unacceptable.
> But of course, that's not how we do things. Programmers really do have
> some early idea of how they will be accessing any given "collection".
> If they don't know whether they will need to access the collection
> through a key value, whether key is a numeric index or something else,
> and whether constant-time is important or not, then I bet things are so
> vague in their mind that they will end up re-designing and re-writing
> a bunch of code. Such a program is pretty messed up algorithmicaly:
> it's not just a matter of changing some data access expressions.
> And if you're going through that exercise, Lisp already lets you do
> all that same re-writing without having to declare the data type.
> In fact, in Lisp, you probably got better feedback sooner about how
> confused you were, due to the obvious need to make certain decisions,
> and due to the ability to get your experimental/prototype code fragments
> running more quickly than in C# or JAVA. So having an unspecified type
> of "collection" would not really have been such a helpful idea, after all!
Indeed, Common-Lisp has a basic sequence abstract data type: COPY-SEQ,
ELT, SUBSEQ, LENGTH, MAP, which is the union of two main data types:
lists and vectors, so you can program some of your algorithms without
early binding to lists or vectors. But this is only a strict minimum.
What if you're unsure of the type of your "indices"? You'd have to
build your own interface allowing you to later decide whether you
implement it with vectors, with hash-table, or with balanced binary
trees.
Just because Common-Lisp provides you with convenient low level
primitives (and much more than most of the other languages!) does not
mean that you don't have to implement your own interfaces and abstract
data types.
On the other hand, the fact that Common-Lisp provides this atomic PAIR
data type, that allow you to consider a data indifferently as a list,
a tree, a graph, a set, or whatever you build with it, allows you to
play tricks that you could not with strictly enforced abstract data
types. If you had to move your elements from one container class to
another, it would be much more inconvenient and much less efficient
than just using the function of your choice from the Common-Lisp
toolbox. But that means that you're not programming with abstract
data types anymore, you're programming in Lisp!
Jon Boone
"Vassil Nikolov" <vnik...@poboxes.com> wrote:
> Pascal Bourguignon <sp...@mouse-potato.com> writes:
>
>> Vassil Nikolov <vnik...@poboxes.com> writes:
>>
>>> Chris Capel <ch....@iba.nktech.net> writes:
>>>
>>>> [...]
>>>> Can you tell me what SETF stands for, anyway?
>>>
>>>
>>> I'm probably too dumb not to be able to recognize a rhetorical
>>> question, but... SET Field.
>>
>> I'd bet on: SET Form
>> or: SET reFerence
>
>
> I am fairly sure SET Field was what the name meant when invented,
> and SET Form is a latter-day reinterpretation (not sure how
> popular).
>
> Unfortunately, I don't have references to original sources (from the
> mid-1970s?); here are three (not necessarily a representative
> sample) that I found during the time I had to spend searching:
>
> http://groups.google.com/groups?selm=201%40mirror.UUCP
> http://groups.google.com/groups?selm=sfwsmt3ya36.fsf%40shell01.TheWorld.com
> http://groups.google.com/groups?selm=3092758408130571%40naggum.no
>
> ---Vassil.
>
PAIP (Norvig) and Lisp (Winston & Horn) both indicate that setf is short for
"set field".
--jon
Christopher C. Stacy
> Obviously, in my sentence above, "lists" must be understood differently!
> I have in mind: THE abstract data type I HAVE IN MIND.
Okay, I understand now. Lisp (the name of the language, how it has
always been defined, the ANSI spec, and everything that's ever been
written about it) is using the word "list" incorrectly. You have some
other meaning of "list" "IN YOUR MIND", and everybody else is wrong.
I am curious, do you think Lisp has a data type called a number?
>
> No. It's quite easy to avoid any implementation decision. Just
> expression yourself with _interfaces_.
As I explained, I don't think that's a very good idea.
> I should refer you to the first chapters of SICP...
I confess I haven't read SICP since the proofreading copy.
Thanks for sharing.
Pascal Bourguignon
> Christopher C. Stacy wrote:
>
> > ch...@ibanktech.net (Chris C apel) writes:
> >
> >> What's wrong is that you have to have the symbol.
> >> A collection shouldn't be tied to its symbol.
> >
> > What symbol are you talking about?
>
> (defparameter *my-list* (list 1 2 3))
>
> (defun do-something ()
> (remove-at 1 *my-list*))
>
> (defun remove-at (index list)
> (setq list (delete-if (lambda (ignored) t) list :start index :count 1)))
>
> (do-something)
>
> *my-list* ==> (1 2 3)
Obviously, because you have a bug in your remove-at!
If you want to consider what Common-Lisp provides you, namely the PAIR
data type (ie. cons cells) as representing your list abstract data
type in which you include such a remove-at operation, you have to keep
that identity! So you must implement remove-at as:
(defun remove-at (index list) ;; note how we write list but we get a cons!
(if (zerop index)
(if (null (cdr list))
(error "YOUR choice of representation cannot bear empty lists!")
(setf (car list) (cadr list)
(cdr list) (cddr list)))
(setf (cdr list) (delete-if (constantly t) (cdr list)
:start (1- index) :count 1)))
list) ;;remove-at
[21]> (progn
(defparameter p (list 1 2 3 4 5))
(print (progn (remove-at 0 p) p))
(print (progn (remove-at 1 p) p))
(print (progn (remove-at 2 p) p)))
(2 3 4 5)
(2 4 5)
(2 4)
(2 4)
[22]>
And don't complain about the empty list. If that was in your
specifications to have both list objects (ie. identity) and empty
lists, you would not try to implement them with cons since:
(consp nil) --> NIL !
I'd propose as a minimum:
(defstruct list-adt (head nil))
(defun l-prepend (list item) (push (item (list-adt-head list))))
(defun l-length (list) (length (list-adt-head list)))
(defun l-elt (list index) (elt (list-adt-head list) index))
(defun l-remove (list item)
(setf (list-adt-head list) (delete item (list-adt-head list))))
(defun l-remove-at (list index)
(setf (list-adt-head list) (delete-if (constantly t) item
:start index :count 1)))
1- of course, instead of a structure you could use a cons for the head.
for example merely changing the structure type:
(defstruct (list-adt (:type list)) (head nil))
2- you will probably want to specify your list abstract data type with
more functionality and optimization. Feel free to add caches fields
to the structure, such as: the length, the tail, the current element
(to allow for cdr and rdc, I mean, next, current and previous), etc.
Common-Lisp is a LOW-LEVEL language! I should propose to the next
standardization commitee to prefix all COMMON-LISP symbols with a %
character...
The question of the OP remains: where are Common-Lisp libraries of
abstract data types?
Christopher C. Stacy
> Chris Capel <ch....@iba.nktech.net> writes:
>
> > Christopher C. Stacy wrote:
> >
> > > ch...@ibanktech.net (Chris C apel) writes:
> > >
> > >> What's wrong is that you have to have the symbol.
> > >> A collection shouldn't be tied to its symbol.
> > >
> > > What symbol are you talking about?
> >
> > (defparameter *my-list* (list 1 2 3))
> >
> > (defun do-something ()
> > (remove-at 1 *my-list*))
> >
> > (defun remove-at (index list)
> > (setq list (delete-if (lambda (ignored) t) list :start index :count 1)))
> >
> > (do-something)
> >
> > *my-list* ==> (1 2 3)
>
> Obviously, because you have a bug in your remove-at!
The attributions are messed up on this message.
Pascal Bourguignon
> Pascal Bourguignon <sp...@mouse-potato.com> writes:
>
> > Obviously, in my sentence above, "lists" must be understood differently!
> > I have in mind: THE abstract data type I HAVE IN MIND.
>
> Okay, I understand now. Lisp (the name of the language, how it has
> always been defined, the ANSI spec, and everything that's ever been
> written about it) is using the word "list" incorrectly. You have some
> other meaning of "list" "IN YOUR MIND", and everybody else is wrong.
> I am curious, do you think Lisp has a data type called a number?
No. You don't understand. When the OP writes about "collections" and
"interfaces", he has in mind _abstract_data_types_.
Any implemented type represent some abstract data type. So you can say
that CONS,CAR,CDR,NULL implement the PAIR abstract data type.
What if what you want is a double-linked list abstract data type?
Well, CONS,CAR,CDR,NULL and no other subset of Common-Lisp implement
the double-linked list abstract data type. So you're on your own, you
have to implement it yourself!
You have the choice of either be content with whatever abstract data
types Common-Lisp provides (what you are doing), or expecting some
more complete or merely some different abstract data type (what the OP
is doing), and then you have to implement it yourself or search for a
library.
> > No. It's quite easy to avoid any implementation decision. Just
> > expression yourself with _interfaces_.
>
> As I explained, I don't think that's a very good idea.
It's a very good and very sound software engineering practice thought.
> > I should refer you to the first chapters of SICP...
>
> I confess I haven't read SICP since the proofreading copy.
>
> Thanks for sharing.
--
Edi Weitz
Judging from the way the lines are colored by Gnus I'd say that the
attributions are correct.
Edi.
--
"Lisp doesn't look any deader than usual to me."
(David Thornley, reply to a question older than most languages)
Real email: (replace (subseq "spam...@agharta.de" 5) "edi")
Alan Crowe
> CL-USER> (defvar lst (list 1 2 3 4 5))
>
> MAP-INTO is hopeless in this case...
Poking about in a dark and dusty corner of the hyper spec
http://www.lispworks.com/reference/HyperSpec/Issues/iss239_w.htm
I tripped over (map-into x #'+ x y) and realised that one can do
* (defvar numbers (list 1 2 3 4 5))
* (map-into numbers (lambda(n)(+ n 10)) numbers)
=> (11 12 13 14 15)
* numbers
=> (11 12 13 14 15)
Enjoy!
Alan Crowe
Edinburgh
Scotland
szymon
> [......] >>MAP-INTO is hopeless in this case... [......]
> * (defvar numbers (list 1 2 3 4 5))
> * (map-into numbers (lambda(n)(+ n 10)) numbers)
> => (11 12 13 14 15)
Eh, stupid me...
> [...] Enjoy! [...]
Thank you.
Regards, Szymon.
Christopher C. Stacy
> On Thu, 23 Sep 2004 09:29:42 GMT, cst...@news.dtpq.com (Christopher C. Stacy) wrote:
>
> > Pascal Bourguignon <sp...@mouse-potato.com> writes:
> >
> >> Chris Capel <ch....@iba.nktech.net> writes:
> >>
> >> > Christopher C. Stacy wrote:
> >> >
> >> > > ch...@ibanktech.net (Chris C apel) writes:
> >> > >
> >> > >> What's wrong is that you have to have the symbol.
> >> > >> A collection shouldn't be tied to its symbol.
> >> > >
> >> > > What symbol are you talking about?
> >> >
> >> > (defparameter *my-list* (list 1 2 3))
> >> >
> >> > (defun do-something ()
> >> > (remove-at 1 *my-list*))
> >> >
> >> > (defun remove-at (index list)
> >> > (setq list (delete-if (lambda (ignored) t) list :start index :count 1)))
> >> >
> >> > (do-something)
> >> >
> >> > *my-list* ==> (1 2 3)
> >>
> >> Obviously, because you have a bug in your remove-at!
> >
> > The attributions are messed up on this message.
>
> Judging from the way the lines are colored by Gnus I'd say that the
> attributions are correct.
Hmmm, I think you're right. I was thinking that the first marker went
with the first person who was marked at that level; but I can see now
that the first person's name is not marked, but they're text is.
(That is, all text is marked, but the toplevel attribution is not).
Do you get different colors for different people or something?
All I get is the first attribution in normal black, and everthing
with a mark in front of it is just red.
Duane Rettig
> Pascal Bourguignon <sp...@mouse-potato.com> writes:
>
> > Obviously, in my sentence above, "lists" must be understood differently!
> > I have in mind: THE abstract data type I HAVE IN MIND.
>
> Okay, I understand now. Lisp (the name of the language, how it has
> always been defined, the ANSI spec, and everything that's ever been
> written about it) is using the word "list" incorrectly. You have some
> other meaning of "list" "IN YOUR MIND", and everybody else is wrong.
I think you're misunderstanding what Pascal is trying to say. I
think I understand, and will attempt to regurgitate it in another
way that might help it to become clear (or it will be clear to
Pascal that I in fact did not understand him, and he can correct
me).
> I am curious, do you think Lisp has a data type called a number?
Actually, in a Pure Lisp with Church numerals, no. But as I
understand it, even Schemes are impure in this respect, for
practical reasons.
But no, in one sense, Lisp does not have a data type called a number.
It is purely an implementation issue, but one which is mandated by
the concepts of the Lisp definition(s). Read on...
In this discussion, I will be talking only about Common Lisp,
since that's the implementation I'm most familiar with, but the
discussion should be applicable to other lisps as well.
I will use the term "abstract type" and "concrete type" to describe
what I mean. For this discussion, a concrete type is a kind of CL
data object which has a type-code associated with it. All CL objects
have a concrete type, and implementations usually have some internal
function to return that typecode [1]. An abstract type is a type
which is built from one or more concrete types. I view a concrete
type as being an abstract type, but this is not necessary; it only
makes the discussion easier for me.
Your question about numbers forms a perfect segue into this issue:
As an example, consider the concrete types "fixnum" and "bignum".
These together form the "exhaustive partition" (CL definition) of
the abstract type "integer". However, there is no CL object that
has an implementational type-code of integer; the type code accessor
for any integer will either return the code for fixnum or for bignum.
There are concrete types for different kinds of floats, as well,
usually single-float and double-float, and the abstract types
short-float and long float are mapped into the concrete types,
respectively. You can add all of the concrete types that make up
numbers, so that you wind up with an abstract type of number,
but no number will have "number" as its concrete type. This is
the sense that there are no numbers in CL; there are fixnums
and bignums and floats etc. which are each numbers, but there
is no object that has the implementational, concrete type of
"number".
Now let's apply this concept to the less obvious case of
lists. There is a concrete type in CL called a "cons", another
concrete type called "null" and an abstract type called "list",
which includes the abstract types "dotted list" and "circular
list", but none of these are concrete types, and the latter two
are not usually considered truly to be types, but to be descriptions
of subsets of the list type. The list type is also described
in terms of cons and null; together, these form an exhaustive
partition of it.
Note also that there is a description of a list type called a
"tree", which basically consists of lists of lists and atoms
at all of the ends, or the more traditional way of looking at
it is as CL defines it: a binary recursive structure made up
of conses and atoms.
To get back to your original question, from which I read a
bit of sarcasm:
> Okay, I understand now. Lisp (the name of the language, how it has
> always been defined, the ANSI spec, and everything that's ever been
> written about it) is using the word "list" incorrectly.
From the way you're describing it, yes, the word "list" is being
used incorrectly. However, note that Lisp does not stand for
"made from lists" or "lists R us", but "list _processing_". A
list doesn't have to be a concrete data type in order to be
useful for processing, as long as it's an abstract type, as
I've defined it here. Thus, I believe that the term Lisp is
perfectly valid, and is just as valid today as the terms "car"
and "cdr" (eve though I know of no modern machines that have
a "decrement register" :-)
Pascal, perhaps you can comment on whether this discussion
goes in the direction you had intended...
[1] type-of is not actually this function; it is somewhat lower
level - the type returned by type-of is an abstract type.
--
Duane Rettig du...@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Christopher C. Stacy
> cst...@news.dtpq.com (Christopher C. Stacy) writes:
>
> > Pascal Bourguignon <sp...@mouse-potato.com> writes:
> >
> > > Obviously, in my sentence above, "lists" must be understood differently!
> > > I have in mind: THE abstract data type I HAVE IN MIND.
> >
> > Okay, I understand now. Lisp (the name of the language, how it has
> > always been defined, the ANSI spec, and everything that's ever been
> > written about it) is using the word "list" incorrectly. You have some
> > other meaning of "list" "IN YOUR MIND", and everybody else is wrong.
> > I am curious, do you think Lisp has a data type called a number?
>
> No. You don't understand. When the OP writes about "collections" and
> "interfaces", he has in mind _abstract_data_types_.
>
> Any implemented type represent some abstract data type. So you can say
> that CONS,CAR,CDR,NULL implement the PAIR abstract data type.
>
> What if what you want is a double-linked list abstract data type?
Then you're not thinking of the normal meaning of the word "list",
and Lispf doesn't have those built-in (but of course you can make
one up). (But a doubly-linked list is no more abstract than an array).
But he wasn't asking for that, he was asking for ".NET ArrayList",
saying that it was a "collection", and suggesting that this is
more abstract than a list. He wrote: "I don't even want a list...
No, no, no. I want a collection of objects. I want an ArrayList.
I want /abstraction/." He then went into detail about what the
ArrayList data type does and what a "collection" is in C#.
Your claim that "Lisp does not have lists" does not follow logically
from that. Meanwhile, I certainly did not claim that "list" was an
"abstract" data type, but rather quite the opposite. I also did not
comment on whether "ArrayList" is a ignificantly more "abstract" data
type than "list", but I strongly implied that I don't think so.
I said that Lisp included lists (as well as arrays and hash tables),
and observed that if the programmer wants to work with those kinds
of data types but does not have any idea whatsoever how he plans to
access his data, he's probably going to have to re-design his program.
I already gave my criteria for whether a language "includes" a given
data type such as "list". If one wants "abstraction", I would not
look to "list", but rather to functional protocols and to CLOS.
Christopher C. Stacy
Let me reiterate, in case that was not clear, that I am talking about
program design above the level of basic building blocks like conses,
lists, arrays, instances, and functions that have the word LIST in
their name. A programmer concerned with "abstraction" ought not to
be concerned with such primitive data types, but rather with the data
in his applicaion domain. If he doesn't have any idea how it's going
to fit together, it's too early to write code using lists or arrays.
My claim is that a "collection" data type is a bad "level of abstraction"
because you actually _are_ writing array indexes, hash values, and lists.
My further claim is that Lisp already facilitates abstraction by allowing
the programmer to experiment with the program design at both "higher" and
"lower" levels than the mish-mashed "collection" so-called "abstraction",
that this will more quickly lead to insights about the nature of the
relationships between the domain data types (and by the way that the
correct "concrete implementation" will be in place sooner).
Christopher C. Stacy
Pascal Bourguignon
> cst...@news.dtpq.com (Christopher C. Stacy) writes:
>
> > Pascal Bourguignon <sp...@mouse-potato.com> writes:
> >
> > > Obviously, in my sentence above, "lists" must be understood differently!
> > > I have in mind: THE abstract data type I HAVE IN MIND.
> >
> > Okay, I understand now. Lisp (the name of the language, how it has
> > always been defined, the ANSI spec, and everything that's ever been
> > written about it) is using the word "list" incorrectly. You have some
> > other meaning of "list" "IN YOUR MIND", and everybody else is wrong.
>
> I think you're misunderstanding what Pascal is trying to say. I
> think I understand, and will attempt to regurgitate it in another
> way that might help it to become clear (or it will be clear to
> Pascal that I in fact did not understand him, and he can correct
> me).
> [...]
> Pascal, perhaps you can comment on whether this discussion
> goes in the direction you had intended...
Yes, you explored correctly some aspects.
Another is that of the interfaces ie. the higher level of abstract
data types.
> Note also that there is a description of a list type called a
> "tree", which basically consists of lists of lists and atoms
> at all of the ends, or the more traditional way of looking at
> it is as CL defines it: a binary recursive structure made up
> of conses and atoms.
There are the simple binary trees that are implemented directly by
Common-Lisp cons cells:
( ( :a . :b ) . :c )
.
/ \
/ \
. :c
/ \
:a :b
But over this concrete (pair) cons type, one can implement a more
complex abstract data type, for example attaching to each node a label
and allowing any number of children:
"root"
|
+-------+---+----+---------+
| | | |
"n1" "l2" "n2" "n3"
| | |
+-----+---+ +--+--+ +--+---+------+------+
| | | | | | | |
"l3" "l4" "l5" "l6" "l7" "l8" "l9" "l10"
which could be implemented as:
("root" . ( ("n1" . ( "l3" "l4" ))
("l2")
("n2" . ( "l5" "l6" ))
("n3" . ( "l7" "l8" "l9" "l10 "))))
ie.:
("root" ("n1" "l3" "l4") ("l2") ("n2" "l5" "l6") ("n3" "l7" "l8" "l9" "l10 "))
.
/ \
/ \
"root" .
/ \
/ \
. .
/ \ ...
/ \
"n1" .
/ \
/ \
"l3" .
/ \
/ \
"l4" NIL
It should be evident already with the above two tree diagrams that
they are DIFFERENT trees! They don't have the same form, not the
same structure. However, the second tree "encodes" or represents the
first, IF you DECIDE on a convention for this encoding.
Common-Lisp does not provide you with functions enforcing these
conventions (there's no function named TREE-LABEL and TREE-CHILDREN).
See also the recently cited:
http://homepages.inf.ed.ac.uk/wadler/steele-oopsla98.pdf
starting from page 10, for a reason why.
For example, I could have DECIDED on another representation:
("root" ( ("n1" ( "l3" "l4" ))
("l2")
("n2" ( "l5" "l6" ))
("n3" ( "l7" "l8" "l9" "l10 "))))
.
/ \
/ \
"root" .
/ \
/ \
. NIL
/ \
/ \
. ...
/ \
/ \
"n1" .
/ \
/ \
. NIL
/ \
/ \
"l3" .
/ \
/ \
"l4" NIL
Et voilà, a third tree, different from the second one, but still
representing the same first tree!
What is important however, is not that Common-Lisp provides us with a
specific, concrete tree type (CONS, CAR, CDR, NIL), but that you want
to implement an abstract tree type with for example the following
interface:
;; abstract data type: node-list
(MAKE-NODE-LIST)
(APPEND-NODE node-list node)
(NODE-LIST-EMPTY-P node-list)
(MAP-NODE-LIST function node-list)
;; abstract data type: labelled, multi-children tree
(MAKE-TREE :LABEL label :CHILDREN children-list)
(TREE-LABEL tree)
(TREE-CHILDREN tree)
In my first representation above (the second tree), I would implement
TREE-LABEL with CAR and TREE-CHILDREN with CDR, while if I choosed the
second representation, I would implement TREE-LABEL with FIRST and
TREE-CHILDREN with SECOND.
SECOND, THIRD, ... are already an abstraction (provided by
Common-Lisp) over the underlying representation CAR/CDR,
(SECOND x) == (CAR (CDR x)).
See Chapter 2 "Building Abstractions with Data" of SICP:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-13.html#%_chap_2
------------------------------------------------------------------------
The following diagrams are drawn with the CDR cell on the left and the
CAR cell on the right to limit the width (since the trees are wider
than deep).
( ( :a . :b ) . :c )
+--------------------------------+
| +---+---+ |
| |CDR|CAR| |
| +---+---+ |
| |
| +---+---+ +---+---+ +----+ |
| | * | * |-->| * | * |-->| :A | |
| +---+---+ +---+---+ +----+ |
| | | |
| v v |
| +----+ +----+ |
| | :C | | :B | |
| +----+ +----+ |
+--------------------------------+
("root" . ( ("n1" . ( "l3" "l4" ))
("l2")
("n2" . ( "l5" "l6" ))
("n3" . ( "l7" "l8" "l9" "l10 "))))
+------------------------------------+
| +---+---+ |
| |CDR|CAR| |
| +---+---+ |
| |
| +---+---+ +--------+ |
| | * | * |-->| "root" | |
| +---+---+ +--------+ |
| | |
| v |
| +---+---+ +---+---+ +------+ |
| | * | * |-->| * | * |-->| "n1" | |
| +---+---+ +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +------+ |
| | | * | * |-->| "l3" | |
| | +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +------+ |
| | |NIL| * |-->| "l4" | |
| | +---+---+ +------+ |
| v |
| +---+---+ +---+---+ +------+ |
| | * | * |-->|NIL| * |-->| "l2" | |
| +---+---+ +---+---+ +------+ |
| | |
| v |
| +---+---+ +---+---+ +------+ |
| | * | * |-->| * | * |-->| "n2" | |
| +---+---+ +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +------+ |
| | | * | * |-->| "l5" | |
| | +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +------+ |
| | |NIL| * |-->| "l6" | |
| | +---+---+ +------+ |
| v |
| +---+---+ +---+---+ +------+ |
| |NIL| * |-->| * | * |-->| "n3" | |
| +---+---+ +---+---+ +------+ |
| | |
| v |
| +---+---+ +------+ |
| | * | * |-->| "l7" | |
| +---+---+ +------+ |
| | |
| v |
| +---+---+ +------+ |
| | * | * |-->| "l8" | |
| +---+---+ +------+ |
| | |
| v |
| +---+---+ +------+ |
| | * | * |-->| "l9" | |
| +---+---+ +------+ |
| | |
| v |
| +---+---+ +--------+ |
| |NIL| * |-->| "l10 " | |
| +---+---+ +--------+ |
+------------------------------------+
("root" ( ("n1" ( "l3" "l4" ))
("l2")
("n2" ( "l5" "l6" ))
("n3" ( "l7" "l8" "l9" "l10 "))))
+------------------------------------------------------------+
| +---+---+ |
| |CDR|CAR| |
| +---+---+ |
| |
| +---+---+ +--------+ |
| | * | * |-->| "root" | |
| +---+---+ +--------+ |
| | |
| v |
| +---+---+ +---+---+ +---+---+ +------+ |
| |NIL| * |-->| * | * |-->| * | * |-->| "n1" | |
| +---+---+ +---+---+ +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +---+---+ +------+ |
| | |NIL| * |-->| * | * |-->| "l3" | |
| | +---+---+ +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +------+ |
| | |NIL| * |-->| "l4" | |
| | +---+---+ +------+ |
| v |
| +---+---+ +---+---+ +------+ |
| | * | * |-->|NIL| * |-->| "l2" | |
| +---+---+ +---+---+ +------+ |
| | |
| v |
| +---+---+ +---+---+ +------+ |
| | * | * |-->| * | * |-->| "n2" | |
| +---+---+ +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +---+---+ +------+ |
| | |NIL| * |-->| * | * |-->| "l5" | |
| | +---+---+ +---+---+ +------+ |
| | | |
| | v |
| | +---+---+ +------+ |
| | |NIL| * |-->| "l6" | |
| | +---+---+ +------+ |
| v |
| +---+---+ +---+---+ +------+ |
| |NIL| * |-->| * | * |-->| "n3" | |
| +---+---+ +---+---+ +------+ |
| | |
| v |
| +---+---+ +---+---+ +------+ |
| |NIL| * |-->| * | * |-->| "l7" | |
| +---+---+ +---+---+ +------+ |
| | |
| v |
| +---+---+ +------+ |
| | * | * |-->| "l8" | |
| +---+---+ +------+ |
| | |
| v |
| +---+---+ +------+ |
| | * | * |-->| "l9" | |
| +---+---+ +------+ |
| | |
| v |
| +---+---+ +--------+ |
| |NIL| * |-->| "l10 " | |
| +---+---+ +--------+ |
+------------------------------------------------------------+
Edi Weitz
> Do you get different colors for different people or something?
Yep. This is Gnus 5.10.6 from Debian and I've enabled font-lock
globally.
Want another screen shot?
<http://zappa.agharta.de/gnus.png>
Edi
Tayssir John Gabbour
> Chris Capel <ch....@iba.nktech.net> writes:
> > I hear a lot that in Lisp, you should use lists, and then switch to
arrays
> > when you need performance.
>
> You should use lists when lists are the natural way to represent the
> data in question. You should use arrays when arrays are the natural
> way to represent the data in question.
I've also found that a little COERCE goes a long way.
MfG,
Tayssir
jayessay
> In Lisp, you don't need to cast things to treat them as having a
> certain type, so this problem goes away.
Presumably you mean "cast objects" (data, values, ...). You can't
cast these since values carry their type with them and consequently
you also can't treat them as having another type. Don't confuse this
with type/subtype behavior.
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
Eduardo Muñoz
* Edi Weitz <spam...@agharta.de>
| On Thu, 23 Sep 2004 15:48:55 GMT, cst...@news.dtpq.com (Christopher C. Stacy) wrote:
|
| > Do you get different colors for different people or something?
|
| Yep. This is Gnus 5.10.6 from Debian and I've enabled font-lock
| globally.
|
| Want another screen shot?
|
| <http://zappa.agharta.de/gnus.png>
Yet another?. This one with a black background and a nicer
(IMHO) summary line format.
http://213.97.131.125/images/Gnus-colors.png
--
Eduardo Muñoz | (prog () 10 (print "Hello world!")
http://213.97.131.125/ | 20 (go 10))
Johan Bockgård
> Yet another?. This one with a black background and a nicer (IMHO)
> summary line format.
Ok, here's mine:
http://www.dd.chalmers.se/~bojohan/emacs/img/gnus/summary.png
--
Johan Bockgård
Bulent Murtezaoglu
[...]
EM> http://213.97.131.125/images/Gnus-colors.png
That font looks nice, what is it? (Actually the colors look good too,
could we have the incantation for .emacs?).
cheers,
BM
Eduardo Muñoz
* Bulent Murtezaoglu <b...@acm.org>
The font is Bitstream Vera (google will help). The next bit
makes emacs use the font once installed.
(set-default-font "-*-Bitstream Vera Sans Mono-normal-r-*-*-13-97-96-96-c-80-iso8859-1")
The colors settings can be found at http://213.97.131.125/misc/gnus
gnus-summary-line-format and face definitions at the end of
the page.
Since we are already fairly off topic feel free to mail me
further questions.
Jeremiah Bullfrog
> Adam Warner wrote:
>
>> Hi Chris Capel,
>>
>>> Coming from a C# background, one thing I've begun to miss in lisp is a
>>> nice, flexible array/collection feature. Let me describe the .NET
>>> ArrayList class.
>>>
>>> It's built over a fixed-length array that's reallocated and copied when
>>> you add elements over the maximum length.
> ..
> Although I'm curious--is there a constant time algorithm for this sort of
> thing? /Primae facie/, it seems impossible.
It's possible in /amortized/ constant time. Every time you extend
the array you extend it by a fixed factor; 100%, 50%, your choice.
Say you extend it by 100% each time, the total amount of time
you've spent in getting it to some size is: n + n/2 + n/4 + ... 1,
(the sum of the copying operations you've made) ie
2n total time -> O(n). Other percentages give you bigger constants,
but still O(n).
Rahul Jain
> Paul F. Dietz wrote:
>
>> The 'F' macros apply to places. SETF sets them.
>>
>> Simple, no?
>
> Oh, I see. Like GETF, INCF, DECF, and PUSHF. Heh. Yeah, section 5.1.1.1.
There is also a meta-level interface for these operations (so you can
define your own macros or types of places):
DEFUN (SETF ...) - for straightforward accesses
DEFMETHOD (SETF ...) - to do OO dispatch on the data types involved
DEFSETF - for when you need some basic macro functionality
DEFINE-SETF-EXPANDER - when you want to get really fancy (e.g., caching
exact location after a search for the real place to be set)
DEFINE-MODIFY-MACRO - give it an operation and it'll create a modifier
macro. e.g., INCF could be defined by
(define-modify-macro incf (&optional (delta 1)) +)
GET-SETF-EXPANSION - for use in your modify macros when you need more complex
functionality
--
Rahul Jain
rj...@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain
> Will, you mean MAP, not LOOP. The reason why LOOP doesn't have a
> generic sequence iteration form is a good question.
It's ok, we have SERIES for that. ;)
Rahul Jain
> Common Lisp's sequence functions predate (and influenced) Dylan's
> iteration protocol, and are arguably less elegantly worked-out. But you
> could implement the iteration protocol for sequences (and anything else
> you like) if that's really something you feel you need.
AFAICT, this is what SERIES is supposed to be.