www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Immutable and unique in C#

reply =?ISO-8859-15?Q?S=F6nke_Ludwig?= <sludwig outerproduct.org> writes:
Just stumbled over this, which is describing a type system extension for


http://research.microsoft.com/pubs/170528/msr-tr-2012-79.pdf

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.
Nov 09 2012
next sibling parent reply "Kagamin" <spam here.lot> writes:
:) do they implement `inout`?
Nov 09 2012
parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 09.11.2012 18:45, schrieb Kagamin:

 :) do they implement `inout`?


Haven't seen it, yet ;)

But seriously, they go a lot further with their `isolated` type
qualifier. That together with their functions, which are basically
weakly pure, opens up a lot of new opportunities for statically verified
code without casting around all the time or bending the code structure
so much that it hurts.

The article is quick to read in it's core and _really_ anyone interested
in D's development should read it. This pretty much what we have + the
bits that are currently missing (especially concerning objects in the
immutable/shared world).

It fits perfectly with what's already there, it's proven to be sound and
practical, and IMO it's definitely what should be implemented in D.
Nov 10 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Sönke Ludwig:


 It fits perfectly with what's already there, it's proven to be 
 sound and
 practical, and IMO it's definitely what should be implemented 
 in D.


Seems fit to be added to Remus then :-)

Bye,
bearophile
Nov 10 2012
parent "Namespace" <rswhite4 googlemail.com> writes:
On Saturday, 10 November 2012 at 12:51:15 UTC, bearophile wrote:

 Sönke Ludwig:


 It fits perfectly with what's already there, it's proven to be 
 sound and
 practical, and IMO it's definitely what should be implemented 
 in D.


 Seems fit to be added to Remus then :-)

 Bye,
 bearophile


Gladly, if you would help me to write the necessary structures to 
emulate the behaviour. ;)
Nov 10 2012
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/10/2012 12:23 PM, Sönke Ludwig wrote:

 Am 09.11.2012 18:45, schrieb Kagamin:

 :) do they implement `inout`?


 Haven't seen it, yet ;)

 But seriously, they go a lot further with their `isolated` type
 qualifier. That together with their functions, which are basically
 weakly pure, opens up a lot of new opportunities for statically verified
 code without casting around all the time or bending the code structure
 so much that it hurts.

 The article is quick to read in it's core and _really_ anyone interested
 in D's development should read it. This pretty much what we have + the
 bits that are currently missing (especially concerning objects in the
 immutable/shared world).

 It fits perfectly with what's already there, it's proven to be sound and
 practical, and IMO it's definitely what should be implemented in D.


Agreed. Do you file an enhancement request?
Nov 10 2012
parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Enhancement request:

http://d.puremagic.com/issues/show_bug.cgi?id=8993
Nov 10 2012
parent Marco Leise <Marco.Leise gmx.de> writes:
Am Sat, 10 Nov 2012 15:41:21 +0100
schrieb S=C3=B6nke Ludwig <sludwig outerproduct.org>:


 Enhancement request:
=20
 http://d.puremagic.com/issues/show_bug.cgi?id=3D8993


Its true that we avoid shared because it isn't finalized and
in its current state more or less a broken feature. It also
highlights the bluntness of the casts again, that are needed
to use it. *sigh* If it takes 5 full-time researchers to come
up with that type system extension then be it. I hope it can be
applied to D and resolves the 'shared' situation.

--=20
Marco
Nov 10 2012
prev sibling next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Fri, 09 Nov 2012 14:53:27 +0100
S=F6nke Ludwig <sludwig outerproduct.org> wrote:


 Just stumbled over this, which is describing a type system extension

=20
 http://research.microsoft.com/pubs/170528/msr-tr-2012-79.pdf
=20


