Research

Home

Rick Halterman's Ph.D. research at the University of Tennessee, Knoxville Computer Science Department involved developing techniques for dataflow constraint optimization.

Dataflow constraints allow relationships among programming objects to be expressed declaratively; for example, a typical system of constraints might be represented by the following set of formulas: 

   inner_box.left = outer_box.left + 5
   inner_box.width = outer_box.width - 10
   inner_box.top = outer_box.top + 5
   inner_box.height = outer_box.height - 10

(Here, as is common in computer graphics, the origin is in the upper-left corner, and the y-axis is inverted.)

Boxes image

These formulas constrain a smaller rectangle to remain within a larger rectangle. (See the figure.) The distance between corresponding edges of the two boxes remains constant (5 units), no matter how the larger box is moved or resized. (These constraints are one-way constraints, so the relationships will not hold if the inner box is moved or resized.)

Constraints are useful in graphical interface technology. They make the development of highly interactive interfaces easier for the applications programmer. In addition to enforcing geometric relationships among visual components, constraints can reconcile an application's internal state to its graphical presentation, and vice-versa. While the creation of widgets (dialog boxes, menus, etc.) is easy with interface builders, tools and techniques for easing the task of creating application specific graphics remain limited research projects. Dataflow constraints have proven a useful tool in this area. Constraint-based programming is not just limited to GUIs, though; it is applicable to any system in which the relationships among objects must be specified and maintained—just about any reasonably complex system.

Currently, however, constraints are not used by most commercial software developers. Systems that use constraints tend to be much larger and slower than systems built with the traditional, but much more tedious, methods. This is because systems that use constraints require accessory data structures that must be maintained in addition to the application's programming objects. These dependency graphs required by dataflow constraints can be become enormous as the number objects in an application increases. Eventually an application may need to access virtual memory to meet the storage requirements, and interactive performance degrades considerably.

My research explored ways to optimize software systems that use constraints. Dynamic analysis, including techniques used in optimizing compilers and high performance computer architectures, are employed to assist the process. Using model dependency graphs I reduced number of edges in dependency graphs by around 80% in actual applications. The ultimate goal is to produce constraint-based systems with executables that are just as efficient as those systems that do not use constraints. The result will be a big win for programmers since code can be written more quickly and naturally, and in a more modular and robust fashion, than with the traditional approach.

Much of my work was done in Amulet . Amulet is a research tool developed at Carnegie Mellon University. Written in C++, it is used for building graphical user interfaces supporting techniques of current research interest including constraints.

This research has been in collaboration with Dr. Brad Vander Zanden and has been funded in part by a grant from the National Science Foundation.

Papers