|
|
|
|
General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
|
Type Analysis
User-Defined TypesA language that permits user-defined types must provide constructs for the user to denote such types. These constructs are called type denotations. If a programmer writes two type denotations that look the same, it is natural to ask whether they represent the same type. There are two general answers to this question:
A type identifier is a name used in a source language program to refer to a type. It is important to distinguish between the concept of a type and the concept of a type identifier, using different keys to implement them, because a particular type might have zero or more type identifiers referring to it. For example, consider the following snippet of C code:
typedef float time;
typedef float distance;
typedef struct { time t; distance d; } leg;
leg trip[100];
This snippet creates two user-defined types, a structure type and
an array (or pointer) type.
Moreover, it defines three type identifiers, time, distance,
and leg.
The first two refer to the language-defined float type, and the third
refers to the structure type; the array type is anonymous -- no
type identifier refers to it.
Seven definition table keys are therefore associated with the types and
type identifiers of this snippet; three more are associated with the typed
entities t, d, and trip
(see Typed Entities).
The
Type denotations
Type denotations are language constructs that describe user-defined types.
The symbol on the left-hand side of a rule defining a type denotation
characterizes the type denoted.
It inherits the
TypeDenotation.Type cannot be dependent on the results of type analysis
(see Dependences for typed entities).
For example, some languages (e.g. Modula-3, Ada) allow a user to define
a subrange type that is characterized by its bounds.
The bound information may be needed in various contexts where the type is
used, and therefore it is reasonable to store that information as
properties of the subrange type's key.
Suppose, therefore, that
SYMBOL SubrangeSpec INHERITS TypeDenotation END;
RULE: SubrangeSpec ::= '[' Number 'TO' Number ']' COMPUTE
SubrangeSpec.GotType+=
ORDER(
ResetLower(SubrangeSpec.Type,atoi(StringTable(Number[1]))),
ResetUpper(SubrangeSpec.Type,atoi(StringTable(Number[2]))));
END;
Here
Type identifiers
The computational role
The computational role
Referring to a typeA type might be referenced in program text in any of three different ways, each illustrated by a Java or C variable definition:
Each of these representations of a type uses its own mechanism for encoding
the type.
In order to standardize the encoding, a type reference is normally
represented in the tree by a distinct symbol having a
RULE: VrblDecl ::= Type VarIdDefs ';' COMPUTE VrblDecl.Type=Type.Type; END;
Here the value of SYMBOL TypIdUse INHERITS TypeDefUseId END; RULE: Type ::= TypIdUse COMPUTE Type.Type=TypIdUse.Type; END; RULE: Type ::= 'int' COMPUTE Type.Type=intType; END; RULE: Type ::= SubrangeSpec COMPUTE Type.Type=SubrangeSpec.Type; END;
The
Operator, function, and method definitions
A user-defined type is often associated with one or more operators.
For example, an array type requires an access operator
(see Operators with explicit operands).
The
All operators associated with user-defined types must be added to the
database of valid operators before type analysis of expressions can begin.
This dependence is made explicit by having the left-hand side symbol of any
rule in which operators are defined inherit the
The
The
Operators are actually defined by rule computations. Let `ind', `opr', `rand', `rand1', `rand2', and `rslt' be definition table keys and `rands' be a list of definition table keys.
The actual value of `opr' is often irrelevant in these computations,
because the designer does not ask which operator was selected from the
given indication.
The
Consider a type denotation for one-dimensional arrays.
Assume that a subscript must be of the language-defined integer type,
and that each new array type overloads the standard array indexing
indication
SYMBOL ArraySpec INHERITS TypeDenotation, OperatorDefs END;
RULE: ArraySpec ::= Type '[' ']' COMPUTE
ArraySpec.GotOper+=
DyadicOperator(
indexInd,
NoOprName,
ArraySpec.Type,
intType,Type.Type);
END;
Another approach defines the
ATTR Indic: DefTableKey;
SYMBOL IndexTypes INHERITS OpndTypeListRoot END;
RULE: ArraySpec ::= Type '[' IndexTypes ']' COMPUTE
.Indic=NewKey();
ArraySpec.GotType+=ResetAccessor(ArraySpec.Type,.Indic);
ArraySpec.GotOper+=
ListOperator(
.Indic,
NoOprName,
IndexTypes.OpndTypeList,
Type[1].Type);
END;
Functions and methods are simply operators with operand lists. These operators overload the indication that is the function or method name. In many cases, of course, a singleton operator set will be associated with a function or method name. The operator name may or may not be interesting, depending on how the designer chooses to interpret the results of type analysis. Java method definitions overload the method identifier:
SYMBOL MethodHeader INHERITS OperatorDefs END;
SYMBOL Formals INHERITS OpndTypeListRoot END;
RULE: MethodHeader ::= Type MethIdDef '(' Formals ')' COMPUTE
MethodHeader.GotOper+=
ListOperator(
MethIdDef.Key,
NoOprName,
Formals.OpndTypeList,
Type.Type);
END;
The corresponding method call uses the method identifier as the
operator symbol in a list context.
Its indication is its Key attribute, as in the declaration:
SYMBOL MethIdUse INHERITS OperatorSymbol COMPUTE
SYNT.Indic=THIS.Key;
END;
SYMBOL Arguments INHERITS OpndExprListRoot END;
RULE: Expr ::= Expr '.' MethIdUse '(' Arguments ')' COMPUTE
ListContext(Expr[1],MethIdUse,Arguments);
END;
Every value in a C enumeration is coercible to an integer:
SYMBOL enum_specifier INHERITS TypeDenotation, OperatorSymbol END;
RULE: enum_specifier ::= 'enum' '{' enumerator_list '}'
enum_specifier.GotOper+=
Coercible(NoOprName,enum_specifier.Type,intType);
END;
Reducing specification sizeA user type definition often requires definition of a number of operators, based on the relationship between the new type and its components. Although all of those operations can be defined using the techniques of the previous section, it may be simpler to define a "template" for the particular type constructor and then instantiate that template at each corresponding type denotation. The necessary information can be captured in an OIL class (see Class definition of Oil Reference Manual). For example, a set type in Pascal implies operators for union, intersection, membership, and comparison:
CLASS setType(baseType) BEGIN
OPER
setop(setType,setType): setType;
setmember(baseType,setType): boolType;
setrel(setType,setType): boolType;
COERCION
(emptyType): setType;
END;
INDICATION
plus: setop;
minus: setop;
star: setop;
in: setmember;
equal: setrel;
lsgt: setrel;
lessequal: setrel;
greaterequal: setrel;
Within the class definition, the class name (setType in this
example) represents the type being defined.
The parameters of the class (e.g. baseType) represent the related
types.
Thus a set requires a set member operation that takes a value of the base
type and a value of the set type, returning a Boolean.
Notice that the designer chose to use the same operator for union,
intersection, and difference because all of these operators have the same
signature and distinguishing them is irrelevant for type analysis.
Let `cl' be an OIL class name, and `typ', `arg1', `arg2', `arg3' be definition table keys representing types. Each of the following rule computations instantiates an OIL class with a specific number of parameters:
A class instantiation creates operators, so it should have the SYMBOL TypeDenoter INHERITS TypeDenotation, OperatorDefs END; RULE: TypeDenoter ::= 'set' 'of' type COMPUTE TypeDenoter.GotOper+=InstClass1(setType,TypeDenoter.Type,type.Type); END;
|
