Re: ADT List (2)

[Peter Froehlich <pfroehli@ics.uci.edu>]

Hi!

At 9:48 PM +0200 6/2/98, Tim Teulings wrote:

>That's ok for me. I also want to announce that I'll be away on holiday
>from saturday this week to friday next week. So dont be suprised when
>I suddenly stop argumenting ;-)

   Hey! Have a nive holiday! :-)

>> What would we gain with this approach?  Obviously, it is very
>
>I also asked for this.

   I was not arguing that we "gain" anything in particular. I was just
making a point that the original statement by Michael was wrong: You can
have "method based constructors" with extensible parameterlists. He claimed
you can not.

>These fields are special to this special implementation of a list (one
>could implement a gap list or a list using nodes of short arrays...).
>So you can export them, the user can use them but he must be aware that
>he cannot exchange the implementation on the fly a sa result.

   Okay, from this point of view I have to agree. However I thought we were
arguing design policies in general. And the *general* list container class
should not export these things. It should only provide an interface that
all other list classes must adhere to.

>> provided by the ADT implementation itself.  For convenience and
>> efficiency.  That is, we don't need a minimal set of procedures, but a
>> minimal _convenient_ set.
>
>That is my understanding of "confortable", too.

   Okay, okay! Of course I was not arguing for a "theoretically sound
minimal interface" but for a "usable/convinient but not bloated/fat
interface".

>> You should provide some information how these iterators of yours are
>
>I'll give a statement on iterator later, too...

   Well the basic Iterator design is quite straightforward: You provide
something like

   IteratorDesc = RECORD
     PROCEDURE (self: Iterator) Current (): Object;
     PROCEDURE (self: Iterator) More (): BOOLEAN;
     PROCEDURE (self: Iterator) Next ();
   END;

as an abstract base class somewhere (StdTypes comes to mind but maybe this
is getting to large already). You should describe the behaviour of each
method there (eg. that Next () does not guarantee any order by default,
what the behaviour on an empty container is, etc.).

   A particular implementation of a container then also implements a
derived Iterator and returns a new instance of this from it's NewIterator()
method. Of course, it also connects the iterator to the container.

   Note that it should be a matter of the container to decide if it
supports multiple iterators. Whether the policy of what happens on deletes
should be defined by each container or if we should provide a general rule
still remains to be discussed.

>If Stack uses List as its implementation it must not inherit but List
>must be a private member and Stack should delegate all its calls to
>List. This gives us another principal question. Should it be allowed
>for the library to reuse other datatypes (like Stack uses List) or
>should every datatype be implemented "native". The first one reduces
>code bloat and minimizes bugs my reusing proofed code the later one
>maybe more speed optimized.

   I don't think that implementing everything over again is a good policy
to require in general. I would defer that decision to the author of a
particular container, he can then present his analyssi of the tradeoffs in
the documentation for his "product". :-)

>Ok. As a result of my own implementation I would state that some base
>classes are usefull while others are not. Exspecially good was the
>introduction of a Comparable Object, that implements comparisons, I
>would sugest to implement this again. I would also suggest to implement
>the evaluation of a hashvalue (LONGINT) somewhere in the baseclass.
>This way you can heasily hash any objects not only string. hashtables
>get simpler.

   While this seems to be easy enough, it raises a number of complicated
design problems in a language such as Oberon. For instance, where should
the methods for those different things really be put? If you have classes
Object, Comparable, Hashable, and Container, how are these related? Is a
Container a Comparable or a Hashable? If you collapse the methods into
object, suddenly all objects become comparable, which might not be what you
want. The possibilities are nearly endless.

   As an aside, Lagoona solves many of these issues very elegantly through
the use of categories. :-)

>However not all collections inherting from Collectable were able to
>implement this methods correct (Note, a hashtable needs two objects -
>a key and a value - for adding).

   No, a *hashtable* is just that: A table into which you hash things. You
are thinking of a dictionary that is *implemented* using a hashtable. Note
that this difference is important! Java just got it wrong when they say
that "Hashtable" IS-A "Dictionary". Note that this separation of
"abstraction" versus "data structure" versus "implementation" was part of
my original ADT mail a while back. It still remains to be solved. Maybe it
is a research issue? :-)

By(T)e...        /  Department of Information and Computer Science  \
        Peter... \ University of California - Irvine, CA 92697-3425 /