Operator overloading -- lets collect some use cases

[Don]

Don wrote:
> Daniel Keep wrote:
>>
>>
>> Andrei Alexandrescu wrote:
>>> [snip]
>>>
>>> All right, let's do this with operator overloading :o). Ideas? I have 
>>> a couple, but I don't want to introduce bias.
>>>
>>> Andrei
>>
>> The only idea I can come up with is to introduce the following:
>>
>> struct Vector
>> {
>>     macro opExpression(ast)
>>     {
>>         ...
>>     }
>> }
>>
>> The compile-time opExpression macro's job is to spit out a function 
>> that takes each leaf of the AST as an argument and returns the final 
>> value of the expression.
>>
>> You could simplify it by ensuring that you don't get any 
>> subexpressions that don't result in the type "Vector".  For example:
>>
>> Vector a, b, c;
>> double g, h;
>>
>> a = b + (g*h) * c;
>>
>> The AST would have "(g*h)" as a single node of type double.
>>
>> Of course, this would probably be exceedingly complex, both on the 
>> compiler and user side of things.  I can't imagine what the contents 
>> of that macro would even look like...
> 
> My BLADE library pretty much does that, so you don't need to guess.
> The ast is a string of the form "A=B+(C*D)", together with a type tuple 
> Tuple!(Vector, Vector, double, Vector), and a values array 
> ["a","b","(g*h)","c"].
> ("g*h" is something like "4.564e+2" if g and h are compile-time constants).
> One approach would be to look at that code and try to simplify it.

It performs the following steps. Note that it uses [5...3, 6, , 2..$]
or [5...3, 6, 0..$, 2..$] syntax for multi-dimensional slicing.

=== (1) Simplify the expression. ===
(A) Remove all duplicate symbols.
(B) Combine all scalars into a single scalar. Combine slicing operations 
into vector variables.
(C) Deal with slices.
     - A[B..C, whatever][D..E] = A[(B+D)..(B+E), whatever] for any 
non-slicable expression A, including something ending with an index.
          Assert(E-D <= C-B).
       (Special case A[B..$, whatever][D..$] = A[(B+D)..$, whatever])
     - A[whatever][D..E] = A[D..E, whatever] if A is slicable.
(D) Rank and arithmetic transformations.
     - Use slicing distributive law for linear algebra:
       Given A[B..C] for expressions A,B,C
       where B and C are non-slicable, and A is slicable, the slice
       can be moved to every vector inside A. Note that this may
       convert matrix multiplications into dot products.
     - Remove unary minus where possible, eg A-(-B) => A+B, abs(-A) => 
abs(A).
     - Use associativity of * in intrinsics:
       sum(A*V) => A*sum(V), abs(A*B) => abs(A)*abs(B)
(E) Expression standardisation
     - Move multiplies to left: Convert A[]*B into B*A[] (assumes * is 
commutative, not valid for quaternions).
     - Convert C-A*B into C+(-A)*B whenever possible.
(F) Remove '$'. Convert x[$] into x[x.length].
(G) Check all of the ranks for each operation. Add each one to the list 
of asserts.

=== (2) Categorize the expression ===
This determines which type of loop it is. For example, with a 
matrix-vector multiply you have nested loops.

=== (3) Generate asserts ===
Spit out all the asserts which were generated during the simplification 
pass.

=== (4) Generate code, based on expression category ===
I only did this for a few cases, but it's generally pretty 
straightforward. It would get much more complicated once you start 
adding cache blocking techniques and sparse matrices...

I completely implemented steps 1 to 3, so this isn't complete fantasy.

> 
>>
>> The one positive to this method is that it's about as general as you 
>> can get; assuming this was implemented, it would hopefully be possible 
>> to implement a simpler scheme on top of it.
>>
>> struct Vector
>> {
>>     mixin FusionOverloadFor!("+","-","*","/",".dot",".cross");
>> }
>>
>> I really hope there's a better way.
>>
>>   -- Daniel