Abstract
Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that one window be to the left of another, requiring that a pane occupy the leftmost of a window, or preferring that an object be contained within a rectangle if possible. For interactive use, we need to solve similar constraint satisfaction problems repeatedly for each screen refresh, with each successive problem differing from the previous one only in the position of an input device and the previous state of the system. We present an algorithm for solving such systems of constraints using projection. The solution is compiled into very efficient, constraint-free code, which is parameterized by the new inputs. Producing straight-line, constraint-free code of this sort is important in a number of applications: for example, to provide predictable performance in real-time systems, to allow companies to ship products without including a runtime constraint solver, to compile Java applets that can be downloaded and run remotely (again without having to include a runtime solver), or for applications where runtime efficiency is particularly important. Even for less time-critical user interface applications, the smooth performance of the resulting code is more pleasing than that of code produced using other current techniques.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Borning. The programming language aspects of ThingLab, a constraint-oriented simulation laboratory. ACM TOPLAS, 3(4):353–387, 1981.
A. Borning, R. Anderson, and B. Freeman-Benson. Indigo: A local propagation algorithm for inequality constraints. In Procs. ACM Symp. on User Interface Software and Technology, 129–136, Seattle, 1996.
A. Borning and B. Freeman-Benson. The OTI constraint solver: A constraint library for constructing interactive graphical user interfaces. In Procs. of CP95, 624–628, Cassis, France, 1995.
A. Borning, B. Freeman-Benson, and M. Wilson. Constraint hierarchies. Lisp and Symbolic Computation, 5(3):223–270, 1992.
A. Borning, R. Lin, and K. Marriott. Constraints for the web. In Proceedings of ACM MULTIMEDIA'97, November 1997. To appear.
A. Borning, K. Marriott, P. Stuckey, and Y. Xiao. Solving linear arithmetic constraints for user interface applications. In Proceedings of the 1997 ACM Conference on User Interface Software and Technology, October 1997. To appear.
W. Harvey, P. Stuckey, and A. Borning. Compiling constraint solving using projection. TR 97/6, Dept. of Computer Science, University of Melbourne, 1997.
R. Helm, T. Huynh, C. Lassez, and K. Marriott. A linear constraint technology for interactive graphic systems. In Graphics Interface '92, 301–309, 1992.
H. Hosobe, S. Matsuoka, and A. Yonezawa. Generalized local propagation: A framework for solving constraint hierarchies. In Procs. of the CP96, Boston, 1996.
S. E. Hudson and I. Smith. SubArctic UI toolkit user's manual. Tech. report, College of Computing, Georgia Institute of Technology, 1996.
B. A. Myers. The Amulet user interface development environment. In CHI'96 Conference Companion: Human Factors in Computing Systems, Vancouver, B.C., April 1996. ACM SIGCHI.
C.G. Nelson. An nlog n algorithm for the two-variable-per-constraint linear programming satisfiability problem. Report STAN-CS-78-689, Stanford, 1978.
M. Sannella, J. Maloney, B. Freeman-Benson, and A. Borning. Multi-way versus one-way constraints in user interfaces: Experience with the DeltaBlue algorithm. Software-Practice and Experience, 23(5):529–566, 1993.
Z. Somogyi, F. Henderson, and T. Conway. Mercury: an efficient purely declarative logic programming language. In Procs. of the ACSC95, 499–512, Glenelg, Australia, 1995.
I. Sutherland. Sketchpad: A man-machine graphical communication system. In Proceedings of the Spring Joint Computer Conference, 329–346. IFIPS, 1963.
B. Vander Zanden. An incremental algorithm for satisfying hierarchies of multi-way dataflow constraints. ACM TOPLAS, 18(1):30–72, 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Harvey, W., Stuckey, P.J., Borning, A. (1997). Compiling constraint solving using projection. In: Smolka, G. (eds) Principles and Practice of Constraint Programming-CP97. CP 1997. Lecture Notes in Computer Science, vol 1330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017462
Download citation
DOI: https://doi.org/10.1007/BFb0017462
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63753-0
Online ISBN: 978-3-540-69642-1
eBook Packages: Springer Book Archive