15 TYPES

15.1 Equivalent Types
15.2 Subtypes
15.3 Enumeration Types
15.4 Type Variables
15.5 Object Types
15.6 Type Conversions
15.7 Summary

 

Types are playing an important role in the language. In previous chapters we used the basic data types, being boolean, character, integer, and reals, and we discussed array and list types, descriptor types, terms, and category types. There are, however, some other types defined in the language. They include equivalent types, subtypes, enumeration types, and type variables. Those types will be discussed in this chapter. Furthermore, operations on compound types and rules for type conversion are examined.

15.1 Equivalent Types

Equivalent type specifications are used to introduce new type names which are equivalent to other, already existing types. For example, the type specification:

type Address = text;

defines that the type Address is equivalent to the type text. Everywhere Address is used also text may be used, and visa versa.

Often, an equivalent type such as Address is used to denote a specific meaning of a type. It is recommended to use equivalent types where possible because it helps to avoid programming errors and it elucidates the meaning of a program.

An equivalent type specification may also be used for more elaborate type expressions, such as:

type Month    = array (integer);
type Year     = array (Month);
type Matrix   = array (array (real));
type Family   = list (Person);
type Children = list (Person);

In general, equivalent type specifications can be used to give meaningful names to types and they can also be used to introduce abbreviated names.

15.2 Subtypes

A subtype specification introduces a new type as a subtype of another type. For example, the subtype specification:

type Fahrenheit = subtype (integer);

defines the type Fahrenheit as a subtype of the integer type. The integer type is called the base type.

A subtype is not equivalent to the base type, it is a new type and it will need it own set of operations. For example, the usual operations for integer type, such as +, -, * , /, are not defined for a subtype like Fahrenheit.

However, there are easy ways for type conversions between base types and subtypes. For example, to convert a quantity F, expressed in Fahrenheit, to an integer value, the following will do:

integer: F

The opposite is also possible. To convert an integer value I to a quantity in Fahrenheit we may use the following type conversion:

Fahrenheit: I

This will allow us to use base type operations where necessary.

As an example we will illustrate how subtypes can be used to define different concepts, such as Fahrenheit and Celsius, and how they can be converted:

type Fahrenheit	= subtype (integer);
type Celsius    = subtype (integer);

Degrees (Fahrenheit) -> Celsius;
Degrees (F) = Celsius: ( 5 * ( integer: F - 32) / 9);

Degrees (Celsius) -> Fahrenheit;
Degrees (C) = Fahrenheit: ( 9 * integer: C / 5 + 32);

After the two subtype specifications two definitions have been introduced: One definition converts degrees Fahrenheit to degrees Celsius (in centigrade); the other definition does the opposite.

Now we may use these definitions in the following way:

Degrees (Celsius: 100)?
212

Degrees (Fahrenheit: 0)?
-17

These examples show us that subtypes can be used to define specific operations for subtypes. Operations, such as Fahrenheit + Celsius, or Celsius * Celsius are not defined, because they are meaningless for these subtypes.

Subtypes may be defined of any type. That means, for example, that subtypes of categories are allowed, and, also that subtypes of subtypes may be defined. This allows us to create a hierarchy of subtypes.

Exercises:

15.1 Define dollars and euros as subtypes of reals. Make two definitions which are changing dollars for euros and visa versa.

15.2 Express the law velocity = distance / time in a definition by using subtypes.

 

15.3 Enumeration Types

Enumeration type specifications are used to introduce new type names together with names of the associated values. There are two kinds of enumerated types in the language: one based on symbols, the other based on integers. Enumeration types have the same properties as subtypes. That means that there are no implied operations defined on enumeration values. Operations of the base type can only be used after applying explicit type conversion. The only exceptions are the == and <> operations for enumeration types based on symbols, as will be explained later on.

We will start with enumeration types based on symbols. The way to define such an enumeration type is by explicit enumeration of the associated symbols. For example, if we are interested in a problem which deals with days of the week, we may introduce the type Day by writing:

