General Information

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

Tutorials

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

Reference Manuals

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

Libraries

	Eli library routines
	Specification Module Library

Translation Tasks

	Lexical analysis specification
	Syntactic Analysis Manual
	Computation in Trees

Tools

	LIGA Control Language
	Debugging Information for LIDO
	Graphical ORder TOol

FunnelWeb User's Manual

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

Generating Unparsing Code

Monitoring a Processor's Execution

Administration

System Administration Guide

Tutorial on Type Analysis

Function Types

We finally extend our language towards the orthogonal use of functions, i.e. wherever a typed entity is allowed it can have a function type. In particular, evaluation of an expression may yield a function, which may be called, assigned to a variable, passed as an argument, or returned as a function result. For that purpose it is sufficient to add another TypeDenoter which denotes function types. New notations for expressions are not needed.

Here is an example program that defines a function type and a higher order function:

FctTypeExamp[127]==

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 following productions are added to the grammer:

Abstract function type syntax[128]==

RULE: TypeDenoter  ::=    FunctionType END;
RULE: FunctionType ::=    '(' ParamTypes '->' TypeDenoter ')' END;
RULE: ParamTypes   LISTOF ParamType END;
RULE: ParamType    ::=    TypeDenoter END;

This macro is invoked in definition 133.

The specifications for FunctionTypes exactly correspond to those for FunctionHeads in the context of function declarations. An Operator is created, that has a signature as given by the types of the parameters and of the result:

Function type denotation[129]==

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

SYMBOL FunctionType INHERITS TypeDenotation, OperatorDefs END;

RULE: FunctionType ::= '(' ParamTypes '->' TypeDenoter ')' COMPUTE
  FunctionType.GotOper +=
     ListOperator (
       FunctionType.Type,
       FunctionType.Type,
       ParamTypes.OpndTypeList,
       TypeDenoter.Type);

 .moreTypeProperies =
    ORDER
      (ResetTypeName (FunctionType.Type, "function..."),
       ResetTypeLine (FunctionType.Type, LINE));
END;

This macro is invoked in definition 133.

The introduction of function types to our language allows programs to use values which represent functions. They have a function type which must fit to the type required in the context. For example, the apply2 (3.1, add) passes the function add as an argument of the called function apply2. Hence, the type of the declared function add must be equivalent to the type required for the second parameter of apply2 (or coercible under type rules for parameter, as specified in the chapter on functions).

In this case we have to specify structural equivalence of function types, in oder to let the type rules allow such uses of functions. If we would specify name equivalence instead, then for the above example, the signature of the function declaration and the type fct specified for the second parameter of apply2 are different notations of types. They would be considered not to be name equivalent; but, they are structural equivalent.

Structural type equivalence is specified for denotations of function types that either occur in a type denotation or as the signature of a declared function. We state that two types a and b are equivalent if both have the kind FunctionClass, and the component types, which are the types of the parameters and of the result, are elementwise equivalent:

Function type equivalence[130]==

RULE: FunctionHead ::= '(' Parameters ')' TypeDenoter COMPUTE
  FunctionHead.GotType +=
    ORDER (
      AddTypeToBlock (
         FunctionHead.Type, FunctionClass,
         VResetComponentTypes 
           (FunctionHead.Type, 
            ConsDefTableKeyList
              (TypeDenoter.Type, Parameters.OpndTypeList))),
         ResetTypeName (FunctionHead.Type, "function..."),
         ResetTypeLine (FunctionHead.Type, LINE));
END;

RULE: FunctionType ::= '(' ParamTypes '->' TypeDenoter ')' COMPUTE
  FunctionType.GotType +=
    AddTypeToBlock
      (FunctionType.Type, FunctionClass,
         VResetComponentTypes 
           (FunctionType.Type, 
            ConsDefTableKeyList
             (TypeDenoter.Type, ParamTypes.OpndTypeList)))
  <- .moreTypeProperies;
END;

SYMBOL ParamTypes INHERITS OpndTypeListRoot END;
SYMBOL ParamType INHERITS OpndTypeListElem END;

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

This macro is invoked in definition 133.

Function class[131]==

FunctionClass;

This macro is invoked in definition 132.

We require for our language, that a function type f may not directly or indirectly have a component type f, unless the recursion passes through a pointer type. The check is specified in the context of type definitions.

FunctionType.pdl[132]==

Function class[131]

This macro is attached to a product file.

FunctionType.lido[133]==

Abstract function type syntax[128]
Function type denotation[129]
Function type equivalence[130]

This macro is attached to a product file.

FunctionType.con[134]==

Function type syntax[142]

This macro is attached to a product file.