Various Topics on Lisp

..r.. ..p..

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 cl***.

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 cl*** 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 cl*** 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.

.... ..rn..

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 cl***.
>
> 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

..r.. ..p..

Adam Warner wrote:

>> 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

.... ..rn..

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 cl***.
>
> 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 cl*** 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

..r.. ..p..

Adam Warner wrote:

>>, 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

..r.. ..p..

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 cl***.
>>
>> 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 cl*** 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.

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 cl*** 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

.... ..rn..

Hi Chris Capel,

> Adam Warner wrote:
>
>>> 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!

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

..t.. ..ib..

Adam Warner <usenet@consulting.net.nz> writes:

> Hi Chris Capel,
>
>> Adam Warner wrote:
>>
>>>> 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!
>
> 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.

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 peter@javamonkey.com

Lisp is the red pill. -- John Fraser, comp.lang.lisp

..r.. ..p..

Adam Warner wrote:

> 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 ***umed 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 cl*** 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

.... ..rn..

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)))

Regards,
Adam