CS 2360 Lecture 14: February 28

Constraints

A good deal of this material (both in textual and idea forms) are due to Scott Hudson.

Constraints offer the ability to describe, in a high-level and declarative fashion, a set of relationships that are to hold among data items. Given a set of values and a set of relationships between them expressed as equations, a constraint maintenance or evaluation system can be employed to automatically maintain the proper relationships between these values in the face of changes. The automatic nature of this update allows very high level specifications to be employed for a number of tasks in the user interface software domain. These include, for example, controlling user interface presentations [Huds89, Huds90, Vand90, Myer93], making connections between data objects and interactive views of those objects [Huds88, Hill92], support for construction of graphical documents [VanW82], and controlling animation [Born86].

Because of their inherent advantages, constraint systems of various sorts have been used in a number of user interface systems (see for example [Bart86, Born86, Myer90, Huds93b]). However, constraints are still considered an "exotic" technology in many circles. One reason for this is that, in the compiled languages that would typically be used for production user interface development (i.e., languages like Pascal, C, C++, Eiffel, etc.), there have been no systems that allow truly convenient and efficient integration of constraints with the rest of the user interface and application code. Many such systems however exist for our target language: Lisp. More the details of this in a minute.

One Way or Many Ways?

The general problem of constraint satisfaction is unsolvable (I believe its no to be the same as solving systems of Boolean equations which is known to be NP hard). Consequently, all constraint systems place some limitations on the classes of constraints that they can deal with. Among systems supporting user interface applications both so called "one-way" and "multi-way" constraint satisfaction systems have been used.

One-way systems (such as the one described here) place limitations on the form of equations that may be used such that information always flows only from the right hand side of a constraint rule to the left hand side hence the designation as "one-way". In general, these systems support rules of the form (in a pascal-like notation):

A = F(B,C,D); This rule states that the value of attribute A will always be equal to the value obtained by applying function F to (the updated values of) attributes B, C, and D. This form of rule allows only a single attribute on the left hand side and does not allow any given attribute to be defined by more than one equation. Typically these systems also require that there are no circular dependencies between attributes, however, this restriction is lifted in various ways in some systems.

Consider if this were not the case. Here is a system of cyclic constrains which could cause you a problem:

A= B -2 ; B= A -2 ; What values satisfy these equations? If a constraint system was processing these values what might happen? (Hint: Think about substituting the equations in for the values in the above equations.) It is important that you understand that in the constraint

A = F (B,C,D); says nothing about the values of B, C, and D. It says how to compute A from the values in question not the reverse. This is why the system is called "one-way." Note that a one-way system which guarantees that the constraints will be satisfied will adjust the value of A to meet the constraint above but if A is modified it will not modify B, C, or D to insure the constraint is met. Multi-way constraints normally remove the asymmetry from rules and allow information flow in different directions at different times. In general they may support rules such as:

F(A,B) = G(C,D); or

F (A,B) < G(C,D); However, except in special cases (such as multi-linear equations) the system designer is typically responsible for providing a series of solution methods (or factorizations of the rule equation), each of which allows one attribute's value to be computed as a function of the remaining attributes.

In general, multi-way constraints are more powerful and can support some constructions that one-way constraints cannot. However, with this generality comes some cost.

First, multi-way constraint satisfaction systems can fail to find a solution to a system of constraints that arise at runtime either because no such solution exists, or because the particular solution mechanism being employed cannot find one. Currently few analysis techniques exist for detecting or characterizing this possibility in advance. Consequently the system designer may need to explicitly provide for this possibility in all aspects of a system that uses constraints (see [Born87, Free90] for one approach to this). In contrast, one-way constraints are guaranteed to find a solution in all cases (so long as the code for each individual constraint equation completes in finite time).

Second, multi-way constraint systems are much less predictable and understandable than one-way systems. For example, unlike one-way systems, multi-way systems can find themselves in under-constrained situations where more than one solution is valid. Robust approaches for specifying how the system is to respond in these cases have been developed (see [Born87, Free90]). However, it is can still be difficult to understand at design or specification time, just how the system will react in all cases at run-time. Again, this is in contrast to one-way systems which, because of their more restricted form, are very easy to understand and predict.

Why In The World Would I Want To Use This Stuff

