Debugging Spreadsheet-style Constraints

Objective. The project seeks to develop new techniques for visualizing and debugging one-way, dataflow constraints.

Background. One-way, dataflow constraints (also called spreadsheet-style constraints) are widely recognized as a potent programming methodology. They have found research uses in a variety of applications including graphical interfaces, attribute grammars, and circuits, and they have found commercial use in spreadsheets. Indeed, if one considers the number of spreadsheet users, one-way constraints are probably the most widely used programming technique today. However, there is considerable evidence that one-way constraints are difficult to debug and that this difficulty can pose both productivity and reliability concerns. This debugging problem seems to be preventing one-way constraints from achieving even wider spread use. For example, discussions with researchers in industry and toolkit developers at conferences suggest that they are reluctant to use constraints because of the debugging problem.

Significance of the Research. Better debugging and visualization techniques for one-way constraints would have a number of significant benefits:

  1. Greater acceptance for constraints outside the research and spreadsheet communities. Researchers and toolkit developers would have greater confidence that constraints can be reliably used to create applications, making them more amenable to including constraints in toolkits.

  2. Greater productivity among existing constraint users. Programmers would spend less time testing and debugging applications, thus improving productivity.

  3. Greater reliability for applications. Programmers would find it easier to resolve troublesome behavior, thus encouraging them to fix problems rather than ignoring them. The result would be increased reliability for applications, especially spreadsheet applications.

The current research assumes that users have some knowledge of programming. However, our long-term goal is to gain experience with the proposed technology so that it can be simplified and made useable by non-programmers.

Methods. We are developing three sets of new techniques for debugging and visualizing one-way constraints:

  1. Visualization techniques that will allow programmers to examine a constraint solver's data structures, especially its dataflow graph.

  2. Incremental debugging techniques that will allow programmers to single-step through the constraint solver and set breakpoints in the constraint solver.

  3. Explanation-based techniques that will allow the debugger to record significant events during the solving process and then analyze these events to help the programmer pinpoint the source of a bug.
These techniques are analagous to tools with which programmers are familiar, yet are adapted to the constraint solving paradigm. By leveraging off programmers' existing knowledge, the techniques should be more easily learned and readily accepted.

Project Snapshot

Here's a snapshot of the visual techniques we've been developing:

The window in the upper left corner is a sample application that is being debugged. The window in the upper right corner is an "inspector" window that shows the values of the properties for the upper, leftmost rectangle in the application window. Finally the bottom window shows a dataflow graph for the constraints that are being used to lay out the objects in the application window. An arrow from a property to a constraint indicates that the constraint is using the property's value as an input. An arrow from a constraint to a property indicates that the constraint is setting the value of that property. The exclamation mark indicates that a breakpoint has been placed on the constraint, which causes the constraint solver to pause when it starts to evaluate the constraint. The green lines indicate that constraint3 is currently being executed by the solver. The dataflow graph helps a programmer see how data propagates through the constraints. It can be used to determine if there are cycles in the constraint graph, or whether there are unexpected paths through the constraint graph (i.e., constraints depending on properties that the programmer did not expect the constraint to depend on, or not depending on properties that the programmer expected the constraint to depend on).

Funding

This project is being supported by the National Science Foundation under Grant No. CCR-9970958.

Graduate Students

Alumni

Publications

  • Bradley T. Vander Zanden, Richard L. Halterman, Brad A. Myers, Rich McDaniel, Rob Miller, Pedro Szekely, Dario Giuse, and David Kosbie. ``Lessons Learned About One-Way, Dataflow Constraints in the Garnet and Amulet Graphical Toolkits'', In ACM Transactions on Programming Languages and Systems, Nov, 2001, 23(6), pp. 776-796.
  • Bradley T. Vander Zanden, Richard L. Halterman, Brad A. Myers, Rob Miller, Pedro Szekely, Dario Giuse, David Kosbie, and Rich McDaniel. ``Lessons Learned from Users' Experiences with Spreadsheet Constraints in the Garnet and Amulet Graphical Toolkits'', University of Tennessee Technical Report ut-cs-02-488, October, 2002, Knoxville, TN 37996.

  • Bradley T. Vander Zanden, David Baker, and Jing Jin. ``An Explanation-Based, Visual Debugger for Spreadsheet-like Constraints''. University of Tennessee Technical Report ut-cs-02-487, October, 2002, Knoxville, TN 37996.

    Software

    In order to develop a testbed for the debugging research, we our creating the Silhouette toolkit. Silhouette is Java-based and provides a set of classes that allow custom graphical shapes to be created, displayed, and manipulated by the mouse and keyboard. Silhouette's goal is to make it almost as easy to create and manipulate custom graphical objects as it is to create and manipulate Java's swing components. This goal is supported in the following fashion:

    1. Primitive shapes, such as lines, rectangles, and text, are provided that resemble Swing components in some respects, although they do not extend the JComponent class and should not be mistaken as JComponents. The way in which these shapes resemble Swing components is that:

      1. They have a set of user-settable properties, such as position, size, and fill color. These properties control the graphical appearance of each shape.
      2. When the user modifies a shape's property, Silhouette automatically redraws the shape and any other shapes that intersect the changed shape. In other words, Silhouette redraws the damaged portions of the display.
      3. A Silhouette version of event listeners can be attached to primitive shapes. Just as Java automatically dispatches events to the appropriate Swing components, Silhouette automatically dispatches events to the appropriate Silhouette objects. Additionally, Silhouette understands that once an interaction with an object has started, that subsequent events should be dispatched to that object until the interaction has been completed. As a result, the programmer does not have to write "traffic-cop" code that directs events to objects, or that suppresses inappropriate interactions from starting while another interaction is in progress.

    2. Primitive shapes can be assembled into more complicated shapes using CompositeShape objects. CompositeShape objects resemble Swing container objects although CompositeShape objects are meant to create a shape rather than to specify layout, as Swing containers typically do. For example, a programmer can create a labeled box by building a composite shape that consists of a rectangle and a text shape. Silhouette provides a scripting language that allows the programmer to easily specify composite shapes. The scripting language uses the specification to generate code that automatically creates and assembles the parts for the composite shape. The programmer can then create an arbitrary number of these composite objects at run-time by simply creating instances of the composite shape.

    3. Silhouette allows spreadsheet-style formulas to be attached to properties. These formulas allow a property's value to depend on the values of other shape's properties, and just as in a spreadsheet, if one of these properties is changed, the formula will be automatically re-computed. For example, if the programmer wants a label centered inside a box, the programmer could attach the following formula to the label's left property: 

           label.left = box.centerX - label.width / 2
      Silhouette also provides a number of pre-defined formulas that make it easier to specify many geometric relationships. For example, Silhouette has a pre-defined formula called alignCenterX that centers one object within another object. Therefore the programmer could also have written: 

           label.left = alignCenterX(box)