Re: ADT List

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

Hi all!

At 7:20 PM +0200 6/1/98, Michael van Acken wrote:

>I want to coordinate the development of some basic ADTs, starting with
>the list class brought up by MKG.  The general framework is, as he
>described it, the "single root model".

   Good that someone as starting to push things a little bit.  Congrats
regarding your quick promotion! :-)

>Please keep in mind, that this module is intended as a
>role model for a whole family of ADT implementations.  Any faults that
>we make here will make us unhappy further on.

   Only too true. That's why I am going to shred it... :-)

>Right now I ONLY want
>to see comments that apply to this module, its general design, or its
>base classes.  Also, comments should be as precise as possible,
>preferably accompanied by a piece of pseudo code.

   Well, we'll see... :-)

>Naming of entities in the module is open for discussion.

   I suggest sticking to established "Oberon conventions" as documented eg.
in Moessenboeck's Oberon-2 book. No need to deviate from my point of view.

>Because other ADTs may need further procedure arguments, `Init' and
>`New' are implemented as normal procedures.  If they would be a
>type-bound procedures, we would be forced to have parameterless `Init'
>and `New' for all out ADTs.

   Not true. There is an alternative for simulating "well-behaved"
constructors in Oberon-2 but it does come at a price: the same price as
message passing as used for the GUI parts of the Oberon System.

   MODULE StdTypes

     TYPE
       Initializer* = RECORD (* some generic data, I don't know *)

     PROCEDURE (self: Object) Initialize (init: Initializer);
     BEGIN (* Abstract? *)
     END Initialize;

   MODULE Hashtables

     IMPORT ST := StdTypes;

     TYPE
       Hashtable* = POINTER TO HashtableDesc;
       HashtableDesc* = RECORD (ST.Object) (* or maybe a Container base
type? *)
         data: POINTER TO ARRAY OF Object;
         (* other stuff here *)
       END;

       Initializer* = RECORD (ST.Initializer) size*: INTEGER; END;

     PROCEDURE (self: Hashtable) Initialize (init: ST.Initializer);
     BEGIN
       WITH init: Initializer DO
         NEW (self.data, NextPrime (init.size));
         (* ... *)
       END;
     END Initialize;

I used this approach quite successfully in my old "Nice Class Library"
project which sadly got shelved. If I had the sources here I would gladly
contribute them, but they sit on my Amiga back in Germany. :-(

>Most operations are destructive.  E.g., `Reverse' and `Filter' act
>upon the list itself, instead of creating a modified copy.  If
>desired, the user can explicitly call `Copy'.

   Good policy! Keep the overhead low by making these things explicit.
However the "generalist" in me tends to also see the good things of
creating new structures all the time, eg. the "filtering" would become
easier to code if we would create a new list.

   However, I don't think that "Reverse" or "Filter" should even be part of
the container class itself. They should rather be provided externally, most
likely using some kind of "Iterator" or "Carrier-Rider" design pattern.

   My "Nice Class Library" (NCL from now on) project seperated Iterators
into a class hierarchy on its own. Container classes exported a method

   PROCEDURE (self: Container) NewIterator (): Iterator;

that returned an Iterator appropriate for the container class in question.
In cases where it made sense to provide more specialized iterators, a
special container class could also have a special iterator like this:

   PROCEDURE (self: Tree) NewTreeIterator (): TreeIterator;

where TreeIterator has methods like SetInOrder(), SetPreOrder() and
SetPostOrder(), which would in turn influence the behaviour of Next() which
advances an Iterator the the next element in the collection. You could also
make these paramters to the NewTreeIterator() method of course, or design
an even fancier setup using NewIterator() with a variant of the Initializer
in form of a factory method. Yeah, making it more and more complicated is
easy. :-)

>Should we allow to store the NIL object in a list?

   Since NIL means "no object" most of the time, I would say no.

>How many specializations should be provide in the module interface?
>E.g., `Append' and `Prepend' are simple specializations of
>`InsertAfter' and `InsertBefore'.  We have `Remove'.  Do we need
>specialized procedures to remove the first/last element?

   I would vote for minimal procedure sets. Other abstractions (eg. a
stack) can use the list class as implementation, but should provide a new,
distinct interface. Keep interfaces small! Also certain abstractions, eg.
Stack, should not have iterators or iterator-like constructs: It doesn't
fit!

>Currently, ADT List is a direct descendant of the type `Object'.
>Should we define a intermediate (possibly abstract) type
>Container/Collection/Bag?  And what properties should this
>intermediate type have?  [If anyone answers to this with "let's
>introduce xyz" WITHOUT giving a detailed outline and a module
>interface, I am seriously annoyed.]

   Oops, sorry to annoy you. :-) The problem is that an abstract class
container can only provide "Empty(): BOOLEAN" or maybe "Elements():
INTEGER" but no "real" methods. Collection could then add "NewIterator" or
whatever, but eg. Stacks would then be derived from "Container" directly,
or possibly a new class "Dispenser" in between (see Meyers class library
for Eiffel).

>Persistence.  Should we integrate generic load/store mechanisms into
>our library?  I think there are three different approaches to this
>problem in the Oberon community: the one presented in Moessenboeck's
>"OOP in O2", the one used by Gadgets, and the version described in
>Templ's diss "Meta-programming in Oberon".  I cannot comment on the
>pros and cons of the approaches, because I do not know Gadgets at all.

   If you do, please consider it to the fullest extent possible: You
actually have to be able to linearize arbitrary data structures. Anything
less is not general enough, and it is hard to provide support for it later.
I implemented arbitray linearization for NCL, so maybe you might want to
wait another month until I am back in Germany and can dig out and publish
those old sources.

>Another thing: I wondered why we should not provide two
>implementations of certain ADTs, e.g. a "single root" list for
>flexibility and a "low-overhead" list (as presented by MKG at the very
>beginning of this thread) for efficiency.

   Interesting! I did the same in NCL, but for different reasons. There was
actually a "Simple Class Library" (SCL) that included very basic data
structures like an efficient list and an efficient hashtable. These were
then used to implement certain NCL services, eg. the hashtable was used as
part of the linearization algorithm.

>MODULE List;
>
>IMPORT
>  StdTypes;
>
>TYPE
>  Node* = POINTER TO NodeDesc;
>  NodeDesc = RECORD
>    next-, prev-: Node;
>    (* The read-only fields `next' and `prev' are provided for efficient
>       navigation.  A value of NIL designates the end of the list. *)
>    obj-: StdTypes.Object;
>    (* Data of the list element.  *)
>  END;

   I would no export these. They should only be accessible through the
iterator or rider or whatever the "accessor" is called (Enumeration in
Java).

>PROCEDURE Destroy* (VAR l: List);
>(* Removes all elements from list `l' and destroys the list object itself.
>   The variable parameter `l' is set to NIL.
>   Note: The user is not required to call this procedure.  Resources like
>   unused lists are automatically freed by the garbage collector.  This
>   procedure is provided for convenience, both for the user and the garbage
>   collector.  *)
>  END Destroy;

  Reminds me of NCL again: If OOC supports "CLOSE" (or some equivalent
library function) I could actually contribute code to simulate "real"
destructors.

>PROCEDURE (l: List) Copy* (): List;
>(* Creates a copy of the given list `l'.  *)
>  END Copy;

   Deep of shallow? How could you do a deep copy without Object supporting
a "Clone()" method?

>PROCEDURE (l: List) Apply* (op: StdTypes.Operator);
>(* Successively applies operator `op' to the elements of `l'.  *)
>  END Apply;
>
>PROCEDURE (l: List) Map* (fct: StdTypes.Function): List;
>(* Successively applies the function `fct' to the elements of `l', and
>collects
>   the results into a new list.  The list `l' is not destroyed.  *)
>  END Map;
>
>PROCEDURE (l: List) Filter* (pred: StdTypes.Predicate);
>(* Successively applies the predicate `fct' to the elements of `l'.  Nodes,
>   for which `pred' evaluates to FALSE, are removed from the list.  *)
>  END Filter;

   I vote for real Iterators again. Okay, since I am in a hurry I can't
proofread this mail, so please be "tolerant" about any errors in the above
chaos. Have a nice day!

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