On Tue, Oct 13, 2009 at 10:39 AM, Chad J <chadjoan@__spam.is.bad__gmail.com> wrote:
> Forgotten already?

Apparently, yes!

> http://prowiki.org/wiki4d/wiki.cgi?DocComments/Property#Semantic
>
> This is the same problem as property lvalue-ness and it has the same solution.  When property rewriting is done correctly, the opIndexAssign problem can then be solved almost for free.
>
> Just treat opIndex expressions as properties, and when they are the subject of a side-effect then make sure the write property (AKA opIndexAssign) gets called.

Good call.

--bb

Don wrote:
> Andrei Alexandrescu wrote:
>> Right now we're in trouble with operators: opIndex and opIndexAssign don't seem to be up to snuff because they don't catch operations like
>>
>> a[b] += c;
>>
>> with reasonable expressiveness and efficiency.
>>
>> Last night this idea occurred to me: we could simply use overloading with the existing operator names. Consider:
>>
>> a += b
>>
>> gets rewritten as
>>
>> a.opAddAssign(b)
>>
>> Then how about this - rewrite this:
>>
>> a[b] += c
>>
>> as
>>
>> a.opAddAssign(b, c);
>>
>> There's no chance of ambiguity because the parameter counts are different. Moreover, this scales to multiple indexes:
>>
>> a[b1, b2, ..., bn] = c
>>
>> gets rewritten as
>>
>> a.opAddAssign(b1, b2, ..., bn, c)
>>
>> What do you think? I may be missing some important cases or threats.
>>
>>
>> Andrei
> 
> Well timed. I just wrote this operator overloading proposal, part 1.
> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
> I concentrated on getting the use cases established.
> 
> The indexing thing was something I didn't have a solution for.
> 
> BTW we need to deal with slices as well as indexes. I think the way to do this is to make a slice into a type of index.


I like the idea of enforcing relationships between operators. In fact, I think we can take it even further, and require that operator overloading in general *must* follow mathematical rules, and anything else leads to undefined behaviour. For example, if n is an integer, a and b are scalars, and x and y are general types, the compiler should be free to rewrite

         n*x  <-->  x + x + ... + x    <-->  2*x + 2*x + ...
        x^^n  <-->  x * x * ... * x    <-->  x^^2 * x^^2 * ...
   x/a + y/b  <-->  (b*x + a*y)/(a*b)

and so on, based on what it finds to be the most efficient operations. (Note how I snuck my favourite suggestion for an exponentiation operator in there. I *really* want that.)

-Lars

Lars T. Kyllingstad wrote:
> Don wrote:
>> Andrei Alexandrescu wrote:
>>> Right now we're in trouble with operators: opIndex and opIndexAssign don't seem to be up to snuff because they don't catch operations like
>>>
>>> a[b] += c;
>>>
>>> with reasonable expressiveness and efficiency.
>>>
>>> Last night this idea occurred to me: we could simply use overloading with the existing operator names. Consider:
>>>
>>> a += b
>>>
>>> gets rewritten as
>>>
>>> a.opAddAssign(b)
>>>
>>> Then how about this - rewrite this:
>>>
>>> a[b] += c
>>>
>>> as
>>>
>>> a.opAddAssign(b, c);
>>>
>>> There's no chance of ambiguity because the parameter counts are different. Moreover, this scales to multiple indexes:
>>>
>>> a[b1, b2, ..., bn] = c
>>>
>>> gets rewritten as
>>>
>>> a.opAddAssign(b1, b2, ..., bn, c)
>>>
>>> What do you think? I may be missing some important cases or threats.
>>>
>>>
>>> Andrei
>>
>> Well timed. I just wrote this operator overloading proposal, part 1.
>> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
>> I concentrated on getting the use cases established.
>>
>> The indexing thing was something I didn't have a solution for.
>>
>> BTW we need to deal with slices as well as indexes. I think the way to do this is to make a slice into a type of index.
> 
> 
> I like the idea of enforcing relationships between operators. In fact, I think we can take it even further, and require that operator overloading in general *must* follow mathematical rules, and anything else leads to undefined behaviour. For example, if n is an integer, a and b are scalars, and x and y are general types, the compiler should be free to rewrite
> 
>          n*x  <-->  x + x + ... + x    <-->  2*x + 2*x + ...
>         x^^n  <-->  x * x * ... * x    <-->  x^^2 * x^^2 * ...
>    x/a + y/b  <-->  (b*x + a*y)/(a*b)
> 
> and so on, based on what it finds to be the most efficient operations. 