Ugh, "researchers" really need to quit releasing shit in multi-column
PDF. Fucking pain in the ass to read. They need to try researching
what the current decade is, what do they think this is, 1950? Don't they
ever even try to read their *own* shit? Or, heck, even *other*
researcher's papers? Or do they just live and die by their printer? I
really don't get why they keep doing it, makes no damn sense at all.
Some sort of idiotically mandated requirement? And then they wonder why
people dismiss/ignore them as out-of-touch ivory tower. Geez.
Nov 11 2012
prev sibling next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 09 Nov 2012 07:53:27 -0600, Sönke Ludwig <sludwig outerproduct.org>
wrote:


 Just stumbled over this, which is describing a type system extension for


 http://research.microsoft.com/pubs/170528/msr-tr-2012-79.pdf

 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.


What's wrong with std.typecons.Unique?
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. 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. 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. 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.

P.S. Thanks for the link to the paper.
Nov 11 2012
parent reply =?ISO-8859-15?Q?S=F6nke_Ludwig?= <sludwig outerproduct.org> writes:
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.
Nov 11 2012
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Nov 11 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Nov 11 2012
parent =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
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.
Nov 12 2012
prev sibling parent deadalnix <deadalnix gmail.com> writes:
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.
Nov 12 2012
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Nov 12 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Nov 12 2012
prev sibling next sibling parent reply deadalnix <deadalnix gmail.com> writes:
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.
Nov 12 2012
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Nov 12 2012
prev sibling parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
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
Nov 12 2012
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 11/12/2012 11:48 PM, Sönke Ludwig wrote:

 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


I've thought some more about it, and there are some implementation problems
with 
doing it as a storage class. Specifically, the issue of enforcing destructive 
reads from unique variables, which is a very intrusive and complex change for 
little gain.

However, this is not an issue if, instead, we created:

    Unique!T v = ...;

where T is a pointer/class type. It's a wrapper around T with some interesting 
properties. Unique!T can be implemented to only allow one, destructive, read. 
All that read does is return a value of type T.

A Unique!T can only be initialized by:

    1. a destructive read of another instance of Unique!T
    2. an expression that can be determined to generated an isolated pointer



      __unique(Expression)

which will allow it through if Expression is some combination of new, pure 
functions, and other Unique pointers.

There is also the issue of "I know it's a unique pointer, but the compiler 
cannot guarantee that, so how do I set it?" for which I propose that in  system 
functions, __unique(Expression) always says it's ok.

Note that dereferencing a Unique!T variable will always entail a destructive 
read of it. Therefore, multiple reads will require storing it into an instance 
of T. Calling a method with a Unique!T this will also require converting it
into 
a T. Getting it back into a Unique!T will require some  system programming.


P.S. Yes, I know there's std.typecons.Unique, but it has a lot of holes in it, 
such as:

     &up.a.b;   // uh-oh, now we have another address
                // into the supposedly isolated graph!
Nov 13 2012
next sibling parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 13.11.2012 09:40, schrieb Walter Bright:

 On 11/12/2012 11:48 PM, Sönke Ludwig wrote:

 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


 
 I've thought some more about it, and there are some implementation problems
with doing it as a
 storage class. Specifically, the issue of enforcing destructive reads from
unique variables, which
 is a very intrusive and complex change for little gain.
 
 However, this is not an issue if, instead, we created:
 
    Unique!T v = ...;
 
 where T is a pointer/class type. It's a wrapper around T with some interesting
properties. Unique!T
 can be implemented to only allow one, destructive, read. All that read does is
return a value of
 type T.
 
 A Unique!T can only be initialized by:
 
    1. a destructive read of another instance of Unique!T
    2. an expression that can be determined to generated an isolated pointer
 

 
      __unique(Expression)
 
 which will allow it through if Expression is some combination of new, pure
functions, and other
 Unique pointers.
 
 There is also the issue of "I know it's a unique pointer, but the compiler
cannot guarantee that, so
 how do I set it?" for which I propose that in  system functions,
__unique(Expression) always says
 it's ok.


Wouldn't it be better to handle this as a special means of construction in the
Unique struct, along
the lines of assumeUnique()? Assuming that still most functions are still
 system, this would
