From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_05,INVALID_DATE autolearn=no autolearn_force=no version=3.4.4 Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!philabs!cmcl2!seismo!caip!nike!cad!ucbvax!CLSEPF51.BITNET!EBEL From: EBEL@CLSEPF51.BITNET Newsgroups: net.lang.ada Subject: BITNET mail follows Message-ID: <8606111547.AA23897@ucbvax.Berkeley.EDU> Date: Wed, 11-Jun-86 11:47:51 EDT Article-I.D.: ucbvax.8606111547.AA23897 Posted: Wed Jun 11 11:47:51 1986 Date-Received: Sat, 14-Jun-86 04:57:03 EDT Sender: daemon@ucbvax.BERKELEY.EDU Organization: The ARPA Internet List-Id: 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