Movimentum - Polynomial folding 2

In the previous posting, we created a long list of rules how to rewrite square expressions in the polynomial folder. Now, we have to code this. Obviously, we want to reuse our template matching machinery, which we already use to find constraints that we can expand. Roughly, our code should look like this:

    // Static definition of match template for P[V] + sqrt(E)
    var p = new TypeMatchTemplate<IPolynomial>();
    var e = new TypeMatchTemplate<IAbstractExpr>();
    var sqrtE = new UnaryExpressionTemplate(new PositiveSquareroot(), e);

    var template = p + sqrtE;

    ...

    // Code for rewrite rule using template
    var m = template.CreateMatcher().TryMatch(innerOfSquare);
    if (m != null) {
        var newExpr = m.Match(p).Times(m.Match(p)) +
                        m.Match(p).Times(2) * m.Match(sqrtE) +
                        m.Match(e);
        return newExpr;
    }

However, this code is much too long, and quite unreadable. First of all, the control logic has to vanish into a class so that we can at least write:

    // Static definition of rewrite rule using template
    var rule = new StandardExpressionRewrite(null, null,
                    p + sqrtE,
                    m => m.Match(p).Times(m.Match(p)) +
                         m.Match(p).Times(2)*m.Match(sqrtE) +
                         m.Match(e));

    ...

    // Execution of rule, somewhere else
    var result = rule.SuccessfulMatch(innerOfSquare);
    if (result != null) {
        return result;
    }

Another change easily done is the defininition of a binary operator on a matcher to get rid of all these Match calls. I choose the operator & as a replacement for Match. The rule now suddenly gets much shorter:

    new StandardExpressionRewrite(p + -sqrtE,
        m => ((m & p) * (m & p))
             + (-2 * (m & p) * (m & sqrtE)
             + (m & e)));

I say that this code is short and readable enough (even though the many parentheses make this somewhat Lisp-like ...).

To also get rid of the many m & repetitions (and one level of parentheses), one would have to introduce a static context, probably in a ThreadStatic field. I'll not do this.

Using this notation, we can now more or less easily write our rewrite rules for the square operator. Here are the first seven rules from the previous posting reformulated as C# code:

    new StandardExpressionRewrite("P", _squareRewrites,
        p,
        m => (m & p) * (m & p));

    new StandardExpressionRewrite("sqrt(E)", _squareRewrites,
        sqrtE,
        m => m & e);
    new StandardExpressionRewrite("-sqrt(E)", _squareRewrites,
        -sqrtE,
        m => m & e);
    new StandardExpressionRewrite("-E", _squareRewrites,
        -e,
        m => new UnaryExpression(m & e, new Square()));

    new StandardExpressionRewrite("P[V]+-sqrt(Q[V])", _squareRewrites,
        p + -sqrtQ, HaveSameVar(p, q),
        m => ((m & p) * (m & p) + (m & q))
             + -2 * (m & p) * (m & sqrtQ));
    new StandardExpressionRewrite("P[V]+sqrt(Q[V])", _squareRewrites,
        p + sqrtQ, HaveSameVar(p, q),
        m => ((m & p) * (m & p) + (m & q))
             + 2 * (m & p) * (m & sqrtQ));
    new StandardExpressionRewrite("P+-sqrt(E)", _squareRewrites,
        p + -sqrtE,
        m => ((m & p) * (m & p))
             + (-2 * (m & p) * (m & sqrtE) + (m & e)));

I added three more features:

• HaveSameVar(p, q) returns true if both polynomials use the same variable, or if at least one of them is a constant. This is necessary for rules that require that two matched polynomials coincide on their variable, so that they can be merged into a single polynomial.
• Each rule gets a string to identify it during debugging.
• Also, the rules are stored in a List (here, _squareRewrites) that is passed to a general rewrite loop. This, finally, can be used to implement the visiting method for the square operator:

    private static readonly List<ExpressionRewrite> _squareRewrites =  
                                        new List<ExpressionRewrite>();

    public IAbstractExpr Visit(Square op, IAbstractExpr inner, Ignore p) {
        return Rewrite(inner, "Cannot handle square", _squareRewrites);
    }

    private static IAbstractExpr Rewrite(IAbstractExpr expr,  
             string cannotHandleMessage,  
             IEnumerable<ExpressionRewrite> rewrites) {
        foreach (var r in rewrites) {
            IAbstractExpr result = r.SuccessfulMatch(expr);
            if (result != null) {
                return result;
            }
        }
        throw new InvalidOperationException(cannotHandleMessage);
    }

