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
