www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The problem with opX_r (or more powerful template specialization)

reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
I have written about this before, but haven't gotten any reaction. 
Apologies for the long post that follows.

Problem 1
---------

With todays behavior, I can make a custom template type, say:

struct Matrix(T) { alias T ElementType; ...}

and implement template operator overloads

opAdd(U)(U x) {
   static if (is(typeof(T+U))) { // Matrix + element
     // return a matrix with x added to each element
   } else static if (is(U.ElementType T2)) { // Matrix + Matrix
     // return a Matrix!(typeof(T+T2)) that is the result of
     // a element wise addition of *this and x
   }
} etc...

so that given,

Matrix!(Uncertain!(double)) m;

the following works:

m += 2;
m + 2;
m - 2;
m * 2;
m / 2;
2 + m;
2 * m;

But the following isn't possible to implement today:

2 - m;
2 / m;


The reason
----------

You can not define an

opSub_r(T)(T x) {...}

overload, if you already have an opSub(T)(T x) {...}, because they will 
generate conflicts. opAdd and opMul "works" because of the automatic 
commutative fallback for those operators.

There is no way to define a opSub_r template function for only the cases 
where opSub(T)(T x) { ...} doesn't exist.


Problem 2
---------

opAdd, opMul and other commutative operators automatically fall back to 
the commutative overload if no matching overload is found. This means 
that it could silently breach the incommutability of an underlying type.

Example:
Say you have an incommutative x:

Incommutative x;

for which (1 + x) != (x + 1)

and I use the above Matrix type:

Matrix!(Incommutative) n;

1 + n will silently be transformed into n + 1 which will evaluate
(x + 1) instead of (1 + x) and give the wrong result.

Problem Summary
---------------

To properly implement a custom generic algebraic type, such as 
Matrix(T), one needs to provide both opX and opX_r overloads for all 
supported operators X. You have no way of knowing what operators on T 
are commutative and what aren't, so by not implementing opX_r, for for 
example opAdd, you risk silently disregarding the incommutability of T.
The problem here is that you can't do that today.


Solutions
---------

I see two possible solutions.

1) Change the opX_r overloading rules, so that

opX_r(T)(T x) {...}
opX(T)(T x) {...}

can coexist. opX_r is picked only of no opX overload is found.

This would basically suggest that all opX_r operator overloads gets 
demoted one priority step so that having both a matching opX and a 
matching opX_r will pick the opX overload. Not as today, giving a 
conflict error.

With this, the opX_r overloads would mimic the automatic commutative 
behavior of opAdd, opMul, opAnd, opOr, et.al.

This change would solve the above mentioned problems, but there are more 
complex problems that remain. (Matrix!(Matrix!(Uncertain!(double))) for 
instance) The following solution is more general:

2) Make it possible somehow to explicitly define an opX_r(?)(T x) 
overload only for the cases where no opX(T)(T x) matches.

I have two different suggestions for this.

A) (My favourite) Introduce an extremely powerful special template 
specialization syntax:

template Temp(T: <boolean value>) {}

that matches only when the boolean value is true. The boolean value 
should be evaluated first when looking for possible specializations for 
a given type and allow a template expression dependent on T, making the 
following possible:

template Temp(T: IsNumeric!(T)) {...}
template Temp(T: HasNoMatchingOpXOverload1(typeof(*this),T)) {...}
template Temp(T: ForwardIterable!(T)) {...}
etc...

B) (As partial specialization isn't very well supported by IFTI in DMD 
today, and as an alternative. (I haven't thought this though carefully))
Make it possible for a template function instantiation to fail without 
generating and error when looking for the existence of a operator 
overload (and in other cases too).

For example, a static assert(0); could make the instantiation fail, but 
let the compiler look for other templates/functions instead.

/Oskar
Nov 03 2006
parent reply Sean Kelly <sean f4.ca> writes:
Oskar Linde wrote:
 1) Change the opX_r overloading rules, so that
 
 opX_r(T)(T x) {...}
 opX(T)(T x) {...}
 
 can coexist. opX_r is picked only of no opX overload is found.

I thought operators worked this way: x = y - z; 1. Call y.opSub(z) if it exists. 2. If not, call z.opSub_r(y). ie. I had thought that the opX_r operations were for situations where the called object was on the right-hand side of the operation. Assuming this were true, there should be no problem in having opX and opX_r coexist peacefully.
 This would basically suggest that all opX_r operator overloads gets 
 demoted one priority step so that having both a matching opX and a 
 matching opX_r will pick the opX overload. Not as today, giving a 
 conflict error.

I suppose I really need to read up on D's operator overloading. I had no idea this currently happened. Sean
Nov 03 2006
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Sean Kelly wrote:
 Oskar Linde wrote:
 1) Change the opX_r overloading rules, so that

 opX_r(T)(T x) {...}
 opX(T)(T x) {...}

 can coexist. opX_r is picked only of no opX overload is found.

