View mode: basic / threaded / horizontal-split · Log in · Help
November 13, 2012
Re: Immutable and unique in C#
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

#2 is the interesting bit. That requires some compiler support, sort of like:

     __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!
November 13, 2012
Re: Immutable and unique in C#
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
> 
> #2 is the interesting bit. That requires some compiler support, sort of like:
> 
>      __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.
What makes the C# system usable are mostly the automatic uniqueness-recovery rules, and I think
those can only be implemented by the compiler (setting apart AST macros ;) ).
November 13, 2012
Re: Immutable and unique in C#
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.
> What makes the C# system usable are mostly the automatic uniqueness-recovery 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().
November 13, 2012
Re: Immutable and unique in C#
Am 13.11.2012 09:40, schrieb Walter Bright:
> 
> #2 is the interesting bit. That requires some compiler support, sort of like:
> 
>      __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.
November 13, 2012
Re: Immutable and unique in C#
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.
November 13, 2012
Re: Immutable and unique in C#
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.
>> What makes the C# system usable are mostly the automatic uniqueness-recovery 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.
November 13, 2012
Re: Immutable and unique in C#
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
November 13, 2012
Re: Immutable and unique in C#
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
November 13, 2012
Re: Immutable and unique in C#
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
November 13, 2012
Re: Immutable and unique in C#
"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
>
> #2 is the interesting bit. That requires some compiler support, sort of 
> 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");
}
1 2 3 4
Top | Discussion index | About this forum | D home