BITNET mail follows

[EBEL@CLSEPF51.BITNET]

Problems with abstract data types packages when trying to unify them for
subranges and access structures.


     In writing abstract data types packages, we define a set of operators for
structures build from a generic parameter ITEM_TYPE. In this case we want to
have the generic formal parameter ITEM_TYPE of limited type because it is more
general and allows one to instantiate the package with any type. The client
must then furnish a procedure ASSIGN (and a function "=") which we use for
implementing the package. We then offer the expected operators and in combining
these packages the user can build combinations of abstract data types, for
instance queues of stacks, of sets or even of queues.

     Example:

     generic
       type ITEM_TYPE is limited private;
       with procedure ASSIGN (DESTINATION : out ITEM_TYPE;
                              SOURCE      : in ITEM_TYPE) is <>;
       with function "=" (LEFT, RIGHT : ITEM_TYPE) return BOOLEAN is <>;

     package QUEUE_G is

       type QUEUE_TYPE is limited private;
       procedure INSERT (QUEUE : in out QUEUE_TYPE ; ITEM : in ITEM_TYPE);
       ...

     private
       type CELL;
       type LINK is access CELL;
       type CELL is
         record
           DATA: ITEM_TYPE;
           NEXT: LINK;
         end record;
       type QUEUE_TYPE is
         record
           FIRST, LAST: LINK;
           COUNT: NATURAL := 0;
         end record;
     end QUEUE_G;

the procedure ASSIGN furnished by the user has the usual semantics

     DESTINATION := SOURCE;

     The first problem arises with data structures pointed by access. Any
reference to an old structure is lost when using this procedure ASSIGN and you
can get a STORAGE_ERROR very soon. The solution to this problem is then to
collect the lost memory, organizing it in a free list. This can be easily done
in changing the mode of the parameter DESTINATION of the procedure ASSIGN to
"in out". This generic procedure becomes now:

     with procedure ASSIGN (DESTINATION: in out ITEM_TYPE;
                            SOURCE     : in ITEM_TYPE);

which is the implementation we currently offer.
     Every thing seems to be OK. We had just to program a free list because
our implementation does not provide garbage collection.

Now comes the problem with simple types. Example :

     subtype MY_RANGE is range MIN .. MAX ;

     MY_QUEUE is new QUEUE_G (ITEM_TYPE => MY_RANGE ; ...);

A sequence such as:

     declare
       P: LINK := new CELL;
     begin
       ASSIGN(P.DATA, ITEM);
     end;

     may raise CONSTRAINT_ERROR since P.DATA, which is of type MY_RANGE, is
checked for range conformance at entry of the procedure ASSIGN. Our compiler
checks that the value of the variable given as destination to the procedure
ASSIGN has a value in the subrange.

      Three solutions seem to remain:

     1) Furnish two packages for every data type: one for simple types and one
for complex data types: this is sad and even does not work for a  data type of
mixed kinds.

     2) Implement no free list but this is impossible in some applications
because it will soon raise STORAGE_ERROR .

     3) Put an additional generic procedure

       INIT_ITEM (DESTINATION: out ITEM_TYPE; SOURCE: in ITEM_TYPE)

to the packages which will then allow the implementor for the first assignement
for every created variable before using it. In this case there is no allocated
memory to collect and the parameter can be of mode "out". The subsequent
assignments will be done with the procedure ASSIGN and the mode "in out" will
cause no problem, because the object already contains a "reasonable" value.
This procedure would contain only a "null" statement for unconstrained types.


     Does anybody have a better idea than the number 3 above?

     More details on the packages have appeared in the proceedings of the Ada-
Europe International Conference Edinburgh 6-8 May 1986.



                         N. Ebel, C. Genillard, F. Mercier, N.H. Lam
                         Swiss Federal Institute of Technology
                         1015 Lausanne