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

4 Parameterization and Parametric Polymorphism

4.2 Implicit Parameterization

While explicit parameterization and instantiation is sufficient for programming parameterized objects and types, it is frequently inconvenient. For example, consider the implementation of an explicitly-parameterized pair_do method:

method pair_do[T1,T2](c1@:cons[T1], c2@:cons[T2],
                      closure:&(T1,T2):void):void {
	eval(closure, head[T1](c1), head[T2](c2));
	pair_do[T1,T2](tail[T1](c1), tail[T2](c2), closure);
}
Singly-dispatched languages do not face this verbosity, because methods are defined within a class and within the scope of the parameterized class's type parameters. Additionally, invocations of methods on a parameterized object, such as the head message above, would not need to specify an instantiating parameter because it can be derived from the instantiating parameter of the distinguished receiver object. The following pseudo-code is representative of the kind of support found in singly-dispatched languages:

class cons[T] {
	field head:T;
	field tail:list[T];
	method length():int { 1 + tail.length() }	
	...
}
In this code, the formal type parameter T is introduced in the cons class declaration and is scoped over all fields and methods defined on the class. Consequently, none of these fields and methods need be explicitly parameterized, and the recursive length call need not pass any explicit type parameters, since it is implied by the type of the receiver expression.

To regain much of the conciseness of parameterization in singly-dispatched languages while still supporting multi-methods, object extensions, and other of Cecil's more flexible constructs, Cecil allows implicit type parameter bindings to be present in the type declarations of formal arguments of a method or field. These implicit type parameters are instantiated automatically with the corresponding type of the actual argument in each call site. A binding occurrence of such an implicit type variable is indicated by prefixing the type name with a back-quote character; other occurrences of the type variable simply name the bound type.

The operations on parameterized cons objects can be rewritten with implicit type parameters as follows:

template representation cons[T] isa list[T];
	field head(@:cons['T]):T;
	field tail(@:cons['T]):list[T] := nil[T];
	method pair_do(c1@:cons['T1], c2@:cons['T2],
	               closure:&(T1,T2):void):void {
		eval(closure, head(c1), head(c2));
		pair_do(tail(c1), tail(c2), closure);
	}
	method prepend(h:T, t:list['T]):list[T] {
		concrete object isa cons[T] { head := h, tail := t } }
Like explicit formal type parameters, an implicit formal type parameter may be bounded from above by some type using the <= type notation, and an implicit formal parameter is quantified over all types that are subtypes of its upper bound (where any is used as the default upper bound). Like explicit type parameters, implicit type parameters are scoped over the entire declaration. An implicit type parameter must have a name that is distinct from any other implicit or explicit type parameters. Like explicit type parameters, implicit type parameters may be used in the type declarations of earlier formal arguments, as in the prepend method above, as long as no cyclic dependencies result. Implicit type parameters are akin to polymorphic type variables in languages like ML [Milner et al. 90]. Note that unlike 'a type variables in ML, the back-quote in Cecil's 'T is not part of the type name, but rather identifies that the use of the type T is a binding occurrence as opposed to a simple use of a previously-defined type.

Implicit type parameters are useful not only for parameterized types but also for performing simple calculations on argument types to compute appropriate result types. For example, the following method describes its result type in terms of its argument types:[16]

method min(x1:'T1 <= comparable, x2:'T2 <= comparable):T1|T2 {
	if(x1 < x2, { x1 }, { x2 }) }
User-defined control structures often compute the types of their results from the types of their arguments:

signature if(condition:bool, true_case:&():'T1, false_case:&():'T2):T1|T2;
method if(condition@:true,  true_case:&():'T1, false_case:&():void):T1 {
	eval(true_case) }
method if(condition@:false, true_case:&():void, false_case:&():'T2):T2 {
	eval(false_case) }
As illustrated by the above examples, least-upper-bound types over implicit type parameters are relatively common when expressing the type of a method's result in terms of its arguments' types.

Implicit type parameter bindings can only appear in the declared type of a formal parameter or variable, as the upper bound type of another type parameter, or as the instantiating parameter of a parameterized object or type being augmented in an extension declaration. A type that can contain an implicit type parameter binding is called a type pattern. The syntax of several constructs is updated to reflect where implicit type parameter bindings are legal:

type_pattern	::=	binding_type
	|	named_type_p
	|	closure_type_p
	|	lub_type
	|	glb_type
	|	paren_type
binding_type	::=	"'" name ["<=" type_pattern]
named_type_p	::=	name [param_patterns]
closure_type_p	::=	"&" "(" [arg_type_ps] ")" [type_decl_p]
signature_decl	::=	"signature" method_name
		    "(" [arg_type_ps] ")" [type_decl] ";"
field_sig_decl	::=	["var"] "field" "signature" msg_name [formal_params]
		    "(" arg_type_p ")" [type_decl] ";"
arg_type_ps	::=	arg_type_p { "," arg_type_p }
arg_type_p	::=	[name ":"] type_pattern
specializer	::=	location [type_decl_p]	specialized formal
	|	[type_decl_p]	unspecialized formal
	|	"@" ":" named_object_p	sugar for @named_obj_p :named_obj_p
closure_formal	::=	[name] [type_decl_p]	formal names are optional, if never referenced
type_ext_decl	::=	"extend" "type" named_type_p {type_relation} ";"
obj_ext_decl	::=	"extend" extend_kind named_object_p
		    {relation} [field_inits] ";"
type_relation	::=	"subtypes" type_patterns
parents	::=	named_object_p { "," named_object_p }
named_object_p	::=	name [param_patterns]
type_decl_p	::=	":" type_pattern
formal_param	::=	["'"] name [ "<=" type_pattern ]
param_patterns	::=	"[" type_patterns "]"
type_patterns	::=	type_pattern { "," type_pattern }
[16] Section 4.7 will revise this version of min to use a more sophisticated comparable type.
The Cecil Language: Specification and Rationale, Version 2.1 - 25 MARCH 1997
[Next] [Previous] [Up] [Top] [Contents] [Index]

Generated with Harlequin WebMaker