View mode: basic / threaded / horizontal-split · Log in · Help
November 11, 2012
Re: Immutable and unique in C#
Am 11.11.2012 18:20, schrieb Robert Jacques:
> 
> What's wrong with std.typecons.Unique?

- Does not implicitly cast to immutable
- Has no way to enforce uniqueness of data referenced within the
contained object
- Cannot be passed between threads (i.e. in std.concurrency) and if it
would be passable, it would not be safe
- Does not allow temporal elevation to non-unique in pure contexts
- No support for arrays and unique partitions

Probably more, but basically in its current form it's mostly useless
apart from documenting the intent. Some of the things can be fixed in
the library type, but to make it really sound and useful, a library
solution is not enough (at least not with the current means that the
language offers).

> By the way, back when concurrency in D was actively being discussed and
> developed, (IIRC) Walter did try to implement unique as a proper type in
> D, but ran into several gotchas.

Do you remember which? All I could find was a thread stating that Walter
did not like the idea of adding an additional transitive type modifier
along const, immutable and shared because of the combinatorial number of
types. Oddly, I could have sworn that I have commented on unique at that
time, but can't find that either.

> In essence, while we all want
> unique/mobile, for unique/mobile to be non-broken it also needs at least
> a lent/scope and an owned type.

The system described in the paper does not need need lent/owned types.
That can be attributed to the fact that their function definition
disallows access of mutable global fields. So as long as only 'pure'
functions operate on a given 'isolated' value, their recovery
rules allow working pretty comfortable, while still statically enforcing
memory isolation.

Calling normal, impure methods or functions would have to break the
'isolated' property and inhibit recovery. This would be the place where
the system with 'lent'/'owned' would allow more freedom, but only at the
cost of a generally higher complexity.

> Ownership type systems are a relatively
> new area of CS and as demonstrated by the paper, still an active area of
> research. The thorny issue of these systems is that you need to
> associate variables with types. For example, this.x = that.y; is only
> valid if x and y are both owned by the same region. This is easy to
> verify at runtime, but not at compile-time.

At least the following assignments can be verified statically using only
local information, no need to track exact memory region ownership:

unique <- unique
immutable <- unique
writable <- unique
writable <- writable

this.x = this.y inside an 'isolated' memory region would be valid as
long as it happens in a pure context and no non-unique/non-immutable
values are passed into the function. Anything else would inhibit
recovery of 'isolated' after the implicit conversion to 'writable' that
is necessary to pass the object to a function/method.

> Anyways, ownership types (or
> whatever supersedes them) were pushed back to D3 and we were left with
> message passing for the common user, synchronized for traditional
> lock-based shared memory and shared for lock-free programming.

Yeah, I'm well aware of that.. unfortunately ;)

This system has the potential to be backward (vs current state) and
forward (vs a full ownership system) compatible, while not affecting
anything of the existing language (like needing to store explicit
ownership information).

However, I have to admit that without actually trying it and seeing how
usable it is first hand, it's difficult to tell how usable it is in
practice (e.g. because D functions have to be explicitly tagged 'pure'
for the recovery to work). Maybe also error messages would be difficult
to understand or something else.
November 12, 2012
Re: Immutable and unique in C#
On 11/11/2012 10:59 AM, Sönke Ludwig wrote:
> However, I have to admit that without actually trying it and seeing how
> usable it is first hand, it's difficult to tell how usable it is in
> practice (e.g. because D functions have to be explicitly tagged 'pure'
> for the recovery to work).

With purity, transitive immutability, and transitive sharing, D already is quite 
a long way down the road. But we can go further, as currently new() and pure 
functions are not exploited for their implicit casting ability.

For example,

    struct S { int x; }
    ...
    shared S* s = new S();

can be made to work, as can:

    pure S* foo(S* s);
    shared S* s = foo(new S());

