Saturday, June 30, 2012

Movimentum - The solver algorithm, second try

Now that we have three necessary ingredients for solving our constraints, we can try once more to solve simple linear equations. We take our example from the posting of our first attempt:
0 = y + 2
0 = x + y

A test case


Here is a test case that verifies that the first solver step works:
  • At first, we set up the two constraints.
  • Then we do a step.
  • Afterwards, we check that (a) we have now the constraints 0 = 0 and 0 = x + –2; (b) that we still do not have a complete solution.

    public void Test2SimpleConstraintsAndOneStep() {
        // Try to solve:
        //   0 = y + 2
        //   0 = x + y
        EqualsZeroConstraint e1 =  
            new EqualsZeroConstraint(new NamedVariable("y") + new Constant(2));
        EqualsZeroConstraint e2 =  
            new EqualsZeroConstraint(new NamedVariable("x") + new NamedVariable("y"));
        var current = new SolverNode(new[] {e1, e2}, null);
        SolverNode solutionOrNull;

        // First step: Find that y = -2, and substitute -2 for y everywhere.
        IEnumerable<SolverNode> expanded = SolverNode.SolverStep( 
            new[] { current },  
            new Dictionary<Variable, VariableRangeRestriction>(),
            out solutionOrNull);

        Assert.AreEqual(1, expanded.Count());
        Assert.AreEqual(
            new EqualsZeroConstraint(new Constant(0)),
            expanded.ElementAt(0).Constraints.ElementAt(0));
        Assert.AreEqual( 
            new EqualsZeroConstraint(new NamedVariable("x") + new Constant(-2)),
            expanded.ElementAt(0).Constraints.ElementAt(1));
        Assert.IsNull(solutionOrNull);
    }

We do not yet have a constructor for a SolverNode, so let's write one. The central use of this constructor will be in the Expand method, hence we need to pull over the variable knowledge from some "current node" to the newly created node—this is already included here, although we do not need it for this initial setup:

    public SolverNode(IEnumerable<AbstractConstraint> constraints,  
                      SolverNode origin) {
        _constraints = constraints;
        _variableInRangeKnowledges = origin == null
            ? new Dictionary<Variable, VariableRangeRestriction>()
            : new Dictionary<Variable, VariableRangeRestriction>(
                  origin._variableInRangeKnowledges
              );
    }

To make the test work, we have to write implementations for the two methods that got too complicated in the posting of our first attempt: FindBestRewrite and ExecuteRewrites. The first of these methods now should use templates to find constraints of the form 0 = V + E. So we set up a template ...

        private VariableToConstantRewrite FindBestRewrite( 
                IDictionary<Variable, VariableRangeRestriction> previousValues) {
            var v = new TypeMatchTemplate<Variable>();
            var e = new TypeMatchTemplate<Constant>();
            var zeroEqualsVPlusETemplate = new EqualsZeroConstraintTemplate(v + e);

... but I did not write any constraint templates, only expression templates! Back to the drawing board.

Constraint templates


Here is a straightforward extension of the expression templates to constraints.

internal abstract class ScalarConstraintTemplate {
    private readonly AbstractExpressionTemplate _expr;
    protected ScalarConstraintTemplate(AbstractExpressionTemplate expr) {
        _expr = expr;
    }
    public AbstractExpressionTemplate Expr { get { return _expr; } }

    public abstract bool TypeMatches(ScalarConstraint abstractConstraint);
}

internal class EqualsZeroConstraintTemplate : ScalarConstraintTemplate {
    public EqualsZeroConstraintTemplate(AbstractExpressionTemplate expr)
        : base(expr) {}
    public override bool TypeMatches(ScalarConstraint constraint) {
        return constraint is EqualsZeroConstraint;
    }
}

internal class AtLeastZeroConstraintTemplate : ScalarConstraintTemplate {
    public AtLeastZeroConstraintTemplate(AbstractExpressionTemplate expr)
        : base(expr) {}
    public override bool TypeMatches(ScalarConstraint constraint) {
        return constraint is AtLeastZeroConstraint;
    }
}

internal class MoreThanZeroConstraintTemplate : ScalarConstraintTemplate {
    public MoreThanZeroConstraintTemplate(AbstractExpressionTemplate expr)
        : base(expr) {}
    public override bool TypeMatches(ScalarConstraint constraint) {
        return constraint is MoreThanZeroConstraint;
    }
}

Let us also add a mutable Matcher, as I did for expression templates:

internal class ScalarConstraintMatcher {
    private readonly ExpressionMatcher _expressionMatcher;
    private readonly ScalarConstraintTemplate _template;

    public ScalarConstraintMatcher(ScalarConstraintTemplate template) {
        _template = template;
        _expressionMatcher = new ExpressionMatcher(template.Expr);
    }

    public bool TryMatch(ScalarConstraint constraint) {
        return _template.TypeMatches(constraint)
            && _expressionMatcher.TryMatch(constraint.Expr);
    }

    public AbstractExpr Match(FixedExpressionTemplate t) {
        return _expressionMatcher.Match(t);
    }

    public BinaryExpression Match(BinaryExpressionTemplate t) {
        return _expressionMatcher.Match(t);
    }

    public UnaryExpression Match(UnaryExpressionTemplate t) {
        return _expressionMatcher.Match(t);
    }

    public T Match<T>(TypeMatchTemplate<T> t) where T : AbstractExpr {
        return _expressionMatcher.Match(t);
    }
}

Finding the best rewrite, second attempt


Now our code from above compiles, and we can add the crucial loop: Run over all constraints until we find one that matches 0 = V + E; and return a corresponding rewrite:

        foreach (var c in Constraints.OfType<ScalarConstraint>()) {
            var matcher = new ScalarConstraintMatcher(zeroEqualsVPlusETemplate);
            if (matcher.TryMatch(c)) {
                return new VariableToConstantRewrite(
                    matcher.Match(v),
                    -matcher.Match(e).Value);
            }
        }
        throw new NotSupportedException("I found no 0=V+E-Constraint");
    }