severely limit the verification value of the Unique type otherwise.


 
 Note that dereferencing a Unique!T variable will always entail a destructive
read of it. Therefore,
 multiple reads will require storing it into an instance of T. Calling a method
with a Unique!T this
 will also require converting it into a T. Getting it back into a Unique!T will
require some  system
 programming.
 
 
 P.S. Yes, I know there's std.typecons.Unique, but it has a lot of holes in it,
such as:
 
     &up.a.b;   // uh-oh, now we have another address
                // into the supposedly isolated graph!


Did you see my effort on this?
(http://forum.dlang.org/thread/k7orpj$1tt5$1 digitalmars.com?page=4#post-k7rhoj:24m8h:241:40digitalmars.com)

This version, instead of requiring the initialization expression to be unique,
enforces that the
type cannot contain non-unique references. That is, except for shared data.
Allowing shared data
greatly improves its flexibility for passing data between threads.

But because it guarantees that the type cannot contain non-unique data, it can
allow multiple
dereferences and still guarantee that no references are shared. Only immutable
(or shared)
references can be extracted. Everything else can only be copied or moved,
keeping everything isolated.

The result is, I think, more usable because a) shared data is allowed and b)
step-by-step
construction of unique data is possible naturally without constantly moving a
unique pointer around.

rules, and I think
those can only be implemented by the compiler (setting apart AST macros ;) ).
Nov 13 2012
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 11/13/2012 1:38 AM, Sönke Ludwig wrote:

 Wouldn't it be better to handle this as a special means of construction in the
Unique struct, along
 the lines of assumeUnique()? Assuming that still most functions are still
 system, this would
 severely limit the verification value of the Unique type otherwise.


The trouble is that templates don't work on expression ASTs, they work on
types. 
Being able to determine if an expression is unique requires access to the 
expression tree, currently only the compiler can do that.



 Did you see my effort on this?
 (http://forum.dlang.org/thread/k7orpj$1tt5$1 digitalmars.com?page=4#post-k7rhoj:24m8h:241:40digitalmars.com)

 This version, instead of requiring the initialization expression to be unique,
enforces that the
 type cannot contain non-unique references.


By operating on the expression, a lot more cases can be handled.


 That is, except for shared data. Allowing shared data
 greatly improves its flexibility for passing data between threads.

 But because it guarantees that the type cannot contain non-unique data, it can
allow multiple
 dereferences and still guarantee that no references are shared. Only immutable
(or shared)
 references can be extracted. Everything else can only be copied or moved,
keeping everything isolated.


Allowing shared access into the middle of something means that unique pointers 
cannot be implicitly cast to immutable.

The other trouble is doing assignments into the isolated data. What if you're 
assigning to a pointer, and the pointer value is pointing outside of the 
isolated graph?



 The result is, I think, more usable because a) shared data is allowed and b)
step-by-step
 construction of unique data is possible naturally without constantly moving a
unique pointer around.

rules, and I think
 those can only be implemented by the compiler (setting apart AST macros ;) ).


I think we can do this with __unique(Expression), which is not a pervasive 
change to the compiler, it's fairly isoloated (!). That construct would perform 
the "recovery". I implemented a little bit of this in NewExp::implicitConvTo().
Nov 13 2012
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
I think the only way values can be extracted from Unique!T containers is by 
copying them, and those values cannot contain any non-immutable references.

A Unique!T can be implicitly cast to mutable/shared/immutable, which then
grants 
direct mutable/shared/immutable access, but it won't be unique anymore.
Nov 13 2012
parent =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 13.11.2012 12:08, schrieb Walter Bright:

 I think the only way values can be extracted from Unique!T containers is by
copying them, and those
 values cannot contain any non-immutable references.
 
 A Unique!T can be implicitly cast to mutable/shared/immutable, which then
grants direct
 mutable/shared/immutable access, but it won't be unique anymore.
 


Ditto
Nov 13 2012
prev sibling parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 13.11.2012 12:00, schrieb Walter Bright:

 
 By operating on the expression, a lot more cases can be handled.


