CHAPTER 13 PACKAGES YOUR HOUSE HAS A PLUMBING problem and you need to do some repair work. You could use the resources you have at home-at three o'clock in the morning almost anything can be made to stop a drip. However, it will be better in the long run to go to a hardware store in the morning and get the package of materials needed to do the job correctly and efficiently. Finally, at home, you can collect the tools you need and put them to use. It isn't important how the tools work but just that they do work. Now, Ada isn't going to stop your leaky faucets, but there is a parallel here. In Ada, a programmer may collect software tools in a package. The first tow design examples have both used packages in their solutions so by now you should have an intuitive feel for the use of this language feature. This chapter takes a closer look at packages and examines their structure and applications. 13.1 THE FORM OF ADA PACKAGES A package forms a collection of logically related entities or computational resources. Formally, we say that a package encapsulates (puts a wall around) these resources. In Chapter 6, we introduced the symbol for an Ada package, repeated herein Figure 13-1. From this figure we see that a package consists of tow parts, the specification and the body. The specification identifies and describes the visible parts of the package; formally, the package exports these entities. We have used tow different symbols in the package specification to distinguish between exporting objects and type (the rounded rectangle)and exporting operations (the regular rectangle). In a sense, this package specification is the contract between the implementer of the package and the user. This interface specifies which parts of the package may be used and, furthermore, how they may be used. It is not important for a user to understand how these operations are actually implemented. In addition, a package user may refer only to these visible entities. For example, the human interface to a car includes the steering wheel, brakes, and accelerator; these are the resources that are visible. The driver doesn't need to know how these resources work-that's an implementation detail. In Ada, similar details can be hidden in the package body. This structure directly supports the principles of modularity, abstraction, localization, and information hiding. Of course, good programmers can apply these principles in other languages, including FORTRAN or even assembly languages. The difference between Ada and most other programming languages is is that Ada packages enforce and encourage these principles. The language rules do not permit a package user to do anything more than what the package specification allows. If the user tries, he or she will be trapped at compilation time with syntax errors. Since the specification and body may be separately compiled, it is a simple matter to create the specification early in the software design and then add the body later. Furthermore, it is good practice to separate the two parts physically-supporting information hiding literally. Perhaps most importantly, though, Ada packages help the programmer control the complexity of software solutions by giving him or her a mechanism with which to physically group related entities into a logical chunk. PACKAGE SPECIFICATIONS A package specification takes the form: package SOME_NAME is . . . end SOME_NAME; A package specification may itself be further divided into tow parts, the visible part and the private part. The visible part declares the resources that may be used outside the package; the package is said to export these entities. A pack- age may export any of a number of items, including objects, types, subtypes, subprograms, tasks, numbers, exceptions, constants, renamed entities, and even other packages. It is good practice to keep package specifications small and to export only a single logical chunk. Later in this chapter, we shall discuss how this grouping may best be chosen. The private part appears only at the end of the package specification and is introduced by the reserved work private. The private part is textually available to a package user and, like the visible part, consists of declarative items. However, the private part cannot be referenced outside the package. It exists in the specification part to support the separate compilation unit mechanism. Its use will be explained later in a section on private types. A program unit may use the resources of any package that is visible. For example, consider the package COMPLEX introduced in Chapter 4: package COMPLEX is type NUMBER is record REAL_PART : FLOAT; IMAGINARY_PART : FLOAT; end record; function "+" (A,B : in NUMBER) return NUMBER; function "-" (A,B : in NUMBER) return NUMBER; function "*" (A,B : in NUMBER) return NUMBER; end COMPLEX; Package COMPLEX is visible to another program unit P if it is declared within or in an outer scope of P and is not hidden by another declaration. There are more detailed scope rules, and these are discussed in Chapter 20. For an example of the general case, we have: procedure MAIN_PROGRAM is procedure FIRST is . . . end FIRST; --start of the declarative part package COMPLEX is . . . end COMPLEX; --specification of the package package body COMPLEX is . . . end COMPLEX; --body of the package procedure SECOND is . . . --another declarative item procedure THIRD is . . . end THIRD; --a nested procedure end SECOND; begin -- --sequence of statements -- end MAIN_PROGRAM; COMPLEX is visible in the MAIN_PROGRAM from the point at which it is first named. As a result of the scope and visibility rules of Ada, the FIRST procedure cannot see the COMPLEX package; however, the SECOND and THIRD procedures, along with the MAIN_PROGRAM body, can use the resources of the COMPLEX package. Another, and usually preferred, method of establishing visibility is through the with clause. Thus, the package COMPLEX may be separately compiled and may be used by other program units; as in the following example: with COMPLEX; procedure MAIN_PROGRAM is . . . MAIN_PROGRAM is said to import the unit COMPLEX> COMPLEX is then visible throughout the MAIN_PROGRAM, and the type NUMBER and the three functions are available. The benefit of this approach is that it supports the principles of modularity and localization and so helps limit the scope of any changes that may be made during software maintenance. Another more subtle benefit is that it encourages the transportability of software units. Eventually, you'll be able to go to your local software package store, specify the interface you need, and then receive these packages for use with your program units. The structure of Ada packages clearly facilitates the develop- ment of an industry of transportable software modules. Once a package is visible, parts of its specification may be identified with selected component notation (the visible parts only). For example with COMPLEX; procedure SOME_PROGRAM is NUMBER_1,NUMBER_2 : COMPLEX.NUMBER; begin -- --sequence of statements -- end SOME_PROGRAM; Notice how our choice of names made the declaration of NUMBER_l and NUMBER_2 quite readable. This notation may be used with other names, such as: NUMBER_1.IMAGINARY_PART :=37.961; NUMBER_1 := COMPLEX."+"(NUMBER_1,NUMBER_2); The last example looks a bit awkward, since the addition operator is not directly visible and must be selected. Normally, we would like to write our equations using infix rather than prefix notation. Alternatively, we may gain direct visibility through the use clause. Application of this clause permits components to be referenced without requiring the package name as a prefix (as long as the component name is not ambiguous). For example: with COMPLEX; procedure ANOTHER_PROGRAM is use COMPLEX; NUMBER_3, NUMBER_4 : NUMBER; begin NUMBER_3 : = NUMBER_3 + NUMBER_4; end ANOTHER_PROGRAM; In this example, the addition operator refers to the operation exported from the package COMPLEX, not the predefined operator for numeric types. The addition operator is directly visible, and so we may use infix notation and drop the quotation marks. We say that the addition operator is overloaded, and, as long as the compiler can determine the operator to which we are referring (by examining the actual parameters of the call, for example), we may freely use any such overloaded entity. Note another style issue: Ada permits declaration of several objects at the same time (NUMBER_3, NUMBER_$) in what is called an identifier list. In most cases, it is recommended that a programmer use only one object name per declaration in order to improve readability. The use clause is sometimes convenient to apply since it permits shorter names, but it can cause a loss of clarity and could introduce a name clash (the condition in which there are two or more entities at the same level with the same name). The use clause does not prohibit prefixing the package name, however; so NUMBER_3 and NUMBER_4 could still be declared as COMPLEX.NUMBER to improve readability. Generally, it's still good practice to avoid the use clause in order to minimize the number of names directly visible at one time. PACKAGE BODIES A package body takes the form: package body SOME_NAME is ... end SOME_NAME; Note that the package body name must correspond exactly to its specification name. Every package specification must have a corresponding body unless the specification contains only types and objects, and then the body is optional. The elements in a package body are not accessible (visible) outside the package, thus supporting the principle of information hiding. A body has a form somewhat similar to a subprogram. It consists of a declarative part, followed by an optional block with a sequence of statements and an optional exception handler. If we introduce any subprogram, task, or package specifications in this package's specification, then their bodies must be completed in the declarative part (unless we define them as subunits, as Chapter 20 describes). As with subprogram bodies, any local declarations and local program units may be introduced in a package body. When a package body is elaborated, its declarative part is elaborated first, and then its sequence of statements, if any, are executed. This last feature is useful if any package initialization must be accomplished, as was illustrated in the previous chapter for the DATA_BASE.DATA initialization. We can complete the package COMPLEX as follows: package body COMPLEX is function "+" (A,B : in NUMBER) return NUMBER is RESULT : NUMBER; begin RESULT.REAL_PART:=A.REAL_PART + B.IMAGINARY_PART; RESULT.IMAGINARY_PART:=A.IMAGINARY_PART + B.IMAGINARY_PART; return RESULT end "+"; function "-" (A,B : in NUMBER) return NUMBER is begin return NUMBER' (REAL_PART =>A.REAL_PART-B.REAL_PART, IMAGINARY_PART=>A.IMAGINARY_PART- B.IMAGINARY_PART); end"-"; function"*" (A,B : in NUMBER) return NUMBER is RESULT : NUMBER; begin RESULT.REAL_PART:=(A.REAL_PART*B.REAL_PART)- (A.IMAGINARY_PART*B.IMAGINARY_PART); RESULT.IMAGINARY_PART:=(A.REAL_PART*B.IMAGINARY_PART)+ (A.IMAGINARY_PART*B.REAL_PART); return RESULT; end "*"; end COMPLEX; Notice the two styles for writing function return statements. In the case of the "+" function, we chose to declare a local entity (RESULT), calculate a value for RESULT, and then return the value through RESULT. In the case of the "-" function, we simply returned an aggregate value. We recommend the style of the "-" function unless the calculation of an aggregate value becomes cumbersome. In the last example, we required no package initialization. If we have a random number generator, however, we need to initialize some SEED value. This can be expressed in the package body as follows: package RANDOM is function NUMBER return FLOAT range 0.0.1.0 is end RANDOM; package body RANDOM is SEED : INTEGER; function NUMBER return FLOAT range 0.0..1.0 is . . . end NUMBER; begin SEED :=1234567; end RANDOM; In this case, when we elaborate the RANDOM package body, we initialize the SEED, which is a local object. In this simple example, we could have provided an initial SEED value by using an expression to create a default instead. As a general style rule, the use of default expressions is recommended, unless they become too complicated to generate (such as that implemented in the DATA_BASE initialization in Chapter 12). Notice the meaningful names we applied to this package; we may call the function as RANDOM.NUMBER. Before we can call any subprograms declared in the visible part of a package specification, both the specification, both the specification and body must be elaborated. We may textually separate the specification and body, provided that the specification appears first. This is quite a normal style, as the following indicates: procedure YET_ANOTHER_PROGRAM is package FIRST is --specification of FIRST . . . end FIRST; procedure SECOND; --specification of SECOND procedure THIRD; --specification of THIRD package body FIRST is... --body of FIRST procedure SECOND is ... --body of SECOND procedure THIRD is ... --body of THIRD -- begin -- --sequence of statements -- end YET_ANOTHER_PROGRAM; In this manner, we specify the interfaces of each program unit first and then group their bodies at the end of the declarative part. However, one problem with placing each complete unit body there is that it tend to makes the main unit quite lengthy and difficult to read. To reduce the length of the program text and to literally hide the implementation of each local unit, a preferred method is the introduction of a subunit, as in the following example: procedure STILL_YET_ANOTHER_PROGRAM is package FIRST is . . . end FIRST; package body FIRST is separate; procedure SECOND is separate; procedure THIRD is separate; begin -- --sequence of statements -- end STILL_YET_ANOTHER_PROGRAM; In this example, the body of each unit is compiled independently, although the specification is directly visible. Further use of this method is discussed in Chapter 20. 13.2 PACKAGES AND PRIVATE TYPES Earlier, we mentioned that packages can enforce the principle of abstraction. Often, a programmer wishes to create an object whose logical properties must be maintained outside a package but whose structural details are irrelivent. This is accomplished primarily with private types. A private type definition may appear only in the visible part of a package. There exist two cases of private types: --simple private types --limited private types For simple private types, the only information available outside the package is that given in the visible part of the package in which it was declared. Thus, the type name is available, but the set of values or structure applicable to the type is hidden. The only operations available to objects of the private type are those applicable subprograms declared in the visible part, plus the assignment operator and tests for equality and inequality. For limited private types, the same rules apply, except that even assignment and tests for equality and in- equality are not available outside the package. Of course, within the private part and body of the same package, the structure of the private type is visible, which means that its structure may be referenced. If a package contains a private type definition, then the specification must also contain a private part that completes the type definition. A private part may contain more than the definition of the private type (although this is generally not good style). Futhermore, a package without a private type may include a private part. Within a package specification, we may not only define private types but may also declare constants of a private type (although we may not define objects of the private type until the elaboration of the private part). For example, we may wish to create a package that issues PASSWORDs and also checks their validity. As we create PASSWORD objects, we want to initialize them to some NULL_PASSWORD value, which we can declare as a private constant: package MANAGER is type PASSWORD is private; NULL_PASSWORD : constant PASSWORD; function GET return PASSWORD; function IS_VALID (P : in PASSWORD) return BOOLEAN; private type PASSWORD is range 0..7_000; NULL_PASSWORD : constant PASSWORD :=0; end MANAGER; We have chosen to declare PASSWORD as a private type, as opposed to limited private, to permit users to assign PASSWORDs to each other. How- ever, we cannot directly name values of the type, since the complete type declaration is hidden from us. Even though we have hidden the implementation of the constant, we may freely use NULL_PASSWORD outside the package. For example, when declaring PASSWORD objects, we can indicate a default value: use MANAGER; MY_PASSWORD : PASSWORD :=NULL_PASSWORD; Private and limited private types therefore permit a programmer to exercise complete control over the operations available on an exported type. This feature is particularly useful when creating abstract data types, which we discuss in the next section. 13.3 APPLICATIONS FOR ADA PACKAGES Ada is a general-purpose language with considerable power, but it still does not prevent a programmer from abusing certain features of the language -- it is definitely possible to write unreadable, unstructured Ada code. To avoid this trap, each language construct must be applied in a purposeful manner. This is clearly true for Ada packages, since they form an essential element of any software system. Ada packages should be logically small, that is, they should export only a single, small chunk. We recommend four different applications for Ada packages, namely: named collections of declarations groups of related program units abstract data types abstract state machines These applications are further characterized by the kinds of entities they usually export: Named collections of declarations Export objects and types. Do not export other program units. Groups of related program units Do not export objects and types. Export other program units. Abstract data types Export objects and types. Export other program units. Do not maintain state information in the body. Abstract state machines Export objects and types. Export other program units. Maintain state information in the body. Note that these represent the purest form of application: in practice, we may find hybrid versions. The following sections provide a discussion and examples of each of these general applications. NAMED COLLECTIONS OF DECLARATIONS One of the simplest uses of packages is for the logical grouping of objects and types. This application benefits maintainability by factoring out common data, objects, and types and placing their definition in one location. This definition may then be used by any other program unit. As changes are made, only the one package must be altered, thus ensuring consistency. For example, in a system that requires an earth model, such as a guidance program or a mapping application, it is important to maintain a set of constants that every other program unit may reference. We may package this set as follows: package METRIC_EARTH_CONSTANTS is EQUATORIAL_RADIUS : constant:=6_378.145; --km GRAVITATION_CONSTANT : constant:=3.986_012e5; --km**3/sec**2 SPEED_UNIT : constant:=7.905_368_28; --km/sec TIME_UNIT : constant:=806.811_874_4; --sec end METRIC_EARTH_CONSTANTS; In this example, there are no other program units defined in the specification; so we may omit the package body. A an even better (safer) implementation, we could export types defining kilometers and seconds, and then declare the numbers as constants of that specific type. In this manner, we would prevent a user from applying a constant with the wrong units. To ensure portability, predefined types such as FLOAT should not be used. In fact, in our example above, we used numeric constants (of type universal_real) instead of naming constants of type FLOAT. As another application, it is often useful to collect a set of logically related types. In a system that manipulates dates, it would be useful to package day, month, and year types. For example: package DATE_INFORMATION is type DAY_NAME is (MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY); type DAY_VALUE is range 1..31; type MONTH_NAME is (JANUARY, FEBRUARY, MARCH, APRIL, MAY, JUNE, JULY, AUGUST, SEPTEMBER, OCTOBER, NOVEMBER, DECEMBER); type YEAR_VALUE is range 0..INTEGER'LAST; end DATE_INFORMATION; Again, a package body is not required to complete the package declaration. A few comments on style are in order here. In the example above, note that we chose to apply meaningful names, even though they take longer to write. We do this to enhance understandability. Note also that the packages in both examples are relatively small. If package specifications are made too large (beyond our Hrair limit), they become unreadable and difficult to understand. In such a case, the programmer probably missed factoring the data one more level. It would then be appropriate to create subpackages (packages nested within another package). Also, if packages are used as collections of declarations, they should not be used as if they were FORTRAN COMMONs or JOVIAL COMPOOLs. Such an application turns them into nothing more than named pools of global data, which then makes Ada programs reflect the topology of first or second generation languages. This clearly is not in the spirit of Ada and, furthermore, it defeats much of the power of the language. GROUPS OF RELATED PROGRAM UNITS In the previous examples, we were able to group logically related data. It is also possible to group program units, namely, subprograms, tasks, or even other packages. For example, since Ada does not have predefined trigonometric functions, we might need to specify such a package. (Actually, a programmer would not normally have to write such a package; he or she would most likely just reference it as a predefined library unit.) We could specify the package as follows: package transcendental_FUNCTION is type RADIANS is digits 5; type RESULT is digits 7; function COS (ANGLE : in RADIANS) return RESULT range -1.0..1.0; function SIN (ANGLE : in RADIANS) return RESULT range -1.0..1.0; function TAN (ANGLE : in RADIANS) return RESULT; end TRANSCENDENTAL_FUNCTIONS; Notice that we have defined RADIANS and RESULT as different types, both with relative precision, rather than using predefined numerics like FLOAT. Actually, in a production environment, we could increase the utility of the package by adding a generic part so that the package could operate at accuracies defined by the user. We shall do so in the next chapter. Since this specification includes entities other than objects, constants, and types, a package body is required. Of course, a user of the package need not see the body -- how the functions execute is an implementation detail. It would be good practice forthe package implementer to compile the package separately. This has the added benefit that if the transcendental algorithms were ever modified (for reasons of efficiency), the change would not affect any program units that use the package. We provide one implementation of a package body in the following example, in which a trigonometric series is used to calculate values. The implementation is not rigorously designed to account for all accuracy considerations (we leave that up to the numerical analysts), but it is sufficient to again illustrate Ada's control features: package body TRANSCENDENTAL_FUNCTIONS is SERIES_LENGTH : constant :=5; function ODD (INDEX : in INTEGER) return BOOLEAN is -- return TRUE if INDEX has an odd value begin return ((INDEX mod 2)/=0); end ODD; function FACTORIAL (VALUE : in INTEGER) return INTEGER is -- determine VALUE! using a recursive function begin if VALUE = 1 then return 1; else return (VALUE * FACTORIAL(VALUE - 1)); end if; end FACTORIAL; function TERM (ANGLE : in RADIANS, POWER : in INTEGER, NUMBER : IN INTEGER) return RESULT is -- calculate a term of the trigonometric series begin if ODD (NUMBER) then return RESULT(-((ANGLE)**POWER)/(RADIANS(FACTORIAL(POWER)))); else return RESULT (+((ANGLE)**POWER)/(RADIANS(FACTORIAL(POWER)))); end if; end TERM; function COS (ANGLE : in RADIANS) return RESULT range -1.0..1.0 is -- calculate the cosine of ANGLE ANSWER : RESULT; POWER : INTEGER; begin ANSWER := 1.0 for | in reverse 1 .. SERIES_LENGTH loop POWER := | * 2; ANSWER := ANSWER + TERM(ANGLE, POWER, NUMBER); end loop; return ANSWER; end COS; function SIN (ANGLE : in RADIANS) return RESULT range -1.0..1.0 is -- calculate the sine of ANGLE ANSWER : RESULT; POWER : INTEGER; begin ANSWER:= RESULT(ANGLE); for | in reverse 1 .. SERIES_LENGTH loop POWER := (|*2) + 1; ANSWER := ANSWER + TERM(ANGLE, POWER, NUMBER); end loop; return ANSWER; end SIN; function TAN (ANGLE : in RADIANS) return RESULT is -- calculate the tangent of ANGLE begin return (SIN(ANGLE)/COS(ANGLE)); end TAN end TRANSCENDENTAL_FUNCTIONS; In this implementation, note particularly the use of the SERIES_LENGTH constant that determines the length of the trigonometric series. By declaring this value as a constant, it is easier for a programmer to modify the package later. Furthermore, the body does not have the optional sequence of statements for initialization, but three local subprograms are declared to complete the implementation. These functions, ODD, FACTORIAL, and TERM, are hidden in the body and may therefore not be accessed outside the package. Within COS and SIN, we step through the series from the smallest term to the largest (to minimize roundoff errors). For the TAN subprogram, the facilities provided by COS and SIN are used. Graphics packages demonstrate another application of Ada packages as collections of subprograms. Since transformations (ROTATE, SCALE, and TRANSLATE) are common graphics algorithms, a user might be provided with the following package specification: package TWO_D_TRANSFORM is type COORDINATE is record X : FLOAT; Y : FLOAT; end record; procedure ROTATE (POINT : in out COORDINATE; ANGLE : in FLOAT) procedure SCALE (POINT : in out COORDINATE; X,Y : in FLOAT); procedure TRANSLATE (POINT : in out COORDINATE; X,Y ; in FLOAT); end TWO_D_TRANSFORM; We have somewhat violated our philosophy of never using predefined types such as FLOAT, but we have done so here to simplify our solution and also to show some more applications of type transformations. Our package will need the resources of the TRANSCENDENTAL_FUNCTIONS, but we can hide the reference in the TWO_D_TRANSFORM body. We apply the use clause to permit shorter names in the implementation; since the package specification is small, there is little chance of ambiguity. One possible body is as follows: with TRANSCENDENTAL_FUNCTIONS; use TRANSCENDENTAL_FUNCTIONS; package body TWO_D_TRANSFORM is procedure ROTATE (POINT : in out COORDINATE; ANGLE : in FLOAT) is --rotate the POINT by ANGLE radians about the origin TEMP: COORDINATE ;= POINT begin POINT.X:= (POINT.X*FLOAT(COS(RADIANS(ANGLE)))) + (POINT.Y*FLOAT(SIN(RADIANS(ANGLE)))); POINT.Y:= -(POINT.X*FLOAT(SIN(RADIANS(ANGLE)))) + (POINT.Y*FLOAT(COS(RADIANS(ANGLE)))); end ROTATE; procedure SCALE(POINT : in out COORDINATE; X,Y : in FLOAT) is --scale the POINT by a factor of X and Y begin POINT.X:=POINT.X*Y; POINT.Y:=POINT.Y*Y; end SCALE; procedure TRANSLATE(POINT : in out COORDINATE; X,Y : in FLOAT) is --translate the POINT by a distance of X and Y begin POINT.X:=POINT.X + X; POINT.Y:=POINT.Y + Y; end TRANSLATE; end TWO_D_TRANSFORM; As before, package initialization is not required. So far, we have shown applications of packages as collections of subprograms, but it is also reasonable to use packages to collect other packages or problem. 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. ABSTRACT STATE MACHINES A state machine, or automta, is an entity that has well-defined states and operations for changing from state to state. Additionally, there is some means of detecting the current state of the machine. We may think of abstract state machines as simple "black box" objects. A user may act upon the box (with procedures) or examine the attributes of the box (via functions). The latter are considered to be the state. Of course, any actions on the box may change its state. In terms of form, packages as abstract state machines do not export types or (usually) objects. In a sense, they look like abstract data types or simple collections of program units. However, the essential difference is that packages used as abstract state machines have retained state information in the package body. For example, the TRANSCENDENTAL_FUNCTIONS package declared earlier consisted of several subprograms, but calling one subprogram did not affect any state. In fact, each subprogram was quite independent, and its outcome never could affect the other. For state machines, however, the operations applied do affect the state. For example, we may abstract a FURNACE to the user as: package FURNACE is function IS_RUNNING return BOOLEAN; procedure SET(TEMPERATURE : in FLOAT); procedure SHUT_DOWN; function TEMPERATURE_IS return FLOAT; OVERTEMP : exception; end FURNACE; The package user may only apply the four given subprograms to either change the state of the FURNACE or determine the current TEMPERATURE. Clearly, the order in which these subprograms are called makes a difference, due to the retained data. Since no types or objects are exported, this package defines only one object. Furthermore, since the package specification defines several subprograms, a complete package body must eventually be supplied. Another typical example of a state machine is a lexical analyzer, which is a machine that can recognize and classify a stream of characters. Such machines are necessary tools for compilers and communication systems. For example, as part of a compiler, we may wish to create a state machine that can recognize identifiers or numbers. A state transition diagram for such a machine is shown in Figure 13-2. As seen in the diagram, the machine is initially in a START state. When the first symbol is received, it moves to a BUILD_IDENTIFIER state if it is a LETTER, to a BUILD_NUMBER state otherwise. The machine stays in either state as long as a stream of LETTERs or DIGITs (for BUILD_IDENTIFIER) or just DIGITs (for BUILD_ NUMBER) is received. Once a different symbol is received, the machine moves to a STOP state; at that point, the token has been recognized. Figure 13-2 State machine for LEXICAL_ANALYZER We may define the interface to this abstract state machine as: package LEXICAL_ANALYZER is procedure SET_START_STATE; procedure RECEIVE_SYMBOL(C : in CHARACTER); IDENTIFIER_ACCEPTED : exception; INVALID_CHARACTER : exception; MACHINE_HALTED : exception; NUMBER_ACCEPTED : exception; end LEXICAL_ANALYZER; Notice that we have identified the accepting conditions as exceptions. In this way, a user of this package may continue to send symbols to the state machine without the overhead of explicitly checking to see if the token has been accepted. If desired, we could easily pass the accepting information as a parameter through RECEIVE_SYMBOL. We have included an INVALID_CHARACTER exception, which is raised if the first symbol is neither a LETTER nor a DIGIT. We have also included the operation SET_START_STATE so that the user may reinitialize the state machine, plus a MACHINE_HALTED exception in case the user tries to apply an operation to a halted machine. We may implement our state machine as follows: package body LEXICAL_ANALYZER is type STATE is (START, BUILD_IDENTIFIER, BUILD_NUMBER, STOP); PRESENT_STATE : STATE := START; subtype ALPHA is CHARACTER range 'A'..'Z'; subtype DIGIT is CHARACTER range '0'..'9'; procedure SET_START_STATE is --initialize state machine begin PRESENT_STATE := START; end SET_START_STATE; procedure RECEIVE_SYMBOL(C : in CHARACTER) is --accept a symbol from the transmitter begin case PRESENT_STATE is when START => if (C in ALPHA) then PRESENT_STATE := BUILD_IDENTIFIER; elsif (C in DIGIT) then PRESENT_STATE := BUILD_NUMBER; else raise INVALID_CHARACTER; end if; when BUILD_IDENTIFIER => if (C in ALPHA) or (C in DIGIT) then null; else PRESENT_STATE := STOP; raise IDENTIFIER_ACCEPTED; end if; when BUILD_NUMBER => if (C in DIGIT) then null; else PRESENT_STATE := STOP; raise NUMBER_ACCEPTED; end if; => raise MACHINE_HALTED; when STOP end case; end RECEIVE_SYMBOL; end LEXICAL_ANALYZER; This completes our implementation of a simple LEXICAL_ANALYZER. Since we defined the STATE as an enumeration type, it would be quite simple to modify the machine to accept other tokens. Ada packages derive their power from their ability to encapsulate a local entity and then enforce that abstraction. In the next chapter, we shall study additional packaging concepts involving generic program units. EXERCISES 1. Create a package specification called COMPLEX which exports a private type called NUMBER. Complete the package by describing a body which includes the operations of addition, substraction, multiplication, division, setting and retrieving values, and determining angle and length. 2. Create a package, called METRIC_ENGLISH_CONVERSION, that exports the types LITER and GALLON, INCH and CENTIMETER, along with constants with the appropriate universal_real values needed for conversion. 3. Write the package specification for a unit that brings in the current date in month-day-year form and returns an equivalent Julian date. (A Julian date includes the year number and the day of the year. For example, 128 83 is the 128th day of 1983.) 4. Rewrite the factorial routine in TRANSCENDENTAL_FUNCTIONS without using recursion. 5. Write the package specification for three-dimensional transformations (scale, rotate, translate). *6. Rewrit ethe body of FIFO, this time using access types as the underlying implementation for the QUEUE. *7. Modify the LEXICAL_ANALYZER so that an exception occurs whenever an invalid character is received. *8. Modify the LEXICAL_ANALYZER so that we can recognize delimiters such as ".=", "+", and "+".