As in our first attempt, the code throws an exception if it does not find a matching constraint—i.e., it gives up.

In contrast to the first attempt, the rewrite code can now easily be written in three lines:

    private IEnumerable<SolverNode> ExecuteRewrites(
            VariableToConstantRewrite rewrite) {
        var rewriter = new RewritingVisitor( 
            new Dictionary<AbstractExpr, AbstractExpr>
                { { rewrite.Var, new Constant(rewrite.Value) } }
            );
        IEnumerable<AbstractConstraint> rewrittenConstraints =
             Constraints.Select(c => c.Accept(rewriter, Ig.nore));
        return new [] { new SolverNode(rewrittenConstraints, this)};
    }

Running the test


Finally, we are done—let's run our first constraint solving test! ... and it is ... red!

What happened? Well, we get told in no uncertain terms that, in the second Assert,
Expected: <{EqualsZeroConstraint}0 = 0>
But was: <{EqualsZeroConstraint}0 = -2+2>
Of course! Replacing y with -2 in 0 = y + 2 will yield the latter, not the former. Constant folding comes to our rescue: We decree that each constraint in a SolverNode must always be as simplified as possible, which right now means constant folded. To this end, we change the constructor for a SolverNode as follows:

    public SolverNode(IEnumerable<AbstractConstraint> constraints,
              SolverNode origin) {
        _constraints = constraints
             .Select(c => c.Accept(new ConstantFoldingVisitor(), Ig.nore));
        ...
    }

And now, the test is green! Time to publish this achievement in the blog.

Friday, June 29, 2012

Movimentum - Three basic algorithms: Expression replacement.

We want to replace a variable with a constant. Here is a visitor that can do a little more: Replace subexpressions with other expressions. We pass in a set of replacements, using a dictionary:

class RewritingVisitor :
        ISolverModelConstraintVisitor<AbstractConstraint>,
        ISolverModelExprVisitor<AbstractExpr> {
    private readonly IDictionary<AbstractExpr, AbstractExpr> _rewrites;

    public RewritingVisitor(
            IDictionary<AbstractExpr, AbstractExpr> rewrites) {
        _rewrites = rewrites;
    }

    // ...
}

For the three simple expressions—NamedVariables, AnchorVariables, and Constants—we return the replacement from the dictionary; or the original expression, if there is no replacement:

    private AbstractExpr RewriteSimpleExpr(AbstractExpr expr) {
        AbstractExpr result;
        return _rewrites.TryGetValue(expr, out result) ? result : expr;
    }

    public AbstractExpr Visit(Constant constant, Ignore p) {
        return RewriteSimpleExpr(constant);
    }

    public AbstractExpr Visit(NamedVariable namedVariable, Ignore p) {
        return RewriteSimpleExpr(namedVariable);
    }

    public AbstractExpr Visit(AnchorVariable anchorVariable, Ignore p) {
        return RewriteSimpleExpr(anchorVariable);
    }

