This documentation is archived and is not being maintained.

Solving Constraints with J#

Visual Studio .NET 2003
 

Pratap Lakshman
Microsoft Corporation

January 2005

Applies to:
   Microsoft Visual J# .NET
   Visual Studio .NET

Summary: Design a system representing an equation that can be used to compute one variable in terms of another unknown with information and examples in this article about Visual J# .NET. This is the last part of a three-part series discussing problem solving with J#. (11 printed pages)

Note   The other two articles in the series are part one, An Introduction to Design Concepts Using J#, and part two, Delegates in Action with J#.

Contents

Introduction
Problem Statement
Solution Domain
Design Exercises

Introduction

In CAD systems, it is common to be able to specify mathematical conditions on already drawn parts of a drawing that the system then automatically satisfies to make the drawing take the desired shape. For instance, one could specify the condition that two line segments must remain parallel to each other. If one of the line segments is moved, then the system moves the other line segment in such a manner that they continue to remain parallel to one another. One can think of the line segments involved as variables and the mathematical condition as a constraint applied to those variables. The constraint scopes the degree of freedom of the variables, that is, it restricts the ranges of values that the variables may assume. Given the position of any one of the line segments, the system can solve the constraint to compute the position of the other line segment.

Computer programs organized as one-directional computations, which perform operations on inputs to produce desired outputs, are ill-suited for implementing systems that need to solve constraints. The common equation relating the temperature in Celsius and Fahrenheit illustrates this issue of variables and constraints.

9c = 5(f - 32)

Such an equation is not unidirectional. Given any one of the quantities, we can use it to compute the other. We have an equation where c and f are the variables, and the constraints that apply to them are the mathematical conditions of add, subtract, multiply, and divide—much like the CAD system. Yet translating this equation to a program would force us to compute one of the quantities in terms of the other. A function to compute c cannot be used to compute f although their computations arise from the same equation.

Problem Statement

Design a system representing the above equation that can be used to compute one quantity in terms of the other.

Problem Domain

We have an equation where c and f are the variables, and the constraints that apply to them are the mathematical conditions add, subtract, multiply, and divide. As we solve the equation, various constraints are enforced and intermediate values computed. Denoting all values (including the intermediate values) as held in variables, the left hand side of the equation can be broken down as follows.

k = 9;
u = k * c;

The same product u can also be computed for the right hand side of the equation as follows.

l = 5;
u = l * v;
m = 32;
f = m + v;

Solution Domain

Our design goal is to be able to represent these relations in terms of variables and constraints.

A constraint shall specify and enforce a certain relation between variables. Variables hold values and may participate in more than one constraint. For example: add(x, y, z) specifies that the variables x, y, z are related by the relation x + y = z; multiply(x, y, z) specifies the relation x*y = z; and constant(5, x) specifies that the value of x must be 5. We shall combine such constraints to form a constraint network that will represent the entire equation.

We create two variables c and f and link them together in our constraint network.

    variable c = new variable();
    variable f = new variable();
    cfconverter(c, f);

cfconverter is the Celsius-Fahrenheit network. The network is built as follows.

    variable u  = new variable();
    variable k  = new variable();
    constant c1 = new constant(9, k);
    multiply m1 = new multiply(c, k, u);

    variable l  = new variable();
    constant c2 = new constant(5, l);
    variable v  = new variable();
    multiply m2 = new multiply(v, l, u);

    variable m  = new variable();
    constant c3 = new constant(32, m);
    add a = new add(v, m, f);

The variables u, v, k, l, m are related using add, multiply, and constant constraints, corresponding to the manner in which we broke up the equation earlier. On such a network, if we can now set a value for c we should be able to see the value of f computed, and vice versa.

Computation through such a network proceeds as follows:

