7 ARRAYS
7.1 Array Creation
7.2 Array Indexing
7.3 Getting the Array Size
7.4 Multi-dimensional Arrays
7.5 Array Definitions
7.6 Arrays and Streams
7.7 Text
7.8 Summary
The basic data types we have encountered so far are representing single values. However, in many practical applications single values are not sufficient. There is often a need to define collections of elements. For example, forests as collections of trees, libraries as collections of books.
There are two kinds of basic collections defined in the language: arrays and lists. In this chapter we will discuss arrays, in the following chapter lists. The basic collections can be used to build more specific types of collections as will be described later on.
An array is a one-dimensional collection with a fixed number of elements. The elements of an array are indexed by successive integers, starting at 1 and ending at the last element of the array. There are numerous examples of arrays: A book as an array of pages, a page as an array of lines.
Arrays are created explicitly. A new array is created by calling the predefined array function. This function expects two arguments: the first argument gives the type of the elements of the array, the second specifies the number of elements in the array. Here is an example:
A = array (integer, 10);
The evaluation of the array function results in the creation of an array of 10 elements. The elements are of integer type. The type of the array is a compound type. It is derived from the type of the elements. In this case it is the compound type array (integer). There is no room for confusion because also here the number of arguments is a distinguishing factor. For example, array (integer, 10) refers to the predefined array creation function while array (integer) is an example of a compound type.
In our example, A has been given as a name to the new array-object. If we are using from now on the name A, the system knows that A is the name of an array with the type array(integer). Here are some other examples:
B = array (real, n); << type of B is array(real) >>C = array (character, p * q); << type of C is array(character) >>D = array (array (real), m); << type of D is array(array(real)) >>
Later on, we will discuss how to define descriptors for Employees, Cars, and many other concepts. These concepts may also be used as elements of arrays, as in:
E = array (Employee, N); << type of E is array(Employee) >>F = array (Car, 50); << type of F is array(Car) >>
In our examples so far, the arrays defined are homogeneous arrays with elements which are all of the same type. To create heterogeneous arrays with elements of different types the element type must be the name of a category or it must be the term type. Categories are discussed in Chapter 14; terms are discussed in Chapter 13.
Indexing is used to select elements of an array. In general, the elements of a newly created array are empty; data items should be assigned to these elements by means of assignment statements, as shown in the following example:
A[1]:= 27; A[5]:= 39; A[9]:= -57;
If these assignments were given as part of a session we may now be interested in the values of the array A:
array(27, 0, 0, 0, 39, 0, 0, 0, -57, 0)
Suppose, we are not satisfied with the result and we want to initialize all elements of the array A with the value 5, this can be done by:
A[1..10]:= 5;
This assignment statement is equivalent to the following block:
[ i = 1 .. 10; A[i]:= 5 ];
We have introduced in this statement block a local name i which represents the stream (1, 2, ..., 10). As we know, the scope of i ends at the closing bracket of the block. The first value of i will be 1 as the first value of the stream. With this value the block-elements to the right of the name-definition of i are executed: in our situation only A[1]:=5; then the next value of the stream will be assigned to i and A[2]:=5 will be executed, and so on. The repetition with new values for i will continue until all items of the stream have been used.
To use another example: suppose we want to initialize A in such a way that the value of each element will become the value of its index:
[ i = 1 .. 10; A[i]:=i ];
Indexing can also be used to refer to individual elements of an array, as shown in the following example:
A[5]:=A[3] + A[8];
If we are now asking for A we get:
array(1, 2, 3, 4, 11, 6, 7, 8, 9, 10)
It is an error if you try to access an element which is outside the array. For example, A[11], A[0], and A[-1] are non-existent and are therefore illegal accesses.
In general, an indexed array expression may be used as an operand in an expression or statement as illustrated in the following example. Suppose we want to test if the elements of an array are greater than a given value, and we want to count the number of array elements which satisfies that condition, then we may use an indexed array in the following way:
[ count:=0; count:= count + 1 when A[1..n] > V ]
which is equivalent to:
[ count:=0; [ i = 1..n; count:=count + 1 when A[i] > V ] ]
At the end, the variable count contains the number of elements whose value are exceeding the value of V.
In order to avoid illegal accesses it is sometimes convenient to ask for the number of elements in an array. This can be done by using the predefined size function. This function must have as an argument an array and returns the number of elements of the array. The function is defined for all types of arrays. For example,
size (A)
will return the integer value 10.
Although the language only knows one-dimensional arrays, it is rather easy to create also multi-dimensional arrays. And that is because there are no restrictions on the types of elements of an array. This allows us to create arrays of arrays. For example, a matrix can be implemented as a two-dimensional array with M rows and N columns, by:
Matrix = array (array (real), M); Matrix[1 .. M]:= array (real, N);
At the first line Matrix is created. It is an one-dimensional array with M elements. Each element is of the compound type array(real). Consequently, Matrix is of the compound type array(array(real)).
At the second line, to each element of Matrix a new array is assigned. Each array consists of N elements which are of type real. The type of each array is array(real), which is in accordance with the element type of Matrix.
In general, the type of an element of an array may be any type. The types we used so far were basic data types and compound types. Both can be represented by so-called type-expressions. A type-expression specifies the type of an entity. It may be the name of a simple type or it may be a compound type. So, integer, real, array(real), array(array(real)) are all examples of type-expressions. In the following chapters we will see many other examples of type-expressions.
A question is: How are we selecting elements of a multi-dimensional array? Let us return to our Matrix example. If we want to select the third row of the Matrix, we simply write Matrix[3], and we know that a row is of type array(real). To select the second column of that row we may write:
Matrix[3] [2]
We also may use the abbreviated notation:
Matrix[3, 2]
These rules also apply to arrays with more than two dimensions.
Exercise:
- 7.1 Initialize the Matrix in such a way that the value of each element is equal to the product of its row and column indices.
Arrays may be used as arguments but also as results of definitions. Let us assume that we want to define a general function which creates a row of reals:
Row (integer) -> array(real); Row (N) = array (real, N);
The first line is the signature which says that the function Row has as input an integer parameter and has as output an array of reals. The second line is a definition rule which says that a Row of N elements is defined as an array with N real elements.
Each invocation of Row will return a new array with N empty real elements. For example, the evaluation of the function-call Row(5) will return an array with 5 vacant places for real values.
Let us now use a more complex example. Suppose we want a general function which creates at each invocation a new matrix as a two-dimensional array with M rows and N columns:
NewMatrix (integer, integer) -> array (array(real));
NewMatrix (M, N) = [ Matrix = array (array(real), M);
Matrix[1..M]:= array (real, N);
Matrix ];
The first line is again a signature. Note that the result-specification is a compound type-expression. The second line starts with a definition rule. It is in essence the same as given in the preceding section.
Each invocation of NewMatrix will return a new matrix with M rows and N columns.
Exercises:
- 7.2 Write a definition which
returns a three dimensional array.
7.3 Beside two-dimensional rectangular arrays it is also possible to define otherwise shaped arrays. Write a definition which returns a two-dimensional triangular array.
Possible expressions in the left-hand target of an assignment statement will be evaluated before the right-hand expression. That means, for example, that if the target is an array-element and the index-expression represents a stream of integer values and the right-hand of the assignment represents a stream of data items then first the left-hand index-expression is evaluated. As an example:
A[1 .. N] := 1 .. P;
is equivalent to:
[ i = 1 .. N; j = 1 .. P; A[i]:= j ];
That means in this example that ultimately all N elements of A will have the value P.
If the target contains more than one expression then the expressions are evaluated from left to right. For example:
B[1 .. N, 1 .. M] := 1 .. P;
is equivalent to:
[ i = 1 .. N; j = 1 .. M; k = 1 .. P; B[i, j]:= k ];
That means in this example that ultimately all N * M elements of B will have the value P.
To transform arrays into streams we simply use the expression:
ArrayName[ 1 .. size (ArrayName)]
This expression is sufficient to create a stream of all the elements of an array because it is equivalent to the block:
[ i = 1 .. size (ArrayName); ArrayName[ i] ]
For example, the expression A[1..10] represents the stream (A[1], A[2], ..., A[10]).
If we want to do the opposite, we may store the data items of a stream-expression into an array A by means of the following block of statements:
[ i:= 0; E = StreamExpression; i:=i+1; if i > size(A) then ready; A[i]:= E ]
The block starts with initializing the local variable i with the value 0. The next line contains a name-definition where StreamExpression produces a stream of data items which are successively assigned to E. The following line increases i with 1 for each item of E. The ready statement will terminate the execution of the loop when the number of data item of the StreamExpression exceeds the total number of elements of the array. The last line contains the assignment of a data item of E to the corresponding element of A.
The type text is a predefined type which is equivalent to the compound type array (character). That means that a text string is an array of characters. Text literals are also arrays of characters. So "AB" is a character array, as are "John Smith" and "X=A*B".
All the operations defined for arrays are also applicable to text strings. For example, we may change the text string "X=A*B" into "Y=A*C" by means of the following program:
String = copy ("X=A*B");
String[1]:= 'Y';
String[5]:= 'C';
First a copy is made of the text-literal "X=A*B" by means of the predefined copy function, then the text string is changed. The copy is required because text literals may not be modified because the same text literal can also used by other expressions.
Exercise:
- 7.4 Transform the text "ADAM" into a stream of characters.
In addition to the operations defined on arrays, a number of text specific operations are defined, as given in the following overview:
type text = array( character);text == text -> boolean; text <> text -> boolean; text < text -> boolean; text <= text -> boolean; text > text -> boolean; text >= text -> boolean; text & text -> text;
The binary operations ==, <>, <, <=, >, >= are also defined for text operands. They are used for comparison and they represent the familiar operations of equal to, not equal to, less than, less than or equal to, greater than, and greater than or equal to. The result is a boolean value. For example, the result of the expression "AB" < "AC" will be true.
Comparing two text strings works as follows: The text strings of both operands are compared from left to right, character by character, and the result is determined according to the integer values of the characters. If the two text strings are of equal lengths, and all characters of the first operand are equal to the corresponding characters of the second operand, the text strings are considered to be equal. If the characters of both operands are not equal, the relation is determined by the integer values of the leftmost characters which are different. If the two text strings are of different lengths and are equal up to the length of the shorter one, the shorter text string is considered to be less than the longer one.
In addition to the comparison operations there is another operation defined on text strings. It is a concatenation operation which concatenates two text strings together and returns the concatenated text string. The symbol used as concatenation operator is the ampersand &. For example, evaluation of the expression "AB" & "pqr" will result in the new text string "ABpqr".
We will give some other examples of the comparison and concatenation of text strings. The following declarations will be used for some of the examples:
A = "ab"; B = "abc";A == "ab"? << true >>A == B? << false >>"aa" < "b"? << true >>A < B? << true >>A & B? << "ababc" >>A & "**" & A? << "ab**ab" >>
- There are two kinds of basic collections defined in the language: arrays and lists.
- Basic collections can be used to build more specific types of collections.
- An array is a one-dimensional collection with a fixed number of elements. The elements of an array are indexed by successive integers, starting at 1 and ending at the last element of the array.
- Arrays are created explicitly by means of the predefined array (type, integer) function.
- The type of an array is of the compound type array (type), where type is the element type.
- The elements of a homogeneous arrays are all of the same type.
- The elements of a heterogeneous array may be of different types.
- Indexing of an array is used to select elements of an array.
- The predefined function size (array) returns the number of elements of an array.
- Multi-dimensional arrays are defined as combinations of one-dimensional arrays.
- Arrays may be used as arguments but also as results of definitions.
- Arrays can be easily transformed into streams.
- text is a predefined type which is equivalent to the compound type array(character).
- Text specific operations include comparison operations and text concatenation.
|
Part 1: Language Description | Chapter 7: Arrays |