General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration

Type AnalysisStructural Type Equivalence
The specific rules governing structural equivalence of types vary greatly
from one language to another.
Nevertheless, their effect on the type analysis task can be described in a
manner that is independent of those rules.
That effect is embodied in the
$/Type/StructEquiv.fw
Partitioning the set of typesThis module defines two types as structurally equivalent if they satisfy two conditions:
For example, consider the structure types in the following variable declarations:
struct a { int f; struct a *g; } x; struct b { int h; struct b *i; } y; struct c { struct c *i; int h; } z; The first two have the same components in the same order, but the field names are different. The second and third have the same field names naming the same components, but the order of those components is different. Depending on the rules of the language, either pair could be equivalent or all three could be distinct. A designer specifies possiblyequivalent types by partitioning a subset of the set of types such that all of the types in a particular block of the partition might be equivalent according to the rules of the language. Types assigned to different blocks can never be equivalent. If a type is not assigned to any block, then it is assumed to be unique. An ordered (possibly empty) set of components may be associated with each type when it is assigned to a block.
Let `type' and `set' be definition table keys, and
`components' be a list of definition table keys.
Suppose that the designer chose to assign every structure type to the same
set (represented by a known key), and to list the field types in order of
appearance.
Then variables
Computing equivalence classes
Let `S1',...,`Sp' be the partition established by
invocations of
Computations supplied by the
The blocks `Ei' are the equivalence classes determined by refining
the original partition introduced by The algorithm then selects an arbitrary member of each `Ei' as the representative type for that equivalence class, and alters the properties of the other members of that class so that they act as type identifiers pointing to the key for the representative type (see Dependences among types and type identifiers). This means that the values of an arbitrary property of the key used to represent a type in subsequent computation may not be the value of that property set at a specific instance of a type denotation for that type (see Referring to a type).
Functions as typed entitiesMany languages have the concept that a function is a typed entity. Such a language provides a form of type denotation that can describe function types. Function definitions also implicitly describe function types, since there is usually no way of using a type identifier to specify the type of a function. Thus every function definition must also be considered a type denotation. Function definitions are operator definitions, defining an operator that is used verify the typecorrectness of the function invocation. Because the structural equivalence algorithm will select an arbitrary element to represent the equivalence class, every function type denotation must also define an invoker.
Modula3 has constructs representing type denotations for
function types ( SYMBOL Formals INHERITS OpndTypeListRoot END; SYMBOL ProcTy INHERITS TypeDenotation, OperatorDefs END; RULE: ProcTy ::= 'PROCEDURE' '(' Formals ')' ':' Type COMPUTE .Indic=NewKey(); ProcTy.GotType+= ORDER( ResetInvoker(ProcTy.Type,.Indic), AddTypeToBlock( ProcTy.Type, procClass, ConsDefTableKeyList(Type.Type,Formals.ParameterTypeList))); ProcTy.GotOper+= ListOperator(.Indic,NoOprName,Formals.ParameterTypeList,Type.Type); END; SYMBOL Procedure INHERITS TypeDenotation, OperatorDefs END; RULE: Procedure ::= '(' Formals ')' ':' Type '=' Block COMPUTE Procedure.EqClass=procClass; Procedure.ComponentTypes= ConsDefTableKeyList(Type.Type,Formals.ParameterTypeList); .Indic=NewKey(); Procedure.GotType+= ORDER( ResetInvoker(Procedure.Type,.Indic), AddTypeToBlock( Procedure.Type, procClass, ConsDefTableKeyList(Type.Type,Formals.ParameterTypeList))); Procedure.GotOper+= ListOperator(.Indic,NoOprName,Formals.ParameterTypeList,Type.Type); END; SYMBOL Expr INHERITS ExpressionSymbol END; SYMBOL Actuals INHERITS OpndExprListRoot END; RULE: Expr ::= Expr '(' Actuals ')' COMPUTE ListContext(Expr[1],,Actuals); Indication(GetInvoker(Expr[2].Type,NoKey)); END;
