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

4 Parameterization and Bounded Parametric Polymorphism

It is often necessary to express some assumptions or restrictions on type parameters. For example, a `sort`

method can only sort collections whose elements can be compared with each other. A `matrix_multiply`

method may require that matrix elements be numbers. This situation is known as bounded polymorphism [Cardelli & Wegner 85]. Cecil supports bounded polymorphism by allowing *type constraints* on type parameters.

There are two kinds of type constraints in Cecil. A *subtype constraint* specifies the requirement that one type be a subtype of another. A common use of subtype constraints is to specify upper or lower bounds of type variables. In the following example, the type of matrix elements is constrained to be a subtype of `num`

:

methodmatrix_multiply(a:matrix['T], b:matrix['T]):matrix[T]whereT<=num { ... }

A *signature constraint* specifies the requirement that the given signature hold. A common use of signature constraints is to require certain operations to be provided for the type parameters. In the following example, the message send of `<=`

in the body of `sort`

is guaranteed to be legal as long as the constraint is satisfied:

methodsort(a:array['T]):voidwhere signature<=(T,T):bool { ...leta_i:T := a!i;leta_j:T := a!j; if(a_i <= a_j, {... swap}); ... }`a!i and a!j ...`

Type constraints are allowed in the `where`

part of the `forall`

clause and in a `where`

clause following the header of a declaration. The common case of the subtype constraints, type variables' upper bounds, are also allowed wherever that type variable is introduced (in a `forall`

clause, using the backquote sugar, or as an explicit type parameter).

type_cxt ::= "forall" formal_param { "," formal_param }[type_cons]":" type_cons ::= "where" type_constraint { "," type_constraint } type_constraint ::= sub_constraint | sig_constraint sub_constraint ::= type ("<=" | ">=") type sig_constraint ::= "signature" (msg_name [params] | op_name) "(" [arg_types] ")" type_decl name_binding ::= name[">=" type] ["<=" type]tp_decl ::= [type_cxt] [privacy] "type" name [formal_params] {type_relation}[type_cons]";" object_decl ::= [type_cxt] [privacy] rep_role rep_kind name [formal_params] {relation}[type_cons][field_inits] ";" predicate_decl ::= [type_cxt] [privacy] "predicate" name [formal_params] {relation}[type_cons][field_inits] ["when" expr] ";" type_ext_decl ::= [type_cxt] [privacy] "extend" "type" named_type[type_cons]{type_relation} ";" obj_ext_decl ::= [type_cxt] [privacy] "extend" extend_kind named_object {relation}[type_cons][field_inits] ";" signature_decl ::= [type_cxt] [privacy] "signature" method_name "(" [arg_types] ")" [type_decl][type_cons]";" method_decl ::= [type_cxt] [privacy] impl_kind method_name "(" [formals] ")" [type_decl][type_cons]{pragma} "{" (body | prim_body) "}" [";"] field_sig_decl ::= [type_cxt] [field_privacy] ["var"] "field" "signature" msg_name [formal_params] "(" arg_type ")" [type_decl][type_cons]";" field_decl ::= [type_cxt] [field_privacy] ["shared"] ["var"] "field" field_kind msg_name [formal_params] "(" formal ")" [type_decl][type_cons]{pragma} [":=" expr] ";"

The `matrix_multiply`

method in the above example can be re-written more concisely as follows (this sacrifices the visual symmetry between the arguments `a`

and `b`

, but is semantically equivalent, because it introduces exactly the same type variable and constraint):

methodmatrix_multiply(a:matrix['T<=num], b:matrix[T]):matrix[T] { ... }

The `@:`

syntactic sugar is extended to allow a type variable with an upper bound. This idiom is used when it is desirable to give a more precise type to a formal that is specialized on some object (and the type of the formal is expected to subtype the specializer object). For example,

methodfoo(x@:'T<=bar):T { ... }

desugars into

methodfoo(x@bar:'T<=bar):T { ... }

It is a useful programming idiom to associate constraints with parameterized types. For example, the type of a binary search tree may require that the comparison operation be defined on the type of the tree element, similarly to the sorting method above:

template objectbinary_tree[T]wheresignature<=(T,T):bool;

Cecil provides a syntactic sugar that automatically inserts these associated constraints. If a backquoted type variable is used as an explicit instantiating parameter of a parameterized type, the constraints that the type associates with its explicit parameter in the corresponding position are imposed on the type variable. For example, in the following method:

methodinsert(t@:binary_tree['T], elm:T):void { ... }

the constraint `where signature <=(T,T):bool`

is automatically added, so in the body of `insert`

it is legal to send the message `<=`

to tree elements and `elm`

.

"The Cecil Language: Specification and Rationale" - 7 Feb 1999

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

Generated with Harlequin WebMaker