Unfortunately, the last one doesn't work for reals. a*b could overflow or underflow.
x/ real.max + y / real.max   is exactly 2.0 if x and y are both real.max
But
(real.max * x + real.max *y)/(real.max * real.max) is infinity/infinity = NaN.

The others don't always work in general, either. I'm worried about decimal floats. Say n==10, then it's an exact operation; but addition isn't exact. It always works for n==2, since there's at most one roundoff in both cases.

But I do feel that with floating-point, we've lost so many identities, that we must preserve every one which we have left.

> (Note how I snuck my favourite suggestion for an exponentiation operator in there. I *really* want that.)

I want it too. Heck, I might even make a patch for it <g>.

Don wrote:
> Lars T. Kyllingstad wrote:
>> Don wrote:
>>> Andrei Alexandrescu wrote:
>>>> Right now we're in trouble with operators: opIndex and opIndexAssign don't seem to be up to snuff because they don't catch operations like
>>>>
>>>> a[b] += c;
>>>>
>>>> with reasonable expressiveness and efficiency.
>>>>
>>>> Last night this idea occurred to me: we could simply use overloading with the existing operator names. Consider:
>>>>
>>>> a += b
>>>>
>>>> gets rewritten as
>>>>
>>>> a.opAddAssign(b)
>>>>
>>>> Then how about this - rewrite this:
>>>>
>>>> a[b] += c
>>>>
>>>> as
>>>>
>>>> a.opAddAssign(b, c);
>>>>
>>>> There's no chance of ambiguity because the parameter counts are different. Moreover, this scales to multiple indexes:
>>>>
>>>> a[b1, b2, ..., bn] = c
>>>>
>>>> gets rewritten as
>>>>
>>>> a.opAddAssign(b1, b2, ..., bn, c)
>>>>
>>>> What do you think? I may be missing some important cases or threats.
>>>>
>>>>
>>>> Andrei
>>>
>>> Well timed. I just wrote this operator overloading proposal, part 1.
>>> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
>>> I concentrated on getting the use cases established.
>>>
>>> The indexing thing was something I didn't have a solution for.
>>>
>>> BTW we need to deal with slices as well as indexes. I think the way to do this is to make a slice into a type of index.
>>
>>
>> I like the idea of enforcing relationships between operators. In fact, I think we can take it even further, and require that operator overloading in general *must* follow mathematical rules, and anything else leads to undefined behaviour. For example, if n is an integer, a and b are scalars, and x and y are general types, the compiler should be free to rewrite
>>
>>          n*x  <-->  x + x + ... + x    <-->  2*x + 2*x + ...
>>         x^^n  <-->  x * x * ... * x    <-->  x^^2 * x^^2 * ...
>>    x/a + y/b  <-->  (b*x + a*y)/(a*b)
>>
>> and so on, based on what it finds to be the most efficient operations. 
> 
> Unfortunately, the last one doesn't work for reals. a*b could overflow or underflow.
> x/ real.max + y / real.max   is exactly 2.0 if x and y are both real.max
> But
> (real.max * x + real.max *y)/(real.max * real.max) is infinity/infinity = NaN.

Good point. I am thinking like a mathematician, not a programmer. :)


> The others don't always work in general, either. I'm worried about decimal floats. Say n==10, then it's an exact operation; but addition isn't exact. It always works for n==2, since there's at most one roundoff in both cases.

But the case x*2 --> x+x would also likely be the most common in terms of optimisation, right?


> But I do feel that with floating-point, we've lost so many identities, that we must preserve every one which we have left.
> 
>> (Note how I snuck my favourite suggestion for an exponentiation operator in there. I *really* want that.)
> 
> I want it too. Heck, I might even make a patch for it <g>.

If you do, make sure to announce it loudly and clearly on the NG. Don't want to miss it. ;)

-Lars

