Eli   Documents

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

Tutorial on Type Analysis

Previous Chapter Next Chapter Table of Contents


Union Types

We introduce union types to our language in order to demonstrate how subtype relations and their coercions are specified. A union type is described by a sequence of type denotations, which constitute the subtypes of the specified union type. A value of one of the subtypes can be coerced to the union type. A value of a union type can be treated as a value of one of the subtypes using a cast operation or a case statement.

Here is an example program that defines and uses a union variable named rv:

UnionExamp[75]==

begin
  var   union int, bool end rv;
  var   int j, bool c;
  rv = 42; rv = true;
  j = <int> rv;
  case rv of
    int t: j = t;
    bool t: c = t;
  end
end
This macro is attached to a product file.

In the case statement the case expression has a union type. Each case declares a variable of a subtype of that union type. The branch which corresponds to the current type of the case expression is selected, its variable is initialized with the value of the case expression, and the statement is executed.

The following productions describe union types, type casts, and case statements: Abstract union syntax[76]==

RULE: TypeDenoter ::= UnionType END;
RULE: UnionType  ::= 'union' UnitedTypes 'end' END;
RULE: UnitedTypes LISTOF UnitedType END;
RULE: UnitedType ::= TypeDenoter END;

RULE: Expression ::= '<' TypeDenoter '>' Expression END;

RULE: Statement ::= CaseStmt END;
RULE: CaseStmt ::= 'case' Expression 'of' Cases 'end' END;
RULE: Cases LISTOF Case END;
RULE: Case ::= ObjDecl ':' Statement END;
This macro is invoked in definition 88.

The following computations introduce a type denoter for union types and associate properties for test output to it: In order to check whether a type is a union type, as required for example in a case statement, we introduce a property IsUnionType. Is union type[77]==

IsUnionType: int;
This macro is invoked in definition 87.

Union type denoter[78]==

SYMBOL UnionType INHERITS TypeDenotation END;

RULE: UnionType ::= 'union' UnitedTypes 'end' COMPUTE
  .GotTypeProp =
      ORDER (
        ResetIsUnionType (UnionType.Type, 1),
        ResetTypeName (UnionType.Type, "union..."),
        ResetTypeLine (UnionType.Type, LINE));
END;

RULE: TypeDenoter ::= UnionType COMPUTE
  TypeDenoter.Type = UnionType.Type;
END;
This macro is invoked in definition 88.

For the comparison of union types stuctural equivalence is specified, such that the fact that it is a union type and the sequence of subtypes are relevant for type equality. UnionClass is the the set containing all union types for initialization of the equivalence check.

Union type class[79]==

UnionClass;
This macro is invoked in definition 87.

The UnionClass and the sequence UnitedTypes.OpndTypeList are used as arguments of AddTypeToBlock to specify type equivalence of union types. Property ComponentTypes is set accordingly:

Union type equality computation[80]==

RULE: UnionType ::= 'union' UnitedTypes 'end' COMPUTE
  UnionType.GotType +=
      AddTypeToBlock 
        (UnionType.Type, UnionClass, 
         VResetComponentTypes (UnionType.Type, UnitedTypes.OpndTypeList))
      <- .GotTypeProp;
END;

SYMBOL UnitedTypes INHERITS OpndTypeListRoot END;
SYMBOL UnitedType  INHERITS OpndTypeListElem END;

RULE: UnitedType ::= TypeDenoter COMPUTE
  UnitedType.Type = TypeDenoter.Type;
  UnitedType.DefTableKeyElem = UnitedType.Type;
END;
This macro is invoked in definition 88.

Note, that here the order of the subtypes in the type denoter is relevant for type equality. If that is not desired, one could for example sort the list of the component types in a canonical order before using it as an argument of AddTypeToBlock.

For each union type we introduce two groups of conversion operators: A widening coercion from each subtype type to the union type, and a down cast from the union type to each subtype. For the latter an indication has to be introduced: Downcast indication[81]==

DownCast;
UnionWiden;
This macro is invoked in definition 87.

As a pair of operators has to be introduced for each subtype, the context of the subtype denoter is the right place to do it. The coercion operator is not created explicitly; it is only stated that the subtype is Coercible to the union type. The down cast conversion is introduced as a MonadicOperator:

Widening coercion computation[82]==

SYMBOL UnitedType INHERITS OperatorDefs COMPUTE
  SYNT.GotOper +=
    ORDER
      (Coercible (UnionWiden, THIS.Type, INCLUDING UnionType.Type),
       MonadicOperator
        (DownCast, NewKey(), 
         INCLUDING UnionType.Type, THIS.Type));
END;
This macro is invoked in definition 88.

The context of the down cast construct imposes a requirement on the type of the operand expression. Any conversion operator of the DownCast indication can be applied to the operand expression, in addition to any coercions, to satisfy this requirement:

Down cast[83]==

RULE: Expression ::= '<' TypeDenoter '>' Expression COMPUTE
  CastContext (Expression[1], , Expression[2], TypeDenoter.Type);
  Indication (DownCast);
END;
This macro is invoked in definition 88.

In a case statement it is required that the case expression has a union type:

Union case statement[84]==

SYMBOL CaseStmt: Type: DefTableKey;

RULE: CaseStmt ::= 'case' Expression 'of' Cases 'end' COMPUTE
  CaseStmt.Type = Expression.Type;

  IF (NOT (GetIsUnionType (Expression.Type, 0)),
  message (ERROR, "Case expression must have a union type",
           0,COORDREF))
  <- INCLUDING Program.TypeIsSet;
END;
This macro is invoked in definition 88.

Each branch of a case statement forms a range for the declaration of the variable that gets the value of the case expression if that case is selected. It is required that the type of the variable is a subtype of the type of the case expression. We here require that it is coercible to the type of the case expression, although that is not quite exact. Union case[85]==

SYMBOL Case INHERITS RangeScope END;

RULE: Case ::= ObjDecl ':' Statement COMPUTE
  IF (NOT (IsCoercible 
             (ObjDecl.Type, INCLUDING CaseStmt.Type)),
  message (ERROR, "Must be a subtype of the case expression",
           0, COORDREF))
  <- INCLUDING Program.GotType;
END;
This macro is invoked in definition 88.

In other contexts ObjDecl occurs in a CHAIN. To avoid an error message on missing a chain start we apply the role OpndTypeListRoot here, which has the CHAINSTART, although that role is not needed:

Union CHAIN workaraound[86]==

SYMBOL Cases INHERITS OpndTypeListRoot END;
This macro is invoked in definition 88.

Union.pdl[87]==

Is union type[77]
Union type class[79]
Downcast indication[81]
This macro is attached to a product file.

Union.lido[88]==

Abstract union syntax[76]
Union type denoter[78]
Union type equality computation[80]
Widening coercion computation[82]
Down cast[83]
Union case[85]
Union case statement[84]
Union CHAIN workaraound[86]
This macro is attached to a product file.

Union.con[89]==

Concrete union syntax[144]
This macro is attached to a product file.


Previous Chapter Next Chapter Table of Contents