From: Keunwoo Lee (klee@cs.washington.edu)
Date: Thu Dec 05 2002 - 15:16:22 PST
On Thu, 5 Dec 2002, Andrei Alexandrescu wrote:
> So now, what can and what you cannot do with transient objects? An
> obvious thing to do is to disallow escape; a transient[Square] can not
> be stored nor converted to a Square. This is because the
> transient[Square] could actually originate from a Rectangle that is
> square-shaped. On the other hand, again, a Square happily morphs into a
> transient[Square].
>
> So you cannot store transient objects; the only thing you can do is to
> invoke on them other methods that accept transient objects.
>
> Not bad - but there is a major problem: aliasing. Consider this:
>
> method sneaky(rect:@Rectangle, sq: @transient[Square]);
> ...
> object rect isa Rectangle { ... }; sneaky(rect, rect);
>
> Now inside sneaky a number of Bad Things(tm) are going to happen, caused
> by altering the Rectangle followed by altering what we think is a
> transient[Square]. This problem looks quite hard to solve...
More generally, predicate classes won't work well unless you have a way to
talk about both
(1) aliasing + object lifetimes and
(2) mutation/side effecta
Rather than a hardcoded, binary "transient" qualifier, I think you really
want a way to say, "the lifetime of this object expires before the square
may be mutated, so I can safely store the square as a field of this
object". (If you view a stack frame as an object, then such a system
would give you the right lifetime semantics for procedure calls, and also
give you AliasJava-style "lent" aliases for free.)
Perhaps you can view a predicate type as a (linear?) capability that is
granted by the dispatch (i.e., the predicate test) and can be revoked by
any operation that may mutate the object. In the above, sneaky would not
be able to treat sq as a square after mutating rect, because sq and rect
may be aliased. If the programmer wished to treat sq as a square after
mutating rect, then the programmer would have to specify that they live in
distinct "data groups" or something (see the data groups paper in
PLDI'02), ensuring that sq and rect would not be aliased. In this case,
the call sneaky(rect, rect) would be illegal.
Of course, in such a scheme method profiles would have to be annotated (by
the programmer, or by inference) with information about whether they may
invalidate a predicate on the object. And you would have to come up with
a good scheme for limiting object lifetimes, which is hard. Well, it's
easier if you divide the universe into 2 kinds of objects: stack frames,
and everything else. It's harder if you want more expressiveness.
~k
p.s.:
> So imagine Cecil would add a type qualifier "transient" (qualifier that
> can be implemented as a parameterized type -- btw, what's the
> fundamental difference between qualifiers and parameterized types?).
AFAIK "parameterized type" refers quite generically to any of various
kinds of types that have both a "main" part of the type and a "parameter"
part of the type. It does not imply anything about how those types are
propagated around, what kind of polymorphism they have (f-bounded?
universally quantified (like ML)? etc.), or whether the type parameters
are entirely orthogonal to the main type or related to it somehow.
"Type qualifier" is a specific term from work by Jeff Foster and Alex
Aiken, and refers to a way of annotating arbitrary types with an
additional list of "qualifier" types. A type qualifier is essentially an
element of a two-element lattice (it is either present or not present,
e.g. "const" vs. "not const") and is orthogonal to the main type (any
value may be "const" or "not const", independent of its underyling type).
By imposing these restrictions, Foster/Aiken/Terauchi were able to devise
a tractable inference system that made it easy to apply qualifiers in one
part of the source code, and automatically propagate them everywhere else
in a flow-sensitive (but not path-sensitive) manner.
I suspect that as people do follow-on research to Vault, ESP, and the
Foster/Aiken type qualifiers, the usage of the term "type qualifier"
will gradually become watered down. In particular, somebody might someday
generalize type qualifiers to handle more flexible type lattices and add
constraints relating the qualifier to the qualified type. If this
happens, the distinction between type qualifier and type parameter will be
purely one of emphasis and taste rather than any technical distinction.
_______________________________________________
Cecil mailing list
Cecil@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/cecil
This archive was generated by hypermail 2.1.5 : Thu Dec 05 2002 - 15:16:27 PST