Movimentum - A Better ToStringVisitor

The simple ToString visitor in the previous posting creates lots of superfluous parentheses, which makes its output unreadable even for medium-sized expressions. Here is an improved design: Into each expression visiting method, we pass a precedence of the operator of the surrounding expression. By comparing this "parent precedence" with the current operator's precedence, we can then decide whether to place parentheses around an expression.

General Design

Here is the class definition. There are two important differences to the previous one:

• Expression and operator visitors have an int parameter type. It will be used to pass in the parent precedence.
• Moreover, the operator visitors are passed in the AbstractExprs of their expression. The idea is that the operator visitor itself does all the work, because it alone has all the necessary information:

    class ToStringVisitor : ISolverModelConstraintVisitor<Ignore, string>
                , ISolverModelExprVisitor<int, string>
                , ISolverModelBinaryOpVisitor<AbstractExpr, int, string>
                , ISolverModelUnaryOpVisitor<AbstractExpr, int, string> {

The calls from the constraint visitors now pass in zero as parent precedence:

        public string Visit(EqualsZeroConstraint equalsZero, Ignore p) {
        return "0 = " + equalsZero.Expr.Accept(this, 0);
    }

Visiting constants and variables returns the same strings as before—I do not show that code again.

For the unary and binary expressions, we pass on the pieces to the operators, as indicated above:

    public string Visit(UnaryExpression unaryExpr, int parentPrecedence) {
        return unaryExpression.Op.Accept(this,
                                         unaryExpr.Inner,
                                         parentPrecedence);
    }

    public string Visit(BinaryExpression binaryExpr, int parentPrecedence) {
        return binaryExpression.Op.Accept(this,
                                          binaryExpr.Lhs,
                                          binaryExpr.Rhs,
                                          parentPrecedence);
    }

C# operators for easy expression creation

The code up to here consisted only of design-level decisions. The "real meat"—the actual string generation algorithm—is contained in the operator visitors. And because many of the operator visiting methods behave a little bit differently, doing TDD (whichever way—the "non-strict" or the "strict" one) is now certainly worth the effort. First, we implement all operator visitor methods as

    throw new NotImplementedException()

Now, let us write a first test case:

    [Test]
    public void TestWithoutParentheses0() {
        AbstractExpr input = new BinaryExpression(new Constant(1),  
                                                  new Plus(),  
                                                  new NamedVariable("z"));
        string result = input.Accept(new ToStringVisitor(), -1);
        Assert.AreEqual("1+z", result);
    }

Mhm. Writing that simple expression 1+z was already much work. We will need more complex expressions even for testing this simple visitor—let alone for visitors used in the solver—, so a little bit of support for writing expressions would be nice.

Fortunately, C# has operators in the language. Let us quickly define a few of them to write expressions more easily:

   public abstract class AbstractExpr {
      // ...
      public static AbstractExpr operator +(AbstractExpr lhs, AbstractExpr rhs) {
         return new BinaryExpression(lhs, new Plus(), rhs);
      }
      public static AbstractExpr operator *(AbstractExpr lhs, AbstractExpr rhs) {
         return new BinaryExpression(lhs, new Times(), rhs);
      }
      public static AbstractExpr operator /(AbstractExpr lhs, AbstractExpr rhs) {
         return new BinaryExpression(lhs, new Divide(), rhs);
      }
      public static AbstractExpr operator -(AbstractExpr inner) {
         return new UnaryExpression(inner, new UnaryMinus());
      }
      // ...
   }

Here is the test case again, this time using the + operator:

    [Test]
    public void TestWithoutParentheses0() {
        AbstractExpr input = new Constant(1) + new NamedVariable("z");
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("1+z", result);
    }

Binary operators

And here is a first implementation of the visitor for the plus operator according to our design:

• First, we compute the strings for the subexpressions, passing in the precedence of the current operator.
• Then we decide whether we need parentheses around the result, based on the relation between the current operator's precedence and the parent's precedence:

    public string Visit(Plus op, AbstractExpr lhs,
                        AbstractExpr rhs, int parentPrecedence) {
        string r = lhs.Accept(this, PLUS_PRECEDENCE)
                 + "+"
                 + rhs.Accept(this, PLUS_PRECEDENCE);
        return parentPrecedence > PLUS_PRECEDENCE ? "(" + r + ")" : r;
    }

To compile the visitor, we must only define the constant PLUS_PRECEDENCE higher than the zero we pass in from constraints and our tests:

    private const int PLUS_PRECEDENCE = 1;

And the test is green! We can immediately write two more tests, both with three summed terms. In one test, the two left terms are added first; in the other one, the two right ones are summed first. Both tests must return a string without parentheses:

    [Test]
    public void TestWithoutParentheses1() {
        AbstractExpr input = (new Constant(1) + new Constant(2))
                           + new Constant(4);
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("1+2+4", result);
    }
    [Test]
    public void TestWithoutParentheses2() {
        AbstractExpr input = new Constant(1)
                           + (new Constant(2) + new Constant(4));
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("1+2+4", result);
    }

Both tests run green immediately.

Now we come to the crucial tests and implementation: Tests using both a plus and a multiplication operator. Let us quickly write the two important tests—one where the summation is below the multiplication, and another one which does it the other way round:

    public void TestWithoutParentheses4() {
        AbstractExpr input = new Constant(1)
                           + new Constant(2) * new Constant(4);
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("1+2*4", result);
    }
    [Test]
    public void TestWithParentheses1() {
        AbstractExpr input = (new Constant(1) + new Constant(2))
                           * new Constant(4);
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("(1+2)*4", result);
    }

According to our design, the tests should work with the following implementation:

    public string Visit(Times op, AbstractExpr lhs,
                        AbstractExpr rhs, int parentPrecedence) {
        string r = lhs.Accept(this, TIMES_PRECEDENCE)
                 + "*"
                 + rhs.Accept(this, TIMES_PRECEDENCE);
        return parentPrecedence > TIMES_PRECEDENCE ? "(" + r + ")" : r;
    }

Again, we need that constant; and of course, it must be larger than PLUS_PRECEDENCE, as the multiplication operators "binds stronger":

    private const int TIMES_PRECEDENCE = 2;

And all the tests are green!

Of course, the visitor for the multiplication operator is very similar to the one for plus. So it makes sense to factor out the common structure:

    private string Visit(AbstractExpr lhs, AbstractExpr rhs,
                         int parentPrecedence, string opString,  
                         int localPrecedence) {
        string r = lhs.Accept(this, localPrecedence)
                    + opString
                    + rhs.Accept(this, localPrecedence);
        return parentPrecedence > localPrecedence ? "(" + r + ")" : r;
    }

    public string Visit(Plus op, AbstractExpr lhs,
                        AbstractExpr rhs, int parentPrecedence) {
        return Visit(lhs, rhs, parentPrecedence, "+", PLUS_PRECEDENCE);
    }

    public string Visit(Times op, AbstractExpr lhs,
                        AbstractExpr rhs, int parentPrecedence) {
        return Visit(lhs, rhs, parentPrecedence, "*", TIMES_PRECEDENCE);
    }

Nicely enough, the tests are still green.

Of course, after writing one or two more unit tests, we can also implement the visitor for division:

    public string Visit(Divide op, AbstractExpr lhs,
                        AbstractExpr rhs, int parentPrecedence) {
        return Visit(lhs, rhs, parentPrecedence, "/", TIMES_PRECEDENCE);
    }

Unary operators

Let us apply the same design ideas to unary operators. Here are two initial unit tests:

    [Test]
    public void TestUnaryMinusOfConstant() {
        AbstractExpr input = -new Constant(1);
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("-1", result);
    }
    [Test]
    public void TestUnaryMinusOfUnaryMinus() {
        AbstractExpr input = -(-new Constant(1));
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("--1", result);
    }

Here is an implementation of the visitor for unary minus that makes the tests green:

    private const int UNARY_MINUS_PRECEDENCE = 3;

    public string Visit(UnaryMinus op, AbstractExpr inner, int parentPrecedence) {
        string result = "-" + inner.Accept(this, UNARY_MINUS_PRECEDENCE);
        return parentPrecedence > UNARY_MINUS_PRECEDENCE
             ? "(" + result + ")"
             : result;
    }

Next, let us tackle the square operator. Again, we write unit tests: A simple one, and two crucial ones that place or don't place parentheses in the case of a unary minus:

    [Test]
    public void TestSquareOfVariable() {
        AbstractExpr input = new UnaryExpression(new NamedVariable("a"),  
                                                 new Square());
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("a²", result);
    }
    [Test]
    public void TestSquareOfUnaryMinus() {
        AbstractExpr input = new UnaryExpression(-new NamedVariable("a"),  
                                                 new Square());
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("(-a)²", result);
    }
    [Test]
    public void TestUnaryMinusOfSquare() {
        AbstractExpr input = -new UnaryExpression(new NamedVariable("a"),
                                                  new Square());
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("-a²", result);
    }

Here is the implementation that makes the tests green:

    private const int SQUARE_PRECEDENCE = 4;

    public string Visit(Square op, AbstractExpr inner, int parentPrecedence) {
        string result = inner.Accept(this, SQUARE_PRECEDENCE) + "²";
        return parentPrecedence > SQUARE_PRECEDENCE
             ? "(" + result + ")"
             : result;
    }

Of course, we factor out the comparison line, say into a function Parenthesize.

Finally, we visit the four functions formal and positive root, sine, and cosine. Here are two crucial tests—square of sine and sine of square:

    [Test]
    public void TestSquareOfSin() {
        AbstractExpr input =
            new UnaryExpression(
                new UnaryExpression(new NamedVariable("a"),
                                    new Sin()),
                new Square());
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("(sin a)²", result);
    }
    [Test]
    public void TestSinOfSquare() {
        AbstractExpr input =  
            new UnaryExpression(
                new UnaryExpression(new NamedVariable("a"),  
                                    new Square()),
                new Sin());
        string result = input.Accept(new ToStringVisitor(), 0);
        Assert.AreEqual("sin a²", result);
    }

These tests show us that "square is stronger than sine"—i.e., the precedence of the square operator should be above the sine operators's precedence. Therefore, we must push up the square operator precedence, so that the precedence of sine can be 4:

    private const int FUNCTION_PRECEDENCE = 4;
    private const int SQUARE_PRECEDENCE = 5;

    private static string Parenthesize(int parentPrec, int localPrec, string r) {
        return parentPrec > localPrec ? "(" + r + ")" : r;
    }

    public string Visit(Square op, AbstractExpr inner, int parentPrecedence) {
        string result = inner.Accept(this, SQUARE_PRECEDENCE) + "²";
        return Parenthesize(parentPrecedence, SQUARE_PRECEDENCE, result);
    }

    public string Visit(Sin op, AbstractExpr inner, int parentPrecedence) {
        string result = "sin " + inner.Accept(this, FUNCTION_PRECEDENCE);
        return Parenthesize(parentPrecedence, FUNCTION_PRECEDENCE, result);
    }

And that was it. The visitor implementations for cosine, formal and positive square root are similar to the sine visitor. Of course, some more tests are in order, e.g. placing sums inside functions and squares. But they will show that all is good.