A type characterizes a subset of values in the universe manipulated by the program, an operator defines an operation applied to operands of specified types to produce a result of a specific type, and an indication defines a set of operators. These three concepts form the basis for any type model. The designer must specify language-defined types, operators, and indications; it may also be possible for the user to provide additional specifications as part of a program (see User-Defined Types).
Although language-defined types may be specified individually,
they are usually introduced by language-defined operator specifications.
These, along with language-defined indication specifications,
are described in a language called OIL
(see OIL's Specification Language of Oil Reference Manual).
OIL text is written in a file whose name has the form `name'
Each type is represented by a unique definition table key whose
Language-defined types like "integer" are represented by known keys
(see Initializations of Definition Table).
The known key name can be used directly in an attribute computation.
For example, suppose that the designer chose
RULE: Type ::= 'int' COMPUTE Type.Type=intType; END;
Language-defined types are sometimes denoted by pre-defined identifiers (as in Pascal) instead of keywords. This approach increases the complexity of the specification by introducing type identifiers (see Type identifiers). It also allows a user to re-define the names of language-defined types as names of variables or parameters, making programs very hard to understand. We recommend that designers use keywords to denote language-defined types.
An operator has a fixed signature, and is represented by a unique
definition table key.
Properties of that key may be used to provide information about that
The OIL statement
OPER iAddOp (intType,intType):intType; fAddOp (floatType,floatType):floatType; iGtrOp (intType,intType):boolType;
The known keys named
Often there are a number of language-defined operators sharing the same signature. A shorthand notation for describing such a situation allows the designer to provide a comma-separated list of operator names and write the shared signature only once:
OPER iAddOp,iSubOp,iMulOp,iDivOp (intType,intType):intType; fAddOp,fSubOp,fMulOp,fDivOp (floatType,floatType):floatType;
Each operator must belong to a set of operators associated with some
indication, also represented by a unique definition table key.
Properties of that key may be used to provide additional information about
The OIL statement
INDICATION PlusInd: iAddOp, fAddOp; MinusInd: iSubOp, fSubOp;
Language properties like the "usual arithmetic conversions"
of C and the "widening conversions" of Java allow the compiler to
accept an operand of one type as though it were a value of another type.
We use the relation
To see why these properties are important, consider the following
expression in C or Java (
s + f
Both C and Java allow implicit conversion of
Suppose that (
COERCION sToi (shortType):intType; (intType):floatType;
This specification illustrates both named and anonymous coercions. Generally speaking, coercions need be named only if they are to be discussed in associated documentation or extracted to support further processing (such as the evaluation of constant expressions).
A full specification of language-defined operators often leads to a combinatorial explosion. In many applications the effects of this explosion on the written specification can be mitigated by avoiding unnecessary operator names. For example, the task of type analysis is to verify type correctness; the identity of the operator that models the type behavior at a specific node is normally irrelevant.
Language definitions avoid combinatorial explosions by giving names to sets of types and then defining properties of operations in terms of these sets rather than the individual elements. For example, the C definition describes operations on "arithmetic types" rather than describing those operations on integers and then again on floating-point values. OIL provides a notation for naming and manipulating sets of types that allows the designer to encode such language definitions directly.
The OIL statement
Here are some definitions that mirror the C language standard:
SET Signed_IntegerType = [signed_charType, shortType, intType, longType]; SET Unsigned_IntegerType = [unsigned_charType, unsigned_shortType, unsigned_intType, unsigned_longType]; SET FloatingType = [floatType, doubleType, long_doubleType]; SET IntegralType = [charType] + Signed_IntegerType + Unsigned_IntegerType; SET ArithmeticType = IntegralType + FloatingType; SET ScalarType = ArithmeticType + [VoidPointerType];
A specific context in a program will often require a value that can be of
any type in a particular set.
For example, the condition value in a C
When a type set name is used in an
Similarly, signatures containing type set names can be used to reduce the number of specifications needed for operators. For example, consider the following specification:
OPER ArithOp (ArithmeticType, ArithmeticType): ArithmeticType;
It defines a set of 12 operators, each named by the known key
This set of 12 operators can be associated with an indication:
INDICATION ArithInd: ArithOp;
Because the same element of a type set is substituted for each instance of the name of that set in a signature, the only way to get all combinations of elements is to create another name for that set and use both names in the signature. For example, a value of any scalar type in C can be cast to any other scalar type:
SET CastResult = ScalarType; OPER ScalarCast (ScalarType):CastResult;
One of the operators named by the known key