www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - uniqueness propagation

reply Kevin Bealer <kevindangerbealer removedanger.gmail.com> writes:
I think immutable could benefit from a Value Range Propagation-like uniqueness
logic:

string a;
char[] b;

string c = a ~ b; // result of ~ is always unique
string z = c.dup; // also any kind of .dup is definitely unique
char[] q = z.dup; // also okay -- assign to a non-immutable

The lines w/ dup or ~ could be considered legal, since these ops produce
definitely unique values.  A handful
of specific actions known to produce unique values would produce temporaries
with a 'uniqueness' property, which
allows them to go either way toward mutable or immutable.  This list includes
(malloc, new, ~, .dup) but maybe
others.

Once an expression is assigned to a variable it becomes immutable or mutable
as per that variable's traits.

As an extension variables could be labeled as 'unique' which essentially means
they contain a value that is not
shared.  Unique would only be legal in cases where escape analysis can easily
prove that the value does not
get copied into both immutable and mutable variables (see below about
portability).

You could label a function as producing unique values -- only legal if the
value returned is definitely unique.
Again, if the language cannot do escape analysis then the user will be
required to do a defensive dup.

Portability note:  For portability reasons it is better to have well defined
escape analysis rules that can be
implemented by any compiler -- so a smart compiler might actually know there
is no escape but still be required
to forbid a particular expression since it breaks the rules.

Kevin
Feb 24 2011
parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 25 Feb 2011 02:48:01 -0500, Kevin Bealer  
<kevindangerbealer removedanger.gmail.com> wrote:

 I think immutable could benefit from a Value Range Propagation-like  
 uniqueness


'unique' has been proposed and heavily discussed before in the news group.  
There even is std.typecons.Unique. Unfortunately, Walter has stated that  
there are issues/difficulties in adding 'unique' to the language.
Feb 25 2011
parent reply Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Robert Jacques napisa=B3:


 On Fri, 25 Feb 2011 02:48:01 -0500, Kevin Bealer =20
 <kevindangerbealer removedanger.gmail.com> wrote:

 I think immutable could benefit from a Value Range Propagation-like =20
 uniqueness


=20
 'unique' has been proposed and heavily discussed before in the news group=


. =20

 There even is std.typecons.Unique. Unfortunately, Walter has stated that =


=20

 there are issues/difficulties in adding 'unique' to the language.


What were those difficulties?

--=20
Tomek
Feb 25 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 25 Feb 2011 19:01:28 -0500, Tomek Sowiński <just ask.me> wrote:


 Robert Jacques napisał:


 On Fri, 25 Feb 2011 02:48:01 -0500, Kevin Bealer
 <kevindangerbealer removedanger.gmail.com> wrote:

 I think immutable could benefit from a Value Range Propagation-like
 uniqueness


 'unique' has been proposed and heavily discussed before in the news  
 group.
 There even is std.typecons.Unique. Unfortunately, Walter has stated that
 there are issues/difficulties in adding 'unique' to the language.


 What were those difficulties?


YATC (yet another type constructor)

Plus, when this was the topic de jour, there were about 3 other type  
constructors that were touted as "needed" in order to make unique work  
(like "borrowed" and "lent").  Bartosz had a blog post about it.  This  
meant you had to accept 3 or 4 new type constructors to get unique.

I really like this idea as a way to have unique without the type  
constructor: http://d.puremagic.com/issues/show_bug.cgi?id=5081

-Steve
Feb 25 2011
parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 25 Feb 2011 22:35:39 -0500, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Fri, 25 Feb 2011 19:01:28 -0500, Tomek Sowiński <just ask.me> wrote:


 Robert Jacques napisał:


 On Fri, 25 Feb 2011 02:48:01 -0500, Kevin Bealer
 <kevindangerbealer removedanger.gmail.com> wrote:

 I think immutable could benefit from a Value Range Propagation-like
 uniqueness


 'unique' has been proposed and heavily discussed before in the news  
 group.
 There even is std.typecons.Unique. Unfortunately, Walter has stated  
 that
 there are issues/difficulties in adding 'unique' to the language.


 What were those difficulties?


 YATC (yet another type constructor)

 Plus, when this was the topic de jour, there were about 3 other type  
 constructors that were touted as "needed" in order to make unique work  
 (like "borrowed" and "lent").  Bartosz had a blog post about it.  This  
 meant you had to accept 3 or 4 new type constructors to get unique.


My impression was that it was more than that. Yes, also adding a  
'lent/borrowed/scope/no escape' and a 'owned' type would have greatly  
eased and empowered unique, but these were all talked about in the same  
breath back then. Walter indicated that there was something specific to  
unique which was the problem, probably having to do with transitivity.  
Ultimately, 'unique/mobile', 'lent/borrowed/scope/no escape' and 'owned'  
were all about doing shared memory concurrency better, while the flagship  
concurrency model was message-passing.


 I really like this idea as a way to have unique without the type  
 constructor: http://d.puremagic.com/issues/show_bug.cgi?id=5081


