Types and Declarations
Introduction: The applications of types can be grouped under checking and translation:
- Type checking uses logical rules to reason about the behavior of a program at run time. Specifically, it ensures that the types of the operands match the type expected by an operator. For example, the && operator in Java expects its two operands to be booleans; the result is also of type boolean.
- Translation Applications. From the type of a name, a compiler can determine the storage that will be needed for that name at run time. Type information is also needed to calculate the address denoted by an array reference, to insert explicit type conversions, and to choose the right version of an arithmetic operator, among other things.
The actual storage for a procedure call or an object is allocated at run time, when the procedure is called or the object is created. As we examine local declarations at compile time, we can, however, lay out relative addresses, where the relative address of a name or a component of a data structure is an offset from the start of a data area.
Type Expressions: Types have structure, which we shall represent using type expressions: a typeexpression is either a basic type or is formed by applying an operator called atype constructor to a type expression. The sets of basic types and constructorsdepend on the language to be checked.
Example: The array type i n t [2] [3] can be read as "array of 2 arrays of 3 integers each" and written as a type expression array(2, array(3, integer)). This type is represented by the tree in Fig. 6.14. The operator array takes two parameters, a number and a type.
We shall use the following definition of type expressions:
- A basic type is a type expression. Typical basic types for a language include boolean, char, integer, float, and void; the latter denotes "the absence of a value."
- A type name is a type expression.
- A type expression can be formed by applying the array type constructor to a number and a type expression.
- A record is a data structure with named fields. A type expression can be formed by applying the record type constructor to the field names and their types. Record types will be implemented in Section 6.3.6 by applying the constructor record to a symbol table containing entries for the fields.
- A type expression can be formed by using the type constructor —>• for function types. We write s —»• t for "function from type s to type r." Function types will be useful when type checking is discussed in Section 6.5.
- If s and t are type expressions, then their Cartesian product s x t is a type expression. Products are introduced for completeness; they can be used to represent a list or tuple of types (e.g., for function parameters). We assume that x associates to the left and that it has higher precedence than ->.
- Type expressions may contain variables whose values are type expressions. Compiler-generated type variables will be used in Section 6.5.4. A convenient way to represent a type expression is to use a graph. The value-number method of Section 6.1.2, can be adapted to construct a dag for a type expression, with interior nodes for type constructors and leaves for basic types, type names, and type variables; for example, see the tree in Fig. 6.14.3