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:

- Each `
`Ei`' is a subset of some ``Bj`'. - `
`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;