Re: Container Library?

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

I second the idea of a container library. I believe I even have some
code lying around that I would be willing to donate as a "straw man".
However, my efforts along these lines have discouraged me somewhat.
Here is an initial contribution to get discussions started...

My design makes each container a record type which manipulates
pointers to adapter records containing the actual data. Type bound
procedures are used to perform all the requisite operations on the
container. (I favor TBP, although conventional procedures can be
used.) To use the container, one would extend the appropriate adapter
type to contain the actual data.

Now to voice my dissatisfaction with the design. I sometimes find the
need to store primitive data types. For example, suppose I need a heap
of INTEGERs. To use the heap container, I must define an adapter type
to contain INTEGERs. I must allocate an adapter to hold an INTEGER and
finally I must perform a type guard on the adapter when I wish to
access the datum. (I must also tolerate additional memory management
costs associated with this level of indirection.) All to have a heap
of INTEGERs. This seems overly heavy for primitive data types. To be
fair, containers of complex data types are arguably more important
than containers of primitive data types. Complex data types are likely
already records types, but complex data types may also be extensions
and hence cannot be made an extension of the adapter type. Thus, there
is still the need for adapter types.

[It is this same inelegance which turns sours me on Java containers. I
would prefer generic containers such as can be found in Ada, Eiffel,
or SML (but not C++ as its implementation is crippled by complex
syntax and flawed semantics).]

I am willing to tolerate the need for adapter types, particularly if
OOC can strip unused code and data types. The question remains whether
there should be only one adapter type or whether there should be a
base adapter type for each container. It really isn't feasible to
define a single adapter type as each container type will require
different fields. This also makes it infeasible to have one set of
primitive adapter types. Thus, my design has an adapter type per
container. Now, either we require the user to create primitive adapter
types as needed or we require all container modules to also define
adapter types for each of the primitive types. If OOC strips unused
code and types, predefining adapter types is an inconvenience to the
container developer but not otherwise a problem. However, it would be
too much to ask that OO2C do the same because the responsibility for
actually stripping unused items most appropriately rests upon the
latest binding mechanism, the C compiler and linker. Thus for
practical purposes, primitive adapters must be defined on demand.

Enough ruminations, what do others think?

Mark (who cannot volunteer as godfather at this time,
      in spite of having a strong interest to do so)

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