Integrating pointer variables into one-way constraint models

ABSTRACT

Pointer variables have long been considered useful for constructing and manipulating data structures in traditional programming languages. This article discusses how pointer variables can be integrated into one-way constraint models and indicates how these constraints can be usefully employed in user interfaces. Pointer variables allow constraints to model a wide array of dynamic application behavior, simplify the implementation of structured objects and demonstrational systems, and improve the storage and efficiency of constraint-based applications. This article presents two incremental algorithms—one lazy and one eager— for solving constraints with pointer variables. Both algorithms are capable of handling (1) arbitrary systems of one-way constraints, including constraints that involve cycles, and (2) editing models that allow multiple changes between calls to the constraint solver. These algorithms are fault tolerant in that they can handle and recover gracefully from formulas that crash due to programmer error. Constraints that use pointer variables have been implemented in a comprehensive user interface toolkit, Garnet, and our experience with applications written in Garnet have proven the usefulness of pointer variable constraints. Many large-scale applications have been implemented using these constraints.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: ALDUSS. 1990. Alduss Intellidraw. Alduss Corp., 1990.
• 3: Paul S. Barth, An object-oriented approach to graphical interfaces, ACM Transactions on Graphics (TOG), v.5 n.2, p.142-172, April 1986 [doi>10.1145/22949.22951]
• 4: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 5: Alan Borning , Robert Duisberg, Constraint-based tools for building user interfaces, ACM Transactions on Graphics (TOG), v.5 n.4, p.345-374, Oct. 1986 [doi>10.1145/27623.29354]
• 6: Alan Borning , Robert Duisberg , Bjorn Freeman-Benson , Axel Kramer , Michael Woolf, Constraint hierarchies, Conference proceedings on Object-oriented programming systems, languages and applications, p.48-60, October 04-08, 1987, Orlando, Florida, United States
• 7: Jacques Cohen, Constraint logic programming languages, Communications of the ACM, v.33 n.7, p.52-68, July 1990 [doi>10.1145/79204.79209]
• 8: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 9: Bjorn N. Freeman-Benson, Kaleidoscope: mixing objects, constraints, and imperative programming, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.77-88, September 1990, Ottawa, Canada
• 10: B. N. Freeman-Benson, A module mechanism for constraints in Smalltalk, ACM SIGPLAN Notices, v.24 n.10, p.389-396, Oct. 1989
• 11: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• 12: GOSLING, J. 1983. Algebraic constraints. Tech. Rep. CMU-CS-83-132, Computer Science Dep., Carnegie Mellon Univ., Pittsburgh, Pa.
• 13: Tyson R. Henry , Scott E. Hudson, Using active data in a UIMS, Proceedings of the 1st annual ACM SIGGRAPH symposium on User Interface Software, p.167-178, October 17-19, 1988, Alberta, Canada [doi>10.1145/62402.62429]
• 14: Ralph D. Hill, The Rendezvous constraint maintenance system, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.225-234, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168665]
• 15: Ralph D. Hill, Languages for the construction of multi-user multi-media synchronous (MUMMS) applications, Languages for developing user interfaces, A. K. Peters, Ltd., Natick, MA, 1992
• 16: Roger Hoover, Alphonse: incremental computation as a programming abstraction, ACM SIGPLAN Notices, v.27 n.7, p.261-272, July 1992
• 17: R. Hoover, Incremental graph evaluation (attribute grammar), Cornell University, Ithaca, NY, 1987
• 18: Bruce Horn, Properties of user interface systems and the Siri programming language, Languages for developing user interfaces, A. K. Peters, Ltd., Natick, MA, 1992
• 19: Bruce Horn, Constraint patterns as a basis for object oriented programming, ACM SIGPLAN Notices, v.27 n.10, p.218-233, Oct. 1992
• 20: HUDSON, S. E. 1993. A system for efficient and flexible one-way constraint evaluation in C + +. Tech. Rep. 93-15, Graphics Visualization and Usability Center, College of Computing, Georgia Inst. of Technology, Atlanta, Ga.
• 21: Scott E. Hudson, Incremental attribute evaluation: a flexible algorithm for lazy update, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.3, p.315-341, July 1991 [doi>10.1145/117009.117012]
• 22: HUDSON, S.E. 1990. An enhanced spreadsheet model for user interface specification. Tech. Rep. TR90-33, The Univ. of Arizona, Tucson, Ariz.
• 23: S. E. Hudson, Graphical specification of flexible user interface displays, Proceedings of the 2nd annual ACM SIGGRAPH symposium on User interface software and technology, p.105-114, November 13-15, 1989, Williamsburg, Virginia, United States [doi>10.1145/73660.73673]
• 24: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 25: Joxan Jaffar , Spiro Michaylov , Peter J. Stuckey , Roland H. C. Yap, The CLP( R ) language and system, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.3, p.339-395, July 1992 [doi>10.1145/129393.129398]
• 26: Tomihisa Kamada , Satoru Kawai, A general framework for visualizing abstract objects and relations, ACM Transactions on Graphics (TOG), v.10 n.1, p.1-39, Jan. 1991 [doi>10.1145/99902.99903]
• 27: LELF, a, W. 1900. Coa~traint Programming Languages: Their Specification and Generation. Addison-Wesley, Reading, Mass.
• 28: LI, J. 1991. Constraint hierarchies as triangular systems. Tech. Rep. TRITA-NA-P9130, Dept. of Numerical Analysis and Computing Science, Royal Inst. of Technology, Stockholm, Sweden.
• 29: J. Moloney , A. Borning , B. Freeman-Benson, Constraint technology for user-interface construction in ThingLab II, ACM SIGPLAN Notices, v.24 n.10, p.381-388, Oct. 1989
• 30: David L. Maulsby , Ian H. Witten , Kenneth A. Kittlitz, Metamouse: specifying graphical procedures by example, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.127-136, July 1989
• 31: Brad A. Myers, Demonstrational Interfaces: A Step Beyond Direct Manipulation, Computer, v.25 n.8, p.61-73, August 1992 [doi>10.1109/2.153286]
• 32: Brad A. Myers, Graphical techniques in a spreadsheet for specifying user interfaces, Proceedings of the SIGCHI conference on Human factors in computing systems: Reaching through technology, p.243-249, April 27-May 02, 1991, New Orleans, Louisiana, United States [doi>10.1145/108844.108903]
• 33: Brad A. Myers, Creating user interfaces by demonstration, Academic Press Professional, Inc., San Diego, CA, 1988
• 34: Brad A. Myers , Dario A. Giuse , Roger B. Dannenberg , David S. Kosbie , Edward Pervin , Andrew Mickish , Brad Vander Zanden , Philippe Marchal, Garnet: Comprehensive Support for Graphical, Highly Interactive User Interfaces, Computer, v.23 n.11, p.71-85, November 1990 [doi>10.1109/2.60882]
• 35: Brad A. Myers , Brad Vander Zanden, Environment for rapidly creating interactive design tools, The Visual Computer: International Journal of Computer Graphics, v.8 n.2, p.94-116, Feb. 1992 [doi>10.1007/BF01900551]
• 36: Brad A. Myers , Dario A. Giuse , Andrew Mickish , David S. Kosbie, Making Structured Graphics and Constraints Practical for Large-Scale Applications, Carnegie Mellon University, Pittsburgh, PA, 1994
• 37: Brad A. Myers , Dario A. Giuse , Brad Vander Zanden, Declarative programming in a prototype-instance system: object-oriented programming without writing methods, ACM SIGPLAN Notices, v.27 n.10, p.184-200, Oct. 1992
• 38: B. A. Myers , B. V. Zanden , R. B. Dannenberg, Creating graphical interactive application objects by demonstration, Proceedings of the 2nd annual ACM SIGGRAPH symposium on User interface software and technology, p.95-104, November 13-15, 1989, Williamsburg, Virginia, United States [doi>10.1145/73660.73672]
• 39: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 40: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 41: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator reference manual (3rd ed.), Springer-Verlag New York, Inc., New York, NY, 1989
• 42: SANNELLA, M, 1992. The SkyBlue constraint solver. Tech. Rep. 92-07-02, Computer Science Dept., Univ. of Washington, Seattle, Wash.
• 43: SANNELLA, M. AND BORNING, A. 1992. Multi-Garnet: Integrating multi-way constraints with Garnet. Tech. Rep. 92-07-01, Dept. of Computer Science and Engineering, Univ. of Washington, Seattle, Wash.
• 44: Vijay Anand Saraswat , Dana S. Scott, Concurrent constraint programming languages, 1989
• 45: SLEATOR, D. D., AND DIETZ, P.F. 1988. Two algorithms for maintaining order in a list. Tech. Rep. CMU-CS-88-113, Carneige Mellon Univ., Pittsburgh, Pa.
• 46: STEELE, G. L., JR. 1980. The definition and implementation of a computer programming language based on constraints. Ph.D. thesis, Dep. of Computer Science, MIT, Boston, Mass.
• 47: SUTHERLAND, I. E. 1963. Sketchpad: A man-machine graphical communication system. In AFIPS Spring Joint Computer Conference. AFIPS, Washington, D.C., 329-346.
• 48: Pedro Szekely , Brad Myers, A user interface toolkit based on graphical objects and constraints, ACM SIGPLAN Notices, v.23 n.11, p.36-45, Nov. 1988
• 49: Christopher J. van Wyk, A High-Level Language for Specifying Pictures, ACM Transactions on Graphics (TOG), v.1 n.2, p.163-182, April 1982 [doi>10.1145/357299.357303]
• 50: Bradley T. V Zanden, A Domain-Independent Algorithm for Incrementally Satisfying Multi-Way Constraints, University of Tennessee, Knoxville, TN, 1992
• 51: B. T. Zanden, Constraint grammars–a new model for specifying graphical applications, Proceedings of the SIGCHI conference on Human factors in computing systems: Wings for the mind, p.325-330, March 1989
• 52: Bradley T. Vander Zanden, Incremental constraint satisfaction and its application to graphical interfaces, 1989
• 53: Michael R. Wilk, Equate: an object-oriented constraint solver, ACM SIGPLAN Notices, v.26 n.11, p.286-298, Nov. 1991
• 54: Andrew Witkin , William Welch, Fast animation and control of nonrigid structures, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.243-252, September 1990, Dallas, TX, USA [doi>10.1145/97879.565650]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Nonalgebraic algorithms

General Terms:
Algorithms, Design, Languages

Keywords:
Garnet, constraints, development tools, incremental algorithms