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
next sibling parent "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
prev sibling next sibling parent 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

'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? --=20 Tomek
Feb 25 2011
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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