Next: , Up: RootType

10.1 Dependences among types and type identifiers

Consider the following Mystery program: 

     VAR Length: Measurement;
     TYPE Measurement = Inches;
     TYPE Inches = INTEGER;
     BEGIN Length = 3; PRINT Length + 7 END;

This program is correct according to the semantics we have postulated for Mystery (see Overview):

  1. Type identifiers are statically bound, with the scope of a declaration being the entire block. Thus all of the type identifier occurrences have valid bindings.
  2. There is no constraint on the form of the Type appearing on the right-hand side of a type definition. Thus both of the type definitions are valid.

The type analysis of each of the two occurrences of Length in the last line of the program is described by the following specifications discussed earlier: 

     SYMBOL ExpIdUse INHERITS TypedUseId, ChkTypedUseId END;
     
     RULE: Expr ::= ExpIdUse
     COMPUTE PrimaryContext(Expr,ExpIdUse.Type);
     END;

The value of ExpIdUse.Type should be intType, the known definition table key created for the language-defined integer type. Recall that intType was associated with the Mystery keyword INTEGER by the following specification (see Establishing language-defined types): 

     RULE: Type ::= 'INTEGER'
     COMPUTE Type.Type=intType;
     END;

The problem is to make the intType value of the Type.Type attribute in this context the value of the ExpIdUse.Type attribute in the context quoted above.

A human has no trouble seeing how this problem could be solved:

  1. The type definition rule sets the TypIdDef.Type attribute of the occurrence of Inches in the third line of the program to intType.
  2. The value of a property of the Inches entity could be set from the value of the TypIdDef.Type attribute in that context.
  3. That property could be used to set the TypIdUse.Type attribute of the occurrence of Inches in the second line of the program.
  4. The type identifier use rule sets the value of the Type.Type attribute in that context the value of the TypIdUse.Type attribute.
  5. Similar reasoning results in the value of the Type.Type attribute in the variable definition context of the first line of the program becoming intType.
  6. Finally, a property of the Length entity is set in the context of the first line of the program and used to make intType the value of the ExpIdUse.Type attributes in the two contexts of the last line.

Unfortunately, this solution is based on the human's ability to see the dependence among the type identifiers and process the lines of the program in an order determined by that dependence. One cannot, for example, blindly process the lines in the order in which they were written.

The dependence among the lines in our example is a result of our use of the known key intType as the value of a property of the type identifier entities. This strategy is actually an example of a premature evaluation: There is no need to know the key representing the type of Length until the ExpIdUse.Type attribute is evaluated. We can avoid the constraint on the order of rule processing by a “lazy evaluation” strategy in which we use properties of the type identifier entities to establish a means for determining the value of the ExpIdUse.Type attribute rather than establishing the value itself.

There are three possible Type contexts in Mystery: a keyword, a type denotation, and a type identifier. In the first two, we can set the value of the Type.Type attribute to the definition table key for the type itself. In the third, however, the only information that we are guaranteed to have is the definition table key for the type identifier. However, this information is sufficient to find the definition table key for the type once all of the type identifiers have been defined. Thus we can simply set the value of the Type.Type attribute to the definition table key for the type identifier itself in this context.

The computation provided by the Typing module for the TypeDefDefId context sets a property of the type identifier entity to the value of the TypeDefDefId.Type attribute (see Defining and using type identifiers). Effectively, this computation creates a linear list of type identifier entities ending in a type entity. In our example, the value of this property of the identifier Length's definition table key would be the definition table key of the identifier Measurement. The value of its property would be the definition table key of the identifier Inches, whose property would be intType.

When all of the entities corresponding to type identifiers have this property set, the definition table key for a type should be the last element of each list. The Typing module uses an instance of the Defer module (see Deferred Property Association) to provide this computation for the TypeDefUseId context.

There is no guarantee, of course, that the last element of the list is actually a type. For example, consider the following incorrect Mystery program: 

     VAR Length: Measurement;
     TYPE Measurement = Inches;
     VAR Inches: INTEGER;
     BEGIN Length = 3; PRINT Length + 7 END;

Here the last element of the list beginning at Measurement would be Inches, a variable identifier. The ChkTypeDefUseId role checks the IsType property (see Typed Entities) of the key that is the last element of the list to report errors of this kind.

The Typing module establishes RootType.GotType as the post-condition for setting all Type.Type properties and linkages among type identifiers.