[Next] [Previous] [Up] [Top] [Contents] [Index]

4.3 Matching Against Type Patterns

4.3.3 The Matching Algorithm

When a method with implicit type parameters is invoked, the system first binds any explicit type parameters to their corresponding actual type parameters and, for each formal with a declared type with a 'Ti <= prefix, binds the Ti type parameter to the dynamic type of the corresponding actual argument. Then the system attempts to match each actual explicit type parameter and each actual argument dynamic type D against its corresponding upper bound type type[param1,...,paramN] (where N may be zero). If the upper bound is a type variable bound elsewhere in the method's header, checking this upper bound constraint is deferred until the type variable is bound. Otherwise, the system searches the supertypes of D to locate one of the form type[ptype1,...,ptypeN], i.e., one with the same "head" type and the same number of parameters, if any, with the additional constraint that if any of the parami is a simple type without a 'T <= prefix, then ptypei = parami. After finding these matching types for each upper bound, the system binds type variables: for each parameter paramj with a 'Tj <= prefix binding, Tj is bound to ptypej. Then the system recursively matches each ptypej against its upper bound, which may bind additional type parameters. Finally, any formal parameter whose upper bound was a type variable is checked. If any of the matches fail, then a type error results. This matching process subsumes subtyping checks: if any of the upper bounds are types with no embedded type variable bindings, the matching process reduces to a simple subtyping check.

For example, consider the following code:

abstract object printable;
	signature print(@:printable):void;

abstract object number isa printable;

abstract object collection[T];
	signature do(c@:collection['T], closure:&(T):void):void;
	method print(c@:collection['T <= printable]):void {
		"[ ".print;
		do(c, &(x:T){ x.print; " ".print; });
		"]".print;
	}
	method expand_tabs(c@:'T <= collection[char]):T {
		-- return a copy of c, where tab characters have been replaced with spaces
	}

abstract object list[T] isa collection[T];
concrete representation nil[T] isa list[T];
template representation cons[T] isa list[T];

abstract object table[Key,Value] isa collection[Value];
abstract object indexed[T] isa table[int,T];
template object array[T] isa indexed[T];
template object string isa indexed[char];
If the message print is sent to an object of dynamic type cons[number], then the print method defined on collection will be found. Then the dynamic type cons[number] will be matched against the pattern collection['T <= printable] to bind the implicit type parameter T. The supertype graph of cons[number] will be searched for a type of the form collection[something]. This search will locate the type collection[number], binding T to the type number. The system then verifies that the binding for T is a subtype of its upper bound printable.

If, on the other hand, the message expand_tabs is sent to an object of dynamic type string, the method defined for collection[char] will be found. The dynamic type string will be matched against the static formal argument type 'T <= collection[char]. This match will succeed, since string is declared as a subtype of collection[char], and the implicit type parameter T will be bound to string.

It is illegal for a type variable to be bound more than once in a particular scope, e.g., in a method's list of explicit type parameters and in the types of its formals. It is also illegal to use a bound type variable as a parameter of an upper bound type before that type variable has been bound by the matching process. This implies that uses of a type variable as parameters must occur at greater "depth" than the binding occurrence of that type variable.

This matching process forms the heart of the semantics of implicit type parameters, and it needs to be formalized in a clearer and less algorithmic way.

The Cecil Language: Specification and Rationale, Version 2.1 - 25 MARCH 1997
[Next] [Previous] [Up] [Top] [Contents] [Index]

Generated with Harlequin WebMaker