type Day = (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday);

In this example the type name Day is introduced. It is a new enumeration type based on the predefined type symbol. For this type seven distinct values are defined. These values are represented by symbolic names. We may use them in expressions such as:

FirstDay = Sunday;
FirstDay?

The system responds with:

Sunday

We also may compare them to test if they are equal and unequal as in:

FirstDay == Sunday?
true

Sunday <> Monday?
true

This is because for symbols (and other types of entities) the == and <> operations are defined for all kinds of objects as will be described later on in Section 15.5, "Object Types".

There are no other ordering relations defined for these symbolic names. That means that expressions such as Thursday < Friday are not defined and therefore illegal. We may use the comparison of the base type symbol, as in symbol:Thursday < symbol:Friday, but that involves textual comparison of the names, rendering false in our case, so that does not help in our example. In general, for symbolic enumeration types the only operations allowed are == and <>. In many cases that will be sufficient.

In those cases where an ordering of enumeration values is required, another version of enumeration types based on integer values is available. Integer enumeration types are defined by assigning an integer value to the first name in the enumeration list. If we want to specify a type day based on integer values we simply write:

type day = (sunday=1, monday, tuesday, wednesday, thursday, friday, saturday);

In this example the type name day is an enumeration type based on the integer type. For this type seven distinct integer values are defined. The first value is 1 as an initial value, to all other names successive integer values are assigned. So, in this example sunday becomes 1, tuesday 2, wednesday 3, etc. We may use the names in expressions like:

lastday = saturday;
lastday?

The system will return:

7

The values may also be compared for ordering if we use the base type:

integer: monday < integer: thursday?
true

integer: saturday >= integer: sunday?
false

In addition, integer values may also be assigned to other enumerated names of an integer enumeration type. For example, in

type Color = (White = 1, Red, Yellow = 5, Green, Blue);

the values of the enumeration names are: White = 1, Red = 2, Yellow = 5, Green = 6, Blue = 7.

Exercise:

• 15.3 Define an enumeration type for the colors of a traffic light.

15.4 Type Variables

Let us assume that we are writing a program about children in a class room and that we have decided to represent children in a class room as elements of a list. One of the things we like to know is, how many children there are in a class room, or in implementation terms, how many elements there are in a list. Therefore we write the following length definition:

length (list (Child)) -> integer;
length (L) = [ size:=0; [ E = items (L); size:=size + 1]; size ];

This definition counts the number of elements in a list. However, if we want to count something else, for example, the number of articles on a shelf, we will need another definition:

length (list (Article)) -> integer;
length (L) = [ size:=0; [ E = items (L); size:=size + 1]; size ];

We see that in both cases the definition rules are the same. The only reason we have to write another definition is the difference in specification.

This is common for many definitions where definition rules are independent of the actual input types but where the specifications are different. In order to avoid the writing of almost identical definitions, we may use so called type variables. Type variables may be applied to represent any type. As a result, the two different length examples could be combined in one definition:

length (list (entity1)) -> integer;
length (L) = [ size:=0; [ E = items (L); size:=size + 1]; size ];

This definition can be used for all types of lists, because entity1 is a type variable. We will call this definition a polymorphic definition, because it may be used in many different forms. For example, we may use it in:

length ( {2, 3, 4} )?			<< 3 >>

length ( { 'a', 'b', 'c', 'd' } )?	<< 4 >> 

length ( { 3.4, 6.7 } )?		<< 2 >>

length ( {term: 2, 3.4, 'a', "abc" } )?	<< 4 >>

There are two kinds of type variables, entity type variables, and object type variables.

An entity type variable may represent all types. This means that an entity type variable may represent a basic data type, an array type, a list type, a descriptor type, the term type, a category type, a subtype, and so on. There are 5 entity type variables:

entity1
entity2
entity3
entity4
entity5

An object type variable may represent all types except the basic data types and their subtypes. This is because sometimes basic data types have to be excluded as arguments. There are also 5 object type variables:

