Section 11.4 - GADTs versus GADOs

It's still not as flexible as it could be, though. We can't pass around stacks as parameters, and we can't create arrays of them (perhaps we'd like to have an array of stacks!).

We could have that additional flexibility if inside the generic package we defined a new type (e.g., "Stack") and changed every operation to use this new type. Then, using this new type, we can pass Stacks around, use them in arrays, and so on. Here's an example of what such a Generic_Stack's package specification would look like:

  generic
    Size : Positive;
    type Item is private;
  package Generic_Stack is
    type Stack is limited private;
    procedure Push(S : in out Stack; E : in  Item);
    procedure Pop (S : in out Stack; E : out Item);
    Overflow, Underflow : exception;
  private 
    type Stack is array(1 .. Size) of Item; 
  end Generic_Stack;

Compare this to the previous version of our Generic_Stack package:

  generic
    Size : Positive;
    type Item is private;
  package Generic_Stack is
    procedure Push(E : in  Item);
    procedure Pop (E : out Item);
    Overflow, Underflow : exception;
  end Generic_Stack;

The new version of this package is an example of what is called a generic abstract data type (GADT). A generic abstract data type is a generic that defines a central data type for the other operations so that customers of the package can do things such as use them in records and arrays. The version we saw in the previous section is called a generic abstract data object (GADO). You can can think of each instance of a GADO as being "machine" that does a fixed set of operations (such as push and pop). GADTs require just slightly more work to use because you have to instantiate the generic (creating a type you can use), and then declare a value (of that new type) to use them. You also have to specify with each GADT operation what object (i.e. which Stack) to use. In exchange for this very slight additional work, GADTs are more versatile. For example, if you want an array of stacks with a GADT, it's easy. By comparison, it's not really practical to create an array of GADOs. Therefore, in general it's recommended that you develop generic packages as GADTs, not as GADOs (the AQ&S specifically recommends this in chapter 8).

To use our new GADT version of Generic_Stack, we still have to instantiate it. Here's an example (notice that we instantiate it the same way!):

  package Stack_Int is new Generic_Stack(Size => 200, Item => Integer);

Now, however, we have a new type; we'll need to create variables of that type. For example:

  with Stack_Int; use Stack_Int;
  ...
  My_Stack : Stack;  -- Stack_Int's Stack type.

To execute various commands, we now need to tell it which Stack to use.

  Push(My_Stack, 7);

If you're seriously interested in making the component reusable, you should try to make it as flexible as possible. For example, you should be able to "compose" reusable components from other reusable components to create complex data structures. A simple way to test this is to try to compose a reusable component with itself [Wheeler 1992]. While the stack package we've shown so far is pretty good in many respects, it doesn't compose very well - we can't create a stack of stacks. Why? Because the type "Stack" in our new version of the package is a limited private type - it doesn't provide an assignment operation. However, type Item is private, because we need the Item assignment operation to implement Push and Pop.

The solution is simple - we should support assignment between Stacks, too. One approach would be to make Stack a private type, permitting Ada to use its default array assignment operations. A better solution would be to use type "Controlled" that we discussed in lesson 7 so we can better control the assignment operation, and use that to implement our own assignment statement. We'll see more of this a little later.

Quiz:

What is a GADT?

1. A generic package that does not define a new type.
2. A generic package that defines a new type; the new type is used in all the operations (subprograms) defined in the generic package.
3. Any generic package.

Go back to the previous section	Skip to the next section	Go up to lesson 11 outline