-*- Mode: Text; Fonts: Ct18b -*- Chapter 13.3.3: ABSTRACT DATA TYPES As indicated in Chapter 8, Ada has a wealth of primitive data types. Of course, this set of types is not all-encompassing. Thus, the language provides a mechanism whereby a user may create an abstract data type and then encapsulate it in such a manner that the language enforces the abstraction. As we have discussed, this mechanism involves the use of packages and private types. When creating abstract data types, it is good practice to export only one type (or a small set of highly related types) per package. This, a package specification would contain only one private or limited private type, the subprograms that define the operations applicable to the type, and the specification private part. The package COMPLEX described earlier is one example of an abstract data type. However, this abstraction is not enforceable, since the type is not private and its structure is therefore visible. A user could violate this abstraction (for exmple, by adding the imaginary and real parts of a number), and the language would not be able to detect the infraction. To enforce a logical abstraction, we must use private types. For the COMPLEX package, we could declare the type NUMBER as private and move the implementation of the type to a private part. Since we could no longer refer to its structure directly, we would have to add other operations, such as GET_REAL_PART and RETURN_REAL_PART. The complete specification of COMPLEX is left as an exercise. Within the language, Ada does not define any queue data structures, such as first-in-first-out (FIFO) buffers. What is needed is a FIFO.QUEUE data type that can be treated as a primitive type. Additionally, we would like to be able to declare QUEUEs that use only INTEGER elements, although it would be a simple task to create a generic QUEUE for any type of element (as will be seen in the next chapter). We define this abstract data type in the following package specification: package FIFO is type QUEUE(LENGTH : NATURAL) is limited private; procedure CLEAR (BUFFER : out QUEUE); procedure GET (VALUE : out INTEGER; FROM : in out QUEUE); procedure PUT (VALUE : in INTEGER; ON : in out QUEUE); OVERFLOW : exception; UNDERFLOW : exception; private type LIST is array (INTEGER range <>) of INTEGER: type QUEUE(LENGTH : NATURAL) is record ELEMENTS : LIST(0..LENGTH); FRONT : INTEGER; BACK : INTEGER; end record; end FIFO; Notice how we have used a record discriminant in the private type declaration to express dependencies among components of the QUEUE record. The operations defined for this abstract type include CLEAR, PUT, and GET. We consciously decared QUEUE as a limited private type to prohibit a user from assigning QUEUE objects to each other or comparing two QUEUE objects. We also export two exceptions, OVERFLOW and UNDERFLOW, to detect any attempted PUT on a full buffer or GET from an empty buffer. Depending upon the application, it might have been useful to export the Boolean functions IS_EMPTY and IS_FULL, but we omit them here for simplicity. In the next chapter, we shall see how to make this a general purpose abstract FIFO. QUEUE by adding a generic part to parameterize some VALUE type. As before, a user does not need to see how the operations are implemented. Several implementations exist for FIFO buffers including the use of dynamic linked lists or simple arrays. In the following package body, we have chosen to implement the QUEUE as a circular buffer. With this representation, there must be one more QUEUE element than the total number of elements to be buffered (which is achieved with the declaration of FRONT and BACK). This fact can be hidden from the user in the private part. The user can thus declare objects such as: MY_BUFFER : FIFO.QUEUE(70); --a queue of length 70 YOUR_BUFFER : FIFO.QUEUE(LENGTH = >32); --A QUEUE OF length 32 Notice how the use of the private discriminant has been exploited to enable the user to declare queues of varying length. The implementation of the package body is as follows: package body FIFO is procedure CLEAR (BUFFER : out QUEUE) is begin FRONT:=BUFFER.ELEMENTS'LAST; BACK :=BUFFER.ELEMENTS'LAST; end CLEAR; procedure GET (VALUE : out INTEGER; FROM : in out QUEUE) is --retrieve a VALUE FROM a queue begin if FROM.FRONT = FROM.BACK then raise UNDERFLOW; else if FROM.FRONT = FROM.ELEMENTS' LAST then FROM.FRONT: = FROM.ELEMENTS' FIRST; else FROM.FRONT:= FROM.FRONT + 1; end if; VALUE:= FROM.ELEMENTS(FROM.FRONT); end if; end GET; procedure PUT (VALUE : in INTEGER; ON : in out QUEUE) is; --append VALUE ON front of queue begin if ON.BACK = ON.ELEMENTS'LAST then ON.BACK: = ON.ELEMENTS'FIRST; else ON.BACK:=ON.BACK + 1; end if; if ON.FRONT=ON.BACK then raise OVERFLOW; else ON.ELEMENTS(ON.BACK) := VALUE; end if; end PUT; end FIFO; A user of this package is required to explicitly CLEAR any decared QUEUEs. This operation sets the FRONT and BACK pointers to the final element of the QUEUE. In a GET operation, we first check for UNDERFLOW and then adjust the FRONT pointer to reference the top of the QUEUE. A PUT operation first adjusts the BACK pointer and then checks for OVERFLOW. If OVERFLOW is detected, then an exception is raised. Notice that the front of the QUEUE is not destroyed upon OVERFLOW; this permits the user to gracefuly recover from the error. Let us examine another application of Ada packages as abstract data types. When modeling a process control system, a programmer may need to abstract entities such as storage tanks. Ada obviously does not have them as a primitive type, but private types can be used to provide the abstraction. A package user might see storage tank types as: package STORAGE is type TANK is limited private; type PERCENT is delta 0.01 range 0.0..100.0; procedure ADD (AMOUNT : in PERCENT; TO : in out TANK); function LEVEL (PLACE : in TANK) return PERCENT; procedure REMOVE (AMOUNT : in PERCENT; FROM ; in out TANK); IS_EMPTY : exception; IS_FULL : exception; private type TANK is new PERCENT; end STORAGE; Notice that TANK has a simple representation. Encapsulating it, however, prevents a user from violating the abstraction by, for example, directly adding two TANK objects together. Also, the limited private declaration makes it impossible to asign one TANK object to another, which would normally be physically impossible (we instead must REMOVE from one TANK object while ADDing to another). Additional safety is built in with the use of exceptions. Exceptions need to be raised before anything illegal is attempted (such as filling a tank too full). We shall see how this works after examinign the following implementation: package body STORAGE is procedure ADD (AMOUNT : in PERCENT; TO : in out TANK) is --add the AMOUNT to the tank object TO begin TO := TO + TANK(AMOUNT); exception when CONSTRAINT_ERROR => raise IS_FULL; end ADD; function LEVEL (PLACE : in TANK) return PERCENT is --return the LEVEL of the tank object PLACE begin return PERCENT(PLACE); end LEVEL; procedure REMOVE(AMOUNT : out PERCENT; FROM : in out TANK) is --delete the AMOUNT from the tank object FROM begin FROM:=FROM - TANK(AMOUNT); exception when CONSTRAINT_ERROR => raise IS_EMPTY; end REMOVE; end STORAGE; Even though the algorithms in the implementation are trivial, they are shielded from the user. We have had to apply several type transformations, but this too is shielded from the user. Note how the predefined exception (CONSTRAINT_ERROR) is captured and then passed on as the user-defined exceptions IS_EMPTY and IS_FULL. It is important to note that we capture the error before the damage is done. Thus, if we try to ADD to an almost full tank object, the ADD subprogram will attempt the assignment, but an exception will then be raised. Since we did not complete the assignment, (and thus no values would have been copied to the in out parameters) the tank object will retain the value it had before the exception was raised, thus simplifying error recovery.