object1
object2
object3
object4
object5

The specification of a polymorphic definition contains one or more type variables. Equal type variables represent equal types; different type variables may represent different or equal types. For example, the following definition:

Equal (entity1, entity1) -> boolean;
Equal (E1, E2) = E1 == E2; 

will be activated by the following calls:

Equal (2, 4)?

Equal (3.5, 6.8)?

Equal ("AB", "PQR")?

Equal (Point1, Point2)?

because the entity1 type variable represents any type. In this example, the types of both arguments must be the same, as specified by the two equal type variables.

If this is not the case as in:

Equal (2, 7.5)?

Equal (3.5, 'a')?

Equal ("AB", 'P')?

Equal (Point1, Triangle2)?

then no matching between call and definition is possible.

All above mentioned calls would have been matched if we had used the following signature:

Equal (entity1, entity2) -> boolean;

because in this version the type of the second argument is independent of the type of the first argument.

A type variable may also be part of a result specification. In that case the name must be equal to a type variable in the input specification. For example, the specification:

Combine (entity1, entity1) -> list (entity1);
Combine (E1, E2) = { E1, E2}; 

says that two entities of the same type are combined in a list of that type.

Type variables may also be used in operation specifications. Let us assume that we want to define a polymorphic operation which determines if the ordering relation X < Y holds for the elements X and Y. The meaning of the ordering relation X < Y depends on their types. For our example we assume that such a polymorphic relation is defined for entities which may be integers, reals, or text strings. The definition consists of a number of rules:

    entity1 < entity1      -> boolean;
integer: I1 < integer: I2  = intrinsic (I1 < I2);
   real: R1 < real: R2     = intrinsic (R1 < R2);
   text: T1 < text: T2     = intrinsic (T1 < T2);

Each rule selects a pair of equal types. If such a pair has been found the corresponding built-in operation is executed. The intrinsic function specifies that the language defined operations for integers, reals, and text should be used. The intrinsic function is predefined in the language. If, in our example, the intrinsic functions are omitted endless recursion will occur, because the relations I1 < I2, R1 < R2, and T1 < T2 will match with the entity1 < entity1 operation specification. As a consequence the same definition will be called over and over again.

Note that the definition of this polymorphic operation can be easily extended with other data types for which the relation T1 < T2 is defined.

Exercise:

• 15.4 Extend the polymorphic ordering relation operation with booleans, characters, and symbols.

15.5 Object Types

An object is an array, a text string, a symbol, a list, a node of a list, a descriptor, or a term. A value of a basic data type is not an object.

Object types are all the types defined in the language or by the programmer which are not the basic data types or their subtypes. As discussed earlier, object types may be represented by the object type variables.

A number of universal operations are defined in the language for object types. They are:

object1 == object1      -> boolean;
object1 <> object1      -> boolean;
same (object1, object1) -> boolean;
copy (object1)          -> object1;
null (type-expression)	-> null-value;
invalid (object1)       -> boolean;
valid (object1)         -> boolean;
no (type-expression)	-> empty-stream;

These polymorphic operations are defined for any object type.

The == and <> operations may be used to test if two objects are equal. Two objects are equal if they are of the same type, are of the same size, and have equal values for their corresponding elements.

The same (P,Q) function is true if P and Q are both representing the same object.

The copy (P) function makes a copy of the object P. This function is also defined for basic data types.

The null (T) function returns a null value of type T. T is a type-expression representing an object. This function can be used, for example, to empty an element of an array.

The invalid (P) function tests if P represents the null value. The presence of a null value indicates that no object is represented by P. This may happen, for example, if an uninitialized array element is accessed.

The valid (P) function is the opposite of the invalid (P) function. It tests if P represents not the null value.

The no (T) function will return no value but will backtrack. T is a type-expression representing any type. This function is also defined for basic data types.