I'm not convinced that adding a "unique" qualifier is strictly necessary.
November 12, 2012
Re: Immutable and unique in C#
On Sunday, November 11, 2012 17:29:02 Walter Bright wrote:
> I'm not convinced that adding a "unique" qualifier is strictly necessary.

Where it would be particularly valuable would be passing stuff across threads 
with std.concurrency. We don't _need_ it for that however. It would just make 
it cleaner, because you wouldn't have to worry about whether anything else on 
the current thread had a reference to what you were passing across.

So, while I think that it would be nice, I'm not convinced that it's worth 
adding at this point. There's a halfway decent chance that you'd just end up 
casting to unique to pass it across anyway (depending on how the value was 
constructed), which then puts us in exactly the same boat that we're in now 
except for the fact that we're casting to unique instead of casting to shared 
or immutable.

- Jonathan M Davis
November 12, 2012
Re: Immutable and unique in C#
Am 12.11.2012 04:06, schrieb Jonathan M Davis:
> On Sunday, November 11, 2012 17:29:02 Walter Bright wrote:
>> I'm not convinced that adding a "unique" qualifier is strictly necessary.
> 
> Where it would be particularly valuable would be passing stuff across threads 
> with std.concurrency. We don't _need_ it for that however. It would just make 
> it cleaner, because you wouldn't have to worry about whether anything else on 
> the current thread had a reference to what you were passing across.

Exactly, that's the main point. That it would also allow to operate
safely on an already constructed unique value (which is the possible
implicit precursor to an immutable value) is just a nice bonus.

> 
> So, while I think that it would be nice, I'm not convinced that it's worth 
> adding at this point. There's a halfway decent chance that you'd just end up 
> casting to unique to pass it across anyway (depending on how the value was 
> constructed), which then puts us in exactly the same boat that we're in now 
> except for the fact that we're casting to unique instead of casting to shared 
> or immutable.
> 
> - Jonathan M Davis
> 

Sorry, but following that argument, we can also drop
const/immutable/shared. After all there is a chance that they are just
forced using a cast and thus don't buy us anything... The point is of
course to bring the type system closer to a point where such casts are
not needed at all. The programmer would then know that doing such a cast
is probably wrong - right now casting is necessary far too often and as
such looses its usually implied warning sign.

But apart from that, I have started to explore a bit what's possible
using a library solution. So far it looks quite promising, I'll post a
snippet later.
November 12, 2012
Re: Immutable and unique in C#
Le 12/11/2012 02:29, Walter Bright a écrit :
> On 11/11/2012 10:59 AM, Sönke Ludwig wrote:
>> However, I have to admit that without actually trying it and seeing how
>> usable it is first hand, it's difficult to tell how usable it is in
>> practice (e.g. because D functions have to be explicitly tagged 'pure'
>> for the recovery to work).
>
> With purity, transitive immutability, and transitive sharing, D already
> is quite a long way down the road. But we can go further, as currently
> new() and pure functions are not exploited for their implicit casting
> ability.
>
> For example,
>
> struct S { int x; }
> ...
> shared S* s = new S();
>
> can be made to work, as can:
>
> pure S* foo(S* s);
> shared S* s = foo(new S());
>
> I'm not convinced that adding a "unique" qualifier is strictly necessary.
>

