guideline

Consider using abstract data types (not to be confused with Ada's abstract types) in preference to abstract data objects.

Consider using generic units to implement abstract data types independently of their component data type.

This example presents a series of different techniques that can be used to generate abstract data types and objects. A discussion of the merits of each follows in the rationale section below. The first is an abstract data object (ADO), which can be used to encapsulate an abstract state machine. It encapsulates one stack of integers:

------------------------------------------------------------------------
package Bounded_Stack is
   subtype Element is Integer;
   Maximum_Stack_Size : constant := 100;
   procedure Push (New_Element : in     Element);
   procedure Pop  (Top_Element :    out Element);
   Overflow  : exception;
   Underflow : exception;
   ...
end Bounded_Stack;
------------------------------------------------------------------------

The second example is an abstract data type (ADT). It differs from the ADO by exporting the Stack type, which allows the user to declare any number of stacks of integers. Because multiple stacks may now exist, it is necessary to specify a Stack argument on calls to Push and Pop:

------------------------------------------------------------------------
package Bounded_Stack is
   subtype Element is Integer;
   type    Stack   is limited private;
   Maximum_Stack_Size : constant := 100;
   procedure Push (On_Top      : in out Stack;
                   New_Element : in     Element);
   procedure Pop  (From_Top    : in out Stack;
                   Top_Element :    out Element);
   Overflow  : exception;
   Underflow : exception;
   ...
private
   type Stack_Information;
   type Stack is access Stack_Information;
end Bounded_Stack;
------------------------------------------------------------------------

The third example is a parameterless generic abstract data object (GADO). It differs from the ADO (the first example) simply by being generic, so that the user can instantiate it multiple times to obtain multiple stacks of integers:

------------------------------------------------------------------------
generic
package Bounded_Stack is
   subtype Element is Integer;
   Maximum_Stack_Size : constant := 100;
   procedure Push (New_Element : in     Element);
   procedure Pop  (Top_Element :    out Element);
   Overflow  : exception;
   Underflow : exception;
   ...
end Bounded_Stack;
------------------------------------------------------------------------

The fourth example is a slight variant on the third, still a GADO but with parameters. It differs from the third example by making the data type of the stack a generic parameter so that stacks of data types other than Integer can be created. Also, Maximum_Stack_Size has been made a generic parameter that defaults to 100 but can be specified by the user, rather than a constant defined by the package:

------------------------------------------------------------------------
generic
   type Element is private;
   Maximum_Stack_Size : in Natural := 100;
package Bounded_Stack is
   procedure Push (New_Element : in     Element);
   procedure Pop  (Top_Element :    out Element);
   Overflow  : exception;
   Underflow : exception;
   ...
end Bounded_Stack;
------------------------------------------------------------------------

The fifth example is a generic abstract data type (GADT). It differs from the GADO in the fourth example in the same way that the ADT in the second example differed from the ADO in the first example; it exports the Stack type, which allows the user to declare any number of stacks:

------------------------------------------------------------------------
generic
   type Element is private;
   Maximum_Stack_Size : in Natural := 100;
package Bounded_Stack is
   type Stack is private;
   procedure Push (On_Top      : in out Stack;
                   New_Element : in     Element);
   procedure Pop  (From_Top    : in out Stack;
                   Top_Element :    out Element);
   Overflow  : exception;
   Underflow : exception;
   ...
private
   type Stack_Information;
   type Stack is access Stack_Information;
end Bounded_Stack;
------------------------------------------------------------------------

rationale

The biggest advantage of an ADT over an ADO (or a GADT over a GADO) is that the user of the package can declare as many objects as desired with an ADT. These objects can be declared as standalone variables or as components of arrays and records. They can also be passed as parameters. None of this is possible with an ADO, where the single data object is encapsulated inside of the package. Furthermore, an ADO provides no more protection of the data structure than an ADT. When a private type is exported by the ADT package, as in the example above, then for both the ADO and ADT, the only legal operations that can modify the data are those defined explicitly by the package (in this case, Push and Pop). For these reasons, an ADT or GADT is almost always preferable to an ADO or GADO, respectively.

A GADO is similar to an ADT in one way: it allows multiple objects to be created by the user. With an ADT, multiple objects can be declared using the type defined by the ADT package. With a GADO (even a GADO with no generic formal parameters, as shown in the third example), the package can be instantiated multiple times to produce multiple objects. However, the similarity ends there. The multiple objects produced by the instantiations suffer from all restrictions described above for ADOs; they cannot be used in arrays or records or passed as parameters. Furthermore, the objects are each of a different type, and no operations are defined to operate on more than one of them at a time. For example, there cannot be an operation to compare two such objects or to assign one to another. The multiple objects declared using the type defined by an ADT package suffer from no such restrictions; they can be used in arrays and records and can be passed as parameters. Also, they are all declared to be of the same type, so that it is possible for the ADT package to provide operations to assign, compare, copy, etc. For these reasons, an ADT is almost always preferable to a parameterless GADO.

The biggest advantage of a GADT or GADO over an ADT or ADO, respectively, is that the GADT and GADO are generic and can thus be parameterized with types, subprograms, and other configuration information. Thus, as shown above, a single generic package can support bounded stacks of any data type and any stack size, while the ADT and ADO above are restricted to stacks of Integer, no more than 100 in size. For this reason, a GADO or GADT is almost always preferable to an ADO or ADT.

The list of examples above is given in order of increasing power and flexibility, starting with an ADO and ending with a GADT. These advantages are not expensive in terms of complexity or development time. The specification of the GADT above is not significantly harder to write or understand than the specification of the ADO. The bodies are also nearly identical.

Compare the body for the simplest version, the ADO:

------------------------------------------------------------------------
package body Bounded_Stack is
   type Stack_Slots is array (Natural range <>) of Element;
   type Stack_Information is
      record
         Slots : Stack_Slots (1 .. Maximum_Stack_Size);
         Index : Natural := 0;
      end record;
   Stack : Stack_Information;
   ---------------------------------------------------------------------
   procedure Push (New_Element : in     Element) is
   begin
      if Stack.Index >= Maximum_Stack_Size then
         raise Overflow;
      end if;
      Stack.Index := Stack.Index + 1;
      Stack.Slots(Stack.Index) := New_Element;
   end Push;
   ---------------------------------------------------------------------
   procedure Pop (Top_Element :    out Element) is
   begin
      if Stack.Index <= 0 then
         raise Underflow;
      end if;
      Top_Element := Stack.Slots(Stack.Index);
      Stack.Index := Stack.Index - 1;
   end Pop;
   ---------------------------------------------------------------------
   ...
end Bounded_Stack;
------------------------------------------------------------------------

with the body for the most powerful and flexible version, the GADT:

------------------------------------------------------------------------
package body Bounded_Stack is
   type Stack_Slots is array (Natural range <>) of Element;
   type Stack_Information is
      record
         Slots : Stack_Slots (1 .. Maximum_Stack_Size);
         Index : Natural := 0;
      end record;
   ---------------------------------------------------------------------
   procedure Push (On_Top      : in out Stack;
                   New_Element : in     Element) is
   begin
      if On_Top.Index >= Maximum_Stack_Size then
         raise Overflow;
      end if;
      On_Top.Index := On_Top.Index + 1;
      On_Top.Slots(On_Top.Index) := New_Element;
   end Push;
   ---------------------------------------------------------------------
   procedure Pop (From_Top    : in out Stack;
                  Top_Element :    out Element) is
   begin
      if From_Top.Index <= 0 then
         raise Underflow;
      end if;
      Top_Element := From_Top.Slots(From_Top.Index);

      From_Top.Index := From_Top.Index - 1;
   end Pop;
   ---------------------------------------------------------------------
   ...
end Bounded_Stack;
------------------------------------------------------------------------

There is only one difference. The ADO declares a local object called Stack, while the GADT has one additional parameter (called Stack) on each of the exported procedures Push and Pop.