The code for unary and binary epxressions looks somewhat similar to the constant folding visitor. But as we do not need any operator-specific behavior, it consists only of these two methods:

    public AbstractExpr Visit(UnaryExpression unaryExpression, Ignore p) {
        AbstractExpr result;
        if (_rewrites.TryGetValue(unaryExpression, out result)) {
            return result;
        } else {
            AbstractExpr oldInner = unaryExpression.Inner;
            AbstractExpr newInner = oldInner.Accept(this, Ig.nore);
            if (newInner != oldInner) {
                return new UnaryExpression(newInner, unaryExpression.Op);
            } else {
                return unaryExpression;
            }
        }
    }

    public AbstractExpr Visit(BinaryExpression binaryExpression, Ignore p) {
        AbstractExpr result;
        if (_rewrites.TryGetValue(binaryExpression, out result)) {
            return result;
        } else {
            AbstractExpr oldLhs = binaryExpression.Lhs;
            AbstractExpr oldRhs = binaryExpression.Rhs;
            AbstractExpr newLhs = oldLhs.Accept(this, Ig.nore);
            AbstractExpr newRhs = oldRhs.Accept(this, Ig.nore);
            if (newLhs != oldLhs | newRhs != oldRhs) {
                return new BinaryExpression(
                    newLhs, binaryExpression.Op, newRhs);
            } else {
                return binaryExpression;
            }
        }
    }

Oh yes—test cases. I forgot to present them here. But I wrote a few of them!

Tuesday, June 26, 2012

Movimentum - Three basic algorithms: Pattern matching

The next algorithm we need is for matching a constraint or an expression against a "template." For the templates, we need a new data structure that looks like an expression (i.e. can have operators and constants and variables), but also can contain "wild cards"—nodes that can match a complete expression. Two different design ideas come to mind:
  • One, extend the present expressions with an additional WildCard node that has some matching rule.
  • Two, create a new data template structure.
The former might be less work—but the latter is definitely cleaner, because it clearly separates the purposes of the two sorts of data structures. Here is a first attempt for such a Template data structure:

abstract class AbstractExpressionTemplate {
    public ... TryMatch(AbstractExpr e) {
        return ...;
    }
}

class UnaryExpressionTemplate : AbstractExpressionTemplate {
    private readonly UnaryOperator _op;
    private readonly AbstractExpressionTemplate _inner;
}

class BinaryExpressionTemplate : AbstractExpressionTemplate {
    private readonly AbstractExpressionTemplate _lhs;
    private readonly BinaryOperator _op;
    private readonly AbstractExpressionTemplate _rhs;
}

class TypeMatchTemplate<T> : AbstractExpressionTemplate  
                                         where T : AbstractExpr {
}

class FixedExpressionTemplate : AbstractExpressionTemplate {
    private readonly AbstractExpr _expr;
}

UnaryExpressionTemplate and BinaryExpressionTemplate are intended to match unary and binary expressions with specific operators. A TypeMatchTemplate can be used to match e.g. a constant expression. Moreover, with type AbstractExpr it will match any expression. A FixedExpressionTemplate might be useful to match a specified expression—however, I confess that I do not yet see any need for this.

We add constructors and read-only properties and, for convenience, C# operators to create templates—I do not show the corresponding code here.

For the matching algorithm, we do not write a visitor, but put the code into our new data structure. One design questions has to be answered beforehand:
  • We certainly want to store the "captured" expressions somewhere. Should we store them in the template while visiting, or in yet another data structure?
I opt for an additional datastructure. The reason is my immutability conviction—mutable objects should be avoided in functional algorithms. For the templates, this means that they (like expressions) can be reused and even used in parallel. Therefore, I use the following method for finding a match:

    /// <returns><c>null</c> if not successful; or 
    /// a dictionary of (template,expression) pairs if successful.</returns>
    public IDictionary<AbstractExpressionTemplate, AbstractExpr> TryMatch(AbstractExpr e) {
        var collector = new Dictionary<AbstractExpressionTemplate, AbstractExpr>();
        return TryMatchAndRemember(e, collector) ? collector : null;
    }