All these functions (with the exception of the last one) are polymorphic functions defined for all object types. That means that these functions are applicable to, for instance, arrays, lists, descriptors, categories, terms.

15.6 Type Conversions

In the language there is a distinction between two kinds of conversions, called value conversion, and type conversion.

With type conversion the type of a data item is changed without a change of the representation of the data item. For example, Fahrenheit:23 will not change the representation of the integer value 23, only its type.

With value conversion the specified value is converted to another value. Value conversion is performed by predefined operations, such as integer (real) -> integer. For example, integer (4.7) converts the value 4.7 to the value 4. Value conversion includes also type conversion; in this example from real to integer.

Type conversion is performed by means of a special expression, called the type conversion expression. A type conversion expression specifies that the type of an expression is converted to a desired type. It has the following syntax:

type-expression: expression

The desired type is specified by the type-expression. The type-expression and the expression are separated by a semicolon.

A type-expression denotes a simple type or a compound type. Type-expressions are recursively defined. A type-expression is one of the following language elements:

• type-constant

• type-variable

• array (type-expression)

• list (type-expression)

• node (type-expression)

A type-constant is the name of a predefined type or a user-defined type. Examples of type-expressions are:

Employee
entity1
array (integer)
list (Article)
list (array (integer))
node (Article)

Not all combinations of type conversions are legal. Legal combinations depend on the type T1 represented by the type-expression and the type T2 of the expression. If the type-expression T1 and the type of the expression T2 are equal no type conversion will be necessary.

An expression with the type T2 is converted to the required type T1, if one of the following conditions is satisfied:

- T1 is a subtype of T2

- T2 is a subtype of T1

- T1 is a category to which T2 belongs

- T1 and T2 are both categories and T1 belongs to T2

- T1 is the predefined type term

In these cases the value of the expression is converted to the type T1 at translation time.

Examples:

integer: 45 		<< no type conversion required >>

Celsius: 37 		<< integer converted to Celsius >>

integer: (Celsius: x) 	<< Celsius converted to integer >>

term: "ABC" 		<< text converted to term >>

Type conversion expressions can also be used for run-time conversions. For example, if it is known that a heterogeneous collection contains only elements of the same type, then run-time type conversion can be used. There are three cases where type conversion at run-time is possible:

- T2 is the predefined type term

- T2 is a category to which T1 belongs

- T2 is a type-variable

Expressions of terms, categories, and type variables may represent several different types. In these cases, type conversion is only successful if the current value of the expression (which has type T2) is of type T1. Because terms, categories, and type variables may also represent other types, the type conversion will fail if the run-time type is unequal to T1. If the type conversion fails, a run-time error is reported.

Examples of trials of run time conversions:

integer: (term: 45)? 		<< 45 >>

character: (term: 45)? 		<< no run-time conversion possible >>

list (integer): (term: {35})? 	<< {35} >>

list (real): (term: {"ABC"})? 	<< no run-time conversion possible >>

The resulting type of a type-conversion-expression is T1. Where necessary the values of the expression are converted to values of type T1.

A type conversion expression can also be used to make an implicit type explicit in the program, as, for example, in:

T2 = Triangle: Translate (Triangle: T1, Point: P1)

By making types visible the readability of a program can be enhanced. Furthermore, wrong type assumptions can be detected early by the translator during debugging.

15.7 Summary

• A type specification defines the meaning of a type.

• An equivalent type definition defines a type name as being equivalent to another type.

• A subtype definition defines a new type as a subtype of another type.

• An enumeration type defines a type name and a set of names which are representing the allowed values of the type. There are two kinds of enumerated types in the language: one based on symbols, the other based on integers.

• Type variables are used in the specifications of polymorphic definitions. There are two kinds of type variables: entity and object types.

• In the language there is a distinction between two kinds of conversions, called value conversion, and type conversion.

• Type conversion is performed by means of type conversion expressions. A type conversion expression converts the type of an expression to a desired type, if possible.

Part 1: Language Description

Chapter 15: Types