8 Structural Type Equivalence

Up to this point we have tacitly assumed that each type denotation represents a distinct user-defined type. This assumption cannot hold for a language like Mystery, which allows user-defined procedure types and yet requires that a procedure denotation include the procedure's signature. Such languages must regard two procedures to be of the same type if they have the same signatures, even though each signature is a distinct type denotation. In other words, procedure types that have the same structure are equivalent.

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 Typequ module, a replacement for the Typing module. It is instantiated by

        $/Type/Typequ.gnrc +referto=KEY :inst

The referto parameter modifies the names of Key attributes, and has to be the same as the referto parameter used for the module instance that supplies those key attributes.

All of the techniques discussed in this document apply independently of the selection of name equivalence among user-defined types (by instantiating the Typing module) or structural equivalence (by instantiating the Typequ module). Exactly one of these two modules must be instantiated in order to use any of the other modules discussed in this document.

The Typequ module assumes that the set of all type denotations is partitioned into disjoint blocks such that all of the members of a block represent equivalent types. It selects an arbitrary member of each block as the representative type, and alters the properties of the other members of that block so that they act as type identifiers pointing to the key for the representative type (see Dependences among types and type identifiers).

There are two kinds of information that must be supplied to the module:

• For each type denotation `t', an ordered list `f1(t)',...,`fn(t)' of the types of any parameters or components.
• An initial partition of the set of all type denotations into disjoint blocks `B1',...,`Bp'.

Computations supplied by the module find the coarsest (having fewest blocks) partition {`E1',...,`Eq'} such that:

1. Each `Ei' is a subset of some `Bj'.
2. `x' and `y' in `Ei' implies that `fj(x)' and `fj(y)' are in some one `Ek', for all `fj'.

The Typequ module provides two additional attributes of the TypeDenotation node to carry the information for the structural equivalence computation:

ComponentTypes

An ordered list of definition table keys representing the parameters or components of the type represented by the Type attribute. A default computation in the lower context of the TypeDenotation node sets TypeDenotation.ComponentTypes to the empty list. Thus, by default, a type has no parameters or components.

EqClass

A definition table key representing the block `Bj' of the initial partition that contains the type represented by the Type attribute. A default computation in the lower context of the TypeDenotation node sets TypeDenotation.EqClass to a new definition table key. Thus, by default, no other types could be equivalent to this one.

The remainder of this chapter gives a specification for Mystery that will make subrange types equivalent when they have the same bounds, array types equivalent when they have equivalent index types and equivalent element types, and procedure types equivalent when they have equivalent parameter types corresponding positions and equivalent result types. As noted in the introduction to this document, the specifications are limited to the direct type analysis computations. A complete definition for Mystery can be found elsewhere (see Overview).

Subrange types have no parameters or components, so the blocks of the initial partition that contain such types will never be split. A subrange type belongs to a block of the initial partition if and only if its bounds are the same as those of the other subrange types in that block. Thus the default computation for the TypeDenotation.ComponentTypes attribute suffices, but the TypeDenotation.EqClass must be set depending on the bounds:

     RULE: SubrTy ::= '[' Number 'TO' Number ']'
     COMPUTE SubrTy.EqClass=SubrEqCl(SubrTy.Lower,SubrTy.Upper);
     END;

SubrEqCl is a function defined in the Mystery specification to associate a unique definition table key with each distinct bound pair (see Subrange Types).

Array types have two components, the index type and the element type. These are the only aspects that distinguish one array type from another, so one block of the initial partition can contain all array types. Thus the default computations for both TypeDenotation.ComponentTypes and TypeDenotation.EqClass must be overridden:

     RULE: ArrayTy ::= 'ARRAY' Type 'OF' Type
     COMPUTE
       ArrayTy.EqClass=arrayClass;
       ArrayTy.ComponentTypes=
         ConsDefTableKeyList(
           Type[1].Type,
           SingleDefTableKeyList(Type[2].Type));
     END;

Procedure types have an arbitrary number of parameters and a result type. The computations provided by the Typequ module first split initial partition blocks on the basis of the number of parameters or components each type has, so one block of the initial partition can contain all procedure types. Thus the default computations for both TypeDenotation.ComponentTypes and TypeDenotation.EqClass must be overridden:

     RULE: ProcTy ::= 'PROCEDURE' '(' Formals ')' ':' Type
     COMPUTE
       ProcTy.EqClass=procClass;
       ProcTy.ComponentTypes=
         ConsDefTableKeyList(Type.Type,Formals.ParameterTypeList);
     END;
     
     RULE: Procedure ::= '(' Formals ')' ':' Type '=' Block
     COMPUTE
       Procedure.EqClass=procClass;
       Procedure.ComponentTypes=
         ConsDefTableKeyList(Type.Type,Formals.ParameterTypeList);
     END;