When a variable is given a value, it awakens all of its associated constraints (except for the constraint that just awakened it) to inform them that it has a value. Each awakened constraint polls its variables to see if there is enough information to determine a value for a variable. If so, the constraint sets that variable, which then awakens all of its associated constraints, and so on. For example, in conversion from Celsius and Fahrenheit, the constant constraints immediately set the values of the k, l, and m variables to 9, 5, and 32, respectively. The variables awaken the multipliers and the adder, which determine that there is not enough information to proceed. When the value of c is set to say, 100, the leftmost multiplier is awakened, which sets u to 100 * 9 = 900. Then u awakens the second multiplier, which sets v to 180, and v awakens the adder, which sets f to 212.

The interface to a variable is through the following methods:

  • boolean has_value()

    tells if there is a value.

  • double get_value()

    returns the value.

  • void set_value(double d, IConstraint theConstraint)

    indicates that theConstraint wants to set the value to d.

  • void reset(IConstraint theConstraint);

    indicates that theConstraint wants to reset the value.

  • void connect(IConstraint theConstraint);

    indicates that theConstraint wants this variable to participate as a value.

Variables communicate back to a constraint to inform about updates. Constraints perform the role of a mediator [1], encapsulating how a set of variables relate. The interface to the constraint is through the following methods:

  • void valueChanged()

    indicates that the variable's value has changed (and there is a new value).

  • void reset()

    indicates that the variable's value has been reset.

The constant constraint is the simplest. It sets its variable to a constant value, and does not care about the valueChanged and reset methods. Here is our implementation.

// file: IConstraint.jsl
interface IConstraint
{
  void valueChanged();
  void reset();
}

// file: constant.jsl
public class constant implements IConstraint
{
  public constant(double d, variable v)
  {
    v.connect(this);
    v.set_value(d, this);
  }

  public void valueChanged()
  {
    // no op
  }

  public void reset()
  {
    // no op
  }
}

The multiply constraint coordinates the update to three variables: multiplier, multiplicand, and product. The constraint connects itself to these variables so that it is notified if their values are updated. The valueChanged method enforces the relationship between the three variables. Similarly, the reset method resets all variables whenever one of them reports that its value has been reset.

// file: multiply.jsl
public class multiply implements IConstraint
{
  private variable multiplier;
  private variable multiplicand;
  private variable product;

  public multiply(variable v1, variable v2, variable v3)
  {
    multiplier   = v1;
    multiplicand = v2;
    product      = v3;

    multiplier.connect(this);
    multiplicand.connect(this);
    product.connect(this);
  }

  public void valueChanged()
  {
    if (multiplier.has_value() && multiplicand.has_value())
    {
      product.set_value(multiplier.get_value() * multiplicand.get_value(), this);
    }
    else if (multiplier.has_value() && product.has_value())
    {
      if (multiplier.get_value() == 0.0)
      {
        multiplicand.set_value(0.0, this);
      }
      else
      {
        multiplicand.set_value(product.get_value() / multiplier.get_value(), this);
      }
    }
    else if (multiplicand.has_value() && product.has_value())
    {
      if (multiplicand.get_value() == 0)
      {
        multiplier.set_value(0.0, this);
      }
      else
      {
        multiplier.set_value(product.get_value() / multiplicand.get_value(), this);
      }
    }
  }

  public void reset()
  {
    multiplier.reset(this);
    multiplicand.reset(this);
    product.reset(this);
  }
}

The add constraint is similar.

// file: add.jsl
public class add implements IConstraint
{
  private variable addend;
  private variable augend;
  private variable sum;

  public add(variable v1, variable v2, variable v3)
  {
    addend = v1;
    augend = v2;
    sum    = v3;

    addend.connect(this);
    augend.connect(this);
    sum.connect(this);
  }

  public void valueChanged()
  {
    if (addend.has_value() && augend.has_value())
    {
      sum.set_value(addend.get_value() + augend.get_value(), this);
    }
    else if (addend.has_value() && sum.has_value())
    {
      augend.set_value(sum.get_value() - addend.get_value(), this);
    }
    else if (augend.has_value() && sum.has_value())
    {
      addend.set_value(sum.get_value() - augend.get_value(), this);
    }
  }

