Parameterised Types

[Matthew Tuck]

Hans-Dieter Dreier wrote:

> 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;

This is difficult in general because of the following case.

class A<X>
   Field: X
   ...

procedure ...
   ...
   Variable: A<General> := new A<Special>
   Variable.Field := new General

Here Variable.Field gets a General object although it is only allowed a
special object.  Generic parameters have to be invariant where they are
used to instantiate read-write variables.  Where the X was only used for
read-only variables, the covariant relationship you outlined would
hold.  Where the X was only used for write-only variables, it would be
contravariant instead.

Hence we might prevent covariant generic parameters from being used in
read-write fields and so on.

The book "A Theory of Objects" that I recommended before goes into this
sort of thing a bit more if you're interested, although I'm not entirely
satisfied with the system as I've seen it.

Whether or not A<X> and A<Y> are the same "type" differs depends on who
you talk to and is probably just a semantic quibble anyway.

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

Hmm, could you elaborate?

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

This is possible, but it would invalidate existing references.  How is
this usually handled?  Copying GCs already have to handle this sort of
situation.  What languages do you know that do this?  This is similar to
being able to change an object's impl, parent impl, etc. at run-time.  I
think some object-based inheritance languages allow the addition of
fields at run-time, in parallel to a type downcast.

I'm not sure this would always work easily in general however.  The
canonical example of value-driven data is an array but generic value
parameters can be used for typing as well as allocation.  Exactly how
the changed parameters would affect the dependent entities (ie any
contained elements relying on the surrounding generic parameter (which
could theoretically cascade deeply) would be interesting.

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

I wasn't really worried about the precedence here, since this is only
two level and easily learned.

> And if we use it, it should be usable everywhere a comparison is allowed.

Regarding using the shorthand everywhere, if you're referring to normal
expressions here, maybe.  Normal expression "<" could be implemented
with shorthands the same as above, but it would be a different shorthand
in a different context.  The presence of all the other comparison
operators could dramatically complicate things, whichly is partly why I
only used <.  But all this is reliant on what sort of shorthands the
shorthand engine makes possible, which is as yet unknown/undecided.
 
>> 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.

Yes, the overriding model probably makes more sense than a default value
model, but I'm not sure if it would be enough of a perfect analogy to
unify them in the language.

> Contravariance is what I would allow by default.

That would be the other option I'd take.  I haven't really decided
whether contravariance or invariance is better.

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

You could put a run-time constraint but this dilutes the benefit.  The
essential problem is that if you want to feed an animal, the information
on what food it accepts should not be hidden.  Hence making it a
parameter to the type ensures it won't and prevents type problems.  A
standard checked downcast should be adequate to achieve what I think
you're looking for.

> I'd suggest to use normal function syntax, ie write
> AnIntegerArray = new Array (Integer);
> instead of
> AnIntegerArray = new Array <Integer>;

Possibly.  () is usually used for construction parameters, which are
handled differently, so I'd like a way of demonstrating to the reader
that they are a different type of parameter, say by putting the type
parameters first and separating them by a "|" or similar symbol.  Since
the type parameter list is defined in a different place to the
construction paremeter list, it would be handy to determine which list
has been passed to incorrectly better, which would be easier if you
separated them.

> The C++ template syntax makes parsing unneccessarily hard because <> are
> used as operators too.

Well I don't think this would affect a top-down parser.  A bottom up
parser might be affected, but I doubt this is significant.  Error
recovery could be a bit more important.

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

Possibly.  Uniformity would be nice but I don't want perfect uniformity
if there are significant differences between the two.  That's probably
view dependent anyway.  Similar format but with a keyword might achieve
this.

                            Normal Field    Subtype Param   Client Param
Part Of Variable Type Spec       N                Y               Y
Can Be Overriden                 Y                Y               N#
Can Be Nonconstant               Y                N               N
Specified At Instantiation       N*               N@              Y
Restricted To Type Fields        N                Y               Y

# = Unless provided as a default value in the absence of client
specification.
* = Only through constructor parameters.
@ = Implictly.

-- 
     Matthew Tuck - Software Developer & All-Round Nice Guy
             mailto:matty@box.net.au (ICQ #8125618)
       Check out the Ultra programming language project!
              http://www.box.net.au/~matty/ultra/