On Wed, Oct 14, 2009 at 12:48 AM, Lars T. Kyllingstad <public@kyllingen.nospamnet> wrote:
> Don wrote:
>>
>> Andrei Alexandrescu wrote:
>>>
>>> Right now we're in trouble with operators: opIndex and opIndexAssign don't seem to be up to snuff because they don't catch operations like
>>>
>>> a[b] += c;
>>>
>>> with reasonable expressiveness and efficiency.
>>>
>>> Last night this idea occurred to me: we could simply use overloading with the existing operator names. Consider:
>>>
>>> a += b
>>>
>>> gets rewritten as
>>>
>>> a.opAddAssign(b)
>>>
>>> Then how about this - rewrite this:
>>>
>>> a[b] += c
>>>
>>> as
>>>
>>> a.opAddAssign(b, c);
>>>
>>> There's no chance of ambiguity because the parameter counts are different. Moreover, this scales to multiple indexes:
>>>
>>> a[b1, b2, ..., bn] = c
>>>
>>> gets rewritten as
>>>
>>> a.opAddAssign(b1, b2, ..., bn, c)
>>>
>>> What do you think? I may be missing some important cases or threats.
>>>
>>>
>>> Andrei
>>
>> Well timed. I just wrote this operator overloading proposal, part 1.
>> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
>> I concentrated on getting the use cases established.
>>
>> The indexing thing was something I didn't have a solution for.
>>
>> BTW we need to deal with slices as well as indexes. I think the way to do this is to make a slice into a type of index.
>
>
> I like the idea of enforcing relationships between operators. In fact, I think we can take it even further, and require that operator overloading in general *must* follow mathematical rules, and anything else leads to undefined behaviour. For example, if n is an integer, a and b are scalars, and x and y are general types, the compiler should be free to rewrite
>
>         n*x  <-->  x + x + ... + x    <-->  2*x + 2*x + ...
>        x^^n  <-->  x * x * ... * x    <-->  x^^2 * x^^2 * ...
>   x/a + y/b  <-->  (b*x + a*y)/(a*b)
>
> and so on, based on what it finds to be the most efficient operations. (Note how I snuck my favourite suggestion for an exponentiation operator in there. I *really* want that.)

You have to be careful when you go rewriting mathematical expressions on the computer, though.  The numerical error for two mathematically identical expressions can be quite different when evaluated in finite precision arithmetic.

I'd love an exponentiation operator, too.

--bb

Don wrote:
> Well timed. I just wrote this operator overloading proposal, part 1.
> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
> I concentrated on getting the use cases established.

I'm not sure multiplication is generally commutative (e.g. in linear algebra it isn't). So why should a * x be interchangeable with x * a?

Also, the much-discussed identity:

x @= y	<-->	x = x @ y

is difficult to enforce statically in practice. I think some types would want to define both to achieve good efficiency. It would be hard for the compiler to render one unnecessary or to prove that the two are equivalent.


Andrei

On Wed, 14 Oct 2009 10:31:06 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Don wrote:
>> Well timed. I just wrote this operator overloading proposal, part 1.
>> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
>> I concentrated on getting the use cases established.
>
> I'm not sure multiplication is generally commutative (e.g. in linear algebra it isn't). So why should a * x be interchangeable with x * a?
>
> Also, the much-discussed identity:
>
> x @= y	<-->	x = x @ y
>
> is difficult to enforce statically in practice. I think some types would want to define both to achieve good efficiency. It would be hard for the compiler to render one unnecessary or to prove that the two are equivalent.
>
>
> Andrei

When a is a scaler, a * x <=> x * a generally holds. It's only when something isn't a scaler, i.e. x1 * x2 != x2 * x1, that community(?) doesn't hold.

On Wed, 14 Oct 2009 18:39:27 +0400, Robert Jacques <sandford@jhu.edu> wrote:

> On Wed, 14 Oct 2009 10:31:06 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>> Don wrote:
>>> Well timed. I just wrote this operator overloading proposal, part 1.
>>> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
>>> I concentrated on getting the use cases established.
>>
>> I'm not sure multiplication is generally commutative (e.g. in linear algebra it isn't). So why should a * x be interchangeable with x * a?
>>
>> Also, the much-discussed identity:
>>
>> x @= y	<-->	x = x @ y
>>
>> is difficult to enforce statically in practice. I think some types would want to define both to achieve good efficiency. It would be hard for the compiler to render one unnecessary or to prove that the two are equivalent.
>>
>>
>> Andrei
>
> When a is a scaler, a * x <=> x * a generally holds. It's only when something isn't a scaler, i.e. x1 * x2 != x2 * x1, that community(?) doesn't hold.

It's commutativity (http://en.wikipedia.org/wiki/Commutativity)

Andrei Alexandrescu wrote:
> Don wrote:
>> Well timed. I just wrote this operator overloading proposal, part 1.
>> http://www.prowiki.org/wiki4d/wiki.cgi?LanguageDevel/DIPs/DIP7
>> I concentrated on getting the use cases established.
> 
> I'm not sure multiplication is generally commutative (e.g. in linear algebra it isn't). So why should a * x be interchangeable with x * a?

