Movimentum - Creating polynomials

The whole goal of the solver model is the easy application of rewriting rules. And therefore, the main design force is standardization of expression: If a certain mathematical expression is always represented by the same expression tree in the solver model, it can reliably be matched against a rule. Consequences of this design rationale are:

• The introduction of the solver model, in the first place: Expressions are now always represented as expression trees of scalar variables.
• Constant folding: Constants are now always represented in the same way, i.e., they are normalized.
• Polynomials: Chains of plus, times, and square operators containing only a single variable will always be represented by the same expression tree, namely a Polynomial object (we are not there yet).

However, in our current design, two types of polynomials can be represented by different expression trees: Constants, and variables.

A constant, right now, can either be represented by a Constant object or by a Polynomial object with degree zero, i.e., with only a single coefficient. Similarly, a variable can be represented either by an object whose type is assignable to Variable; or by a Polynomial object with coefficients [1, 0]. Obviously, this is not what we want.

What we rather would like to have, is twofold:

• Rules matching a polynomial also handle constants and variables without any further ado.
• Rules can reliably match constants and variables.

The solution for the first item is simple: Derive classes Constant and Variable from class Polynomial. However, if we allow Polynomial to remain a concrete class, this creates a subtle problem with visitors: We suddenly need visit methods that can override each other. In virtually all descriptions of the visitor pattern, this topic is ignored, because it is assumed—to my knowledge, always implicitly—that only leaf classes of a visited inheritance tree are concrete classes. This is not required by the visitor pattern, but it is good design practice, and we will follow it.

Therefore, we design our class structure for polynomials as follows:

What about the second item—reliably matching constants and variables?

This requires that constants are always represented by objects of type Constant; and likewise for variables. As long as the constructor for GeneralPolynomial is public, this cannot be enforced (or it could only be enforced by a runtime check, which would put the burden of using the correct constructors on the calling site).

The correct solution is to define a factory method, and to make the constructor of GeneralPolynomial private. However, the factory mathod must be able to access this constructor, and hence we must either put it into the GeneralPolynomial class, or we must make this class a private inner class of Polynomial. The first approach works, but it is (in my opinion, "strangely") asymmetric: The factory method can only access the private constructor of GeneralPolynomial, but must use the public constructors of Constant and Variable. I opt for a different design:

• Instead of using classes for polynomials, we use interfaces everywhere.
• All three concrete polynomial classes become private classes inside class Polynomial.

Here is a diagram showing this setup. The interfaces are colored yellow, the four classes comprising the polynomial inheritance hierarchy are green. The lines with the "plus circles" indicate "nesting," i.e., that the lower classes are nested inside the upper class (from which they are also derived—but these two relationships are orthogonal to each other!):

Why don't I introduce interfaces also for the remaining expression classes, namely UnaryExpression and BinaryExpression? Because ... mhm ... this would be YAGNI: There is, right now, no reason at all to change their design. Lame excuse?

Anyway, now we can write the factory method for polynomials:

    public static IPolynomial CreatePolynomial(IVariable variable,
                                    IEnumerable<double> coefficients) {
        // Skip all leading zero coefficients
        int zeroPrefixLength = 0;
        foreach (var c in coefficients) {
            if (!c.Near(0)) {
                break;
            }
            zeroPrefixLength++;
        }
        double[] normalizedCoefficients =
            coefficients.Skip(zeroPrefixLength).ToArray();

        // Create intermediate coefficient for zero polynomial.
        if (normalizedCoefficients.Length == 0) {
            normalizedCoefficients = new[] { 0.0 };
        }

        // Create result based on degree and coefficients.
        var deg = normalizedCoefficients.Length - 1;
        if (deg == 0) {
            return new Constant(normalizedCoefficients[0]);
        } else if (deg == 1
                   && normalizedCoefficients[0].Near(1)
                   && normalizedCoefficients[1].Near(0)) {
            return variable;
        } else {
            return new GeneralPolynomial(variable, normalizedCoefficients);
        }
    }

Because the constructors and variables are no longer visible, we must provide factory methods for variables (otherwise, we could never create a polynomial!). For simplicity, there is also a factory method for constants, so we do not have to create a polynomial with a throw-away variable and a single coefficient. By the way, these methods could, in the future, cache often-used variables and constants for performance reasons:

    public static IAnchorVariable CreateAnchorVariable(Anchor anchor,
                                    Anchor.Coordinate coordinate) {
        return new AnchorVariable(anchor, coordinate);
    }

    public static INamedVariable CreateNamedVariable(string name) {
        return new NamedVariable(name);
    }

    public static IConstant CreateConstant(double value) {
        return new Constant(value);
    }

Of course, we must also modify the interface for visiting expressions—instead of the three polynomial classes, it now uses interfaces. The same replacement must happen in all implementing classes. ReSharper can do this with a few mouse-clicks:

public interface ISolverModelExprVisitor<in TParameter, out TResult> {
    TResult Visit(IConstant constant, TParameter p);
    TResult Visit(INamedVariable namedVariable, TParameter p);
    TResult Visit(IAnchorVariable anchorVariable, TParameter p);
    TResult Visit(UnaryExpression unaryExpression, TParameter p);
    TResult Visit(BinaryExpression binaryExpression, TParameter p);
    TResult Visit(RangeExpr rangeExpr, TParameter p);
    TResult Visit(IGeneralPolynomial polynomial, TParameter p);
}

This concludes our revised solver model, which now contains polynomials as first class citizens. The next step is to rewrite all expressions to the form P + E_i. I call this "polynomial folding"—it is, so to speak, the "big cousin" of constant folding.