Of course, it is utterly necessary to write test cases for these rewrites. I have created ten test cases for the square operator. Coincidentally, there are ten rewrite rules for the square operator, but I doubt that my test cases check all rules. I'll add a few more tests ... later.

But already a compile attempt shows us that there is still a piece missing: I happily use as yet undefined operators for polynomials and doubles, e.g.

   new StandardExpressionRewrite(...
      ...
      m => ... -2 * (m & p) ...);

After adding an operator that allows us to multiply a double with a polynomial, the rules compile—but one of the first tests is now red. Why? Because I also use plus and times operators to connect polynomials, e.g. here:

   new StandardExpressionRewrite(...
      ...
      m => ((m & p) * (m & p) + ...);

Because I defined these operators already for the AbstractExpr class, they now create a small expression tree from the two polynomials, instead of merging them into one polynomial! But easily enough, redefining the operators in class Polynomial solves the problem. Here is, for example, the unary minus for polynomials:

    public static Polynomial operator -(Polynomial p) {
        return CreatePolynomial(p.Var, p.Coefficients.Select(c => -c)).P;
    }

Plus and times are quite a bit longer, but not really complicated. And after their definition, all the square tests happily run green!

4. Unary minus

Folding a unary minus is now easy. We need just five rules:

    // -(P + -E) --> {-P} + E
    new StandardExpressionRewrite("P+-E", _unaryMinusRewrites,
        p + -e, m => -(m & p) + (m & e));
    // -(P + E) --> {-P} + -E
    new StandardExpressionRewrite("P+E", _unaryMinusRewrites,
        p + e, m => -(m & p) + -(m & e));
    // -(-P) should not happen; the inner -P must have been
    // rewritten to a polynomial with inverted coefficients!
    // -(P) --> {-P}
    new StandardExpressionRewrite("P", _unaryMinusRewrites,
        p, m => -(m & p));
    // -(-E) --> E
    new StandardExpressionRewrite("-E", _unaryMinusRewrites,
        -e, m => m & e);
    // -(E) --> -(E)
    new StandardExpressionRewrite("E", _unaryMinusRewrites,
        e, m => -(m & e));

and a simple visiting method:

    public IAbstractExpr Visit(UnaryMinus op, IAbstractExpr inner, Ignore p) {
        return Rewrite(inner,  
                       "Cannot handle unary minus",
                       _unaryMinusRewrites);
    }

Maybe it is instructive to disect the operators used in the rewrite result of second rule. There, the code is

        m => -(m & p) + -(m & e)

• (m & p) is a polynomial, therefore, the unary minus to the left of it is the operator we defined above. It creates a new polynomial, where all coefficients are inverted.
• (m & e), on the other hand, is an AbstractExpr. Therefore, the preceding unary minus is the expression tree building operator that we defined many postings ago.
• Finally, the + operator is applied to a polynomial and an AbstractExpr. Therefore, the compiler cannot select the polynomial addition, but must use the AbstractExpr operator for building a BinaryExpression.

And thus, this short piece of code actually computes {–P} + –E.

Because we rewrite – –E to E in the fourth rule, sequences of unary minuses are reduced to a single or no unary minus. Here is a test case for this behavior:

    [Test]
    public void TestManyMinuses1() {
        IAbstractExpr a = P("x", 1, 2);
        IAbstractExpr b = a;
        var foldingVisitor = new PolynomialFoldingVisitor();
        for (int i = 0; i < 4; i++) {
            // Apply double unary minus
            b = -(-b.C);
            Assert.AreEqual(a, b.Accept(foldingVisitor, Ig.nore));
        }
    }

This is the reason why we could ignore – –E inside square roots.

And after a mere pair of postings, we are done with folding unary operators around polynomials. Next on the agenda: Binary operators—including the horrible multiplication of P+E's.