Re: Container Library?

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

(I apologize in advance for the amount of large quotations, but I
think they are useful in maintaining the context of the discussion.)

MKG> MODULE LinkedList;
MKG>   IMPORT
MKG>     Out;
MKG>   TYPE
MKG>     (* "Abstract" base type for elements of a linked list *)
MKG>     Element* = POINTER TO ElementDesc;
MKG>     ElementDesc* = RECORD
MKG>       next, prev : Element;
MKG>     END;
MKG>     (* The linked list type *)
MKG>     LinkedList* = POINTER TO ListDesc;
MKG>     ListDesc* = RECORD
MKG>       head : Element;
MKG>     END;

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

We are actually thinking along the same lines. I agree with all these
points. However, the design I proposed does not require that the
user's type be an extension of any element types. (In fact, it cannot
be in general, as I pointed out.) The following type definitions are
similar to the original example I posted and shows how one would use
the linked list by defining an "adapter type" which is an extension of
an element type. (In the original example I used a specific type,
INTEGER, which may have confused the issue.)

[BTW, I am using "adapter" from the adapter pattern to mean an entity
which allows one thing to be used in a context that it was not
designed for.]

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

Note that Data can be any type defined in any module. The confusion
seems to have been that Data would have to be an extension of an
element type. It does not. It should not in a good design. Instead,
the adapter which holds datum needs to be an extension of a container
element. Thus Data is completely arbitrary and can appear in any
number of containers because it is an adapter (by virtue of being an
extension of the element type of some container) that is actually "in
the container". Hopefully it is clear that the design I proposed will
meet every one of the criteria Michael pointed out.

Even so, Michael has a valid counter suggestion:

MVA> MODULE LinkedList;
MVA>   IMPORT
MVA>     Out, StdTypes;
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;  (* well, that's how it's called in LISP *)
MVA>     END;
MVA>
MVA> where StdTypes.Object is a suitable empty record.  Data is stored in
MVA> extensions of the type `Object'.

The advantage to this design is that, for N containers and M data
types, Michael's suggestion would require N elements to be defined (by
the creator of the container) and M extensions of StdTypes.Object
(most likely defined by the user). My suggestion would also require N
elements (also defined by the creator) but in general N x M extensions
of elements (defined by the user). However, not all of the element
extensions (adapters) will be required by every program in either
case. So my feeling is that both designs will be approximately the
same. However, my suggestion has the virtue of having one less level
of indirection.

MKG> (* A procedure for operating on elements of the linked list *)
MKG> Operator* = PROCEDURE (element : Element);

MVA> This operator could be implemented as a type-bound procedure.
MVA> Advantage: 
MVA> o the record, to which the type-bound proc is bound, could be used to
MVA>   pass parameters to it, and the result back to the caller
MVA> o the operator procedure is visible to module `Types'; a very useful
MVA>   thing if you are working with persistent objects

Michael's suggestion concerning making Operator a TBP is a very good
one. I wished I had thought of it! :)

MVA> But memory is cheap

Finally, I quoted this out of context, but it is one of my "favorite
irritants". (I am not picking on Michael at all. The attitude is
extremely prevalent.)

Memory may be getting cheaper and CPU speeds faster, but it has been
shown that applications are getting "fat and lethargic" at a faster
rate than costs have been going down and speeds have been going up.
This is not necessarily bad if we are getting sufficient additional
utility. However, often we are not. I think it is the attitude itself
that has spawned the over abundance of bloatware.

Wirth's adoption of Einstein's statement (probably misquoted by me)
"Keep it as simple as possible, but no simpler" is one of the reasons
I was originally attracted to Oberon. I would like to keep that as a
guiding principle. If design A has arguably better utility than design
B but uses slightly more resources, so be it. I can live with that.
But personally I will never justify a design purely because "memory is
cheap".

[Thanks to all, especially Michael, for the stimulating discussion.]

Mark

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