CONSTRAINT-BASED LANGUAGES AND ENVIRONMENTS
FOR BUILDING INTERACTIVE SYSTEMS

Alan Borning

University of Washington

CONTACT INFORMATION

Department of Computer Science and Engineering, University of Washington, PO Box 352350, Seattle, WA 98195-2350

borning@cs.washington.edu, (206) 543-6678 (voice), (206) 543-2969 (fax)

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. Most of the work to date under the current grant has been on incremental constraint satisfaction algorithms, and tools and techniques for debugging constraint systems. Specific projects completed to date include the design and testing of a new incremental constraint satisfaction algorithm, SkyBlue, construction of the Multi-Garnet user interface development system, and construction of the CNV user interface builder and debugger. Current projects include the design and implementation of a constraint imperative programming language, applying constraint-based systems to financial visualization problems, and supporting constraints in WWW documents. Planned projects include an evaluation of the ease of use of different classes of constraint satisfiers.

PROJECT REFERENCES

Michael Sannella, "Analyzing and Debugging Hierarchies of Multi-Way Local Propagation Constraints", in Alan Borning (ed.), Proceedings of the 1994 Workshop on Principles and Practice of Constraint Programming, Springer-Verlag, Lecture Notes in Computer Science No. 874, pages 63-77.

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.

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.

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 have been emerging as an identifiable subarea of computer science. There is now a yearly international conference on constraint programming, which includes papers on using constraints in interactive systems as well as other topics. Despite this, there is no good introductory text or comprehensive survey of the area. Below are a few relevant papers.

Krishna Bharat and Scott Hudson, "Supporting Distributed, Concurrent, One-Way Constraints in User Interface Applications", to appear in 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.

Scott E. Hudson, "A System for Efficient and Flexible One-Way Constraint Evaluation in C++", Georgia Tech TR 93-15.

Brad Myers et al., "Garnet: Comprehensive Support for Graphical, Highly-Interactive User Interfaces", IEEE Computer, Vol. 23 No. 11, Nov 1990, pages 71-85. (See also papers on the more recent system: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/amulet/www/amulet-home.html)

In addition, see the proceedings of the constraint programming conference CP'95 and its antecedent workshops PPCP'94 and PPCP'93. Papers on constraints and user interfaces often also appear in the ACM UIST proceedings.

Proceedings of the 1995 International Conference on Constraint Programming (Ugo Montanari and Francesca Rossi, eds, published as Springer-Verlag LLNCS 976)

Proceedings of the 1994 Workshop on Principles and Practice of Constraint Programming (Alan Borning, ed, published as Springer-Verlag LLNCS 874);

Principles and Practice of Constraint Programming: The Newport Papers, Vijay Saraswat and Pascal van Hentenryck (eds.), MIT Press, 1995.

RELATED PROGRAM AREAS

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