![]() |
![]() |
![]() |
General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
![]() |
![]() |
Type analysis tasksProperties of TypesIn general it is necessary to associate properties to types that carry characterizing information which is either used for purposes of type analysis, e.g. to check compatibility of two types or to determine the element type of an array, or for translation purposes, e.g. the size of data objects in the target code. It is an important design issue in type analysis to identify the characterizing properties of types. In this section four common type classes are used to demonstrate principles of type properties, and their use in type analysis. Solutions for other types may be derived from these by analogy. Here only properties are described that are used in type analysis itself, disregarding properties for the transformation task. For our solution we use the module for basic type analysis (see Basic Type Analysis) and some modules of the property library (see Property Library of Association of properties to definition).
Array types and pointer types are used to demonstrate how new types are introduced by declarations in a program, as opposed to predefined types, and that type properties refer to other types.
Function types are used to demonstrate type properties that are
lists of types which are specified using the
Record types are used to demonstrate type properties that are
scopes which are specified using modules of the
Array TypesIn this section we use array types to demonstrate how new types are introduced by declarations in a program, as opposed to predefined types. Furthermore it is shown how type properties refer to other types. We assume that an array is described by the type and the number of its elements, like in C. The denotation of an array type shall introduce a new type that is diffierent from any other type, as in Pascal. For ease of our example we do not consider type rules that allow two different array types to be compatible.
The language of our running example is extended by TypeDenoter: ArrayType. ArrayType: TypeDenoter '[' IntNumber ']'. Variable: Variable '[' Expression ']'.The form chosen for TypeDenoter s keeps the grammar simple and
orthogonal, but leads to a bit unconventional notation for declaration
of array variables and array type names:
type int[10] Vector; var Vector v; var float[5] a; v[6] = 1; a[3] = 2.5;
An array type is described here by two properties introduced by the
ElemType: DefTableKey; ElemNo: int;
The rule that any type denoter introduces a new array type is reflected
by using the module role
SYMBOL ArrayType INHERITS TypeDenotation END; RULE: ArrayType ::= TypeDenoter '[' IntNumber ']' COMPUTE ArrayType.GotType = ORDER (ResetElemType (ArrayType.Type, TypeDenoter.Type), ResetElemNo (ArrayType.Type, IntNumber)); END; RULE: TypeDenoter ::= ArrayType COMPUTE TypeDenoter.Type = ArrayType.Type; END;Association of the type properties establishes the postcondition ArrayType.GotType . The module roles ensure that the
properties are set before accessed.
In the context of an indexed RULE: Variable ::= Variable '[' Expression ']' COMPUTE Variable[1].Type = TransDefer (GetElemType (Variable[2].Type, NoKey)); IF (EQ (Variable[1].Type, NoKey), message (ERROR, "index applied to non array", 0, COORDREF)); Expression.ReqType = intType; END;
Pointer Types
In this section we introduce pointer types to the language
of our running example. A type denoted The concrete grammar of our running example is extended by the productions: TypeDenoter: PointerType. PointerType: TypeDenoter '!'. Variable: Variable '!'. Variable: Variable '&'.Two new Variable notations are introduced:
v ! denotes the object which the value of the pointer variable
v points to. v & yields the address of the variable
v , it has the type pointer to t if v is a variable
of type t .
Due to our equivalence rules all variables in the following example have the equivalent types: type int ! IntPtr; type IntPtr IP; var IntPtr i, IP j, int ! k; ... i! = j!;
The property PointsTo: DefTableKey [KReset];(The operation KReset is described below.)
The following computation introduces the notation of
pointer types using the module role
SYMBOL PointerType INHERITS TypeDenotation END; RULE: PointerType ::= TypeDenoter '!' COMPUTE PointerType.GotType = ResetPointsTo (PointerType.Type, TypeDenoter.Type); END; RULE: TypeDenoter ::= PointerType COMPUTE TypeDenoter.Type = PointerType.Type; END;
If we do not take further means any two occurrences of a pointer
type notation would denote different types.
The equivalence rule described above has to be implemented in functions
which compare types. Caution has to be taken to avoid non-termination
of such functions if applied to recursively defined types.
More details can be found in
For the contents operation applied to a RULE: Variable ::= Variable '!' COMPUTE Variable[1].Type = TransDefer (GetPointsTo (Variable[2].Type, NoKey)); IF (EQ (Variable[1].Type, NoKey), message (ERROR, "is not a pointer variable", 0, COORDREF)); END;The call of TransDefer ensures that Type
attributes in expression contexts are type keys rather than
deferred keys. A convention that is introduced by the
module roles, and carried on here.
The address operator implicitly creates a pointer type
that RULE: Variable ::= Variable '&' COMPUTE Variable[1].Type = KResetPointsTo (KResetIsType (NewKey (), 1), Variable[2].Type); END;
The
Function Types
Function types are an example for types that have properties which
are lists of types, the types of the parameters.
They are also used here to demonstrate an application of the
The type of a function is described by its result type and the list of the types of the parameters. Type analysis of a function call has to check the parameter types of the called function against the corresponding argument types, and has to yield the result type as the type of the call. We extend the concrete grammar of our running example by productions for function declarations and calls: Declaration: FunctionDecl. FunctionDecl: 'fun' DefIdent Function ';'. Function: FunctionHead Block. FunctionHead: '(' Parameters ')' TypeDenoter. Parameters: [Parameter // ',']. Parameter: TypeDenoter Ident. Expression: Expression '(' Arguments ')'. Arguments: [Argument // ',']. Argument: Expression. In the context of a function declaration the list of parameter types is composed and associated as a property of the function type. In the context of a function call that property is accessed, the list is decomposed, and its elements - the formal parameter types - are compared with the types of the arguments.
In order to describe lists of parameter types we instantiate
the $/Adt/LidoList.gnrc+instance=DefTableKey+referto=deftbl:inst A function type is described by two properties, the result type and and the list of parameter types as introduced by the following PDL specifications: ParamTypes: DefTableKeyList; "DefTableKeyList.h" ResultType: DefTableKey;where the DefTableKeyList type and the file defining it
is obtained from the module instance.
Several module roles are to be combined in the contexts of
function declarations:
The SYMBOL Function INHERITS RangeScope END; SYMBOL FunctionDecl INHERITS TypedDefinition END; RULE: FunctionDecl ::= 'fun' DefIdent Function ';' COMPUTE FunctionDecl.Type = Function.Type; END; SYMBOL FunctionHead INHERITS TypeDenotation END; RULE: FunctionHead ::= '(' Parameters ')' TypeDenoter COMPUTE FunctionHead.GotType = ORDER (ResetResultType (FunctionHead.Type, TypeDenoter.Type), ResetParamTypes (FunctionHead.Type, Parameters.DefTableKeyList)); END; SYMBOL Parameter INHERITS TypedDefinition END;Language rules that determine when the types of two functions are equal have to be implemented in the functions for type comparison. An example can be found in $/Type/Examples/Type.fw .
The parameter type list is composed using the list construction
roles of the SYMBOL Parameters INHERITS DefTableKeyListRoot END; SYMBOL Parameter INHERITS DefTableKeyListElem END; RULE: Parameter ::= TypeDenoter DefIdent COMPUTE Parameter.DefTableKeyElem = TypeDenoter.Type; END;
In the context of a call the type of the SYMBOL Arguments INHERITS DefTableKeyDeListRoot END; RULE: Expression ::= Expression '(' Arguments ')' COMPUTE Arguments.DefTableKeyList = GetParamTypes (Expression[2].Type, NULLDefTableKeyList); Expression[1].Type = TransDefer (GetResultType (Expression[2].Type, NoKey)); IF (EQ (Expression[1].Type, NoKey), message (ERROR, "call applied to non function", 0, COORDREF)); Expression[2].ReqType = Expression[2].Type; IF (NE (Arguments.DefTableKeyListTail, NULLDefTableKeyList), message (ERROR, "arguments missing", 0, COORDREF)); END;The type of each formal parameter is obtained from the decomposed list and stated to be the required type of the actual argument: SYMBOL Argument INHERITS DefTableKeyDeListElem END; RULE: Argument ::= Expression COMPUTE Expression.ReqType = Argument.DefTableKeyElem; IF (EQ (Argument.DefTableKeyElem, NoDefTableKey), message (ERROR, "too many arguments", 0, COORDREF)); END;
To obey the naming requirements of the #define NoDefTableKey NoKey
Types Having Scope PropertiesIn this section we demonstrate types that have a property which is a scope, i.e. a set of object definitions. Examples for such types are records as in Pascal or C, or classes as in object-oriented languages. This task of type analysis is closely related to the name analysis task: The value of such a property is the scope of a certain range, e.g. the definitions of record components, or the members of a class. Variables of such a type may be used in component or member selections, again, a name analysis task. In See Scopes Being Properties of Objects of Name analysis according to scope rules, it is shown how scopes are used as properties of defined entities. Here we extend that concept towards typed objects using record types as an example. A notation for record types is introduced into our language: type record int a; bool b; end r; var r rv, int i; rv.a = 1; i = rv.a;Here, a record type r is defined, a variable vr
of that type is declared, and component selections are used.
The concrete grammar is extended by productions for record type notations and for component selections: TypeDenoter: RecordType. RecordType: 'record' ObjDecls 'end'. Variable: Variable '.' SelectIdent. SelectIdent: Ident.
We use an instance of the See Scope Properties Algol-like of Name analysis according to scope rules, module.
The name analysis role
SYMBOL RecordType INHERITS TypeDenotation, RangeScopeProp COMPUTE SYNT.ScopeKey = SYNT.Type; END; RULE: TypeDenoter ::= RecordType COMPUTE TypeDenoter.Type = RecordType.Type; END;
The selection identifier is bound in a scope that is obtained from
a scope property. Hence, it has the same computational roles as
specified for the
SYMBOL SelectIdent INHERITS IdUseScopeProp, ChkIdUse, IdentOcc, TypedUseId, ChkTypedUseId END; RULE: Variable ::= Variable '.' SelectIdent COMPUTE SelectIdent.Scope = GetScope (Variable[2].Type, NoEnv) <- INCLUDING RootScope.GotScopeProp; Variable[1].Type = SelectIdent.Type; IF (EQ (SelectIdent.Scope, NoEnv), message (ERROR, "selection applied to non record type", 0, COORDREF)); END;Here the scope property for the selection is obtained from the type of the selected variable. The precondition ensures that the scope properties have been set.
|