For the algorithm inside TryMatchAndRemember, we certainly need a few test cases. Here are two very simple ones for a successful and a failing match:

    [Test]
    public void TestMatchConstant() {
        Constant input = new Constant(1.5);
        var m = new TypeMatchTemplate<Constant>();
        var result = m.TryMatch(input);
        Assert.AreSame(result[m], input);
    }

    [Test]
    public void TestDontMatchConstant() {
        Constant input = new Constant(1.5);
        var m = new TypeMatchTemplate<NamedVariable>();
        var result = m.TryMatch(input);
        Assert.IsNull(result);
    }

Here is a somewhat more complex matching job—namely matching the expression a + 1 * 2 with the template v + e:

    [Test]
    public void TestDoMatchAssignment() {
        // Set up expression a + 1 * 2
        var v = new NamedVariable("a");
        var e = new Constant(1) * new Constant(2);
        AbstractExpr input = v + e;

        // Set up template vt + et
        var vt = new TypeMatchTemplate<Variable>();
        var et = new TypeMatchTemplate<AbstractExpr>();
        BinaryExpressionTemplate template = vt + et;

        // Do matching
        IDictionary<AbstractExpressionTemplate, AbstractExpr> result =
            template.TryMatch(input);

        // Check that
        // * vt matched to a
        // * et matched to 1 * 2
        // * complete template matched to input.
        Assert.AreSame(result[vt], v);
        Assert.AreEqual("a", ((Variable) result[vt]).Name);
        Assert.AreSame(result[et], e);
        Assert.AreSame(result[template], input);
    }

Here is a suggestion for the matching algorithm—nothing fancy, but it does what it's supposed to do:

abstract class AbstractExpressionTemplate {
    internal bool TryMatchAndRemember(AbstractExpr e,
          IDictionary<AbstractExpressionTemplate, AbstractExpr> matches) {
        if (matches.ContainsKey(this)) {
            return matches[this].Equals(e);
        } else if (TryMatch(e, matches)) {
            matches.Add(this, e);
            return true;
        } else {
            return false;
        }
    }
    protected abstract bool TryMatch(AbstractExpr e,
          IDictionary<AbstractExpressionTemplate, AbstractExpr> matches);
}

class TypeMatchTemplate<T> : AbstractExpressionTemplate
                                                        where T : AbstractExpr {
    protected override bool TryMatch(AbstractExpr e,  
          IDictionary<AbstractExpressionTemplate, AbstractExpr> matches) {
        return e is T;
    }
}

class FixedExpressionTemplate : AbstractExpressionTemplate {
    protected override bool TryMatch(AbstractExpr e,  
          IDictionary<AbstractExpressionTemplate, AbstractExpr> matches) {
        return _expr.Equals(e);
    }
}

class UnaryExpressionTemplate : AbstractExpressionTemplate {
    protected override bool TryMatch(AbstractExpr e,
          IDictionary<AbstractExpressionTemplate, AbstractExpr> matches) {
        var ue = e as UnaryExpression;
        return ue != null
            && IsSameOperatorAs(ue.Op, _op)
            && _inner.TryMatchAndRemember(ue.Inner, matches);
    }
    private bool IsSameOperatorAs(UnaryOperator op1, UnaryOperator op2) {
        return op1.GetType() == op2.GetType();
    }
}

class BinaryExpressionTemplate : AbstractExpressionTemplate {
    protected override bool TryMatch(AbstractExpr e,
            IDictionary<AbstractExpressionTemplate, AbstractExpr> matches) {
        var be = e as BinaryExpression;
        return be != null
            && IsSameOperatorAs(be.Op, _op)
            && _lhs.TryMatchAndRemember(be.Lhs, matches)
            && _rhs.TryMatchAndRemember(be.Rhs, matches);
    }
    private bool IsSameOperatorAs(BinaryOperator op1, BinaryOperator op2) {
        return op1.GetType() == op2.GetType();
    }
}

Again, one can think about more elaborate matching algorithms, for example full "unification" of expressions with free variable nodes. This may become necessary later, but we'll do it when we need it.

Movimentum - Three basic algorithms: Constant Folding

Let us start bottom up: We know that we need a simplification algorithm; we know that we need a matching algorithm: and we know that we need a replacement algorithm, at least for variables.

