Changeset 129

Timestamp:

11/06/07 02:44:19 (1 year ago)

Author:

Don Clugston

Message:

BladeRank? now works for unary operators. First steps to constant folding/vector expression simplification.

Files:

• trunk/blade/Blade.d (modified) (1 diff)
• trunk/blade/BladeRank.d (modified) (6 diffs)
• trunk/blade/SyntaxTree.d (modified) (2 diffs)

trunk/blade/Blade.d

@@ -275 +275 @@
-}
-
+/+
+// Simplify a vector expression
+//  - Use slicing distributive law: A[B..C] for expressions A,B,C
+//     where B and C are both rank 0, and A is rank 1, the slice can
+//     be moved to every vector inside A.
+//  - Convert A[]*B into B*A[] (only where * is commutative,
+//      not valid for quaternions).
+// Use associativity of *: A*(B*C[]) == (A*B)*C[]
+// Convert -A*B into +(-A)*B whenever possible.
+// Combine all scalars into a single scalar.
+void simplify(inout AbstractSyntaxTree tree)
+{
+    // Part 1: simplifications which only change the expression string.
+    for (int i=0; i<tree.expression.length; ++i) {
+         int x = i+exprLength(expression[i..$]);
+         if (x==tree.expression.length) continue;
+         if (tree.expression[x+1]=='[') { // potentially a slice
+            int y = x + 1 + exprLength(tree.expression[x+1..$-1])
+            if (y+2<tree.expression.length && tree.expression[y..y+1]=="..") {
+                // it's a slice
+            }
+             
+         }        
+    }
+    // Part 2: simplifications which change the types
+}
++/
-
-// Categorise the expression, and dispatch to the appropriate code generator.

trunk/blade/BladeRank.d