I thought operators worked this way: x = y - z; 1. Call y.opSub(z) if it exists. 2. If not, call z.opSub_r(y). ie. I had thought that the opX_r operations were for situations where the called object was on the right-hand side of the operation. Assuming this were true, there should be no problem in having opX and opX_r coexist peacefully.

Nope. From the spec: "1. The expression is rewritten as both: a.opfunc(b) b.opfunc_r(a) If any a.opfunc or b.opfunc_r functions exist, then overloading is applied across all of them and the best match is used." So those two forms (direct and reverse) compete on equal priority. The ones that have secondary priority are the commutative ones (commutative-direct, commutative-reverse), if the operator allows commutation. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Nov 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
Bruno Medeiros wrote:
 Sean Kelly wrote:
 Oskar Linde wrote:
 1) Change the opX_r overloading rules, so that

 opX_r(T)(T x) {...}
 opX(T)(T x) {...}

 can coexist. opX_r is picked only of no opX overload is found.

I thought operators worked this way: x = y - z; 1. Call y.opSub(z) if it exists. 2. If not, call z.opSub_r(y). ie. I had thought that the opX_r operations were for situations where the called object was on the right-hand side of the operation. Assuming this were true, there should be no problem in having opX and opX_r coexist peacefully.

Nope. From the spec: "1. The expression is rewritten as both: a.opfunc(b) b.opfunc_r(a) If any a.opfunc or b.opfunc_r functions exist, then overloading is applied across all of them and the best match is used." So those two forms (direct and reverse) compete on equal priority.

So if a implemented an opSub(b) and b implemented an opSub_r(a) I'd get a compiler error about an ambiguous overload? This seems somewhat sub-optimal. Why was it implemented this way? Sean
Nov 07 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Sean Kelly wrote:
 Bruno Medeiros wrote:
 Sean Kelly wrote:
 Oskar Linde wrote:
 1) Change the opX_r overloading rules, so that

 opX_r(T)(T x) {...}
 opX(T)(T x) {...}

 can coexist. opX_r is picked only of no opX overload is found.

I thought operators worked this way: x = y - z; 1. Call y.opSub(z) if it exists. 2. If not, call z.opSub_r(y). ie. I had thought that the opX_r operations were for situations where the called object was on the right-hand side of the operation. Assuming this were true, there should be no problem in having opX and opX_r coexist peacefully.

Nope. From the spec: "1. The expression is rewritten as both: a.opfunc(b) b.opfunc_r(a) If any a.opfunc or b.opfunc_r functions exist, then overloading is applied across all of them and the best match is used." So those two forms (direct and reverse) compete on equal priority.

So if a implemented an opSub(b) and b implemented an opSub_r(a) I'd get a compiler error about an ambiguous overload? This seems somewhat sub-optimal. Why was it implemented this way?

I think it makes sense. Given the expression "a + b", it's not clear which add operation should be used. You can disambiguate by calling the method explicitly: a.opAdd(b). Better would be if D had out-of-class operators. Then you could just have a free function - T opAdd(A a, B b) and you don't have to worry about whether a or b owns this particular combination of addition. I believe the general rule of thumb in C++ is that operators that don't modify their arguments (like +-/*) should be stand-alone functions. --bb
Nov 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
Bill Baxter wrote:
 Sean Kelly wrote:
 Bruno Medeiros wrote:
 Sean Kelly wrote:
 Oskar Linde wrote:
 1) Change the opX_r overloading rules, so that

 opX_r(T)(T x) {...}
 opX(T)(T x) {...}

 can coexist. opX_r is picked only of no opX overload is found.

