4.4 F-bounded Polymorphism

This subsection describes an example of advanced use of the Cecil type system, F-bounded polymorphism. As we will see, no special support for this powerful idiom is needed in the type system -- it is made possible by allowing constraints to be recursive, whereby a type variable can appear in its own bound.

For our first example, let us consider an abstract object ordered and a binary method >. A binary method is a method that expects two arguments of similar types; the > method can be applied, for example, to two numbers or two strings, but not a string and a number. We would like to define this method once, in the ordered object, and have other objects, such as num and string, inherit it. The simplest way to achieve it seems to be as follows:

abstract object ordered;
	signature <=(x:ordered, y:ordered):bool;
	method >(x:ordered, y:ordered):bool { not(x <= y) }
extend num isa ordered;
extend string isa ordered;

This code, however, leads to an undesirable effect. Since > and <= are defined for ordered and num and string are its subclasses, we are required to write implementations of <= to compare a num and a string, which we may not want. To avoid mixing of subclasses of ordered, we can apply F-bounded polymorphism as follows:

abstract object ordered[T] where T <= ordered[T];
	signature <=(x:'T, y:'T):bool where T <= ordered[T];
	method >(x:'T, y:'T):bool where T <= ordered[T]
		{ not(x <= y) }
extend num isa ordered[num];
	method <=(x@:num, y@:num):bool { ... }

extend string isa ordered[string];
	method <=(x@:string, y@:string):bool { ... }

Now method > can be instantiated with num for T (because the instantiated constraint num <= ordered[num] can be solved: there is a corresponding declaration in the program) or with string for T, but cannot with (string|num) for T (which would be required in order to compare a num and a string).

With this scheme, in addition to defining binary methods itself, ordered and all its subtypes can inherit binary methods from other objects, for example:

abstract object comparable[T] where T <= comparable[T];
	signature =(x:'T, y:'T):bool where T <= comparable[T];
	method !=(x:'T, y:'T):bool where T <= comparable[T]
		{ not(x = y) }

extend ordered['T] isa comparable[T];
	method =(x@:num, y@:num):bool { ... }
	method =(x@:string, y@:string):bool { ... }

Moreover, num can have subtypes, such as int or float, which can be compared with each other, but not with string or its subtypes:

extend int isa num;
extend float isa num;
3 != 3.14   -- legal 

F-bounded polymorphism can be applied similarly to express families of two or more mutually recursive types. For example, consider a simplified model-view framework, where the model and the view must be able refer to each other and invoke operations on each other.[15] Moreover, instances of the model-view framework, such as a drawing model and a drawing view, must be able to invoke specific operations on each other without loss of type safety. The following code shows how the generic model-view framework can be defined:

abstract object model['M <= model[M,V], 'V <= view[M,V]];
	field views(@:model['M,'V]):set[V] := new_set[V]();
	method register_view(m@:model['M,'V], view:V):void {
		m.views.add(view); }
	method update(m@:model['M,'V]):void {
		m.views.do(&(v:V){
			v.update();
		}); }

abstract object view['M <= model[M,V], 'V <= view[M,V]];
	field model(@:view['M,'V]):M;
	signature update(v@:view['M,'V]):void;

Both model and view are parameterized by the type of the model and the view with the corresponding upper bounds on these two parameters. Correspondingly, the code for the model and view objects is parameterized by the actual types of the instantiation of the framework. For example, the following code instantiates the generic model-view framework to construct a bitmap drawing model and view:

template object drawing isa model[drawing,drawing_view];
	field bitmap(@:drawing):bitmap;
	method set_pixel(m@:drawing, pos:position, value:color):void {
		bitmap.pixel(pos) := value;
		m.views.do(&(v:drawing_view){
			v.update_pixel(pos, value);
		}); }

template object drawing_view isa view[drawing,drawing_view];
	method update(v@:drawing_view):void {
		screen.plot(v.model.bitmap); }
	method update_pixel(v@:drawing_view, pos:position, value:color):void {
		screen.plot_pixel(pos, value); }
	method new_drawing_view(m@:drawing):drawing_view {
		concrete object isa drawing_view { model := m } }

Both drawing and drawing_view add new operations that need to be called by the other type. By parameterizing model as was done, the type of the views field in drawing is known statically to be set of (subtypes of) drawing_view. This knowledge allows the set_pixel operation in drawing to invoke the update_pixel operation without generating either a static type-error or requiring a dynamic "typecase" or "narrow" operation. Similarly, because of the way view is parameterized, the model field in its child drawing_view will be known statically to refer to a (subtype of) drawing, allowing the update operation of drawing_view to access the bitmap field of the model in a statically type-safe manner. Note that it is legal to instantiate model and view with drawing and drawing_view, because the instantiated subtype constraints can be solved successfully.

Alternatively to the unparameterized drawing and drawing_view, the programmer could parameterize them in a way similar to how model and view are parameterized, in order to allow further refinement of these two types. This is similar to having the parameterized ordered subtype of comparable, as opposed to the unparameterized num and string subtypes of ordered, in our earlier examples.