4 Parameterization and Bounded Parametric Polymorphism

## 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. 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 {
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.

 Thanks to Gail Murphy for suggesting this problem to us.