Yes, but _only_ doing that, the unique property is lost as soon as the
expression crosses the
statement border - then the type system somehow needs to take over. But
extending its capabilities
using this is certainly a win.


 

 That is, except for shared data. Allowing shared data
 greatly improves its flexibility for passing data between threads.

 But because it guarantees that the type cannot contain non-unique data, it can
allow multiple
 dereferences and still guarantee that no references are shared. Only immutable
(or shared)
 references can be extracted. Everything else can only be copied or moved,
keeping everything
 isolated.


 
 Allowing shared access into the middle of something means that unique pointers
cannot be implicitly
 cast to immutable.


Not to immutable, but it may still be moved to another thread without
copying/locking etc. Since
this can be easily checked at compile time, in my current implementation, the
freeze() method of
Isolated!T is only available if T is strongly isolated (i.e. does not contain
shared references).


 
 The other trouble is doing assignments into the isolated data. What if you're
assigning to a
 pointer, and the pointer value is pointing outside of the isolated graph?
 


The trick is that an Isolated!T value only has references to immutable or other
Isolated!U data. So
assigning to any field will never violate the isolation. Assigning to an
Isolated!U field requires a
move().


 

 The result is, I think, more usable because a) shared data is allowed and b)
step-by-step
 construction of unique data is possible naturally without constantly moving a
unique pointer around.

rules, and I think
 those can only be implemented by the compiler (setting apart AST macros ;) ).


 
 I think we can do this with __unique(Expression), which is not a pervasive
change to the compiler,
 it's fairly isoloated (!). That construct would perform the "recovery". I
implemented a little bit
 of this in NewExp::implicitConvTo().
 


But how can it do recovery across a statement boundary?

Anyways, it was partly a moot point on my part, as the Isolated struct can
simply make sure to
expose only fields that are safe (i.e. POD, immutable or Isolated fields).
Those can be freely
changed without violating isolation and thus no explicit recovery is even
necessary. But other
fields with references to mutable or shared data are still difficult to handle.
Nov 13 2012
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 11/13/2012 3:18 AM, Sönke Ludwig wrote:

 Am 13.11.2012 12:00, schrieb Walter Bright:

 By operating on the expression, a lot more cases can be handled.


 Yes, but _only_ doing that, the unique property is lost as soon as the
expression crosses the
 statement border - then the type system somehow needs to take over.


That's where Unique!T comes in.



 That is, except for shared data. Allowing shared data
 greatly improves its flexibility for passing data between threads.

 But because it guarantees that the type cannot contain non-unique data, it can
allow multiple
 dereferences and still guarantee that no references are shared. Only immutable
(or shared)
 references can be extracted. Everything else can only be copied or moved,
keeping everything
 isolated.


 Allowing shared access into the middle of something means that unique pointers
cannot be implicitly
 cast to immutable.


 Not to immutable, but it may still be moved to another thread without
copying/locking etc. Since
 this can be easily checked at compile time, in my current implementation, the
freeze() method of
 Isolated!T is only available if T is strongly isolated (i.e. does not contain
shared references).


Ok.


 The other trouble is doing assignments into the isolated data. What if you're
assigning to a
 pointer, and the pointer value is pointing outside of the isolated graph?


 The trick is that an Isolated!T value only has references to immutable or
other Isolated!U data. So
 assigning to any field will never violate the isolation. Assigning to an
Isolated!U field requires a
 move().


Ok.


 The result is, I think, more usable because a) shared data is allowed and b)
step-by-step
 construction of unique data is possible naturally without constantly moving a
unique pointer around.

rules, and I think
 those can only be implemented by the compiler (setting apart AST macros ;) ).


 I think we can do this with __unique(Expression), which is not a pervasive
change to the compiler,
 it's fairly isoloated (!). That construct would perform the "recovery". I
implemented a little bit
 of this in NewExp::implicitConvTo().


 But how can it do recovery across a statement boundary?


