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.

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.

Movimentum - Being a Nice Host: Visitors

The design for the constraint and expression visitor is straightforward. However, with all visitors, I opt for a generic input parameter and a generic return type to get a more versatile facility:

    public interface ISolverModelConstraintVisitor<in TParameter, out TResult> {
        TResult Visit(EqualsZeroConstraint equalsZero, TParameter p);
        TResult Visit(MoreThanZeroConstraint moreThanZero, TParameter p);
        TResult Visit(AtLeastZeroConstraint atLeastZero, TParameter p);
    }

    public interface ISolverModelExprVisitor<in TParameter, out TResult> {
        TResult Visit(Constant constant, TParameter p);
        TResult Visit(NamedVariable namedVariable, TParameter p);
        TResult Visit(AnchorVariable anchorVariable, TParameter p);
        TResult Visit(UnaryExpression unaryExpression, TParameter p);
        TResult Visit(BinaryExpression binaryExpression, TParameter p);
        //TResult Visit(RangeExpr rangeExpr, TParameter p);
    }

I also want to visit the operators, so we could add a simple Operator visitor:

    public interface ISolverModelOpVisitor<in TParameter, out TResult> {
        TResult Visit(Plus op, TParameter p);
        // ...
        TResult Visit(UnaryMinus op, TParameter p);
        TResult Visit(Square op, TParameter p);
        // ...
    }

However, we will need to pass in visited results to the operators (for example, expression evaluation will first require an evaluation of sub-expressions; and then passing the results to the operator). Therefore, we give the operator visitors aditional parameters for expressions (yes, this is a little bit of "up-front-design"—but hey, I know that I will need it!):

    public interface ISolverModelUnaryOpVisitor
            <in TExpression, in TParameter, out TResult> {
        TResult Visit(UnaryMinus op, TExpression inner, TParameter p);
        TResult Visit(Square op, TExpression inner, TParameter p);
        TResult Visit(FormalSquareroot op, TExpression inner, TParameter p);
        TResult Visit(PositiveSquareroot op, TExpression inner, TParameter p);
        //TResult Visit(Integral op, TExpression e, TParameter p);
        //TResult Visit(Differential op, TExpression e, TParameter p);
        TResult Visit(Sin op, TExpression inner, TParameter p);
        TResult Visit(Cos op, TExpression inner, TParameter p);
    }

    public interface ISolverModelBinaryOpVisitor
            <in TExpression, in TParameter, out TResult> {
        TResult Visit(Plus op, TExpression lhs, TExpression rhs, TParameter p);
        TResult Visit(Times op, TExpression lhs, TExpression rhs, TParameter p);
        TResult Visit(Divide op, TExpression lhs, TExpression rhs, TParameter p);
    }