It only applies a is an int or real. Its purpose is to allow constant-folding in the compiler front-end (specifically, when a is a manifest constant).

> Also, the much-discussed identity:
> 
> x @= y    <-->    x = x @ y
> 
> is difficult to enforce statically in practice. I think some types would want to define both to achieve good efficiency. It would be hard for the compiler to render one unnecessary or to prove that the two are equivalent.

Yes, it could not be enforced. But note that there would be no ambiguity as to which should be used in any given expression.
I would propose that the opXXXAssign() variants should exist *only* for performance optimisation, and be completely divorced from the "+=" syntax (effectively, += would be discarded after the parsing step).
My ancient Bugzilla proposal actually included opSubAssign() and opSubAssign_r() for  x = x - y; and x = y - x;
If   the x @= y    <-->    x = x @ y transformations became legal, this would allow unnecessary temporaries to be completely eliminated.

The suggested transformation would be that x = x + y would be transformed into x.opAddAssign(y) whenever it exists, and x = y + x would become x.opAddAssign_r(y)
The transformations would therefore be entirely predictable.

It would make Numpy-style arithmetic impossible (where z=x; x+=y; modifies z, but z = x; x = x+y; does not modify z (under this proposal, the second would be transformed into the first)).

Tightly defined semantics improve performance and reduce the potential for abuse. But, there are existing libraries/techniques which depend on C++'s cavalier, "anything goes" attitude to operator overloading. Are we able to sacrifice them?

On 2009-10-14 23:09:26 +0200, "Robert Jacques" <sandford@jhu.edu> said:

> On Wed, 14 Oct 2009 16:49:28 -0400, Andrei Alexandrescu  <SeeWebsiteForEmail@erdani.org> wrote:
> 
>> Jason House wrote:
>>> Bill Baxter Wrote:
>>> 
>>>> On Wed, Oct 14, 2009 at 7:42 AM, Jason House
>>>> <jason.james.house@gmail.com> wrote:
>>>>> Andrei Alexandrescu Wrote:
>>>>> 
>>>>>> Right now we're in trouble with operators: opIndex and opIndexAssign
>>>>>> don't seem to be up to snuff because they don't catch operations like
>>>>>> 
>>>>>> a[b] += c;
>>>>>> 
>>>>>> with reasonable expressiveness and efficiency.
>>>>> I would hope that *= += /= and friends could all be handled  efficiently with one function written by the programmer. As I see it,  there are 3 basic steps:
>>>>> 1. Look up a value by index
>>>>> 2. Mutate the value
>>>>> 3. Store the result
>>>> And as Chad J reminds us, same goes for in-place property mutations
>>>> like  a.b += c.
>>>> It's just a matter of  accessing  .b  vs .opIndex(b).   And really
>>>> same goes for any function  a.memfun(b) += c could benefit from the
>>>> same thing (a.length(index)+=3 anyone?)
>>>> 
>>>>> it's possible to use opIndex for #1 and opIndexAssign for #3, but  that's not efficient. #1 and #3 should be part of the same function,  but I think #2 shouldnot be. What about defining an opIndexOpOpAssign  that accepts a delegate for #2 and then use compiler magic to  specialize/inline it?
>>>> It could also be done using a template thing to inject the "mutate the
>>>> value" operation:
>>>  The only issue with templates is that they're never virtual
>> 
>> You can make virtuals out of templates, but not templates out of  virtuals. I think Walter is now inclined to look at a template-based  solution for operator overloading. That would save a mighty lot of code  without preventing classes that prefer virtual dispatch from doing so.
>> 
>> Andrei
> 
> I've done something similar for a SmallVec struct. Most of the operator  overloads are actually aliases of templated functions (one each for  uni-ops, bi-ops, bi-op_r and opassign)

I would really like a solution to all the overloading ops, as I missed them in NArray, I think that some small rewriting is ok, but it must be *small*, no magic as already said by other numerics can be tricky.
Also Andrei proposal seem workable, but there is also another solution:

Note that a ref return for opIndex, could work in most situations.
As Bill correctly pointed out sparse matrix offer the most challenging example, there one wants to have two different functions: opIndex and opIndexLhs, the second being called when the index is on the left hand side of an assignment, so that reading a 0 entry in a matrix returns 0, whereas assigning it allocates place for it.
This makes it slightly more complex to control what is being assigned (as you need to return a structure overloading opXAssign, but I think it would be ok in most cases.

Fawzi