Assign to a Unique!T variable, then use that Unique!T variable in the next 
statement.


 Anyways, it was partly a moot point on my part, as the Isolated struct can
simply make sure to
 expose only fields that are safe (i.e. POD, immutable or Isolated fields).
Those can be freely
 changed without violating isolation and thus no explicit recovery is even
necessary. But other
 fields with references to mutable or shared data are still difficult to handle.
Nov 14 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2012 12:03 PM, Walter Bright wrote:

 ...

 But how can it do recovery across a statement boundary?


 Assign to a Unique!T variable, then use that Unique!T variable in the
 next statement.


What he meant is how to create temporary pointers to the data and then 
get an isolated reference to it again in a safe way.
Nov 14 2012
prev sibling next sibling parent =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 13.11.2012 09:40, schrieb Walter Bright:

 

 
      __unique(Expression)
 
 which will allow it through if Expression is some combination of new, pure
functions, and other
 Unique pointers.
 


I just realized that using __unique(expression) vs. verifying the type must be
unique is not really
mutually exclusive. Unique!T (or Isolated!T) could simply support both. It
could still expose plain,
immutable or Isolated!T data fields and could still allow pure methods that
only have these kinds of
parameters to be called. So performing one-time reads is, even in that case,
only necessary for
certain operations.
Nov 13 2012
prev sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Walter Bright" <newshound2 digitalmars.com> wrote in message 
news:k7t125$7on$1 digitalmars.com...

 A Unique!T can only be initialized by:

    1. a destructive read of another instance of Unique!T
    2. an expression that can be determined to generated an isolated 
 pointer


 like:

      __unique(Expression)

 which will allow it through if Expression is some combination of new, pure 
 functions, and other Unique pointers.


This is somewhat possible in the current language.  The makeU function can 
be an arbitrarily complicated strongly pure function.

void funcTakingUnique(U, T...)(U function(T) pure makeU, T args) if 
(is(typeof({ immutable i = makeU(args) }) // If it converts to immutable, it 
is either unique or immutable
{
    auto unique = makeU(args); // guaranteed to be unique/immutable
}

class A
{
    this(int a, string b) {}
}

void main()
{
    funcTakingUnique!A(A function(int a, string b) { return new A(a, b); }, 
4, "Awesome");
}
Nov 13 2012
parent Walter Bright <newshound2 digitalmars.com> writes:
On 11/13/2012 3:47 PM, Daniel Murphy wrote:

 "Walter Bright" <newshound2 digitalmars.com> wrote in message
 news:k7t125$7on$1 digitalmars.com...

 A Unique!T can only be initialized by:

     1. a destructive read of another instance of Unique!T
     2. an expression that can be determined to generated an isolated
 pointer


 like:

       __unique(Expression)

 which will allow it through if Expression is some combination of new, pure
 functions, and other Unique pointers.


 This is somewhat possible in the current language.  The makeU function can
 be an arbitrarily complicated strongly pure function.

 void funcTakingUnique(U, T...)(U function(T) pure makeU, T args) if
 (is(typeof({ immutable i = makeU(args) }) // If it converts to immutable, it
 is either unique or immutable
 {
      auto unique = makeU(args); // guaranteed to be unique/immutable
 }

 class A
 {
      this(int a, string b) {}
 }

 void main()
 {
      funcTakingUnique!A(A function(int a, string b) { return new A(a, b); },
 4, "Awesome");
 }


This is a great insight.
Nov 13 2012
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
Le 13/11/2012 08:48, Sönke Ludwig a écrit :

 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.


BTW, do you have a link to Bartosz's proposal ?


 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
Nov 13 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-11-13 15:21, deadalnix wrote:


 BTW, do you have a link to Bartosz's proposal ?


This is a proposal, or part of one:

http://bartoszmilewski.com/2009/06/02/race-free-multithreading-ownership/

He has other interesting blog post regarding multithreading as well.

-- 
/Jacob Carlborg
Nov 13 2012