General Information

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

Tutorials

 o Quick Reference Card
 o Guide For new Eli Users
 o Release Notes of Eli
 o Tutorial on Name Analysis
 o Tutorial on Type Analysis

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual

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

 Questions, Comments, ....

Tutorial on Type Analysis

Previous Chapter Table of Contents


Function Types

We finally extend our language towards the orthogonal use of functions, i. e. wherever a typed object is allowed it can have a function type. For that purpose we add another TypeDenoter which denotes function types.

The following concrete productions are added:

FunctType.con[69]==


TypeDenoter:    FunctionType.
FunctionType:   '(' ParamTypes '->' TypeDenoter ')'.
ParamTypes:     [ParamType // ','].
ParamType:      TypeDenoter.

This macro is attached to a product file.

Here is an example program that defines a function type and a higher order function: FctTypeExamp[70]==

begin
  fun mul (int x, real y) real
  begin return x * y; end;

  fun add (int x, real y) real
  begin return x + y; end;

  type (int, real -> real) fct;

  fun apply2 (real z, fct ff) real
  begin return ff (2, z); end;

  var real r;

  r = apply2 (3.1, add);
  r = apply2 (3.1, mul);
end

This macro is attached to a product file.

The introduction of function types to our language requires that we state rules for the structural equivalence of function types. Otherwise the type rules would not allow one, for example, to assign a function to a function variable, or to pass it as an argument to a function. The involved types are represented by different type keys. Hence, we extend the insertion point of the EqualTypes function, as in the case of pointer types. The inserted code fragment is applicable if the type t1 is a function type, i. e. the ResultType property is set. If type t2 is a function type, too, both types are decomposed and its components are checked for being pairwise equal.

Function.EqualTypes.phi[71]==


{ /* function types: */
  DefTableKey tr1, tr2;
  tr1 = TransDefer (GetResultType (t1, NoKey));
  if (tr1 != NoKey) 
  { /* tr1 is a function type */
    DefTableKeyList pr1, pr2;
    /* ensure termination: */
    if (InFunctionType (t1, t1)) return 0;
    if (!EqualTypes (tr1, GetResultType (t2, NoKey)))
       return 0; /* tr2 is not a function type */
    if (InFunctionType (t2, t2)) return 0;
    pr1 = GetParamTypes (t1, NULLDefTableKeyList);
    pr2 = GetParamTypes (t2, NULLDefTableKeyList);
    if (0 == CompDefTableKeyList (pr1, pr2, CmpTypes))
       return 1;
  }
}/* end function types */

This macro is attached to a product file.

Here again, we have to make sure that the check terminates if, in erroneous cases, the function type refers to itself using a function InFunctionType. Furthermore, the comparison of the parameter type lists using the function CompDefTableKeyList requires a specific function for element comparison, here CmpTypes. Both function definitions and the header of InFunctionType are supplied to the two insertion points of the type checking module using the .phi mechanism.

Function.TypeFct.phi[72]==


#ifdef PROTO_OK
int InFunctionType (DefTableKey t1, DefTableKey t2)
#else
int InFunctionType (t1, t2) DefTableKey t1, t2;
#endif
/* On exit
 *    returns 1 if t2 is a function type that contains t1;
 *    otherwise 0 is returned.
 */
{ DefTableKey t; DefTableKeyList tl;
  t1 = TransDefer (t1);
  t2 = TransDefer (t2);
  t = TransDefer (GetResultType (t2, NoKey));
  if (t != NoKey) {
        if (t == t1) return 1;
        if (InFunctionType (t1, t)) return 1;

        tl = GetParamTypes (t2, NULLDefTableKeyList);
        while (tl) {
                t = TransDefer (HeadDefTableKeyList (tl));

                if (t == t1) return 1;
                if (InFunctionType (t1, t)) return 1;

                tl = TailDefTableKeyList (tl);
        }
  }
  return 0;
}

static
#ifdef PROTO_OK
int CmpTypes (DefTableKey t1, DefTableKey t2)
#else
int CmpTypes (t1, t2) DefTableKey t1, t2;
#endif
{
  return (EqualTypes (t1, t2) ? 0 : 1);
}

This macro is attached to a product file.

Function.TypeFctHdr.phi[73]==


extern int InFunctionType ELI_ARG((DefTableKey t1, DefTableKey t2));

This macro is attached to a product file.

The composition of the function type representation follows the same pattern as used in function declarations.

We need a check that prohibits a function type directly or indirectly refer to itself, using the function InFunctionType.

FunctType.lido[74]==


RULE: TypeDenoter ::= FunctionType COMPUTE
  TypeDenoter.Type = FunctionType.Type;
END;

SYMBOL FunctionType INHERITS TypeDenotation END;

RULE: FunctionType ::= '(' ParamTypes '->' TypeDenoter ')' COMPUTE
  FunctionType.GotType = 
    ResetParamTypes
      (KResetResultType
         (KResetTypeName (FunctionType.Type, "function..."),
          TypeDenoter.Type),
       ParamTypes.DefTableKeyList);

  IF (InFunctionType (FunctionType.Type, FunctionType.Type),
  message (ERROR, "recursive function type", 0, COORDREF))
  <- INCLUDING Program.GotType;
END;

SYMBOL ParamTypes INHERITS DefTableKeyListRoot END;
SYMBOL ParamType INHERITS DefTableKeyListElem END;

RULE: ParamType ::= TypeDenoter COMPUTE
  ParamType.DefTableKeyElem = TypeDenoter.Type;
END;

This macro is attached to a product file.


Previous Chapter Table of Contents