Of course, we need also the counterpart Accept methods in the model classes. They are straightforward—here are a few of them, the rest looks exactly alike:

    #region Input constraints

    public abstract partial class AbstractConstraint {
        public abstract TResult Accept<TParameter, TResult>(
            ISolverModelConstraintVisitor<TParameter, TResult> visitor, TParameter p);
    }

    public partial class EqualsZeroConstraint : ScalarConstraint {
        public override TResult Accept<TParameter, TResult>(
            ISolverModelConstraintVisitor<TParameter, TResult> visitor, TParameter p) {
   
            return visitor.Visit(this, p);
        }
    }

    // same for the other two constraints types.

    #endregion Input constraints

    #region Expressions

    public abstract partial class AbstractExpr {
        public abstract TResult Accept<TParameter, TResult>(
            ISolverModelExprVisitor<TParameter, TResult> visitor, TParameter p);
    }

    public partial class Constant : AbstractExpr {
        public override TResult Accept<TParameter, TResult>(
            ISolverModelExprVisitor<TParameter, TResult> visitor, TParameter p) {
   
            return visitor.Visit(this, p);
        }
    }

    public partial class NamedVariable : Variable {
        public override TResult Accept<TParameter, TResult>(
            ISolverModelExprVisitor<TParameter, TResult> visitor, TParameter p) {
   
            return visitor.Visit(this, p);
        }
    }

    // same for AnchorVariable

    public partial class UnaryExpression : AbstractExpr {
        public override TResult Accept<TParameter, TResult>(
            ISolverModelExprVisitor<TParameter, TResult> visitor, TParameter p) {
   
            return visitor.Visit(this, p);
        }
    }

    public abstract partial class UnaryOperator : AbstractOperator {
        public abstract TResult Accept<TExpression, TParameter, TResult>(
            ISolverModelUnaryOpVisitor<TExpression, TParameter, TResult> visitor,
            TExpression innerResult,
            TParameter p);
    }

    public partial class UnaryMinus : UnaryOperator {
        public override TResult Accept<TExpression, TParameter, TResult>(
            ISolverModelUnaryOpVisitor<TExpression, TParameter, TResult> visitor,
            TExpression innerResult,
            TParameter p) {
   
            return visitor.Visit(this, innerResult, p);
        }
    }

    // same for all other UnaryOperators

    public partial class BinaryExpression : AbstractExpr {
        public override TResult Accept<TParameter, TResult>(
            ISolverModelExprVisitor<TParameter, TResult> visitor, TParameter p) {
   
            return visitor.Visit(this, p);
        }
    }

    public abstract partial class BinaryOperator : AbstractOperator {
        public abstract TResult Accept<TExpression, TParameter, TResult>(
            ISolverModelBinaryOpVisitor<TExpression, TParameter, TResult> visitor,
            TExpression lhsResult, TExpression rhsResult, TParameter p);
    }

    public partial class Plus : BinaryOperator {
        public override TResult Accept<TExpression, TParameter, TResult>(
            ISolverModelBinaryOpVisitor<TExpression, TParameter, TResult> visitor,
            TExpression lhsResult, TExpression rhsResult, TParameter p) {
   
            return visitor.Visit(this, lhsResult, rhsResult, p);
        }
    }

    // same for all other BinaryOperators

    #endregion Expressions

(I am not really happy about the formatting of the parameters—but this blog is somewhat too narrow to write beautiful code, or so I claim).

One last thought: The whole idea of visitors is the consequence of a separation of concerns: Different concerns, or aspects, should be in different classes. However, with the advent of partial classes in C#, one could "go back" to putting more into a single class, and merely distribute the "concerns" into different source files. The standard answer to this is that a visitor need not see internal details of the visited class, therefore, the separation into different classes leads to better information hiding. However, in all examples I have seen, virtually all structural information of the visited classes has to be published for visitors. Many years ago, this lead a colleague of mine to the observation that the name "visitor" is not derived from an amicable visit, but from the meaning of "visit" that implies an examination of the visited item—e.g. when a general pays a "visit" to some military base.

In German, the sarcasm is even more pronounced, because there is the word "Leibesvisitation", meaning "thorough body investigation" by a police or customs officer.

One consequence of visitors is the normalization of the Visit interface. For my visitor definitions, that means "exactly one parameter in—exactly one result out" (in the next posting you will see that this requires a funny "Ignore" class for simple visitors). One can view this normalization as a (small) benefit, because one design decision for a group of collaborating model methods is predefined. But of course, when one needs more parameters an especially out or ref parameters, the fixed Visit methods become a curse.

One advantage of the visitor pattern is that, with a modern IDE, it is very easy to create a new visitor class. Adding similar methods directly to the model classes is harder, unless one keeps around a template file for partial model classes with visiting methods and expands it using an editor or some sort of script.

Anyway, I'll keep to the visitor pattern in this project.

Movimentum - The Solver: Yet Another Constraint Model

We want to write an algorithm that assigns, for each frame, a well-defined location to each anchor of each object in our model. To find this solution, we will have to juggle the constraints in some way—essentially, we must do what we all learned in school: Solving linear and quadratic equations, substituting variables, simplifying expressions.

You might remember from those times that it sometimes necessary to search for a solution—i.e., it is possible that one has to research more than one path, because some paths might lead to dead ends (unsolvable constraint combinations). This happens, for example, if there are square roots. Here is a simple example:

x = √ 100
x < 0

In order to solve for x, one must first find out that there are two solutions to the equation: x ∈ { -10, +10 }. With both possible values, one now evaluates the inequality and finds that only the solution x = –10 survives.

Here is a more realistic example, from our domain of mechanical linkages: We have two black bars linked at a joint and already have fixed the free end of each bar at the points marked in orange.

Moreover, we know that the link must be on the blue line. We get three constraints:

