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.