NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/object/2955

Internet Message Format | 1992-07-21 | 5.9 KB

Xref: sparky comp.object:2955 comp.lang.eiffel:974
Newsgroups: comp.object,comp.lang.eiffel
Path: sparky!uunet!tcsi.com!iat.holonet.net!uupsi!psinntp!bony1!richieb
From: [e-mail] (Richard Bielak)
Subject: Re: How to design a data structure library.
Message-ID: <[e-mail]>
Organization: lost in NYC
References: <1820@snap>
Date: Tue, 21 Jul 92 12:42:56 GMT
Lines: 174

In article <1820@snap> [e-mail]-mrc (Paul Johnson) writes:

[...]

>Cursors
>-------
>
>The ISE library has the notion of a cursor within the object being
>traversed.  Hence to traverse a list you put the cursor to the
>beginning of the list and then at every step you move it forwards.
>The code looks something like this:
>
>    from list.start; until list.offright loop
>        list.item.foo;
>        list.forth;
>    end; -- loop
>
>In the Sig library, the cursors (called iterators) are separate from
>the objects, so you have something like this:
>
>    from locn := list.iterator; until locn.finished loop
>        list.item (locn).foo;
>        locn.forth;
>    end; -- loop
>
>The ISE system has the disadvantage that multiple iterations over a
>list are difficult to do.  In particular, an interleaved iteration
>involving two cursors at different points in the list can be very
>tricky.

I think that cursors should be separate from the data structure they
are used to traverse. The main reason is to allow multiple iterations
over the same list. The scheme present in the ISE library (with "mark"
and "return") works OK within a single program. It fails, when the
data structured is shared - either through a database or concurrent
process.

With shared data structures the cursor can also specify the kind of
lock (i.e. read or write) to take out on the elements being looked at.

>
>RISC vs CISC
>------------
>
>The ISE data structure classes have large numbers of features.  Many
>of these provide efficient short cuts.  For instance there is a list
>merge facility which removes items from one list and inserts them into
>another.  The ISE linked list implementation allows this to be done
>with a little internal pointer shuffling.  Other features are rarely
>used and do not offer efficiency short-cuts.  For instance, the
>`remove_all' procedure scans the list and removes all items which are
>equal to the argument.  This could be done just as quicly by an
>explicit loop.
>
>Inheriting from the ISE list classes can be a trial.  In order to
>provide a true subtype, one has to implement a large number of
>features, many of which are of doubtful utility and others for which
>there are no clear semantics or implementation.
>
>The SIG design has none of this.  The data structure features provide
>a bare minimum of functionality.  This makes the documentation simpler
>to use, but some tasks are less efficient than they might be.
>

I would prefer RISC. I think it was Jim McKim, who said that the
features of a class should form a "minimum spanning" set - that is
just enough to be complete, but not more.

I've implemented a persistent list class, which did _not_ inherit from
LIST. The main reason was that LIST has too many things that I did not
want to implement for persistent lists (eg. "mark", "return",
"index_of", "duplicate).


>
>Functional vs Procedural
>------------------------

[...]
>
>Things become worse when considering large objects.  The ISE SET class
>provides `intersect', `merge' and `subtract' procedures.  Hence the
>only way to create a new set `c' which is the union of two existing
>sets `a' and `b' is:
>
>    c.Clone (a);
>    c.merge (b);
>
>With some kinds of objects, this would be rather less efficient than
>
>    c := a + b;
>
>On the other hand providing operators `*' and `+' for intersection and
>union would result in something like:
>
>    a := a + b;
>
>This creates a new (and fairly large) object before throwing away the
>old value of `a'.  If this is implemented as a linked list then you
>could have a huge amount of garbage being generated.
>
>Does it make sense to implement both kinds of operations in a class,
>so that the programmer can pick the appropriate one?
>


I suppose one should implement only the more fundamental set of
operations, and then let the descendant create the "+" or "*"
operators if desired. This goes back to the "minimal spanning set"
idea.



>Documentation
>-------------
>
>What should go into the documentation of a cluster?

Good question. There should be a general description of what the
classes are doing. For example, the description of data structure
cluster should talks about cursors.

>What should be in the documentation of each individual class?

At least "flat class | short" :-)

>Do we need discussion of time and space complexity?  At what level of
>detail?

I think so. Sometimes a simple guideline on how to use a class
efficiently would suffice.

>Do we also need an outline of the implementation method?  At what
>level of detail?

This is probably not needed, as long as the source code is available.


>Is the short-flat version of a class useful? (Sig appear to think
>not).

It's essential.

>Do we need a separate section: "Guide to Writing Descendants"?

I think so. I'm in process of writing docs for a database cluster, and
large part of the doc will be on that topic.

What would be useful is a "short-for-descendants". An extract of a
class that contains the signatures of all the features, without the
code.

>What sort of examples are needed?

At least an example of typical use. Perhaps some examples that
illustrate the difference between efficient and inefficient use of the
library.


>Are inheritance graphs useful?
>

I don't find these particularly useful, although they are pretty to
look at.



...richie

--
* Richie Bielak   (212)-815-3072   | "Your brain is a liquid-cooled parallel  *
* Internet:       [e-mail] | super-computer". He pointed to his nose, *
* Bang {uupsi,uunet}!bony1!richieb | "This is the fan."                       *
*    - Strictly my opinions -      |                     - David Chudnovsky - *