• One for the possible locations of the free end of the left bar (the left green circle);
• One for the locations of the free end of the right bar (the other circle);
• And one placing the joint on the blue line.

Any algorithm that first selects any two of these constraints, and then limits the solutions by using the remaining constraint, will get two possible solutions from the first step.
For example, the first two constraints will yield two possible positions by intersecting the two dashed green circles. Only checking both positions against the blue line constraint will reduce the solutions to the single position shown by the dashed lines.

This shows that we need some sort of search algorithm for solving the constraints. But I will postpone the design of that algorithm for some time, because we need another model!

The solver constraint model

Our constraints are complex. They are too complex: There are vector expressions and scalar expressions and mixtures of both types. Solving these constraints would need many different mechanism which is too much work.
Let me therefore introduce a new constraint model that is not derived from the user's perspective (as is the "input constraint model" in the previous postings),  but one that is as simple as possible so that solution algorithms can work with it. The idea is that this "solver constraint model" (as I'll call it from now on) deals only with scalar variables and expressions so that we do not need solution formulas for vector and mixed scalar-vector expression. Of course, we will have to transform the input constraints to the solver constraints, and we will have to write back the results. But the hope is that a simpler solver model saves work overall.

Here is an overview of the model:

The following code is a little boring to read, but if you want to follow the next postings, you should go through it:

    #region Solver constraints

    public abstract class AbstractConstraint {
    }

    public abstract class ScalarConstraint : AbstractConstraint {
        private readonly AbstractExpr _expr;

        protected ScalarConstraint(AbstractExpr expr) {
            _expr = expr;
        }

        public AbstractExpr Expr { get { return _expr; } }
    }

    public class EqualsZeroConstraint : ScalarConstraint {
        public EqualsZeroConstraint(AbstractExpr expr) : base(expr) { }
    }

    public class MoreThanZeroConstraint : ScalarConstraint {
        public MoreThanZeroConstraint(AbstractExpr expr) : base(expr) { }
    }

    public class AtLeastZeroConstraint : ScalarConstraint {
        public AtLeastZeroConstraint(AbstractExpr expr) : base(expr) { }
    }

    #endregion Solver constraints

    #region Solver expressions

    public abstract class AbstractExpr { }

    public abstract class AbstractOperator { }

    public class Constant : AbstractExpr {
        private readonly double _value;
        public Constant(double value) {
            _value = value;
        }
        public double Value { get { return _value; } }
    }

    public abstract class Variable : AbstractExpr {
        private readonly string _name;
        protected Variable(string name) {
            _name = name;
        }
        public string Name { get { return _name; } }
    }

    public class NamedVariable : Variable {
        public NamedVariable(string name) : base(name) { }
    }

    public class AnchorVariable : Variable {
        private readonly Anchor _anchor;
        private readonly Anchor.Coordinate _coordinate;

        public AnchorVariable(Anchor anchor, Anchor.Coordinate coordinate)
            : base(VariableName(anchor, coordinate)) {
            _anchor = anchor;
            _coordinate = coordinate;
        }

        public Anchor.Coordinate Coordinate { get { return _coordinate; } }
        public Anchor Anchor { get { return _anchor; } }

        public static string VariableName(Anchor anchor, Anchor.Coordinate coordinate) {
            return anchor.Thing + "." + anchor.Name + "." + coordinate;
        }
    }

    public class UnaryExpression : AbstractExpr {
        private readonly AbstractExpr _inner;
        private readonly UnaryOperator _op;
        public UnaryExpression(AbstractExpr inner, UnaryOperator op) {
            _inner = inner;
            _op = op;
        }

        public AbstractExpr Inner { get { return _inner; } }
        public UnaryOperator Op { get { return _op; } }
    }

    public abstract class UnaryOperator : AbstractOperator { }

    public class UnaryMinus : UnaryOperator { }
    public class Square : UnaryOperator { }
    public class FormalSquareroot : UnaryOperator { }
    public class PositiveSquareroot : UnaryOperator { }
    //public class Integral : UnaryOperator { }
    //public class Differential : UnaryOperator { }
    public class Sin : UnaryOperator { }
    public class Cos : UnaryOperator { }

    public class BinaryExpression : AbstractExpr {
        private readonly AbstractExpr _lhs;
        private readonly BinaryOperator _op;
        private readonly AbstractExpr _rhs;
        public BinaryExpression(AbstractExpr lhs, BinaryOperator op, AbstractExpr rhs) {
            _lhs = lhs;
            _op = op;
            _rhs = rhs;
        }

        public AbstractExpr Lhs { get { return _lhs; } }
        public BinaryOperator Op { get { return _op; } }
        public AbstractExpr Rhs { get { return _rhs; } }
    }

    public abstract class BinaryOperator : AbstractOperator { }

    public class Plus : BinaryOperator { }
    public class Times : BinaryOperator { }
    public class Divide : BinaryOperator { }

    public class RangeExpr : AbstractExpr {
        // ... Internals missing ...
        public RangeExpr() {
            throw new NotImplementedException("We do RangeExprs later ...");
        }
    }

    #endregion Solver expressions