  public void reset()
  {
    addend.reset(this);
    augend.reset(this);
    sum.reset(this);
  }
}

As part of its state, a variable holds the value, the list of constraints that it is participating in, and the constraint that set its value.

// file: variable.jsl
import java.util.ArrayList;

public class variable
{
  private boolean   hasValue;
  private double    value;
  private ArrayList constraints;
  private IConstraint setter;

  public boolean has_value()
  {
    return hasValue;
  }

  public double get_value()
  {
    return value;
  }

  public void set_value(double d, IConstraint theConstraint)
  {
    value    = d;
    hasValue = true;
    setter   = theConstraint;

    for (int i = 0; i < constraints.size(); i++)
    {
      IConstraint m = (IConstraint) constraints.get(i);
      if (m != setter)
      {
        m.valueChanged();
      }
    }
  }

  public void reset(IConstraint theConstraint)
  {
    if (theConstraint == setter)
    {
      value    = 0.0;
      hasValue = false;
      setter   = null;

      // notify the mediators
      for (int i = 0; i < constraints.size(); i++)
      {
        IConstraint m = (IConstraint) constraints.get(i);
        if (m != setter)
        {
          m.reset();
        }
      }
    }
  }

  public void connect(IConstraint theConstraint)
  {
    if (constraints == null)
    {
      constraints = new ArrayList();
    }
    constraints.add(theConstraint);
  }
}

When the set_value method is invoked, it sets the value, remembers the constraint that made the request, and notifies all other participating constraints. It is important to exclude the setter from the list of constraints that are notified so that the system does not go into an infinite regress. Similarly, reset first checks if the request came from the same constraint that set the value originally, and if so resets its value and notifies all other participating constraints.

We introduce a tap that can be used to "see" the value of a variable. A tap can be thought of as a passive constraint that echoes the value of a variable.

// file: tap.jsl
public class tap implements IConstraint
{
  private variable val;
  private String name;

  public tap(variable v, String s)
  {
    val  = v;
    name = s;

    val.connect(this);
  }

  public void valueChanged()
  {
    System.out.println(name + ": " + val.get_value());
  }
  
  public void reset()
  {
    System.out.println(name + ": " + val.get_value());
  }
}

We can now hook up the network and apply taps to all the variables that we want to monitor.

// file: cf.jsl
public class cf
{
  public static void cfconverter(variable c, variable f)
  {
    variable u  = new variable();    tap tu = new tap(u, "tu");
    variable k  = new variable();    tap tk = new tap(k, "tk");
    constant c1 = new constant(9, k);
    multiply m1 = new multiply(c, k, u);

    variable l  = new variable();    tap tl = new tap(l, "tl");
    constant c2 = new constant(5, l);

    variable v  = new variable();    tap tv = new tap(v, "tv");
    multiply m2 = new multiply(v, l, u);

    variable m  = new variable();    tap tm = new tap(m, "tm");
    constant c3 = new constant(32, m);
    add a = new add(v, m, f);
  }

  public static void main(String[] args)
  {
    variable c = new variable();    tap tc = new tap(c, "c");

    variable f = new variable();    tap tf = new tap(f, "f");

    cfconverter(c, f);

    c.set_value(100, null);
    c.reset(null);
    f.set_value(32, null);
  }
}

When the variable c is set a value of 100, observe how computation propagates until the value of f is reported as 212. At this point, the network is said to be fully constrained. Merely setting f to a new value will not cause the network to compute c. The network has to be reset so that all the constraints are loosened. We can then set a value on f so that c is now computed.

QED.

Design Exercises

  • How would you represent a line segment? How would you represent the constraint that two line segments must remain parallel to each other?

References:

[1] Design Patterns: Elements of Reusable Object-Oriented Software—Gamma E. et al. Addison Wesley, 1995

Show: