Scott E. Hudson
Human Computer Interaction Institute
Carnegie Mellon University
5000 Forbes Ave.
Pittsburgh, PA 15213
Office:
Fax : (412) 268-5576
Email: hudson@cs.cmu.edu
http://www.cc.gatech.edu/gvu/people/scott.hudson/
Constraint Systems, Attribute Evaluation, Tools, Algorithms, Incremental Update, Distributed Interfaces, Interface Generation, Flexible Layout, Semantic Feedback, Visual Specification.
This project seeks to develop and explore the use of advanced constraint-based techniques in the production of user interface software. Constraints as a general computational technique allow the declaration of a set of relationships that are to hold between entities. A constraint satisfaction system is employed to automatically ensure that these relationships hold under changing conditions. This allows the programmer (or user interface implementor) to specify, at a relatively high level, what is to happen, while relying on the system to automatically determine how these requirements are to be carried out.
A subset of constraint techniques (primarily propagation-based techniques often called one-way and multi-way constraints) have been employed in user interfaces for some time. These techniques have been recognized as extremely useful in implementing several aspects of a typical advanced user interface including:
This project seeks to produce two kinds of advances in constraint techniques
for user interface software. First, it seeks to make existing constraint
technology more accessible and practical for real interface implementations
by developing several important practical tools. Second it seeks to create
new advances in constraint systems themselves by extending them to new domains
and considering new user interface tasks that can be supported by them.
[1] Scott E. Hudson, Ian Smith, "Automatic Generation of Starfield Displays Using Constraints", CHI '95 Conference Companion, pp. 202-203 May 1995.
[2] Krishna Bharat, Scott E. Hudson, "Supporting Distributed, Concurrent, One-Way Constraints in User Interface Applications", Proceedings of the ACM Symposium on User Interface Software, pp. 121-132, Nov. 1995.
[3] Scott E. Hudson, Ian Smith , "A Practical System for Compiling One-Way Constraints into C++ Objects", submitted to ACM Transactions on Computer Human Interaction.
[4] Scott Hudson, Ian Smith, "Ultra-Lightweight Constraints"
Proceedings of the ACM Symposium on User Interface Software and Technology,
pp. 147-155, November 1996.
[5] Scott E. Hudson and Ian Smith, "Supporting Dynamic Downloadable
Appearances in an Extensible User Interface Toolkit", to appear in
Proceedings of the ACM Symposium on User Interface Software and Technology,
November 1997.
[6] W. Keith Edwards, Scott E. Hudson, Joshua Marinacci, Roy Rodenstein, Thomas Rodriguez, and Ian Smith, "Systematic Output Modification in a 2D User Interface Toolkit", to appear in Proceedings of the ACM Symposium on User Interface Software and Technology, November 1997.
[7] Krishna Bharat, "Supporting the Construction of Distributed, Interoperative, User Interface Applications", Ph.D. Dissertation, Georgia Institute of Technology, June 1996.
[8] Scott E. Hudson and Ian Smith, "SubArctic: a Java-based User
Interface Toolkit" (Software), distributed free from: http://www.cc.gatech.edu/gvu/ui/sub_arctic/.
The term constraint system actually covers quite a range of specific computational techniques (only some of which are used here). However, each of these techniques share the common thread that they are declarative in nature. At the highest level, each works by having the programmer (or in our case the user interface implementor) declare a set of conditions -- often relationships between objects -- that are to hold true. The constraint system is then responsible for finding an assignment of values that satisfies the constraints. As a result, these systems can provide a general mechanism for relating or connecting data values and data structures that can be employed in a number of ways to support a number of different application areas.
Constraint systems have been used successfully in interactive systems beginning with some of the earliest work in graphical interfaces [9]. They allow very high level descriptions of behavior that turn out to be well suited to tasks of particular importance to user interface implementation. As a result, constraint systems have been employed in a number of user interface implementation tasks. These include, for example, general control of user interface presentations [10,11], making connections between data objects and interactive views of those objects [12,13], supporting construction of graphical documents and drawing editors [14,15], controlling animation [16,17], computer supported cooperative work [13,18], and the creation of generalized composable interaction techniques [19].
In the area of user interface implementation, propagation-based constraint satisfaction techniques have been the most widely used (and this project focuses on those techniques). These techniques normally assume an initially solved system of equality constraints to which changes have been made, then seek to propagate changes around the system in order to reestablish all constraints. (This can be contrasted with logic programming approaches such as [20] and numerical techniques such as [21]). Among propagation-based techniques used to support user interfaces, two general types have been employed, so called one-way and multi-way constraint systems.
One-way systems have their roots in the attribute grammars and incremental
attribute evaluation systems first used for language specific editors. It
is also useful to consider that one-way constraints provide the same computational
mechanism as spreadsheets. As their name implies one-way systems allow information
to flow in only one direction for each constraint. They accept rules of
the form: A = f(B,C). Multi-way constraint systems on the other hand allow
a more general form of constraint where information may flow in different
directions at different times. Part of the work proposed here will be to
thoroughly explore the tradeoffs involved between the simplicity of one-way,
and power of multi-way constraint systems.
[9] Sutherland, I.E., "SKETCHPAD: A Man-Machine Graphical Communications System", Proceedings of the Spring Joint Computer Conference, 1963.
[10] Vander Zanden, B. and Myers, B.A., "Automatic, Look-and-Feel Independent Dialog Creation for Graphical User Interfaces", Proceedings of SIGCHI '90, April 1990, pp. 325-330.
[11] Hudson, S. E. and Mohamed, S. P., "Interactive Specification of Flexible User Interface Displays", ACM Transactions on Information Systems, v8, n3, July 1990, pp. 269-288.
[12] Hudson, S.E., and King, R., "Semantic Feedback in the Higgens UIMS", IEEE Transactions on Software Engineering, v14, n8, August 1988, pp. 1188-1206.
[13] Hill, R.D., "The Abstraction-Link-View Paradigm: Using Constraints to Connect User Interfaces to Applications", Proceedings of SIGCHI '92, April 1992, pp. 335-342.
[14] Nelson, G., "Juno a Constraint-Based Graphics System", Proceedings of SIGGRAPH '85, July 1985, pp. 235-243.
[15] Freeman-Benson, B.N., "Converting an Existing User Interface to Use Constraints", Proceedings of the ACM Symposium on User Interface Software and Technology, Nov. 1993, pp. 207-215.
[16] Borning, A., and Duisberg, R., "Constraint-Based Tools for Building User Interfaces", ACM Transactions on Graphics, v5, n3, Oct. 1986, pp. 345-374.
[17] Gleicher, M. and Witkin, A. "Through-the-lens Camera Control", Proceedings of SIGGRAPH '92, July 1992, pp. 331-340.
[18] Hill, R.D., "The Rendezvous Constraint Maintenance System", Proceedings of the ACM Symposium on User Interface Software and Technology, Nov. 1993, pp. 225-234.
[19] Myers, B.A., "A New Model for Handling Input", ACM Transactions on Information Systems, v8, n3, July 1990, pp. 289-320.
[20] Jaffar, J., Michaylov, S., Stuckey, P.J., Yap, R.H.C, "The CLP(R) Language and System", Proceedings of the Fourth ICLP, 1987.
[21] Gleicher, M., "Integrating Constraints and Direct Manipulation",
Proceedings of the 1992 Symposium on Interactive 3D Graphics, March 1992,
pp. 171-174.
Models and Abstractions for Next-Generation User Interface Software, Robert J.K. Jacob
Alice: Easy to Learn Interactive 3DGraphics, Randy Pausch
Metis: An Object-Oriented 3D Interaction Toolkit for Virtual Environment Research, Russell Turner
Flexible Shared Windows, Prasun Dewan and Kevin Jeffay
UI Toolkit Architectures for Distributed Multimedia Applications, Joseph A. Konstan