Re: [Ocaml-lib-devel] Dllist

[John S. <sk...@us...>]

On Sat, 2005-05-28 at 15:39 -0500, Brian Hurt wrote:
> 
> On Sun, 29 May 2005, John Skaller wrote:
> 
> > Well my view is that a *base* library provides simple
> > efficient things -- it is oriented to the computer NOT the user.
> 
> This is where you and I part company.  

OK.

> Computer cycles are cheap compared 
> to human cycles.

We don't part company on that statement however.

There is actually reason for orienting the library
components to what is simple for the machine,
as well as plenty of experience that it is a good idea,
precisely to make subsequent human use simple.

So there is no dispute on goals, merely on how to
achieve them. 

The bottom line is that library design is difficult.
It is always hard to choose between a lean, simple,
efficient code, and a richer and more immediately
useful one.

In my opinion .. and it is only that .. programming language
standard libraries should not pre-empt the building of
the richer, easier to use but more application specific
style of library -- they should instead wrap up only
low level concepts.

ExtLib is positioned as a replacement system library.

> > The problem with doing that is that you can't so easily
> > chop bits of the list up, or splice bits of a list together.
> 
> Yep.  This is a problem with imperitive data structures.
> 
> >
> > For example, consider two lists A and B, and you join them
> > to create a list C. What happens to A and B?
> 
> A and B are now invalid lists.  Unless A is C.

With the container design. But this doesn't happen with the
nodes only design. That's the point -- all lists are always
valid at all times.

> Note that you can leave A and B in valid states.  

Yes, you can in this case, the issue isn't if they're
valid, but what they *should* represent. That issue
doesn't arise with the nodes only design.

> Conceptually, all the elements of B are removed from it an appended to A.
> 
> Yes, it's a destructive operation.  So?  Welcome to the imperitive world.

No, the 'so' is that 

(a) arbitrary decisions have to be made,
this is not the case for append (its clear you're emptying list B
when you append it to A), but some other cut and paste operations
leave one wondering which lists contain what, and 

(b) maintaining coherence turns out to be very expensive.

The point is that you can construct a 'container' design
from a 'nodes-only' design with a wrapper, but not the
other way around, so the nodes-only design is the right
one to implement in a low level library by Occams razor.

Note that I am NOT saying this is any kind of proof the
right choice was made -- I'm just saying there is a rational
basis for *both* choices. In fact, I'll bet there exist
more than just these two designs ..

Also, I can't contribute any experience with the particular
implementation in Extlib, because I don't use it.

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net