HIGHER LEVEL TYPES 2

1. ENUMERATED TYPES

2. RECORDS AND STRUCTURES

Arrays are used to group together groups of data items of the same type. A record (Ada) or structure (C) is used to group together a "fixed" number of data items (not necessarily of the same type) into a single data item. The items in a record are called fields or components (or sometimes members). Unlike arrays or enumerated types records can be recursive, i.e. they can contain fields of the same type as the record in which the field is contained.

2.1. Accessing Components of Records/Structures

The fields of a record/structure are accessed using the record name and the field name (used in this way the latter is referred to as a selector), linked by a member operator. In Ada, Pascal and C this operator is a `.' (dot). However, in C, if a pointer to a structure is used instead of its name an "arrow" (->) operator is used.

Given a "nesting" of records a number of member operators and selectors can be chained together. Some languages (Pascal) support a with mechanism which can be used to avoid repeated use of pairs of member operators and selectors.

2.2. Assignment to Records/Structures

In some imperative languages (C) each member of a structure must be assigned a value individually. Other imperative languages (Ada and Pascal) support the use of aggregates.

2.3. Comparing Records/Structures

Some imperative languages (Ada, Pascal) provide an operator to carry out comparison of records (Ada uses the = and /= operators). C does not support such comparison.

In the following two examples we create a date record type and two instances of that record (christmas and birthday), assign values to the fields for each of the created records and then output those values by accessing the records.

Ada Record Examples

with CS_IO ; use CS_IO ;

procedure RECORD_EXAMPLE_1 is
   	type DATE_T is record
      		DAY: integer;
      		MONTH: string(1..9);
      		YEAR: integer;
      	end record;
   	BIRTHDAY: DATE_T := (15,"May      ",1993);

begin
   	putline("Birthday = ");
   	put(BIRTHDAY.DAY); 
	put(" ");
   	put(BIRTHDAY.MONTH);
   	put(BIRTHDAY.YEAR); 
	new_line;
end RECORD_EXAMPLE_1 ;

with CS_IO ; use CS_IO ;

procedure RECORD_EXAMPLE is
        type DATE_T is record
                DAY   : integer;
                MONTH : string(1..10);
                YEAR  : integer;
        end record;
        NUMBER        : integer;
        INPUT_STRING  : string(1..10);
        CHRISTMAS     : DATE_T := (25,"December  ",1996);
        BIRTHDAY      : DATE_T;

        -- OUTPUT RECORD PROCEDURE
                procedure OUTPUT_RECORD(RECID: DATE_T) is
                begin
                        put(RECID.DAY); put(" ");
                        put(RECID.MONTH(1..10));
                        put(RECID.YEAR); new_line;
                end OUTPUT_RECORD;

-- TOP LEVEL PROCEDURE

begin
        put("Christmas = ");
        OUTPUT_RECORD(CHRISTMAS);

        get(BIRTHDAY.DAY);
        get_line(BIRTHDAY.MONTH,NUMBER);
        get(BIRTHDAY.YEAR);

        put("Birthday = ");
        OUTPUT_RECORD(BIRTHDAY);
end RECORD_EXAMPLE ;

C Structure Example

#include <stdio.h>
#include <string.h>

typedef struct date {
     int day;
     char month[9];
     int year;
     } DATE_T, *DATE_PTR_T;

void output_structure(DATE_PTR_T);

void main(void)
{
DATE_T stPatricksDay;
DATE_T birthday;

/* Saint Patrick's day. */

stPatricksDay.day = 17;
strcpy(stPatricksDay.month,"March");
stPatricksDay.year = 1996;

output_structure(&stPatricksDay);

/* Birthday. */

scanf("%d",&birthday.day);
scanf("%s",birthday.month);
scanf("%d",&birthday.year);

output_structure(&birthday);
}

void output_structure(DATE_PTR_T datePtr)
{
printf("%d ",datePtr->day);
printf("%s %d\n",datePtr->month,datePtr->year);
}

2.5. Variant Records

It is sometimes useful to be able to specify a number of alternative fields for a record, this is referred to as a variant record. Such records are a feature of imperative languages such Pascal and Modula-2 (but not Ada or C). A variant record comprises a fixed part, with fields as in a normal record, and a variant part, in which alternative fields are specified. The group of alternative fields which are applicable in any given instance of the record type is indicated by the value assigned to a tag field which is contained in the fixed part of the record.

3. ARRAYS OF RECORDS/STRUCTURES

It is often necessary, given a particular application, to create a number of records/structures of the same type in which to store data, e.g. an array of structures.

#include < stdio.h>
#include < string.h>

typedef struct date {
   int day; char month[9];
   int year;
   } DATE_T, *DATE_PTR_T;

/* MAIN */

void main(void) {
int numOfEl;
DATE_T structArray[3];

/* Load array */

assignToStructure(structArray,0,15,"October",1991);
assignToStructure(structArray,1,15,"May",1993);
assignToStructure(structArray,2,9,"August",1997);

/* Output array */

output(structArray,0);
output(structArray,1);
output(structArray,2);
}

/* ASSIGN TO STRUCTURE */

void assignToStructure(DATE_PTR_T newArray, int index, int newDay, char *newMonth, int newYear) {
    newArray[index].day = newDay;
    strcpy(newArray[index].month,newMonth);
    newArray[index].year = newYear;
    }

/* OUTPUT */
    
void  output(DATE_PTR_T newArray, int index) {
    printf("%d %s %d\n",newArray[index].day,newArray[index].month,
    		newArray[index].year);
    } 

In many cases the number of elements in such an array are known in advance, and consequently the amount of memory required is known in advance. We refer to such an array as a static array of structures/records. In other cases we do not know how many elements are to be in the array until run time, i.e. a dynamic array of structures/records. In this case we must create sufficient memory at run time. To create a dynamic data item (i.e. during run time) we must use an allocator which reserves space in memory for the data item. Examples

Ada allocator:

new integer

C allocator:

malloc(sizeof(integer))

here we have dynamically created space for an integer type. An allocator (such as new or malloc) returns a reference (address), referred to as an access value in Ada and a pointer in C, which indicates the first byte of the allocated memory.

In Ada, in addition to reserving memory for a particular type, it is also possible to add initialisation terms to the allocator so that a newly created object can be given a value. This is achieved using an "apostrophe" operator which is inserted between the new type name and the desired value. An example is presented in Table 8.

with CS_IO; use CS_IO;

procedure ALLOCATOR_EXAMPLE is
        type INT_PTR_T is access INTEGER;
        PI: INT_PTR_T;

begin
        PI:= new integer'(2);
        put("PI.all = ");put(PI.all);
        new_line;
end ALLOCATOR_EXAMPLE;

Here we have created an access value for an integer type. Note the use of the "dot" (member) operator. In the following (comprehensive) examples we will created a linked list of date records of the form defined earlier.

Table 9 gives some C example code where we create a dynamic array of structures.

#include < stdio.h>
#include < string.h>

typedef struct date {
   int day; char month[9];
   int year;
   } DATE_T, *DATE_PTR_T;

void main(void)
{
int numOfEl;
DATE_PTR_T structArray;

printf("Enter number of structures ");
scanf("%d",&numOfEl);

if ((structArray = (DATE_PTR_T) (malloc(sizeof(DATE_T) * numOfEl))) == NULL) {
	printf("Insufficient space\n");
	exit(-1);
	}

3. LINKED LISTS

5. UNIONS

It is sometimes desirable to define a variable which can be of two or more different types according to different circumstances (overloading). In imperative languages such a data item is termed a union. The distinction between a union and a structure is that the members of a structure define different variables while the members of a union define different manifestations of the same variable. Thus space need only be allocated to accommodate the largest type specified in a union. C example:

#include <stdio.h>

void main(void)
{
typedef union data {
        int integer;
        char character;
        } DATA_T;
DATA_T input;

input.integer = 2;
printf("input.integer = %d\n",input.integer);

input.character = 'A';
printf("input.character = %c\n",input.character);
}

Note that:

• In languages where it is left to the programmer to remember which type is to be assumed on each occasion that a union is used, we say that the union is undiscriminated (e.g. C).
• In languages where the compiler is able to automatically identify the type of a union on each occasion that it is used we say that the union is discriminated.

Unions are not supported by Ada and Pascal.

6. ORTHOGONALITY OF DATA TYPES (AND DECLARATIONS)

In principle all of the above type constructors can be combined. For example we can arrays of structures, structures contaoning arrays and so on. In practice, however, each langauge has its own set of restrictions dictated (usually) by implementaion considerations. Two features, X and Y, which can be combined freely, without in anyway restricting each other, are said to be orthogonal. The term is derived from a metaphore in which the two featues are ploted on a 2-D graph such that movement along the X axis does not effect instances of Y and vice-versa (see Bal and Grune (1994) for more detail). Orthogonality is a very strong guiding principle in language design, which was first used explicitly in the design of Algol 68.

We can identify three types of orthogonality:

1. Combination orthogonality
2. Sort orthogonality
3. Number orthogonality

6.1 Combination orthogonality

Combination orthogonality states that if one kind of Y can be combined with one kind of X than any kind of Y can be combined with any kind of X.

For example in we can identify three kinds of declaration:

• Ordinary declarations (without initialisatiion)
• Initialisation of variable (declaration and assignment combined).
• Initiallisation of constantd.

We can also identify many different kinds of types: int, char, arrays, structures and so on. Combination orthogonality dor declarations and types states that any kind of declaration can be combined with any kind of type. This sort of orthogonality is violated in a number of places in C (e.g. we cannot initialise unions) although is well supported in Ada.

6.2 Sort orthogonality

Sort orthogonality states that in any circumstance in which one kind of X is allowed to be meaningfully combined with a particular Y any kind of X is allowed to be meaningfully combined with that particylar Y. This is a special case of combination orthogonality (where one axis in the metaphore is kept constant). Sort orthogonality for types implies that (e.g.) where structures may contain basic types they should alos be allowed to contain higher level types.

6.3 Number orthogonality

Number orthogonality states that in any circumstance in which one X is allowed to be meaningfully combined with Y, zero or more than one X can also be meaningfully combined Y. This implies, for example, that where one declartaion is allowed, zero or more than one should also be allowed.