Re: [Ocaml-lib-devel] Dllist

[Brian H. <bh...@sp...>]

On Sun, 29 May 2005, John Skaller wrote:

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

That's what I meant.  I prefer to optimize for human use over computer 
use.  And I don't sweat squezing every last cycle out of my code.  If I 
did, I'd be writting in assembler, or C at the most, not Ocaml.

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

No, there is a dispute on goals.  Easy for humans to use, or easy for 
computers to use?  Or to put it a different way:

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

Yep.  And I'm down on the richer and more immediately usefull side.

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

And if the library was written in Ocaml, it can be rewritten in Ocaml as 
well.  I've yet to see a library in extlib that'd take me more than a day 
to recreate, worst case.  And if I'm recreating the library for a special 
purpose, often times it takes less time than that, as I only recreate 
those functions I actually need.  Hell, I wrote the central data structure 
definitions and two core functions as throw-aways into an email.

>
> ExtLib is positioned as a replacement system library.

I'm more of the Java school of system libraries than the C school.

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

Define valid.  By one definition, in the above example all lists are 
always valid too.  Having no elements does not mean the list is invalid.

If you mean that some other code somewhere can get confused because list B 
changed- that can happen in both implementations.

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

Yes it does, it's just hidden behind the introduced complexity.  In 
appending B to A, you've changed list B.  In my implementation, you empty 
B.  In your implementation, you've appended list A to list B.  In both 
cases, you have still changed list B.

Worse yet, now changes to list B also change list A.  By the act of 
appending the two lists, I've created an identity that didn't exist 
before.

We can argue til the cows come home which behavior is better- but you 
can't pretend that the node-based implementation doesn't have side-effect 
problems.

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

Yep.  And these decisions need to be made no matter what basic design we 
go with.  And they should be consistent, and they should be documented.

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

Yep.  On the other hand, if you want coherence, you should probably be 
using an applicative data structure.  For imperitive data structures, I'd 
be inclined to be maximally destructive, because it's likely the 
destructive variation is what is wanted.

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

And my point is that if I have to write a wrapper library, I won't use the 
base library because reimplementing it isn't that hard.

Brian