Re: Container Library?

[Michael van Acken <KK120y2@mail.lvr.de>]

mkgardne@cs.uiuc.edu wrote:
> Here is a module which should illustrate
> what I mean. (BTW, the module compiles and runs under oo2c v1.3.2.)
> 
>
(*==================================================================*)
> MODULE LinkedList;
>   IMPORT
>     Out;
> 
>   TYPE
>     (* "Abstract" base type for elements of a linked list *)
>     Element* = POINTER TO ElementDesc;
>     ElementDesc* = RECORD
>       next, prev : Element;
>     END;
>     
>     (* The linked list type *)
>     LinkedList* = POINTER TO ListDesc;
>     ListDesc* = RECORD
>       head : Element;
>     END;

This approach, to mix user data with list maintenance data, has
several drawbacks: 

o if a class type is defined, the user has to know if it is managed
  later in a container, and which container class class (LinkedList,
  AVLTree, BTree, whatever) is used for this purpose; in an
  extensible system this need for prior knowledge can be a problem
o the class has to be an extension of `LinkedList.Element'; in terms
  of OO this means, that the class "is a" `Element'; this is often
  incorrect, because the fact that objects are managed in a list is
  no property of the objects themselves
o every instance of this class carries two additional pointers,
  regardless if the object is actually part of a list
o an object can only appear in a single list
o certain list operations are impossible; for example, a filter
  operation that retrieves a subset of a given list, without
  destroying the first list, can't be done

Therefore I suggest something like this:

MODULE LinkedList;
  IMPORT
    Out, StdTypes;

  TYPE
    (* type for elements of a linked list *)
    Element* = POINTER TO ElementDesc;
    ElementDesc = RECORD
      next, prev : Element;
(**)  car : StdTypes.Object;  (* well, that's how it's called in LISP
*)
    END;

where StdTypes.Object is a suitable empty record.  Data is stored in
extensions of the type `Object'.

>    (* A procedure for operating on elements of the linked list *)
>    Operator* = PROCEDURE (element : Element);
  
This operator could be implemented as a type-bound procedure.
Advantage: 
o the record, to which the type-bound proc is bound, could be used to
  pass parameters to it, and the result back to the caller
o the operator procedure is visible to module `Types'; a very useful
  thing if you are working with persistent objects

> To add an INTEGER to the linked list, one needs to define an
> "adapter", in this case IntElement, as an extension of the Element
> type so data can be placed into the container. In general, an
> adapter will need to be made for each type of data which a
> container holds.

Here the "adapter" is an extension of `Object', but Mark's statements
still apply.  This uses more memory, and it needs an additional
indirection for element access.  But memory is cheap, and the
indirection doesn't effect the overall complexity of list operations.
The big pro is, of course, that the data type is much more flexible
this way.  IMO this is more important than minor efficiency
considerations when designing a general purpose library module.

-- mva