Due to how delegate currently work, it isn't safe AT ALL. I've made a 
thread about that already.
November 12, 2012
Re: Immutable and unique in C#
On 11/9/2012 5:53 AM, Sönke Ludwig wrote:
> Independent of this article I think D is currently missing out a lot by
> omitting a proper unique type (a _proper_ library solution would be a
> start, but I'm not sure if that can handle all details). It would make a
> lot of the cases work that are currently simply not practical because of
> loads of casts that are necessary.

Unique as a type qualifier comes with all kinds of subtle problems. For one 
thing, unique is more of a property of an expression rather than a property of 
the type.

But I was thinking - what if it's a storage class? Like ref is? Working through 
the use cases in my head, I think it can work. Unique being a property of an 
expression, this can be tested upon assignment to the unique variable. Upon 
reading that unique variable, the value of it is erased.

Function parameters can be qualified with "unique" as well, meaning their 
corresponding arguments can only be unique expressions.
November 12, 2012
Re: Immutable and unique in C#
Walter Bright:

> Unique as a type qualifier comes with all kinds of subtle 
> problems. For one thing, unique is more of a property of an 
> expression rather than a property of the type.

Unfortunately I am not able to fully understand the paper linked 
by Sönke Ludwig in this thread, but maybe you are able to 
understand its main points.

Generally in this complex field I suggest to build on the ideas 
invented by researchers, and to not try to invent too much.

Bye,
bearophile
November 12, 2012
Re: Immutable and unique in C#
Le 13/11/2012 00:46, Walter Bright a écrit :
> On 11/9/2012 5:53 AM, Sönke Ludwig wrote:
>> Independent of this article I think D is currently missing out a lot by
>> omitting a proper unique type (a _proper_ library solution would be a
>> start, but I'm not sure if that can handle all details). It would make a
>> lot of the cases work that are currently simply not practical because of
>> loads of casts that are necessary.
>
> Unique as a type qualifier comes with all kinds of subtle problems. For
> one thing, unique is more of a property of an expression rather than a
> property of the type.
>
> But I was thinking - what if it's a storage class? Like ref is? Working
> through the use cases in my head, I think it can work. Unique being a
> property of an expression, this can be tested upon assignment to the
> unique variable. Upon reading that unique variable, the value of it is
> erased.
>
> Function parameters can be qualified with "unique" as well, meaning
> their corresponding arguments can only be unique expressions.
>

As much as I like the unique proposal, I don't think it is a good idea 
to integrate at this point.
November 13, 2012
Re: Immutable and unique in C#
On 11/12/2012 3:52 PM, deadalnix wrote:
> As much as I like the unique proposal, I don't think it is a good idea to
> integrate at this point.

Neither do I. But it's good to think about it.
November 13, 2012
Re: Immutable and unique in C#
Am 13.11.2012 00:46, schrieb Walter Bright:
> On 11/9/2012 5:53 AM, Sönke Ludwig wrote:
>> Independent of this article I think D is currently missing out a lot by
>> omitting a proper unique type (a _proper_ library solution would be a
>> start, but I'm not sure if that can handle all details). It would make a
>> lot of the cases work that are currently simply not practical because of
>> loads of casts that are necessary.
> 
> Unique as a type qualifier comes with all kinds of subtle problems. For one thing, unique is more of
> a property of an expression rather than a property of the type.
> 
> But I was thinking - what if it's a storage class? Like ref is? Working through the use cases in my
> head, I think it can work. Unique being a property of an expression, this can be tested upon
> assignment to the unique variable. Upon reading that unique variable, the value of it is erased.
> 
> Function parameters can be qualified with "unique" as well, meaning their corresponding arguments
> can only be unique expressions.
> 

Currently I also see no reason why this should not be possible. Since it is acting recursively and
locally anyway, a storage class will probably capture almost everything that a full type would. I
had thought about the same route to reduce intrusiveness, before looking first what's possible with
a pure library solution.

The library solution seems surprisingly practical for some use cases. With the concept of "string"
and "weak" isolation (*), it can even handle the bridge between isolated and shared memory (thanks
to the completely separated nature of shared). By this, it solves a lot of the problems that only
Bartosz system was able to solve, for example declaring owned collections (no Mutex necessary),
which contain references to shared data, and still everything is safely checked.

A proper language feature can still do a lot more and IMO D should get there at some point - but I
think this is a viable short/mid-term alternative. I would like to get some discussion going to
eventually include something in phobos.


(*)

strong isolation: allows only strongly isolated and immutable references
-> can be passed to other threads and casts implicitly to immutable

weak isolation: allows weakly isolated, immutable and shared references
-> can only be passed to other threads
1 2 3 4
Top | Discussion index | About this forum | D home