My chief interest in the use of constraints is to make user interface programming easier. However, since I realize many of you have probably never built user interface software, I'll try to motivate my examples by giving you cases where people do stupid or ugly things in interfaces that you can see, and/or programming examples you are familiar with.

Geometry Management

How many times have you resized a window on a Mac, Pc w/windows, or a unix box running X and had it, "not do what you wanted." Somehow, the person who wrote the code just didn't "do the right thing" with resizing. The reason this happens is because sophisticated geometry management is hard without constraints. Consider an expression which can make things stay spaced correctly (in a C++ or Modula style notation) as well as as aligned:

object2-left := object1-right + 2 object2-top := object1-top

Connect 4 Display

Suppose you had a terminal package which could control a particular character on the screen based on the contents of a two dimensional array called "screenDisplay." Further suppose you knew that the upper left corner of the connect 4 board should be displayed at (screen location) 5,6. Consider these constraints (again using Pascal or Modula3 notation): screenDisplay(5,6) := ValueAtBoardPosition(0,0) screenDisplay(5,7) := ValueAtBoardPosition(0,2) screenDisplay(5,8) := ValueAtBoardPosition(0,3) ... Now your board is always syncrhonized with your positions, and you never need to write a function which "updates" the screen to reflect new board values.

Now suppose that you have a two player version of connect four which the players were connected to each other (and your program) via a network. You want to make sure that they each get correct (up to date) displays and that you don't to do very much work. Just reuse your constraints above for each players display:

screenDisplayPlayer2(5,6) := screenDisplay(0,0) ... Shazam, now both players have displays that are synchronized to your data structures!

Now suppose each player wants to play red but they can agree who will will go first. How could you use constraints to make sure that each player felt happy (saw the color red (or a little 'R') on their display for their pieces) and yet you didn't have to do very much work? Well, write a function called c4-invert-color which changes red to black and vice versa, but doesn't affect the empty spaces. Now rewrite your constraints for player two's screen to be:

screenDisplay(5,6) := c4-invert-color(ValueAtBoardPosition(0,0)) screenDisplay(5,7) := c4-invert-color(ValueAtBoardPosition(0,2)) screenDisplay(5,8) := c4-invert-color(ValueAtBoardPosition(0,3)) ...

Connect 4 Data Structure

Someone came to my office and said:

Sometimes you want a column-based data structure and sometimes you want a row-based data structure, maybe I should just keep both?

I said, "No, that'll be difficult, because everytime you modify one, you'll have to go modify the other. Further, it requires double the code because every modification (or access) routine now must be written once for each data structure. If you have constraints, this problem goes away. Say you decide to use columns, but might find it convenient to have rows sometimes. You write all of your code to modify/access columns and have one function "extract row from board" which will walk across the columns to extract a row. Now consider these constraints:

row1 := ExtractRowFromBoard(some-board,1); Now you are guaranteed that anytime you need access to row1, it will be "synchronized" with the other (column-based) representation.

The astute observer here will realize that there is a problem with the above. It cannot compute a general transformation of the data structure (i.e. on boards of arbitrary size) because we need to know in advance what values to compute. We would need to enumerate the row values to compute. What we really want to say is:

for i from 0 to number-of-rows(some-board) : row[i]:=ExtractRowFromBoard(some-board,i)

Bank Example

Suppose you wanted to build an interactive system which could constantly display the monthly payments for potential car-buyers. They would input some values such as the amount of the car, the down-payment, the finance rate, the number of months, etc., and at all times the monthly payment should be kept up to date on the screen. This is useful so people can explore what the payment schedule looks like. If you can express the monthly payment as a function of the variables, you are home free with constraints! monthlyPayment:=F(amountOfCar,amountOfDownpayment,rate,numberOfMonths); Now, you never have to worry about recalculating the monthly payment!

Implementing Constraints

Well, all along here we have been assuming that we had a constraint system which could do this for us... Now, the real problem! How would we construct a system which could automatically perform the work of updating values to make sure constraints are always met.

For this discussion, we'll assume that a set of constraints operates over a set of variables. We need to be sure that our system can handle changes to both the set of variables and to the set of constraints.

This is a declarative system. You say (as the programmer) what is to happen, not how it is to happen. The system takes care of the how. Note that "constraints" is a loaded word. There is a whole community of people of who do "Constraint Logic Programming" which is not what we are doing here, nor is this what some scientific programming people call constraint satisfaction (which tends to be numerical in nature).

