Subject: Re: Typing collect
From: Vassily Litvinov (vass@cs.washington.edu)
Date: Thu Jan 13 2000 - 17:39:15 PST
Indeed, it's really surprising how difficult it is to express such an easy
thing as "map" (generalized to arbitrary collection classes).
On the type system side, the interesting issue seems to be how to express
"same kind of collection, but another element type." Some language called
ML_sub can do it, but it has strong other limitations. Of course,
F-omega-sub can, too.
Meanwhile in our world, currently we use "signature constraint" (Craig's
idea, of course) and copy_empty:
method copy(src:`T):R where
signature copy_empty(T):`R,
T<=Collection[`S]
R<=Collection[S]
{ ... }
this approach can be easily extended to make copy_empty create a
collection of a different element type than source, as Jonathan suggests.
This is a workaround the limitation in our type system (can't say `T[`R]).
Surprisingly, it also handles well the irregular dependence between the
kind of source and result collections (where copy_empty creates a
collection of a (slightly) different kind than its argument).
As for the type system for Diesel, the existence of this workaround
motivates me to have a syntactic sugar to abbreviate constraints (so that
the above three constraints were much shorter and didn't cause
inconvenience to the programmer), rather than to support parameterization
over parameterized types (`T[`R]). But I am open to stronger arguments.
It may actually be not that difficult to handle such parameterization
either, but I am not there yet to try.
On the implementation side, the operation "create a new empty object of
the same kind as the argument" has long been in the future work categories
of "object model" and "object factories." I think that "object model"
implies language support where "factories" implies simply some conventions
and implementations of the factory methods for each class (which could be
just sugars in some cases).
A couple of issues need to be kept in mind here. First, the operation
"new T" (or "object isa T") - where T is a type - doesn't really have a
well-defined semantics, mostly because there may be different values of T
appropriate in a given situation, and also there may be cases when the
program doesn't typecheck (aka independence of dynamic semantics from
static semantics). So you have to send a "clone" message to the actual
object you want to clone.
Second, in the particular example of "collect," you don't really want to
create a new collection of exactly the same kind as the source, because if
the source collection is immutable, you cannot add any elements to its
exact copy. This I believe was the reason for having "copy_empty" methods.
Of course, the workaround I mentioned has potentially some implications
for efficiency of typechecking, but we can discuss semantic issues
independently I think.
> Second, I needed to express the fact that the method only applies if the
> collection type can hold the result type. One could do this with a
> Collectible[T] F-bounded type, but this is inelegant because it may
> require a declaration for each collection type.
I am not sure I understand quite the restriction that the collection can
hold the result type. Do you mean "change the type of collection
elements" or something else?
Vass
This archive was generated by hypermail 2b25 : Tue Oct 03 2000 - 15:21:20 PDT