The problem with opX_r (or more powerful template specialization)

Oskar Linde oskar.lindeREM at OVEgmail.com
Fri Nov 3 08:30:30 PST 2006


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



More information about the Digitalmars-d mailing list