Some assumptions we will make to make our situation a little more restricted and thus easier to deal with are:

Information flow is only one way. (See above on one-way constraints).
Variables may only be the target of one constraint (i.e. may only have one defining constraint).
Variables which have a defining constraint may not be assigned to.

Dependency Graphs

Before we get very far we will need to build a dependency graph. This a graph which expresses which variables "depend on" other variables to compute their values. The nodes in the graph are varaibles, the edges are dependencies. An edge from A to B indicates that B is dependent on A. Consider the constraint: A := B + C ; This implies two edges, B->A and C->A. Note: you can reverse the edge direction if you wish, as long as you are consistant.

Simple Approach

Reverse topologically sort graph.
For each variable A, use its constraint to bring it up date.

Topological Sort

A topological sort (for our purposes) is a sort of the nodes of the graph based on the outgoing dependency edges. This sort says that a node X is in front of node Y in the sorted list if there is an edge from Y to X. A reverse topological sort says that X is in front of Y if there is an edge from X to Y.

Note: this does not produce a total order, but sufficiently good partial order. Example:

   b 
 /   \ 
a     d
 \  / 
  c   
   \  
    e

Edges here are from B to A, C to A, D to C, D to B, and E to C. A toplogical sort gives you :

A, B, C, D, E, F. There are other possible orderings, such as A, C, B, F, E. A reverse topological sort gives you: F, E, D, C, B, A Now, returning to our discussion of bringing constraints up to date, you should see that it is useful to topologically sort as if you didn't, you might end up calculating some values more than once. Consider an order like F, E, B, C, D, A. This order is terrible because to make sure the constraints hold you'll end up calculating the value of B and C multiple times!

Approach 2: Data Driven

Here is a better algorithm which updates things in a more intelligent manner. It should be called whenever a variable (or set of variables) is modified.

Make direct-change all the variables just modified.
work=empty;
foreach A in direct-change do work: work union depends_on(A)
while work not empty
remove some variable A from work
temp := value of A
bring A up to date based on its constraint
if temp != value of A work:=work union depends_on(A)
end while

Consider this example:

       (A)
       / \                (all edges are up)
     (B) (C)              Change G
     / \   \              Assume B does not result in a new value
   (D) (E)  (F)           Therefore A,C, & F never get in work list
    |
   (G)

Note that if the values that a variable depends on never get changed, it never ends up in the work list and never (needlessly) gets evaluated.

The big problem here is that variables may end up in the work list multiple times. In fact, they may end up there an exponential number of times! This is a result of a variable gettting "intermediate" values before it gets its final value. Consider modifying the graph above to have an edge from D to E and reconsider our example. (B will end up on the queue multiple times.)

Approach 3: A simple demand driven algorithm

A simple demand driven approach is to start at what you want, and work in the other direction. Note: This approach does not modify the values when the values change, but when they are demanded (asked for) . Consider this algorithm with the assumption that every variable can be marked with a bit that says if it is "out of date".

directNeed := set of variables' values needed
foreach variable A in the graph mark A out of date
foreach variable A in directNeed do demand_eval(A)
demand_eval(A) if A is out of date, bring it up date by:
- foreach edge from B-> A do demand_eval(B)
- evaluate the constraint on A
- mark a not out of date

Note: this is really just a topological sort with the evaluations being done along the way.

Note: This alogorithm doesn't take into account what has changed. It could potentially reevaluate the entire graph.

Sketch Of A Combined Data and Demand Driven Approach

This is just the basic idea of how to combine the data and demand approaches to get an optimal solution. You will need to have a bit stored on each variable to know if it is "out of date" or not.

For each modified variable, mark it and everything that depends on it out of date. Do this recursively on marked nodes!
Foreach variable A whose value you need, evaluate everything that A depends on. Note: You won't need to bother on objects which are not out of date!
If none of the parameters of A have changed and no incoming edges have marks, don't bother evaluating the constraint on A. If they have changed or there is a marked edge, evaluate the constraint on A and note that it is not out of date. If the resulting value of A is different, mark all outgoing edges of A.
After updating A, mark A such that it is not out of date.

Back To The CS2360 Home Page

Ian Smith (iansmith@cc.gatech.edu)