Florian Weimer <fw@[EMAIL PROTECTED]
> writes:
> * Joachim Durchholz:
>
>> Paul Rubin schrieb:
>>> I just came across this. I would have thought it is well known (maybe
>>> it is),
>>
>> I think this is implemented in the form of "uniqueness types" in Clean.
>> I'm not sure whether the people who designed Clean read Henry Baker's
>> essay, or whether Baker and the Clean people simply drew from the same
>> sources.
>
> Some compilers also contain optimization p***** to infer this type
> information. Typically, it's called escape analysis. It's used to
> improve aliasing analysis, turn heap allocation into stack allocation,
> and for lock elision.
Escape analysis is not quite the same as linearity. What is usually
meant by escape analysis is an analysis to determine if an object can
ever escape the scope in which it is allocated. If it can not, it can
be released when the scope is exited (typically by allocating the
object on the stack, so it is unstacked when the scope is exited).
Region analysis generalised this by asking _which_ scope the object
can never escape. I.e., it need not be the scope in which the object
is allocated, but can be any surrounding scope.
Linearity doesn't tell you where an object is needed, only that is is
needed exactly once ("at most once" is rightly called "affine"), but
this can well be outside the scope in which it is allocated. A linear
object can be released or overwritten immediately after its use (as
there can be no other uses), but it can not always be stack allocated.
If linearly-typed objects require linearly-typed accessors, they can
safely be allocated outside the heap, as the accessors can explicitly
release (or reuse in another linear context) the objects. This is not
true for affinely typed objects, as these might never be accessed, and
hence not explicitly reclaimed. Affinely typed accessors can still
rerelease or reuse affine objects, but you need to be able to garbage
collect (or otherwise automatically reclaim) them also.
Linearity is also useful for objects that need finalisation since you
can do this explicitly at the single use of the object rather than
burdening GC with testing for every reclaimed object if a finaliser
needs to be called. For example, a linearly typed file handle will
have operations that explicitly reuse the handle (consuming it and
producing a new identical handle) plus a "close" operation that
consumes the handle, but doesn't produce a new handle. The linearity
also ensures that operations on the same file are sequentialised, even
in a concurrent or lazy setting.
Torben
|