Here are a few notes on the model:

• On the whole, it is quite obvious—there are three constraint types, constants, variables, binary and unary expressions, and a host of binary and unary operators—this time as classes, not as objects.
• The AnchorVariable class is our "return ticket" to the input model: When the solver has assigned values to all such variables, it is possible to place the objects.
• The only decision that is not obvious is the distinction of formal and positive square roots. It took me some playing around with expressions until I realized that this is necessary. The reasoning goes about as follows: We will have to evaluate expressions at some time; but for this, we need unique function results. On the other hand, as we saw in the examples above, the "square roots" we get from the input model constraints are "formal square roots": Their result for a concrete solution may be the positive or the negative root value.
  Of course, our solver machine will, at some point, have to rewrite formal square roots to non-formal square roots—we will deal with this later.

An alternative design possibility is the following: Expression evaluation does not return a single value, but a set of values. However, this designs deviates quite a lot from our usual, manual way of working with equations. It might make a nice research project (which probably has already been done many times), but is not the way I want to follow in this "blog project" that should be easy to understand.

• I skipped code for calculus operators (integral, differential) and for those complex range expressions. If the whole solver is more or less in place, we'll find out whether we still want them (i.e., we can solve them), and whether we need them ...

In the next postings, let me add some machinery that will be required for the solver:

• A visitor facility for constraints and expressions.
• ToString() output for debugging.
• Equality.
• Numerical evaluation of constraints.

And of course we will have to rewrite the input constraints to solver constraints!

Movimentum - How to test an animation?

Hopefully, we'll create a first, simple animation in a short time. How are we going to check whether the output is correct? Of course, there is always the programmer's answer: Unit testing. However, with graphical objects, our eye (together with the brain) is one of the best gadgets to check for errors, as there are:

• A "rigid" body that suddenly gets deformed;
• A moving body that does not move;
• A body whose image is a mirror of the intended one;
• ...and many others.

What I want to say is: We need graphical output! We ... need ... movies ...!

This forces me to think about the design of the data flow from the frames back to the things so that we can draw them at the correct place. I scribbled a little bit on the margin of our daily newspaper and came up with the following trivial design for the main loop:

    IEnumerable<Frame> frames = script.CreateFrames();

    foreach (var f in frames) {
        ... Create drawing pane ...

        // Compute locations for each anchor of each thing.
        IDictionary<string,
                    IDictionary<string, ConstVector>>
            anchorLocations = f.SolveConstraints();
         
        foreach (var th in script.Things) {
            th.Draw(drawingPane, anchorLocations[th.Name]);
        }

        ... Save drawing pane to a new file ...
    }

Filling out the missing parts is easy, e.g.:

    var bitmap = new Bitmap(script.Config.Width, script.Config.Height);
    Graphics drawingPane = Graphics.FromImage(bitmap);
    ...
    bitmap.Save(
        string.Format("{0}{1:000000}.jpg", prefix, f.FrameNo),
        ImageFormat.Jpeg);

This requires adding two new parameters to the .config element to define the width and height of the drawing pane and a suitable update of the grammar.

Additionally, I want to test the solver with simple things. For this, I add a simple "bar" thing, which consists of a list of anchor points connected by lines.

    thingdefinition returns [Thing result]

      : IDENT

        ':'          {{ var defs = new List<ConstAnchor>(); }}
        ( FILENAME
          anchordefinitions[defs]
                     { result = new ImageThing($IDENT.Text,
                                ImageFromFile($FILENAME.Text),
                                defs);
                     }
        | BAR
          anchordefinitions[defs]
                     { result = new BarThing($IDENT.Text, defs); }
        )
        ';'
      ;

