Constraint-Based Languages and Environments for Building Interactive Systems

Alan Borning

Department of Computer Science and Engineering
University of Washington

CONTACT INFORMATION

Department of Computer Science and Engineering
University of Washington
PO Box 352350
Seattle, WA 98195-2350
Phone: (206) 543-6678
Fax : (206) 543-2969
Email: borning@cs.washington.edu

WWW PAGE

Personal home page: http://www.cs.washington.edu/homes/borning
Research project home page: http://www.cs.washington.edu/research/constraints

PROGRAM AREA

Usability and User-Centered Design.

KEYWORDS

Constraints, constraint solvers, user interface toolkits

PROJECT SUMMARY

A constraint represents a relation that should be maintained. This project is concerned with applying constraint technology to building interactive systems, in particular constraint-based user interface toolkits. One activity has been the development and testing of new constraint satisfaction algorithms that can handle the kinds of constraints that arise in such applications, including inequalities, simultaneous equations and inequalities, and non-numeric constraints. Our most recent algorithm (Cassowary) can efficiently and incrementally solve simultaneous linear equality and inequality constraints. We are currently applying this work to a constraint-based web authoring and browsing tool, in which both the author and the viewer of a web document can apply constraints to the layout and appearance of the page. Some of these constraints may be requirements and some preferences. As a result, the appearance of the page is in effect the result of a negotiation between the author and viewer, where this negotiation is carried out by a constraint solver.

Other constraint satisfaction algorithms developed as part of this project include SkyBlue (for local propagation constraints), Ultraviolet (a hybrid solver that supports subsolvers for different kinds of constraints), and a batch compiler based on Fourier elimination that produces very efficient code for simultaneous linear equalities and inequalities. Other work has included the construction of the Multi-Garnet user interface development system and the CNV user interface builder and debugger, and the design and implementation of Kaleidoscope, constraint imperative programming language that integrates constraints with object-oriented, imperative constructs at the language level.

PROJECT REFERENCES

Alan Borning, Richard Anderson, and Bjorn Freeman-Benson, "Indigo: A Local Propagation Algorithm for Inequality Constraints,", Proceedings of the 1996 ACM Symposium on User Interface Software and Technology, pages 129-136.

Alan Borning, Richard Lin, and Kim Marriott, "Constraints for the Web," accepted for ACM Multimedia'97.

Alan Borning, Kim Marriott, Peter Stuckey, and Yi Xiao, "Solving Linear Arithmetic Constraints for User Interface Applications". Accepted for 1997 ACM Symposium on User Interface Software and Technology.

Warwick Harvey, Peter Stuckey, and Alan Borning, "Compiling Constraint Solving using Projection," Accepted for Third International Conference on Principles and Practice of Constraint Programming.

Gus Lopez, Bjorn Freeman-Benson, and Alan Borning, "Kaleidoscope: A Constraint Imperative Programming Language", In Constraint Programming, B. Mayoh, E. Tougu, J. Penjam (Eds.), NATO Advanced Science Institute Series, Series F: Computer and System Sciences, Vol 131, Springer-Verlag, 1994, pages 313-329.

Gus Lopez, "The Design and Implementation of Kaleidoscope, A Constraint Imperative Programming Language", PhD dissertation, April 1997. Published as UW Tech Report 97-04-08.

Michael Sannella, "SkyBlue: A Multi-Way Local Propagation Constraint Solver for User Interface Construction", in Proceedings of the 1994 ACM Symposium on User Interface Software and Technology, pages 137-146.

Most of these papers are available from http://www.cs.washington.edu/research/constraints.

AREA BACKGROUND

A constraint represents a relation that should be maintained in a computer program, for example, that the relationship A+B=C hold among three numbers A, B, and C, that the corner of a rectangle follow the mouse as long as a button is held down, that one window be the same width as another in a window layout manager, or that a resistor obey Ohm's Law in an electrical circuit simulation. In general, constraints can be used multi-directionally. For example, given the A+B=C constraint, the system might satisfy the constraint by finding a value for A, for B, for C, or (in combination with other constraints) values for several of the variables.

It is useful to extend the basic notion of constraints to that of a constraint hierarchy: a collection of constraints, some of which must hold, and some of which are preferences but not requirements. Using constraint hierarchies, we can express such desires as "place window1 above window2 if possible, and, less importantly, place window1 above window3". In addition, a frequent application of constraint hierarchies is to express the desire that objects in an interactive display not move unless there is some stronger constraint that forces them to do so.

Constraints have a number of highly desirable properties that make them useful in building computer systems, in particular interactive graphical applications. They are declarative statements of what the programmer or designer would like, rather than imperative statements of how that relationship should be satisfied. They often closely match ways designers of interactive systems describe their tasks to other humans. Without explicit constraints, programmers must translate them in their heads into procedural code, often scattered in multiple locations. This results in added difficulties in writing the initial program, in debugging, and in maintenance.

AREA REFERENCES

The investigation of constraint languages and constraint-based systems has been emerging as an identifiable subarea of computer science. There is now a yearly international conference on constraint programming, and an archival journal, both of which include papers on using constraints in interactive systems as well as other topics. In addition, papers on constraint solvers and constraint-based systems are often published in the ACM Symposium on User Interface Software and Technology and other UI conferences.

Here are URL's for most recent of these conferences and for the journal:

Two significant UI toolkits that support one way constraint systems are SubArtic in Java (http://www.cc.gatech.edu/gvu/ui/sub_arctic) and Amulet in C++ (http://www.cs.cmu.edu/afs/cs.cmu.edu/project/amulet/www/amulet-home.html).

Unfortunately, however, there is not yet a good introductory text or comprehensive survey of the area focussed on interactive systems.

Below are listed some relevant papers.

Krishna Bharat and Scott Hudson, "Supporting Distributed, Concurrent, One-Way Constraints in User Interface Applications", UIST'95.

Alan Borning, Bjorn Freeman-Benson, and Molly Wilson, "Constraint Hierarchies", Lisp and Symbolic Computation, Vol. 5 No. 3, (September 1992), pages 223-270.

Michael Sannella, John Maloney, Bjorn Freeman-Benson, and Alan Borning, "Multi-way versus One-way Constraints in User Interfaces: Experience with the DeltaBlue Algorithm", Software--Practice and Experience, Vol. 23 No. 5, (May 1993), pages 529-566.

Michael Gleicher, "Practical Issues in Programming Constraints", Principles and Practice of Constraint Programming: The Newport Papers, Vijay Saraswat and Pascal van Hentenryck (eds), MIT Press, 1995, 407-426.

RELATED PROGRAM AREAS

Virtual Environments; Adaptive Human Interfaces; Intelligent Interactive Systems for Persons with Disabilities.