12 GENERIC COMPONENTS
12.1 A Generic Stack Component
12.2 Use Directives
12.3 A Generic Matrix Component
12.4 Summary
12.5 References
In the preceding chapter we discussed collections and components for collections. We assumed that the types of elements of a collection were known in advance. For example, our Stack example only worked for Books and our Queue example was restricted to Vehicles. But what happens if we want to stack or queue elements with other types? Should we make another component for each new element type? That would be a waste of effort, because all components for Stacks (or Queues) would have almost identical structures: the only difference would be the element type information. To avoid that, we will introduce the concept of generic components. Generic components are parameterized components.
In this chapter we will describe the declaration and use of generic components.
12.1 A Generic Stack Component
We will start again with our well-known Stack example. Based on the Stack component of the preceding chapter, we will introduce a generic component applicable to all types of elements (Figure 12-1).
component Stacks ( Stack, Element ); type Stack; Stack (MaxSize = integer) -> Stack; Empty ( Stack ) -> boolean; Full ( Stack ) -> boolean; Push ( Stack, Element) -> nothing; Pull ( Stack ) -> Element; begin Stack (MaxSize) = Stack:[ MaxSize; index:=0; area=array (Element, MaxSize) ];Empty ( stack ) = (stack.index <= 0);Full ( stack ) = (stack.index >= stack.MaxSize);Push ( stack, element ) = [ exception (Full (stack), "Stack Overflow"); stack.index:=stack.index + 1; stack.area[ stack.index]:=element ];Pull ( stack ) = [ exception (Empty (stack), "Stack Underflow"); stack.index:=stack.index - 1; stack.area[stack.index + 1] ];end component Stacks;
Figure 12-1: An example of a generic component for stacks.
This component supports the same operations as the Stacks component of Section 11.2. The only difference is that the stack type and the element type are parameters of the component. This means that this component will work for any type of elements. So, we may use the component for stacking dishes, or for stacking books, or for stacking notes, provided we will tell the component what the type of the elements are.
There is also another distinction we often like to make: that's about the type of the collection. We normally will regard two stacks of dishes as being collections of the same type, but a stack of dishes and a stack of books are two different types of collections. So, the types of the elements are also determining the types of the collections.
As a consequence, our Stacks component has two generic parameters: one for the type of the stack and one for the type of the elements of the stack.
A generic component is invoked by a use directive with corresponding generic arguments. Let us assume that we want to use the generic Stacks component for stacking books. We want to call our stack of books BookStack and the type of element we want to name Book. This is achieved by using the following use directive:
use Stacks (BookStack, Book);
The effect of this invocation is that an instance of the generic Stacks component is obtained for these particular arguments. The resulting component has the following form:
component Stacks; type BookStack; BookStack (MaxSize = integer) -> BookStack; Empty ( BookStack ) -> boolean; Full ( BookStack ) -> boolean; Push ( BookStack, Book) -> nothing; Pull ( BookStack ) -> Book; begin BookStack (MaxSize ) = BookStack:[ MaxSize; index:=0; area=array (Book, MaxSize) ];Empty ( stack ) = (stack.index <= 0);Full ( stack ) = (stack.index >= stack.MaxSize);Push ( stack, element) = [ exception (Full (stack), "Stack Overflow"); stack.index:= stack.index + 1; stack.area [stack.index ]:= element ];Pull ( stack ) = [ exception (Empty (stack), "Stack Underflow"); stack.index:= stack.index - 1; stack.area [stack.index + 1 ] ];end component Stacks;
Figure 12-2: An example of an instantiation of a generic component.
The effect of invoking a generic component will be clear after studying the resulting component. All references to the generic Stack parameter have been replaced by the corresponding BookStack argument and all references to the generic Element parameter have been replaced by the corresponding Book argument.
This instantiated component can now be used as any other, non-generic, component. A session with this instantiated component is somewhat different from the corresponding session of the previous chapter:
type Book = text; S = BookStack (5); S?
The result is:
BookStack:[ MaxSize = 5;
index = 0;
area = array( [],
[],
[],
[],
[] ) ]
The main differences are that the constructor function BookStack has to be called to create a new stack descriptor. And, as we see, the type of the stack descriptor is also named BookStack. The rest of the session is the same.
We are calling the Stacks component a generic component, because it represents a group of components. A generic component has always one or more generic parameters. To instantiate a specific component, the generic component must be invoked by a use directive with proper generic arguments. The names of the generic parameters of the component are replaced by the corresponding generic arguments both in the interface-section and in the implementation-section.
The same generic Stacks component can also be used to stack other kinds of entities. Let us assume that you want to stack our well-known Triangles and also want to stack Circles in different stacks. Your wishes could take the following form:
type Numeric = real; use Points, Triangles, Circles;use Stacks ( Stack_of_Triangles, Triangle); use Stacks ( Stack_of_Circles, Circle);ST1 = Stack_of_Triangles (10); ST2 = Stack_of_Triangles (20);SC1 = Stack_of_Circles (5); SC2 = Stack_of_Circles (7);
In this example, after indicating that we want to use Points, Triangles and Circles, we are invoking the Stacks component two times: the first time to indicate that we want to use a specific component dedicated to Stacks of Triangles, the second time for a specific component dedicated to Stacks of Circles.
The two specific Stacks components can now be used to create different kinds of stacks. ST1 and ST2 are the names of two different Stacks both for Triangles; SC1 and SC2 are Stacks dedicated to Circles.
We are now able to use the operations for the different types. Looking back to this exercise, we see that the first use directive is providing us with all the power of the operations on Points, Triangles, and Circles, and in addition it gives us the operations on two different types of stacks. Some examples of these possibilities are given in the following:
P1 = Point ( 3.0, 4.0); P2 = Point (-23.0, 12.0); P3 = Point ( 12.0, -13.0);Push (ST1, Triangle (P1, P2, P3) ); Push (ST1, Triangle (P3, P2, P1) );T2 = Pull( ST1 ); T1 = Pull( ST1 );Push ( SC1, Circle ( P1, 15.0) ); C1 = Pull ( SC1 );
Exercise:
- 12.1 Predict the entities represented by ST1, ST2, SC1, and SC2, after the preceding operations have been executed.
12.3 A Generic Matrix Component
Generic parameters representing collections types and element types are not the only kinds of generic parameters which are required for generic components. There are cases where also specific values must be instantiated.
Let us use as an example the component for Matrices as discussed in Section 11.4, "Matrices". Our example component was restricted to integer values. However, matrices can also defined for real values, complex values, formula's, and so on. That means that we will need generic parameters for the type of a matrix and the type of a matrix element, just as needed for the generic Stacks component. However, there is an additional complication. If we are looking inside the definition rule for Matrix1 * Matrix2, we discover the assignment:
Matrix3. A[i, j]:=0;
This statement assigns the value zero to a matrix element. However, this value 0 must be of the same type as the element type. That means that the value zero depends on the generic parameter for element type. To solve that problem we will also introduce Zero as an additional generic parameter (see Figure 12-3).
component Matrices (Matrix, Element, Zero); type Matrix; Matrix (Rows = integer, Columns = integer) -> Matrix; Matrix + Matrix -> Matrix; Matrix * Matrix -> Matrix; Fill (Matrix, list (list (Element)) ) -> nothing; begin Matrix (Rows, Columns) = [ M = Matrix:[ Rows; Columns; A = array (array(Element), Rows) ]; M.A[ 1..Rows ]:= array (Element, Columns); M ];
Matrix1 + Matrix2 = [ exception (Matrix1.Rows <> Matrix2.Rows or Matrix1.Columns <> Matrix2.Columns, "Addition of incompatible matrices" );<< Matrix3 is result matrix: >> Matrix3 = Matrix (Matrix1.Rows, Matrix1.Columns );[ i = 1 .. Matrix1.Rows; j = 1 .. Matrix1.Columns; Matrix3.A[i, j]:= Matrix1.A[i, j] + Matrix2.A[i, j] ];Matrix3 ];
Matrix1 * Matrix2 = [ exception( Matrix1.Columns <> Matrix2.Rows, "Multiplication of incompatible matrices" );Matrix3 = Matrix (Matrix1.Rows, Matrix2.Columns);[ i = 1 .. Matrix1.Rows; j = 1 .. Matrix2.Columns; Matrix3.A[i, j]:= Zero; k = 1 .. Matrix1.Columns; Matrix3.A[i, j]:= Matrix3.A[i, j] + Matrix1.A[i, k] * Matrix2.A[k, j] ];Matrix3 ];
Fill (Matrix1, List) = [ i:=0; ListRow= items (List); i:=i+1; ready when i > Matrix1.Rows; [ j:=0; ListElement= items (ListRow); j:=j+1; ready when j > Matrix1.Columns; Matrix1.A[i, j]:= ListElement ] ];end component Matrices;
Figure 12-3: An example of a generic component for matrices.
We can now use this generic component for different kinds of generic parameters. For example, if we want to use matrices for integer numbers but also matrices for real numbers, we may write the following use directives:
use Matrices (IntegerMatrix, integer, 0); use Matrices (RealMatrix, real, 0.0);
The last use directive creates a specific component for reals of the following form (see Figure 12-4).
component Matrices; type RealMatrix; RealMatrix (Rows = integer, Columns = integer) -> RealMatrix; RealMatrix + RealMatrix -> RealMatrix; RealMatrix * RealMatrix -> RealMatrix; Fill (RealMatrix, list (list (integer)) ) -> nothing; begin RealMatrix (Rows, Columns) = [ M = RealMatrix:[ Rows; Columns; A = array (array(real), Rows) ]; M.A[ 1..Rows ]:= array (real, Columns); M ];
Matrix1 + Matrix2 = [ exception (Matrix1.Rows <> Matrix2.Rows or Matrix1.Columns <> Matrix2.Columns, "Addition of incompatible matrices" );<< Matrix3 is result matrix: >> Matrix3 = RealMatrix (Matrix1.Rows, Matrix1.Columns );[ i = 1 .. Matrix1.Rows; j = 1 .. Matrix1.Columns; Matrix3.A[i, j]:= Matrix1.A[i, j] + Matrix2.A[i, j] ];Matrix3 ];
Matrix1 * Matrix2 = [ exception( Matrix1.Columns <> Matrix2.Rows, "Multiplication of incompatible matrices" );Matrix3 = RealMatrix (Matrix1.Rows, Matrix2.Columns);[ i = 1 .. Matrix1.Rows; j = 1 .. Matrix2.Columns; Matrix3.A[i, j]:= 0.0; k = 1 .. Matrix1.Columns; Matrix3.A[i, j]:= Matrix3.A[i, j] + Matrix1.A[i, k] * Matrix2.A[k, j] ];Matrix3 ];
Fill (Matrix1, List) = [ i:=0; ListRow= items (List); i:=i+1; ready when i > Matrix1.Rows; [ j:=0; ListElement= items (ListRow); j:=j+1; ready when j > Matrix1.Columns; Matrix1.A[i, j]:= ListElement ] ];end component Matrices;
Figure 12-4: An example of a instantiated component for matrices.
In this specific component every reference to Matrix of the generic component has been replaced by RealMatrix, Element has been replaced by real and Zero has been replaced by 0.0.
We may now use this specific component as shown in the following session:
MR1 = RealMatrix (3, 4); MR1?
The result is:
RealMatrix:[ Rows = 3;
Columns = 4;
A = array( array( 0.0, 0.0, 0.0, 0.0),
array( 0.0, 0.0, 0.0, 0.0),
array( 0.0, 0.0, 0.0, 0.0) ) ]
These examples of generic components may be extended with many others. For example, some generic components may also need generic parameters for unity, representing 1, or 1.0, and other kinds of generic parameters. We will not do that. It is sufficient if the basic mechanisms of generic component instantiation are understood.
Exercise:
- 12.2 How would you define matrices whose elements are again matrices of integer numbers?
- A generic component represents a family of components.
- Generic components are parameterized components.
- Use directives are used to specify the arguments of generic components.
- The generic parameters of the component are replaced by the corresponding arguments of the use directive, both in the interface-section as well as in the implementation-section.
- Generic parameters may represent collection types, element types, element values, and so on.
Generic program units were introduced in Ada ( ANSI and AJPO (1983)). Meyer (1988) discusses aspects of genericity versus inheritance.
 |
Part 1: Language Description | Chapter 12: Generic Components |