Eli   Documents
Eli: Translator Construction Made Easy

General Information

o Eli: Translator Construction Made Easy
o Global Index
o Frequently Asked Questions
o Typical Eli Usage Errors

Tutorials

o Quick Reference Card
o Guide For new Eli Users
o Release Notes of Eli
o Tutorial on Name Analysis
o Tutorial on Scope Graphs
o Tutorial on Type Analysis
o Typical Eli Usage Errors

Reference Manuals

o User Interface
o Eli products and parameters
o LIDO Reference Manual
o Typical Eli Usage Errors

Libraries

o Eli library routines
o Specification Module Library

Translation Tasks

o Lexical analysis specification
o Syntactic Analysis Manual
o Computation in Trees

Tools

o LIGA Control Language
o Debugging Information for LIDO
o Graphical ORder TOol

o FunnelWeb User's Manual

o Pattern-based Text Generator
o Property Definition Language
o Operator Identification Language
o Tree Grammar Specification Language
o Command Line Processing
o COLA Options Reference Manual

o Generating Unparsing Code

o Monitoring a Processor's Execution

Administration

o System Administration Guide
Mail Home

Type Analysis

Previous Chapter Next Chapter Table of Contents

Structural 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 StructEquiv module, instantiated by 

   $/Type/StructEquiv.fw

Partitioning the set of types

This module defines two types as structurally equivalent if they satisfy two conditions:

  1. They might be equivalent according to the language definition.

  2. Corresponding components have equivalent types.

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 possibly-equivalent 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. AddTypeToBlock(`type',`block',`components') adds type `type' to the partition block defined by `block'. It also sets the DefTableKeyList-valued property ComponentTypes of `type' to `components'.

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 x and y above would have the same type, but z would have a different type. Another possibility would be to generate a unique definition table key on the basis of the sorted list of field identifiers, and then to list the field types in the order of their sorted identifiers. Variables y and z would then have the same type and x would have a different type.

Computing equivalence classes

Let `S1',...,`Sp' be the partition established by invocations of AddTypeToBlock. For each type `t', let `f1(t)',...,`fn(t)' be the ordered list of the component types.

Computations supplied by the StructEquiv module then find the partition {`E1',...,`Eq'} having fewest blocks `Ei' such that:

  1. Each `Ei' is a subset of some `Sj'.

  2. `x' and `y' in `Ei' implies that `fj(x)' and `fj(y)' are in some one `Ek', for all `fj'.

The blocks `Ei' are the equivalence classes determined by refining the original partition introduced by AddTypeToBlock on the basis of the component types.

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 entities

Many 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 type-correctness 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.

Modula-3 has constructs representing type denotations for function types (ProcTy) and function definitions (Procedure) that could be specified as follows (a function invocation is also given): 

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;

Previous Chapter Next Chapter Table of Contents