Various Topics on Lisp

..sc.. ..stan..

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?


Pascal

--
Pascal Costanza University of Bonn
mailto:costanza@web.de Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)

.... ..ni..

In article <pan.2004.09.21.06.17.45.20352@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.

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

.... ..rn..

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

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

..e ..rsha..

Chris Capel <ch.ris@iba.nktech.net> writes:

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

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

No, a number of dim people share this opinion.

..r.. .. ....

V***il Nikolov <vnikolov@poboxes.com> wrote in message news:<lzd60gz11h.fsf@j****.v***il.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. A collection should be fully
available wherever it's available at all--when you p*** 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

..r.. .. ....

Adam Warner <usenet@consulting.net.nz> wrote in message news:<pan.2004.09.21.04.46.05.243204@consulting.ne t.nz>...
> Hi Chris Capel,
>
> > 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

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

..rc.. ..rcza.. ..walcz..

chris@ibanktech.net (Chris C apel) writes:

> 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
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

..r.. .. ....

Pascal Costanza <costanza@web.de> wrote in message news:<cioigc$q96$1@f1node01.rhrz.uni-bonn.de>...
> 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 cl*** 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
> cl***es. 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 supercl***) 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

..a.. ..tt..

Eric Daniel <eric-usenet@barberic.org> writes:

> In article <pan.2004.09.21.06.17.45.20352@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 duane@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

..sc.. ..stan..

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, ***oc, 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 cl*** hierarchy,
you don't have a real problem here. In Java and C#, when you don't have
a method in a cl***, 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 cl***es. 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 supercl***) 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 ****. If you really take it
seriously to program against interface and not against concrete cl***es,
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 cl***es, 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."