I thought operators worked this way: x = y - z; 1. Call y.opSub(z) if it exists. 2. If not, call z.opSub_r(y). ie. I had thought that the opX_r operations were for situations where the called object was on the right-hand side of the operation. Assuming this were true, there should be no problem in having opX and opX_r coexist peacefully.

Nope. From the spec: "1. The expression is rewritten as both: a.opfunc(b) b.opfunc_r(a) If any a.opfunc or b.opfunc_r functions exist, then overloading is applied across all of them and the best match is used." So those two forms (direct and reverse) compete on equal priority.

So if a implemented an opSub(b) and b implemented an opSub_r(a) I'd get a compiler error about an ambiguous overload? This seems somewhat sub-optimal. Why was it implemented this way?

I think it makes sense. Given the expression "a + b", it's not clear which add operation should be used.

Hrm, true enough.
 You can disambiguate by calling the method explicitly: a.opAdd(b).
 
 Better would be if D had out-of-class operators.  Then you could just 
 have a free function - T opAdd(A a, B b) and you don't have to worry 
 about whether a or b owns this particular combination of addition.  I 
 believe the general rule of thumb in C++ is that operators that don't 
 modify their arguments (like +-/*) should be stand-alone functions.

That's the most flexible certainly, but it often means friend functions so data is accessible for the operation. I think it's often easier to implement addition simply by creating a temporary and using AddAssign, expression templates aside. Sean
Nov 08 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Sean Kelly wrote:
 Bill Baxter wrote:
 
 Sean Kelly wrote:

 Bruno Medeiros wrote:

 Sean Kelly wrote:

 Oskar Linde wrote:

 1) Change the opX_r overloading rules, so that

 opX_r(T)(T x) {...}
 opX(T)(T x) {...}

 can coexist. opX_r is picked only of no opX overload is found.

I thought operators worked this way: x = y - z; 1. Call y.opSub(z) if it exists. 2. If not, call z.opSub_r(y). ie. I had thought that the opX_r operations were for situations where the called object was on the right-hand side of the operation. Assuming this were true, there should be no problem in having opX and opX_r coexist peacefully.

Nope. From the spec: "1. The expression is rewritten as both: a.opfunc(b) b.opfunc_r(a) If any a.opfunc or b.opfunc_r functions exist, then overloading is applied across all of them and the best match is used." So those two forms (direct and reverse) compete on equal priority.

So if a implemented an opSub(b) and b implemented an opSub_r(a) I'd get a compiler error about an ambiguous overload? This seems somewhat sub-optimal. Why was it implemented this way?

I think it makes sense. Given the expression "a + b", it's not clear which add operation should be used.

Hrm, true enough.
 You can disambiguate by calling the method explicitly: a.opAdd(b).

 Better would be if D had out-of-class operators.  Then you could just 
 have a free function - T opAdd(A a, B b) and you don't have to worry 
 about whether a or b owns this particular combination of addition.  I 
 believe the general rule of thumb in C++ is that operators that don't 
 modify their arguments (like +-/*) should be stand-alone functions.

That's the most flexible certainly, but it often means friend functions so data is accessible for the operation. I think it's often easier to implement addition simply by creating a temporary and using AddAssign, expression templates aside.

Right. I was about to say that, actually. In most cases your out-of-class add operator is just implemented in terms of one or the other opAddAssign (operator+=) functinos, so you don't need any special access to the internals of the class. And that means that for the a+b case you're making the choice of which add operator to use explicitly by whether you use b's += or a's +=. I guess that's what's missing in D, some way to write an operator function outside of both A and B that makes the final decision. --bb
Nov 08 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Bill Baxter wrote:
 I guess that's what's missing in D, some way to write an operator 
 function outside of both A and B that makes the final decision.

Supporting that means supporting ADL, something I want to avoid.
Nov 08 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Walter Bright wrote:
 Bill Baxter wrote:
 I guess that's what's missing in D, some way to write an operator 
 function outside of both A and B that makes the final decision.

Supporting that means supporting ADL, something I want to avoid.

Ah, Argument Dependent Lookup, aka Koenig Lookup. Ok. Took me a sec to figure out what the Anti-Defamation League had to do with operator overloads. ;-) --bb
Nov 08 2006