Re: Container Library?

["Mark K. Gardner" <mkgardne@rtsl3.cs.uiuc.edu>]

MKG> DataElement = POINTER TO DataElemDesc;
MKG> DataElemDesc = RECORD (LinkedList.ElementDesc)
MKG> datum : Data;
MKG> END;

MVA> Is this type defined by the user?

Yes.

MVA> I'm not sure just how far we agree.  Here is the modified type
MVA> declaration again.  Notice that I derived `LinkedList' from `Object'.
MVA>
MVA>   TYPE
MVA>     (* type for elements of a linked list *)
MVA>     Element* = POINTER TO ElementDesc;
MVA>     ElementDesc = RECORD
MVA>       next, prev : Element;
MVA>       car : StdTypes.Object;
MVA>     END;
MVA>     (* The linked list type *)
MVA>     LinkedList* = POINTER TO ListDesc;
MVA>     ListDesc = RECORD
MVA>       (StdTypes.Object)
MVA>       head : Element;
MVA>     END;
MVA>
MVA> With this kind of definition one can
MVA>
MVA> a) create a list of linked lists on user-level, without the need for
MVA>    additional data type definitions

I just realized where our differences are. There are two prominent
philosophies concerning the design of class libraries typified by
either having an single root to the class hierarchy (i.e., Object) or
multiple roots. If I am not mistaken, you are implicitly assuming that
all classes that we would want to put into lists are extensions of
Object and hence "no" adapter classes are required. On the other hand,
I am making no assumptions about the ancestry of a class, which
typifies the multiple root philosophy.

The benefits of the single root design are:

* No adapter type need ever be defined for record types. (Adapter
  types are still required for basic types because they are not
  subclasses of Object since Oberon is a hybrid OO language.) This
  does require the programmer to extend StdType.Object, but omission
  will be caught by the compiler.

* Containers are heterogeneous (by default). (Runtime type checks 
  must be performed to ensure valid homogeneous containers.)

Thus, single root designs are often considered easier to use. On the
other hand, the benefits of multiple root designs are:

* Containers are homogeneous (by default) but adapter types must be
  defined. (Heterogenous containers require heterogeneous adapter
  types.)

* One less level of indirection in the case where an adapter type must
  be defined anyway (such as containers of a basic type) as the 
  adapter type is defined to be an element type of the container.

There are proponents/opponents of each philosophy. My experience
suggests that there is little difference.

MVA> b) provide (e.g.) a `Copy' procedure in module `LinkedList' that
MVA>    creates a duplicate of a given list; the specs of `Copy': the new
MVA>    list has the same contents as the first list, in the same order,
MVA>    but any destructive operation (like element removal) on the first
MVA>    list will not be visible in the copy
MVA>
MVA> I don't see how this can be achieved by a user-defined `DataElement'
MVA> type.  But then, this may be a kind of subjective blindness :-)

Ah... we are working with Turing complete languages. There is always a
way. It just may not be convenient! :) 

In both cases, a clone of each element of the list needs to be made.
If all data items are subclasses of StdTypes.Object, there is only one
type of element and the clone routine can be "inlined" into the copy
procedure. If no restriction is made on the ancestry of data items, a
CloneElement TBP must be provided and overridden to create an element
of the correct type.

  PROCEDURE (element : Element) CloneElement () : Element;
    VAR
      myElement : MyElement;
  BEGIN
    NEW(myElement);
    myElement.datum := element(MyElement).datum;
    RETURN myElement;
  END CloneElement;

The copy procedure calls CloneElement to create an element of the
correct type and inserts it into the new list in the same manner as
the single root design.

Note that Copy may be most conveniently defined in terms of the
general Iterate construct that Michael has proposed. In the which
case, CloneElement is part of an operator defined by either approach.
The question is who does the definition of CloneElement? The single
root model allows the definition to occur once, while the multiple
root model requires multiple definitions, one for each adapter type.



I think Michael has convinced me that the single root model is the way
to go in terms of simplicity, ease of use, and reduction in "user
lines of code". It even has a successful precedent in Smalltalk.
[There is still this nagging concern in the back of my mind that some
have found the single root model to not scale well to large projects,
but I am satisfied since I do not do large projects.] ;)

Are there any dissenters to the single root model? (I am willing to
revise my LinkedList module to conform and I think I even have an AVL
module lying around.)

Next item of discussion, should all containers be extensions of an
abstract container type as in Smalltalk? What should such a type look
like?

Mark

-- 
Mark K. Gardner (mkgardne@cs.uiuc.edu)
University of Illinois at Urbana-Champaign
Real-Time Systems Laboratory
--