So I’ve been toying a bit with make a math library based on lazy evaluation/expression templates. That is, when you add two matrices, for example, instead of allocating a new matrix with the result, it returns an object that references the two operands and allows you to look up the results lazily, element by element. For example, the type of b in this code
let a = &mat![1u, 2u;
3u, 4u];
let b = a + -(a * a);
is
algebloat::bin_ops::MatrixBinOp<&algebloat::matrix::Matrix,algebloat::un_ops::MatrixUnOp<algebloat::bin_ops::MatrixBinOp<&algebloat::matrix::Matrix,&algebloat::matrix::Matrix,algebloat::bin_ops::OpMul>,algebloat::un_ops::OpNeg>,algebloat::bin_ops::OpAdd>
or (cleaned up):
MatrixBinOp<&Matrix, MatrixUnOp<MatrixBinOp<&Matrix, &Matrix, OpMul>, OpNeg>, OpAdd>
If this reminds of the types you get from chaining Iterators, that’s because Iterator is based on the same concept. This ends up being optimized pretty well by the compiler and leads to efficient code (if somewhat distasteful error messages).
Now, let’s say I wanted to have a generic function where I take two of these lazy objects and perform some mathematical operation on them (I’ll limit myself to just addition and multiplication). Here’s what the function signature ends up looking like:
fn add_or_mul<
T: MatrixRawGet + SameShape + MatrixShape + Clone +
Add<T, MatrixBinOp<T, T, OpAdd>> +
Mul<T, MatrixBinOp<T, T, OpMul>> +
Add<MatrixBinOp<T, T, OpAdd>, MatrixBinOp<T, MatrixBinOp<T, T, OpAdd>, OpAdd>> +
Add<MatrixBinOp<T, T, OpMul>, MatrixBinOp<T, MatrixBinOp<T, T, OpMul>, OpAdd>> +
Mul<MatrixBinOp<T, T, OpMul>, MatrixBinOp<T, MatrixBinOp<T, T, OpMul>, OpMul>> +
Mul<MatrixBinOp<T, T, OpAdd>, MatrixBinOp<T, MatrixBinOp<T, T, OpAdd>, OpMul>> +
Add<U, MatrixBinOp<T, U, OpAdd>> +
Mul<U, MatrixBinOp<T, U, OpMul>> +
Add<MatrixBinOp<T, U, OpAdd>, MatrixBinOp<T, MatrixBinOp<T, U, OpAdd>, OpAdd>> +
Add<MatrixBinOp<T, U, OpMul>, MatrixBinOp<T, MatrixBinOp<T, U, OpMul>, OpAdd>> +
Mul<MatrixBinOp<T, U, OpMul>, MatrixBinOp<T, MatrixBinOp<T, U, OpMul>, OpMul>> +
Mul<MatrixBinOp<T, U, OpAdd>, MatrixBinOp<T, MatrixBinOp<T, U, OpAdd>, OpMul>>
,
U: MatrixRawGet + SameShape + MatrixShape + Clone +
Add<U, MatrixBinOp<U, U, OpAdd>> +
Mul<U, MatrixBinOp<U, U, OpMul>> +
Add<MatrixBinOp<U, U, OpAdd>, MatrixBinOp<U, MatrixBinOp<U, U, OpAdd>, OpAdd>> +
Add<MatrixBinOp<U, U, OpMul>, MatrixBinOp<U, MatrixBinOp<U, U, OpMul>, OpAdd>> +
Mul<MatrixBinOp<U, U, OpMul>, MatrixBinOp<U, MatrixBinOp<U, U, OpMul>, OpMul>> +
Mul<MatrixBinOp<U, U, OpAdd>, MatrixBinOp<U, MatrixBinOp<U, U, OpAdd>, OpMul>> +
Add<T, MatrixBinOp<U, T, OpAdd>> +
Mul<T, MatrixBinOp<U, T, OpMul>> +
Add<MatrixBinOp<U, T, OpAdd>, MatrixBinOp<U, MatrixBinOp<U, T, OpAdd>, OpAdd>> +
Add<MatrixBinOp<U, T, OpMul>, MatrixBinOp<U, MatrixBinOp<U, T, OpMul>, OpAdd>> +
Mul<MatrixBinOp<U, T, OpMul>, MatrixBinOp<U, MatrixBinOp<U, T, OpMul>, OpMul>> +
Mul<MatrixBinOp<U, T, OpAdd>, MatrixBinOp<U, MatrixBinOp<U, T, OpAdd>, OpMul>>
>(a: T, b: U)
{
}
Quite a mouthful, no? In fact, I estimate that it takes n * (n + 1) * m * m operator-specific type bounds (where n is the number of operations and m is the number of parameters). I overload 5 operators in my library, so for 2 parameters I’d need 120 of those bounds! That’s most likely longer than the function itself if I lay them out like this. It’s easy to get over a thousand lines in this signature with relatively small number of function arguments.
The kicker is that it doesn’t even work, because all those add and mul methods conflict, and there’s no easy way to disambiguate them (is this a bug?).
This explosion isn’t really just because of of this laziness. Consider matrix multipication, something introduced using a trait in my library. If I wanted to do only that, then my function signature is a lot simpler:
fn mat_mul<
T: MatrixRawGet + MatrixShape + Clone,
U: MatrixRawGet + MatrixShape + Clone
>(a: T, b: U)
{
}
That works just fine, there are no second order growth terms. The reason why this works here is because in my library I have this implementation:
impl<LHS: MatrixShape + MatrixRawGet,
RHS: MatrixShape + MatrixRawGet>
MatrixMultiply<RHS> for LHS
{
}
I cannot do that for the operator overloading traits, due to coherence rules.
So my question is… how to resolve this? From my perspective, operator overloading traits are fundamentally flawed as they simply don’t work with coherence. I must have that kind of generic implementation for the generic usage of my types to be sane.
My idea to resolve this is to abandon traits as a method for operator overloading, and do things like is done by the old-Rust, Haskell, Scala, C++ and probably every other language out there. That is, operators would literally just call some magically named functions. Thus, what I’d be able to do is this:
trait MyAdd<T, R>
{
#[operator(+)]
fn add(&self, rhs: &T) -> R;
}
And the compiler, when seeing a + b would desugar it to a.+(b). You’d lose the auto-ref behavior of the right-hand side, but frankly, if you are bothered by it, you should picket for the addition of auto-ref in general argument positions… what makes operators so special, after all? Either way, for built-in types, the rhs could be taken by value. I.e. the Add definition in core::ops would become:
trait Add<T, R>
{
#[operator(+)]
fn add(&self, rhs: T) -> R;
}
This would preserve the current syntax for Copy types. In particular, I am not advocating for the removal of the traits in core::ops, but rather demoting their special status as the sole way to obtain operator overloading. If I cared for generic code outside my library wanting to interface with it via the core::ops traits, I can also implement them.
Some other alternatives I heard mentioned was to add a way to declare custom operators… but let’s be serious here. I want this addressed before 1.0 fixes these broken traits in stone. Even if that were an option, why leave the common operators crippled?
I’m going to think about this some more and write-up an RFC, but first I wanted to check if there were any other ideas to fixing my issues.