Here is a standard simplification that I have already mentioned, namely constant folding.

The design idea for constant folding is as follows: We visit the subexpressions bottom-up. For each compound expression (unary or binary expression), we have three possible cases:
  • If all subexpressions are constants, we replace the whole expression with a new constant computed from the sub-constants.
  • Otherwise, at least one of the subexpressions is not a constant, even after simplification. We now check whether at least one of them has changed, i.e., it or one of its descendants has been simplified. If this is the case, we must recreate a new similar expression with the new subexpressions.
  • Else (no subexpression has changed, and at least one subexpression is not a constant), we return the original expression.
Maybe I should explain here a fundamental (and standard) design decision: All the expression objects will always and forever be immutable, i.e., nothing will ever be changed in them. The reason for this is that we can then share such objects between multiple data structures. Here is a diagram that shows the data structures that result from constant folding of (x + 1) + (2 + 3):


The subexpression for x+1 is shared between the original expression tree and the new expression tree. Some consequences of this sharing are:
  • We reduce the memory footprint. For example, if we run constant folding on an expression tree that has already been folded, no new objects will be created.
  • We can share expressions even when we create them. For example, instead of writing new Constant(...) each time we need a constant, we could use a static factory method that looks into an internal set of already created constants; and returns one of them if the value is already in there. In the case of strings, this is called "interning" (and is done e.g. by Java and .Net compilers).
  • If we can force algorithms to visit a single structure only once, this would also save runtime—we will maybe see examples later.
  •  A structural consequence is that we cannot have parent pointers, as each subexpression may have many parents. This restricts the design of algorithm to some sort of functional style —which, on the whole, is a good thing: This restriction prevents that we build contrived, complex, "clever" algorithms that are hard to understand (and to prove correct). If, at some point, we actually do need doubly-linked expression structures, we will most probably consider building a parallel data structure—right now, there is certainly not yet any need for this.
  • Another structural consequence is that we can have "diamonds" in expression trees: Identical subexpressions could be created only once. "Identical subexpression elimination" is a common step in compilers—if we don't forget this idea, we might check later whether it helps us in Movimentum.
  • Even though subexpressions are shared among expression trees, the immutability would still allow us to work on expression trees in parallel. I will not explore parallel expression algorithms for Movimentum, but it is certainly an interesing topic.
At the moment, I will not follow the ideas present in these items, because I want to concentrate on the solver algorithm proper. But when we (have to) optimize the solver later, we'll certainly return to some of them.

Incidentally, the design decision to make expression objects immutable means that a phrase like "a subexpression has changed" is actually meaningless. So what does it mean when I wrote "...whether at least one of [the subexpressions] has changed..." in the second case of our algorithm? Of course, I mean "...whether the visiting result is different from the subexpression..." The code will show this more clearly.

We start with two simple test cases:

    [Test]
    public void TestConstant() {
        Constant input = new Constant(1.5);
        AbstractExpr result = input.Accept(visitor, Ig.nore);
        Assert.AreEqual(new Constant(1.5), result);
        Assert.AreSame(input, result);
    }

    [Test]
    public void TestVariable() {
        NamedVariable input = new NamedVariable("a");
        AbstractExpr result = input.Accept(visitor, Ig.nore);
        Assert.AreSame(input, result);
    }

The assertion that we actually return the same expressions is essential, as the constant folding algorithm for the compound expressions expects this.

The corresponding implementation is as simple as it gets:

class ConstantFoldingVisitor : ISolverModelExprVisitor<AbstractExpr> {
    ...
    public AbstractExpr Visit(Constant constant, Ignore p) {
        return constant;
    }

    public AbstractExpr Visit(NamedVariable namedVariable, Ignore p) {
        return namedVariable;
    }

    public AbstractExpr Visit(AnchorVariable anchorVariable, Ignore p) {
        return anchorVariable;
    }
}

All other methods of the visitor, at this point, just throw a NotImplementedException. But of course, the tests are green.

Now, let us implement the actual folding. We start with the unary operators, where this simple test case checks that we fold for unary minus:

    [Test]
    public void TestDoFoldConstantInUnaryMinus() {
        AbstractExpr input = -new Constant(4);
        AbstractExpr result = input.Accept(visitor, Ig.nore);
        Assert.AreNotEqual(input, result);
        Assert.AreEqual(new Constant(-4), result);
    }