Well, that not unique. That's a way to gain one of the major benefits (the  
building of immutable types) of unique without it. That said, I also would  
like it.
Feb 25 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 25 Feb 2011 23:31:17 -0500, Robert Jacques <sandford jhu.edu>  
wrote:


 On Fri, 25 Feb 2011 22:35:39 -0500, Steven Schveighoffer  
 <schveiguy yahoo.com> wrote:


 On Fri, 25 Feb 2011 19:01:28 -0500, Tomek Sowiński <just ask.me> wrote:


 Robert Jacques napisał:


 On Fri, 25 Feb 2011 02:48:01 -0500, Kevin Bealer
 <kevindangerbealer removedanger.gmail.com> wrote:

 I think immutable could benefit from a Value Range Propagation-like
 uniqueness


 'unique' has been proposed and heavily discussed before in the news  
 group.
 There even is std.typecons.Unique. Unfortunately, Walter has stated  
 that
 there are issues/difficulties in adding 'unique' to the language.


 What were those difficulties?


 YATC (yet another type constructor)

 Plus, when this was the topic de jour, there were about 3 other type  
 constructors that were touted as "needed" in order to make unique work  
 (like "borrowed" and "lent").  Bartosz had a blog post about it.  This  
 meant you had to accept 3 or 4 new type constructors to get unique.


 My impression was that it was more than that. Yes, also adding a  
 'lent/borrowed/scope/no escape' and a 'owned' type would have greatly  
 eased and empowered unique, but these were all talked about in the same  
 breath back then. Walter indicated that there was something specific to  
 unique which was the problem, probably having to do with transitivity.  
 Ultimately, 'unique/mobile', 'lent/borrowed/scope/no escape' and 'owned'  
 were all about doing shared memory concurrency better, while the  
 flagship concurrency model was message-passing.


Unique has other benefits.  You can implicitly cast unique to/from  
immutable.  You can pass a unique reference via a message without it  
having to be immutable.

These would benefit thread-local code, and also message passing.


 I really like this idea as a way to have unique without the type  
 constructor: http://d.puremagic.com/issues/show_bug.cgi?id=5081


 Well, that not unique. That's a way to gain one of the major benefits  
 (the building of immutable types) of unique without it. That said, I  
 also would like it.


Yes, it is a subset of unique, I should have stated it that way.

-Steve
Feb 25 2011
parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 25 Feb 2011 23:49:51 -0500, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Fri, 25 Feb 2011 23:31:17 -0500, Robert Jacques <sandford jhu.edu>  
 wrote:


 On Fri, 25 Feb 2011 22:35:39 -0500, Steven Schveighoffer  
 <schveiguy yahoo.com> wrote:


 On Fri, 25 Feb 2011 19:01:28 -0500, Tomek Sowiński <just ask.me> wrote:


 Robert Jacques napisał:


 On Fri, 25 Feb 2011 02:48:01 -0500, Kevin Bealer
 <kevindangerbealer removedanger.gmail.com> wrote:

 I think immutable could benefit from a Value Range Propagation-like
 uniqueness


 'unique' has been proposed and heavily discussed before in the news  
 group.
 There even is std.typecons.Unique. Unfortunately, Walter has stated  
 that
 there are issues/difficulties in adding 'unique' to the language.


 What were those difficulties?


 YATC (yet another type constructor)

 Plus, when this was the topic de jour, there were about 3 other type  
 constructors that were touted as "needed" in order to make unique work  
 (like "borrowed" and "lent").  Bartosz had a blog post about it.  This  
 meant you had to accept 3 or 4 new type constructors to get unique.


 My impression was that it was more than that. Yes, also adding a  
 'lent/borrowed/scope/no escape' and a 'owned' type would have greatly  
 eased and empowered unique, but these were all talked about in the same  
 breath back then. Walter indicated that there was something specific to  
 unique which was the problem, probably having to do with transitivity.  
 Ultimately, 'unique/mobile', 'lent/borrowed/scope/no escape' and  
 'owned' were all about doing shared memory concurrency better, while  
 the flagship concurrency model was message-passing.


 Unique has other benefits.  You can implicitly cast unique to/from  
 immutable.  You can pass a unique reference via a message without it  
 having to be immutable.


You can't cast immutable to unique.


 These would benefit thread-local code, and also message passing.


Yes, I'd forgot to mention those, even though I prefer 'mobile' over  
'unique', which kinda implies message passing. ('unique' comes from C++,  
while 'mobile' comes from Occam/CSP)


 I really like this idea as a way to have unique without the type  
 constructor: http://d.puremagic.com/issues/show_bug.cgi?id=5081


 Well, that not unique. That's a way to gain one of the major benefits  
 (the building of immutable types) of unique without it. That said, I  
 also would like it.


 Yes, it is a subset of unique, I should have stated it that way.

 -Steve
Feb 25 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 26 Feb 2011 00:41:32 -0500, Robert Jacques <sandford jhu.edu>  
wrote:


 You can't cast immutable to unique.


Yes, you are right.  You actually can't implicitly cast anything to unique.

-Steve
Feb 26 2011