Reference counted containers prototype

[Andrei Alexandrescu]

On 12/27/11 8:21 AM, Michel Fortin wrote:
> On 2011-12-27 02:47:50 +0000, Andrei Alexandrescu
>> 1. "Basic" containers - reference semantics, using classic garbage
>> collection
>>
>> 2. Reference counted containers - still reference semantics, using
>> reference counting
>>
>> 3. COW containers - value semantics, using reference counting to make
>> copying O(1).
>
> I like the idea, but...
>
> I worry about fragmentation.
>
> Say we have those three variant of each container and you write a
> function accepting a container, which one do you use for the parameter?
> The only type common to all three is "DListImpl", except it shouldn't
> work because:
>
> 1. you barred access to the underlying DListImpl in RefCounted (using
> opDispatch instead of alias this)
> 2. you want to spare users of writing "ref" every time they write a
> function prototype
>
> Those two design constrains makes it impossible to have a common type
> independent of the "packaging" policy.

Things could be arranged to make that happen (e.g. by making "cow" a 
runtime parameter), but I think that would be a wrong turn. These 
options are important design choices, not happenstance details; one 
should _not_ naively mix them. For example, say we arrange things such 
that "cow" is opaque. Then code using a DList would have dramatically 
different semantics depending on what DList you pass in, or would need 
to guard everything with lst.isCow vs. not.

> I worry also about const and immutable.
>
> It's nice to have reference counting, but it works poorly with const and
> immutable. If a function declares it takes a const container, you'll
> have to pass the reference counted container by ref to avoid mutating
> the reference count, which goes contrary one of your goals.

I talked a lot about this with Walter and we concluded that the story 
with const and immutable goes like this: in a RefCounted!T object, the T 
is constant, not the RefCounted. So it would be RefCounted!(immutable T).

> - - -
>
> Let me make a language suggestion that will address both of these problems.
>
> Allow structs to be flagged so they are always passed by reference to a
> function, like this:
>
> ref struct DListImpl {…}
>
> Now a function accepting a DListImpl will implicitly have it passed by
> "ref" with no unnecessary copy, and no need to mutate a reference count:
>
> void func(DListImpl list) {…}
>
> Then you can use alias this in RefCounted giving access to a "ref
> DListImpl" which can be passed to functions always by ref, regardless of
> the packaging policy, and without the need to remember to write "ref"
> every time you write a function accepting a container (because it is a
> ref struct which is always implicitly passed by ref).
>
> Functions that don't need to store a reference to the container won't
> have to care about whether the container they get is maintained using a
> reference counter, COW, or the GC. And those functions can accept a
> const container, or even a value-type container (which gets implicitly
> passed by ref).
>
> So with implicit ref parameters for "ref struct" types you solve the
> issue of fragmentation and of passing const containers to functions.
>
> The underlying principle is that how to efficiently pass a type to
> functions should be decided at the type level. You're trying to figure
> out how it should work for containers, but I think it should apply more
> broadly to the language as a whole.
>
> But there is one more thing. ;-)
>
> Implicit ref parameters could also solve elegantly the more general
> problem of passing rvalues by reference if you make them accept rvalues.
> Only parameters explicitly annotated with "ref" would refuse rvalues,
> those implicitly passed by ref would accept them.

Not to seem dismissive, but this sounds quite complicated for what it 
does. Could we implement it as a library feature? And assuming your 
motivating argument wasn't as strong, is it needed?


Andrei