Here is the implementation of the three cases explained above:

    public AbstractExpr Visit(UnaryExpression unaryExpression, Ignore p) {
        AbstractExpr oldInner = unaryExpression.Inner;
        AbstractExpr newInner = oldInner.Accept(this, Ig.nore);
        if (newInner is Constant) {
            return new Constant(
                unaryExpression.Op.Accept(this, (Constant)newInner, Ig.nore)
            );
        } else if (newInner != oldInner) {
            return new UnaryExpression(newInner, unaryExpression.Op);
        } else {
            return unaryExpression;
        }
    }

The actual computation for constants is delegated to the operator. Therefore, we need at least the following additional code:

class ConstantFoldingVisitor : ...
          , ISolverModelUnaryOpVisitor<Constant, Ignore, double> {
    ...
    public double Visit(UnaryMinus op, Constant inner, Ignore p) {
        return -inner.Value;
    }
}

The test runs green, and so we can—after a few more test cases—complete the unary operator visits:

    public double Visit(UnaryMinus op, Constant inner, Ignore p) {
        return -inner.Value;
    }

    public double Visit(PositiveSquareroot op, Constant inner, Ignore p) {
        return Math.Sqrt(inner.Value);
    }

    public double Visit(Sin op, Constant inner, Ignore p) {
        return Math.Sin(inner.Value * Math.PI / 180);
    }

    public double Visit(Cos op, Constant inner, Ignore p) {
        return Math.Cos(inner.Value * Math.PI / 180);
    }

    public double Visit(Square op, Constant inner, Ignore p) {
        return inner.Value * inner.Value;
    }

    public double Visit(FormalSquareroot op, Constant inner, Ignore p) {
        ???
    }

But wait ... what do we do with the formal square root? Well, a formal square root cannot be evaluated, as it does not return a single value (except when the argument is zero). Therefore, we cannot simplify a formal square root! So, we must modify the code that visits unary expressions. Here is a simple version:

    public AbstractExpr Visit(UnaryExpression unaryExpression, Ignore p) {
       ...
        if (newInner is Constant
            && !(unaryExpression.Op is FormalSquareroot)) {
            return new Constant(
                unaryExpression.Op.Accept(this, (Constant)newInner, Ig.nore)
            );
        } else ...
    }

Instead of the specific type check, it might be better to introduce an IsFunction property for operators that is true if the opeator is a true function, i.e., it returns at most one result for an argument. On the other hand, that might be YAGNI—I simply leave this text as a comment in there so that the IsFunction idea does not get completely lost.

For the binary operators, we again write a few test cases, for example (there are more in the actual code):

    [Test]
    public void TestDoFoldConstant() {
        AbstractExpr input = (new Constant(1) + new Constant(2))
                             * new Constant(4);
        AbstractExpr result = input.Accept(visitor, Ig.nore);
        Assert.AreEqual(new Constant(12), result);
    }

    [Test]
    public void TestDontFoldConstant() {
        AbstractExpr input = (new Constant(1) + new NamedVariable("b"))
                             * new Constant(4);
        AbstractExpr result = input.Accept(visitor, Ig.nore);
        Assert.AreEqual(input, result);
        Assert.AreSame(input, result);
    }

And then we implement the folding algorithm:

class ConstantFoldingVisitor : ...
      , ISolverModelBinaryOpVisitor<Constant {
    public AbstractExpr Visit(BinaryExpression binaryExpression, Ignore p) {
        AbstractExpr oldLhs = binaryExpression.Lhs;
        AbstractExpr oldRhs = binaryExpression.Rhs;
        AbstractExpr newLhs = oldLhs.Accept(this, Ig.nore);
        AbstractExpr newRhs = oldRhs.Accept(this, Ig.nore);
        if (newLhs is Constant & newRhs is Constant) {
            return new Constant(
                binaryExpression.Op.Accept(this, (Constant)newLhs,
                                           (Constant)newRhs, Ig.nore)
            );
        } else if (newLhs != oldLhs | newRhs != oldRhs) {
            return new BinaryExpression(newLhs, binaryExpression.Op, newRhs);
        } else {
            return binaryExpression;
        }
    }

    public double Visit(Plus op, Constant lhs, Constant rhs, Ignore p) {
        return lhs.Value + rhs.Value;
    }

    public double Visit(Times op, Constant lhs, Constant rhs, Ignore p) {
        return lhs.Value * rhs.Value;
    }

    public double Visit(Divide op, Constant lhs, Constant rhs, Ignore p) {
        return lhs.Value / rhs.Value;
    }

As a last step, we extend the visitor so that it simplifies complete constraints. This will most probably come in handy in the solver, when we want to match constraints to patterns. Here is the code for the EqualsZeroConstraint:

    public AbstractConstraint Visit(EqualsZeroConstraint equalsZero, Ignore p) {
        AbstractExpr result = equalsZero.Expr.Accept(this, Ig.nore);
        return result != equalsZero.Expr
                      ? new EqualsZeroConstraint(result)
                      : equalsZero;
    }

As you can see, the folding algorithm does not do an elaborate analysis of the expression. This has the consequence that constants in
v+c+c
c+v+c
(where v is a variable, c a constant) are not at all folded, whereas in
c+c+v
v+(c+c)
the sums are folded. It might be that we need better simplification algorithms later. Right now, we hope that this algorithm is good enough.

Monday, June 25, 2012

Movimentum - The solver algorithm

Searching for solutions has been an active branch of artificial intelligence for more than five decades. I am certainly not trying to re-invent the algorithms from all these years, and I will not use very advanced existing algorithms for equation solving.
Still, it's never wrong to have some background in "search." When I looked on the internet for information about search algorithms, I stumbled over the page and book "Artificial Intelligence - Foundations of Computational Agents." Especially chapters three and four are worth reading for background on constraint solving topics.
Most search algorithms fit the following pattern:
  • It is possible to describe a "partial solution" of the problem at hand; such a partial solution is often called a "node."
  • It is possible to refine a partial solution to a more refined solution; such a step is called "traversing an arc" or "expanding a node."
  • There is a set of nodes that are candidates for expansion; this set is usually called the "open set."
  • The solution can be found by
    • first placing the "non-solution" in the open set;
    • repeatedly replace a node from the open set with its expansion, i.e., with all its successor nodes.
The many proposed and used algorithms differ mainly in the way how they select the node to be expanded in the last step. Moreover, different data structures can be used to store the nodes, the open set, and various auxiliary data structures.

I do not yet want to decide on the actual search algorithm. So I will just create the few structures needed for the algorithms explained above; and use a simple, possibly inefficient search algorithm as a first step.

A node captures at least some partial knowledge in the form of original or modified ("rewritten") constraints. In addition, each node captures "knowledge" about variables—however, it is not yet clear, exactly which knowledge we are going to remember. We will certainly remember solved variables here, i.e., the knowledge that a variable has a single value. However, the inequality constraints AtLeastZeroConstraint and MoreThanZeroConstraint may make it useful to remember range knowledge about variables. Let us call that class VariableRangeRestriction and put off its precise design for a little bit of time.

Here is some code that captures the decisions up to now:

    public class SolverNode {
        private readonly ICollection<AbstractConstraint> _constraints;
        private readonly Dictionary<Variable, VariableRangeRestriction>
                                           _variableInRangeKnowledges;
    }

What does the general algoritm look like? Here is a simple framework: The main solver creates an open set and runs solver steps in a loop, until a solution node is found. As an addition, we pass in known solution values from the last frame—in our specific domain, the solution for a frame should be "near" the solution for the previous frame, so those known values might help us to find a solution more quickly:

    public static IDictionary<Variable, VariableRangeRestriction>
        Solve(SolverNode initialNode,
              int loopLimit,
              IDictionary<Variable, VariableRangeRestriction> previousValues,
              int frameNo) {
        // Create open set
        IEnumerable<SolverNode> open = new[] { initialNode };

        // Solver loop
        SolverNode solutionOrNull;
        do {
            if (!open.Any()) {
                throw new Exception("No solution found for frame " + frameNo);
            }
            open = SolverStep(open, previousValues, out solutionOrNull);
            if (--loopLimit < 0) {
                throw new Exception("Cannot find solution");
            }
        } while (solutionOrNull == null);
        return solutionOrNull.VariableInRangeKnowledges;
    }

A solver step finds a node from all the open nodes with a minimal rank, expands it, and computes the new open set. Moreover, it looks whether one of the new nodes is a solution nodes. In the final version, this should be done by checking that all anchor variables have a unique value. However, for this, we need a variable counting visitor, and ... well ... you didn't want to write visitors last time, did you? So we currently use a rough check that all constraints have vanished from the constraint set, and replace this with a better check later:

    public static IEnumerable<SolverNode> SolverStep(
            IEnumerable<SolverNode> open,
            IDictionary<Variable, VariableRangeRestriction> previousValues,
            out SolverNode solutionOrNull) {
        double minRank = open.Min(cs => cs.Rank);
        SolverNode selected = open.First(cs => cs.Rank <= minRank);
        IEnumerable<SolverNode> expandedSets = selected.Expand(previousValues);

        //IEnumerable<SolverNode> newOpen = open.Except(selected).Concat(expandedSets);
        IEnumerable<SolverNode> newOpen = expandedSets.Concat(open.Except(selected));

        // Maybe not really correct: We should check whether all 
        // anchor variables have a single value.
        // For the moment, in our tests, we live with this check.
        solutionOrNull = expandedSets.FirstOrDefault(cs => cs.IsSolved());

        return newOpen;
    }

Into this generic search algorithm, we must now plug in two functions:
  • Assignment of the rank.
  • Methods for expansion.
Regarding the rank, we run, at the moment, an "uninformed search," i.e., a quite primitve search algorithm. Therefore, we just use a constant as the rank, which leads to a
  • breadth first algorithm if we append the new nodes to the end of the open list;
  • depth first searc if we prepend the new nodes.
Above, I start with depth first search, in the hope that we find a solution quickly by "drilling deep."

How to do node expansion? We are in the domain of equations, and here, "rewriting" is the idea: Modify the constraints in such a way that their solution does not change, yet at the end we have very simple constraints that directly provide the solution. Here is a very simple example: Solve the two equations
0 = y + 2
0 = x + y
From the first equation, we can read off that y is –2 in the solution and drop the first constraint. Moreover, we can replace y with –2 in the second equation, so that we get the new constraint
0 = x + (–2)
From which we can read off that x must be 2.

More abstract, to expand a node, our solver has to look at all the constraints of the node and identify a useful rewriting. This identification is done by matching up all the constraints with patterns. If a pattern matches, a corresponding strategy yields a rewriting. For example, if the pattern is 0 = V + C, where V is a variable and C is a constant, a possible corresponding strategy is
  • record that –C is a solution for V;
  • create the rewriting V → –C.
Expansion itself is then simply the execution of the rewriting on all constraints:

    public IEnumerable<SolverNode> Expand(... previousValues) {
        var rewrite = FindBestRewrite(previousValues);
        IEnumerable<SolverNode> result = ExecuteRewrites(rewrite);
        return result;
    }

Here is an attempt to write hardwired code for the two steps to solve the example from above:

FindBestRewrite checks whether there is a constraint of the form 0 = V + C. If there is, it returns a specific rewrite V → –C:

    private VariableToConstantRewrite FindBestRewrite(...) {
        foreach (var c in Constraints) {
            var ce = c as EqualsZeroConstraint;
            if (ce != null) {
                var bin = ce.Expr as BinaryExpression;
                if (bin != null
                    && bin.Lhs is Variable
                    && bin.Op is Plus
                    && bin.Rhs is Constant) {
                    return new VariableToConstantRewrite((Variable)bin.Lhs,
                                                -((Constant)bin.Rhs).Value);
                }
            }
        }
        throw new NotSupportedException("I found no 0=V+E-Constraint");
    }

ExecuteRewrites runs over all constraints, searches V inside the constraint and ...

    private IEnumerable<SolverNode> ExecuteRewrites(VariableToConstantRewrite rewrite) {
        foreach (var c in Constraints) {
            Variable v = rewrite.Var;
            double value = rewrite.Value;
            // create a new constraint from c, where each v is replaced 
            // with new Constant(value); then simplify the new constraint
            // (e.g., replace 1 + 2 with 3).
        }
        throw new NotImplementedException("Not yet completed");
    }

... well, this hard-wired way does not work. It is much more work than we can afford for a simple test case. Using this code, it is not at all clear that a failing or even a succeeding test is caused by the Solve code or the SolverStep—it could as well be that hard-wired supporting code. Maybe there is another way to write this one-shot code, but I think it is more useful to invest one's time into "production code."