As you might notice, I have replaced the dictionary for the anchors with a list of the new class ConstAnchor. The reason is that I want the code to remember the order of anchors from the input, so that it will draw the lines always in the same order (in Java, I'd just have to replace Hashtable with LinkedHashtable. In .Net, this is not - yet? - possible).

The Bar thing must be able to draw itself (do you remember your first book on object orientation where they told you that in these modern times, objects are drawing themselves? Now you finally know why you learned this!):

    public class BarThing : Thing {
        public BarThing(string name, IEnumerable<ConstAnchor> anchors)
            : base(name, anchors) {
        }

        public override void Draw(Graphics drawingPane,
                IDictionary<string, ConstVector> anchorLocations) {
            float height = drawingPane.VisibleClipBounds.Height;
            Point[] points = Anchors
                .Select(a => new Point(
                    (int)Math.Round(anchorLocations[a.Name].X),
                    (int)(height - Math.Round(anchorLocations[a.Name].Y))))
                .ToArray();
            drawingPane.DrawLines(new Pen(Color.Orange, 3), points);
        }
    }

Now I can create a small crowbar or hockey stick:

    .config (20, 200, 200);

    B : .bar P = [0,0] Q = [5,5] R = [5,30];

I'd also like to move it so that I can test the three lines of graphics programming from above. For this, we need a few constraints, e.g. to move it diagonally:

    @0  B.P = [60 + .t, 60 + .t];

        B.Q = [65 + .t, 65 + .t];

        B.R = [65 + .t, 90 + .t];

    @10

Creating the frames requires a minimal ability of "constraint solving". I implement this ability with a rather hardwired assignment of values - which still requires an astonishing number of lines:

    public IDictionary<string, IDictionary<string, ConstVector>> SolveConstraints() {
        var anchorLocations =
                        new Dictionary<string, IDictionary<string, ConstVector>>();
        #region ------- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! -----
        foreach (var c in _constraints) {
            var constraint = c as VectorEqualityConstraint;
            if (constraint != null) {
                Anchor anchor = constraint.Anchor;
                Vector vector = (Vector)constraint.Rhs;
                double x = Get(vector.X as BinaryScalarExpr);
                double y = Get(vector.Y as BinaryScalarExpr);
                var resultVector = new ConstVector(x, y);
                IDictionary<string, ConstVector> anchorLocationsForThing;
                if (!anchorLocations.TryGetValue(anchor.Thing,
                                                    out anchorLocationsForThing)) {
                    anchorLocationsForThing = new Dictionary<string, ConstVector>();
                    anchorLocations.Add(anchor.Thing, anchorLocationsForThing);
                }
                anchorLocationsForThing.Add(anchor.Name, resultVector);
            } else {
                // We ignore the rigid body and 2d constraints for our testing.
            }
        }
        #endregion ---- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! --------
        return anchorLocations;
    }

    #region ----------- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! --------
    private double Get(BinaryScalarExpr expr) {
        // Expression MUST be (c + .t), with constant c.
        var lhs = (Constant)expr.Lhs;
        return lhs.Value + _relativeTime;
    }
    #endregion -------- TEMPORARY CODE FOR TRYING OUT THE DRAWING MACHINE!! --------

A little script helps us to run the chain of programs to create the animation. Test.mvm contains the Movimentum script, ffmpeg can be found here:

    bin\debug\Movimentum.exe test.mvm f_

    \ffmpeg\bin\ffmpeg -y -f image2 -i f_%%06d.jpg test.mpg

    test.mpg

And here it is - my first Movimentum animation!

Of course, the important part of the animation computation is pure fake: The coordinates of the anchors are directly assigned, and the rigid body constraints as well as the 2d constraints are completely ignored by this "solver."

But - we are finally at the rim of the canyon.

------------------------------------------------------------------------------------

P.S. For those of who who look closely: I have changed the names of the expression classes because they were very ad-hoc. They are still somewhat strange, but at least each class ending in "ScalarExpr" is actually a ScalarExpr, and each class ending in "VectorExpr" is now a VectorExpr. Likewise, "Unary" and "Binary" are applied consistently.

P.P.S. I am quite unsatisfied with the expression grammar because it is almost impossible to add the five multiplication operators that should be there:

• Scalar multiplication of scalars;
• Scalar multiplication of vectors ("inner product");
• Left and right multiplication of scalar and vector;
• Outer product of 3d vectors.

I guess that I should have thought about an eighth option in that posting with the severe grammar problem: using semantic predicates. I'll deal with these problems after the canyon ... eh, the constraint solver. So those of you who are interested in language design, stay tuned.

P.P.P.S. There's more to do in the grammar - for example, right now you cannot call an anchor "link" (try it). "pink", however, works perfectly. Not what one would expect.

Movimentum - Not yet: We need "all the constraints for each frame"

I was to rash. We are not yet at the rim.

The constraint solver will have to solve the equations for a single frame - but I still have to implement the logic that selects which constraints are valid for each frame.

To this end, I want to compute a list of frames, where each frame contains all the constraints valid at its time. The frames are then, so-to-speak, "unsolved frames" - we know the constraints that place the things in each frame, but we have not yet computed explicit coordinates for the anchors of each object.

Here is a rough outline of the algorithm:

  Step currentstep = first step;
  List activeConstraints = constraints of current step;

  // time is incremented in, say, 0.1 second intervals.
  for (time = 0; t < end; time += frame_delta_t) {
    if (t > currentstep.AbsoluteTime) {
      // The time flow jumped into the next step!
      currentstep = next step;
      recompute activeConstraints;
    }
    frameList.Add(new Frame(t, activeConstraints);
  }

Obviously, such an algorithm needs enough testing. For which cases do we have to look out? If you think about it, you see that we have two interlocked sequences of instants:

• The sequence of frame instants
• The sequence of step instants

And there can be

• "n" frame instants between any two step instants 
• "n" step instants between any two frame instants

Of course, in practice, only the former will happen: We will have many frames, but only comparatively few steps. This means that typically, there will be many frames between two step instants.
However, our algorithm should also work correctly for the latter case where there is more than one step between two frames. This could e.g. come in handy if you want to create a sequence of slides that show the mechanism at intervals of two or even 10 seconds.
The standard practice for "testing an n" is to select tests with n=0, n=1, and n>1. In our case, we therefore need test cases for

• zero frames between two steps
• one frame between two steps
• two (or more) frames between two steps

and

• zero steps between two frames
• one step between two frames
• two or more steps between two frames

Moreover, we also need cases where a step instant falls exactly on a frame instant. Of course, we also need boundary tests for no steps and one step - but we'll do that after the algorithm works.
Here is my first test input - the comments indicate the frames we want to appear. For each frame,

• T is the absolute time;
• t is the relative time inside the step;
• iv is the length of the step;
• a, b, etc. are the constraints that should hold in this step.

       const string s = @"
       .config(1);

       @10.0     a = 1;
       // Frame at 10: T = 10, t = 0, iv = 1; a
       @11.0     b = 1;
       // Frame at 11: T = 11, t = 0, iv = 1.3;  a, b
       // Frame at 12: T = 12, t = 1, iv = 1.3;  a, b
       @12.3     c = 1;
       @12.5     d = 1;
       @12.7     e = 1;
       // Frame at 13: T = 13, t = 0.3, iv = 0.8;  a, b, c, d, e
       @13.5     f = 1;
       // Frame at 14: T = 14, t = 0.5, iv = 2;  a, b, c, d, e, f
       // Frame at 15: T = 15, t = 1.5, iv = 2;  a, b, c, d, e, f
       @15.5     g = 1;
       @16.0     h = 1;
       // Frame at 16: T = 16, t = 0, iv = 0;  a, b, c, d, e, f, g, h
       ";

We must also assert that the frames are the correct ones. A helper method comes in handy:

    Assert.AreEqual(7, frames.Length);
    AssertFrame(frames[0], 10, 0, 1, "a");
    AssertFrame(frames[1], 11, 0, 1.3, "a", "b");
    AssertFrame(frames[2], 12, 1, 1.3, "a", "b");
    AssertFrame(frames[3], 13, 0.3, 0.8, "a", "b", "c", "d", "e");
    AssertFrame(frames[4], 14, 0.5, 2, "a", "b", "c", "d", "e", "f");
    AssertFrame(frames[5], 15, 1.5, 2, "a", "b", "c", "d", "e", "f");
    AssertFrame(frames[6], 16, 0, 0, "a","b","c","d","e","f","g","h");

where AssertFrame checks the three time values and constraint existence:

    private void AssertFrame(Frame f, double absoluteTime, double t,
                           double iv, params string[] constraintChecks) {
        Assert.AreEqual(absoluteTime, f.AbsoluteTime, 1e-9);
        Assert.AreEqual(t, f.T, 1e-9);
        Assert.AreEqual(iv, f.IV, 1e-9);
        {
            // Check the number of constraints
            int checkSum = constraintChecks.Count();
            Assert.AreEqual(checkSum, f.Constraints.Count());
        }
        {
            foreach (var checkKey in constraintChecks) {
                Assert.IsTrue(f.Constraints.Any(c => c.Key == checkKey));
            }
        }
    }

Writing the algorithm in C# and running the test reveals one conceptual error (that is obvious if you think about it): The if-statement in the pseudo-code above needs to be replaced with a while statement - after all, there can be more steps between two frames. Therefore, we have to deal with all of these steps before emitting the next frame!

Of course, I had a handful of other errors in the code until I got these enumerators right - the test case above helped me to eradicate them one by one.

The complete algorithm is not that long - maybe 25 statements -, but it deserves a few comments:

    public IEnumerable<Frame> CreateFrames() {
        var result = new List<Frame>();
        IEnumerator<Step> stepEnumerator = _steps.GetEnumerator();

        if (stepEnumerator.MoveNext()) {
            var activeConstraints =
                     new Dictionary<string, List<Constraint>>();

            Step currentStep = stepEnumerator.Current;
            Step nextStep = UpdateActiveConstraintsAndGetNextStep
                           (currentStep, activeConstraints, stepEnumerator);

            // We do not want t to miss a step due to rounding, hence
            // we "push each frame a little bit too far" (< a nanosec ...).
            double deltaT = 1.0 / _config.FramesPerTimeunit + 1e-10;

            int seqNo = 1;
            for (var t = currentStep.Time; nextStep != null; t += deltaT) {

                while (nextStep != null && t >= nextStep.Time) {
                    currentStep = nextStep;
                    nextStep = UpdateActiveConstraintsAndGetNextStep
                           (currentStep, activeConstraints, stepEnumerator);
                }

                result.Add(new Frame(
                    absoluteTime: t,
                    relativeTime: t - currentStep.Time,

                    // In last step - when nextStep is null -, we use
                    // currentStep instead of nextStep -> iv is set to 0.
                    iv: (nextStep ?? currentStep).Time - currentStep.Time,

                    // ToArray() necessary to COPY result into Frame.
                    // Otherwise, the iterator will run on the constraints
                    // of the LAST frame when it is executed at some time.
                    constraints: activeConstraints.Values
                                    .SelectMany(c => c)
                                    .ToArray(),
                    sequenceNo: seqNo++)
                );
            }
        }
        return result;
    }

    /// <summary>
    /// Concept: If there are constraints with key K in this step, we
    /// remove ALL earlier constraints with that key from the active
    /// constraints; and afterwards add all the constraints with this
    /// key from the step.
    /// </summary>
    /// <returns>next step; or null if there is none.</returns>
    private Step UpdateActiveConstraintsAndGetNextStep(Step step,
            Dictionary<string, List<Constraint>> activeConstraints,
            IEnumerator<Step> stepEnumerator) {

        foreach (var c in step.Constraints) {
            // For more than one constraint with same key, the following
            // will init c.Key to the empty list more than once. So what.
            activeConstraints[c.Key] = new List<Constraint>();
        }
        foreach (var c in step.Constraints) {
            activeConstraints[c.Key].Add(c);
        }
        return stepEnumerator.MoveNext() ? stepEnumerator.Current : null;
    }

A second test has to show that the key handling of the constraints is done correctly - i.e., that all constraints with some key are removed if there is one new constraint in the current step with that key; and that all the new constraints are then added. Moreover, tests for no step and a single step are necessary (although such scripts should not occur in real life). I do not show these tests here - they are in the code I'll push to github today.