Parameterised Types

[Hans-Dieter Dreier]

Matthew Tuck schrieb:

> This message is about what I think about parameterised types (generics),
> specifically about their type parameters.
>
> Background
> ----------
>
> Parameterised types are types that have members that can vary from
> object to object, but are fixed for the lifetime of the object.  The
> canonical example of a parameterised type is a collection, which works
> something like this (using a list collection):
>
> type List <Element: class>
>    proc AddTail( X: ro Element )
>    ...
>
> ...
>
> a: List <Integer>

It should be stated *why* parameterized types need to be fixed for the
lifetime of the object: It's because they are used in constraints that are
evaluated at compile time. It the type parameter were allowed to change at
run time, these constraints would need be evaluated at runtime as well,
resulting in dynamic type checking and other complications.

Therefore, if a type parameter is not used in a constraint that is evaluated
at compile time, it need not be constant. The type declaration then becomes
something like the template mechanism we already talked about (primarily for
GUI classes).

Conceptually, for me type parameters are instance items. Strictly speaking,
List <Integer> and List <SomethingElse> are actually the same type, but each
of them may or may not be used in some context because their different
parameterization results in different constraints. Those may or may not
evaluate to true in some context. Example:

List <GeneralObject> a ;
List <SpecialObject> b;

b may be used as a data source where a can be used because in this case the
contents of a may be substituted by the contents of b. So it is legal to
write

a = b;

but it is illegal to write

b = a;

The implementation of our parser may of course *assume* that there is such a
constraint if a type parameter is of type type because this will most often
be the case. Then things may probably be simplified by making the value of
this type a part of the type name of the parametrized type (similar to name
decoration in C++). But if we do this, we should keep in mind that it is a
mere simplification and not a concept in its own right.

> This background has covered parameterising types with other types,
> however you can also parameterise by normal data.  For example, a
> dynamic array (an array whose bounds are not fixed at compile-time but
> are at allocation time), would be parameterised by either 1 (eg C) or 2
> (eg Ada) index bounds, plus indexed by an element type.

The bounds may even be changed at runtime, resulting in a reallocation. Some
programming languages allow this. I always found it very convenient to use.

> ...
>
>
> type Assign <A, B, C, D, E, F> : A, B < C, D, E < F
>
> An illustration of a complicated constraint unlikely to be seen in
> practice.  I've done two things here - allow multiple "<" to be chained
> with the meaning the same as in maths, and allowed multiple parameters
> in between the "<"s.  The meaning of this is that every element left of
> "<" is a subtype of every element right of "<".

I'd suggest to write

type Assign <A, B, C, D, E, F> : (A, B) < (C, D, E) < F

to clarify operator precedence, if we choose to use such a notation at all.
And if we use it, it should be usable everywhere a comparison is allowed.

> Subtype Type Parameters
> -----------------------
>
> A "subtype type parameter" is specified by the subtype of the type
> rather than the client.

For me, this would be a (constant) virtual instance item. If the
parameterized type would be declared by normal subtyping, no special syntax
would be needed (the type needs its own name to distinguish it from the base
type anyway). Just the virtual instance item needs to be overridden.

>From this it follows that types with subtype type parameters are *different*
types derived from the same super type, as opposed to "normal" parameterized
types which are different instances of the *same* type (with different
instance items, hence constraints evaluate to different values).

> Subtype type parameters are a solution to the problems of covariance and
> contravariance.  The classical example of this is as follows:
>
> type Animal
>    proc Eat(X: ro Food)
>
> type Cow
>    proc Eat(X: ro Grass)
>
> We expect a cow to be a subtype of Animal, yet we expect it to only eat
> grass.  But this is not type safe since if we had an animal variable and
> it happened to contain a cow, we might try and feed it an apple since
> the
> signature of Animal.Eat expects any food.
>
> Languages take different positions on this.  Most don't allow the type
> to change (invariance), Eiffel allows it to be a subtype (covariance)
> and takes various steps to prevent the problems, Sather allows it  to be
> a supertype (contravariance) since it is type safe, even if it doesn't
> really make sense.

Contravariance is what I would allow by default. But we should also allow
constraints that are checked at runtime (since this cannot be checked at
compile time due to its dynamic nature), and the compiler would take their
results into account. So we could place a runtime constraint on the
parameter of the Eat method and the compiler would take it into account even
if it cannot be evaluated at compile time. Details of this idea need to be
worked out, however.

> It is important to recognise generic parameters and generic constraints
> are inherited.  Hence they must be consistent - e.g. "FoodType < Grass"
> is consistent with "FoodType < Food".  This is true for both times of
> type parameter.

Just as all constraints are inherited. Nothing special about it here.

> Perhaps my syntax could be improved - for example, merging the client's
> parameter specification mechanism with that of the subtypes' to reflect
> their similarity better.

I'd suggest to use normal function syntax, ie write

AnIntegerArray = new Array (Integer);

instead of

AnIntegerArray = new Array <Integer>;

We can do this because we do not have separate name spaces for classes and
items (as C++ has), so there is no ambiguity. IMO this syntax has the
advantage of being natural too; it is a parameterization after all.
The C++ template syntax makes parsing unneccessarily hard because <> are
used as operators too.

Constraints for parameterized types should be declared using the same syntax
as for methods.

> And furthermore, it should be noted an implementation of
> parameterisation need not result in new code being generated for each
> parameterisation, like would occur with C templates.

IMO a very important point.

> --
>      Matthew Tuck - Software Developer & All-Round Nice Guy
>

 Regards,

Hans-Dieter Dreier