Movimentum - A Simple ToStringVisitor

As an exercise for the visiting machinery in the previous posting, let us write a visitor that converts constraints and expressions to strings. This will be very helpful when we have to debug the solver: Strings are much easier to read than nested objects graphs.

The expression and constraint visitor interfaces require two type parameters: One for the result, one for "a parameter." The result of visiting a constraint or expression with the StringVisitor is, of course, a string. However, what is the type of the additional parameter we have to pass in? Well, we do not need such a parameter. Of course, we could pass in an IFormatProvider or the like, but we'll use the result for debugging only, and so we do not need fancy formatting. Therefore, we would like to write

    class ToStringVisitor : ISolverModelConstraintVisitor<void, string>
                          , ISolverModelExprVisitor<void, string> {
        // ...       
    }

However, this is not legal C#: void (and also System.Void) cannot be used as generic type parameters. I have therefore, years ago, started to define an "Ignore class," e.g. as follows:

    public struct Ignore { }
    public static class Ig {
        public static readonly Ignore nore = new Ignore();
    }

(You'll see a usage of that strange Ig close in a moment). Using this class, we can now write:

    class ToStringVisitor : ISolverModelConstraintVisitor<Ignore, string>
                          , ISolverModelExprVisitor<Ignore, string> {

        // ...       
    }

Here is a simple implementation of the visiting methods for the constraints:

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

    public string Visit(MoreThanZeroConstraint moreThanZero, Ignore p) {
        return "0 < " + moreThanZero.Expr.Accept(this, p);
    }

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

The methods for constants and variables are easy:

    public string Visit(Constant constant, Ignore p) {
        return constant.Value.ToString(CultureInfo.InvariantCulture);
    }

    public string Visit(NamedVariable namedVariable, Ignore p) {
        return namedVariable.Name;
    }

    public string Visit(AnchorVariable anchorVariable, Ignore p) {
        return anchorVariable.Name;
   }

For the unary and binary expressions, we delegate the creation of the operator string again to a visitor—more precisely, to this visitor! Here is the code for visiting a UnaryExpression and a BinaryExpression, using that ominous Ig class:

    public string Visit(UnaryExpression unaryExpression, Ignore p) {
        string op = unaryExpression.Op.Accept(this, Ig.nore, Ig.nore);
        return op + "(" + unaryExpression.Inner.Accept(this, p) + ")";
    }

    public string Visit(BinaryExpression binaryExpression, Ignore p) {
        string op = binaryExpression.Op.Accept(this, Ig.nore, Ig.nore, Ig.nore);
        string result = binaryExpression.Lhs.Accept(this, p)
                      + op
                      + binaryExpression.Rhs.Accept(this, p);
        return "(" + result + ")";
    }

We have to put parentheses around each expression so that e.g. the result for a squareroot of sums is "sqrt(a+1)" and not "sqrt a+1". This is correct ... but for larger expressions, it gets very hard to read. For example, the moderatly complex expression (1+2-4)*8+x-16 will be output as (((((1+2)+-(4))*8)+x)+-(16)): Not nice.  Still, let us finish this visitor and think about this problem later.

So that visiting the operators works, we need to implement also the operator visitor interfaces:

    class SimpleToStringVisitor : ISolverModelConstraintVisitor<Ignore, string>
                                , ISolverModelExprVisitor<Ignore, string>
                                , ISolverModelBinaryOpVisitor<Ignore, string>
                                , ISolverModelUnaryOpVisitor<Ignore, string>
    { ... }

Visiting the operators is, of course, simple:

    public string Visit(Plus op, Ignore lhs, Ignore rhs, Ignore p) {
        return "+";
    }
        // etc.

This simple ToStringVisitor works. However, my long experience with parsers, code generators and the like has taught me that one needs readable output also for "purely internal data:" We (and others) will do too much debugging and maintenance later-on. Therefore we have to improve our ToStringVisitor. More to the point: What we need is a concept of operator precedence that controls the addition of parentheses.