@@ -115 +115 @@
-int exprLength(char [] s)
-{
-s[0]>='A' && s[0]<='Z
+(s[0]>='A' && s[0]<='Z') || s[0]=='$
-        return 0;
-    int i = 0;
@@ -135 +135 @@
-}
-
+/** Determine the (tensor) rank of a sub-expression
+*/
+int subexprRank(char [] expr, int [] rank)
+{
+    if (expr.length==1) {
+        if (expr=="$") return 0;
+        return rank[expr[0]-'A'];
+    }
+    // strip off the parentheses
+    return exprRank(expr[1..$-1], rank);
+}
+
-/** Returns the (tensor) rank of the expression expr.
- *
@@ -142 +154 @@
- */
-int exprRank(char [] expr, int [] rank)
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    int x = exprLength(expr);
-    int y = x+1;
-
-
+
+
+
-    char [] op = expr[x+1..y+1];    
-    char [] left = expr[0..x+1];
-    char [] right = expr[y+1..$];
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    if (op=="+" || op=="-" || op=="=" || op=="+=" || op=="-=") {
-        assert(lrank==rrank, "Rank error in expression");
+        return lrank;
+    }
+    if (op=="~") { // concatentating scalars and vectors, or vectors and matrices, is permitted
+        assert(lrank==rrank || lrank==(rrank+1) || rrank==(lrank+1), "Rank error in expression");
+        return (lrank>rrank)? lrank: rrank;
+    }
+    if (op=="~=") { // can do vector~=scalar, but not scalar~=vector.
+        assert(lrank==rrank || lrank==(rrank+1), "Rank error in expression");
-        return lrank;
-    }
@@ -170 +230 @@
-
-unittest {
-B*C)", [1,1,
+(((++B)+D)--)*C)", [1,0,1, 
-    assert(exprRank("A+(B*C)", [0,0,0])==0);
-    assert(exprRank("A=(B*C)", [2,0,2])==2);
@@ -176 +236 @@
-    assert(exprRank("D+=((A+C)*B)", [2,0,2,2])==2);
-    assert(exprRank("D+=((A&C)*B)", [0,1,0,1])==1);
+    assert(exprRank("A+=(A[B..C])", [3,0,0])==3);
+    assert(exprRank("C+=(A[B])", [3,0,2])==2);
+    assert(exprRank("C~=(((A[B])[B])~C)", [3,0,2])==2);
-}
-
@@ -212 +275 @@
-static assert(is(exprElementType!("A+(B*C)", float[], double[], double).ElemType == double));
-}
+
+char [] subexprSimplify(char [] expr, int [] rank)
+{
+    if (expr.length==1) return expr;
+    // strip off the parentheses before simplifying
+    return "(" ~ exprSimplify(expr[1..$-1], rank) ~ ")";
+}
+
+// TODO: Rewrite the expression, taking advantage of distributivity of [] and
+// associativity of *.
+char [] exprSimplify(char [] expr, int [] rank)
+{    
+    // BUG: also need to deal with comma, ?:, &&, ||, is, !is, in, 
+    // unary &, unary !
+        
+    // Deal with ++ and --.
+    if (expr.length>2 && (expr[0..2]=="++" || expr[0..2]=="--")) {
+        return expr[0..2] ~ subexprSimplify(expr[2..$], rank);
+    }
+    if (expr.length>2 && (expr[$-2..$]=="++" || expr[$-2..$]=="--")) {
+        return subexprSimplify(expr[0..$-2], rank) ~ expr[$-2..$];
+    }
+    // Deal with unary operators
+    if (expr[0]=='+' || expr[0]=='-') return subexprSimplify(expr[1..$], rank);
+   
+    int x = exprLength(expr);
+    int y = x+1;
+    // Deal with shifts, op=, and NCEG operators
+    while (expr[y+1]=='<' || expr[y+1]=='>' || expr[y+1]=='=') ++y;    
+
+    char [] op = expr[x+1..y+1];    
+    char [] left = expr[0..x+1];
+    char [] right = expr[y+1..$];
+    if (expr[x+1]=='[') right = expr[y+1..$-1]; // drop off the ']'.
+    int lrank = subexprRank(left, rank);
+    if (op=="[") {
+        // TODO:
+        // We know that 'right' is a 100% scalar. We only need to deal with 'left'
+        // We already know that left is a vector or matrix.
+        // where I, J, K are scalars:
+        // (X*I)[K]  -->  I*(X[K])   where X is any tensor expression
+        // (I*X)[K]  -->  I*(X[K])
+        // 
+        return subexprSimplify(left, rank) ~ "[" ~ right ~ "]";
+    }
+    //TODO:
+    return subexprSimplify(left, rank) ~ op ~ subexprSimplify(right, rank);
+}
+
+unittest {
+     assert(exprSimplify("A+=((B++)*(C[B..B]))", [1,0,1])=="A+=((B++)*(C[B..B]))");
+}

trunk/blade/SyntaxTree.d

@@ -263 +263 @@
-    preOp!("--") opSubAssign(T:int=int)(int x){ return null; }  
-
-text ~ "[" ~ T.text ~ ".." ~ U.text ~"]
-text ~ "[" ~ AllText!(T) ~ "]
+"(" ~ text ~ "[" ~ T.text ~ ".." ~ U.text ~"])
+"(" ~ text ~ "[" ~ AllText!(T) ~ "])
-    AST!("(" ~ text ~ "(" ~ AllText!(T) ~ "))") opCall(T...)(T){ return null; }
-    AST!("((" ~ text ~ "[" ~ AllText!(T) ~ "])=" ~ U.text ~ ")") opIndexAssign(U, T...)(U,T){ return null; }
@@ -361 +361 @@
-    assert(mixin(mixin_getPrecedence("A[B,$-C/D]=E+F"))=="(A[B,($-(C/D))])=(E+F)");
-    assert(mixin(mixin_getPrecedence("A[B]=E+F"))=="(A[B])=(E+F)");
-
-
-
+
+
+
+
-    assert(mixin(mixin_getPrecedence("(A+B)  in(C^D)"))=="(A+B)in(C^D)");
-    assert(mixin(mixin_getPrecedence("A"))=="A");