Lessons learned about one-way, dataflow constraints in the Garnet and Amulet graphical toolkits

ABSTRACT

One-way, dataflow constraints are commonly used in graphical interface toolkits, programming environments, and circuit applications. Previous papers on dataflow constraints have focused on the design and implementation of individual algorithms. In contrast, this article focuses on the lessons we have learned from a decade of implementing competing algorithms in the Garnet and Amulet graphical interface toolkits. These lessons reveal the design and implementation tradeoffs for different one-way, constraint satisfaction algorithms. The most important lessons we have learned are that (1) mark-sweep algorithms are more efficient than topological ordering algorithms; (2) lazy and eager evaluators deliver roughly comparable performance for most applications; and (3) constraint satisfaction algorithms have more than adequate speed, except that the storage required by these algorithms can be problematic.

REFERENCES

• 1: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• 2: 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]
• 3: 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]
• 4: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 5: Richard L. Halterman , Bradley T. V Zanden, Using Model Dataflow Graphs to Reduce the Storage Requirements ofConstraints, University of Tennessee, Knoxville, TN, 1998
• 6: 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]
• 7: 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]
• 8: Ralph D. Hill , Tom Brinck , Steven L. Rohall , John F. Patterson , Wayne Wilner, The Rendezvous architecture and language for constructing multiuser applications, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.81-125, June 1994 [doi>10.1145/180171.180172]
• 9: R. Hoover, Incremental graph evaluation (attribute grammar), Cornell University, Ithaca, NY, 1987
• 10: Roger Hoover, Alphonse: incremental computation as a programming abstraction, ACM SIGPLAN Notices, v.27 n.7, p.261-272, July 1992
• 11: Scott E. Hudson , Roger King, An Semantic Feedback in the Higgens UIMS, IEEE Transactions on Software Engineering, v.14 n.8, p.1188-1206, August 1988 [doi>10.1109/32.7628]
• 12: 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]
• 13: Hudson, S. E. 1993. A system for efficient and flexible one-way constraint evaluation in C++. Tech. Rep. 93-15, Graphics Visualizaton and Usability Center, College of Computing, Georgia Institute of Technology. April.
• 14: Scott E. Hudson, User interface specification using an enhanced spreadsheet model, ACM Transactions on Graphics (TOG), v.13 n.3, p.209-239, July 1994 [doi>10.1145/195784.195787]
• 15: Scott E. Hudson , Ian Smith, Ultra-lightweight constraints, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.147-155, November 06-08, 1996, Seattle, Washington, United States [doi>10.1145/237091.237112]
• 16: Knuth, D. 1968. Semantics of context-free languages. Math. Syst. Theor. 2, 127--145.
• 17: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998 [doi>10.1145/291889.291895]
• 18: Brad A. Myers, Creating user interfaces using programming by example, visual programming, and constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.2, p.143-177, April 1990 [doi>10.1145/78942.78943]
• 19: Brad A. Myers, A new model for handling input, ACM Transactions on Information Systems (TOIS), v.8 n.3, p.289-320, July 1990 [doi>10.1145/98188.98204]
• 20: 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]
• 21: Brad A. Myers , Richard G. McDaniel , Robert C. Miller , Alan S. Ferrency , Andrew Faulring , Bruce D. Kyle , Andrew Mickish , Alex Klimovitski , Patrick Doane, The Amulet Environment: New Models for Effective User Interface Software Development, IEEE Transactions on Software Engineering, v.23 n.6, p.347-365, June 1997 [doi>10.1109/32.601073]
• 22: W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75305]
• 23: T. Reps, Incremental evaluation for attribute grammars with unrestricted movement between tree modifications, Acta Informatica, v.25 n.2, p.155-178, February 1988
• 24: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• 25: 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]
• 26: R. S. Sundaresh, Building incremental programs using partial evaluation, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.83-93, June 17-19, 1991, New Haven, Connecticut, United States
• 27: R. S. Sundaresh , Paul Hudak, A theory of incremental computation and its application, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-13, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99587]
• 28: Sussman, G. and Steele, G. 1980. Constraints--a language for experessing almost-hierarchical descriptions. Artif. Intell. 14, 1--39.
• 29: 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
• 30: Brad Vander Zanden , Brad A. Myers , Dario Giuse , Pedro Szekely, The importance of pointer variables in constraint models, Proceedings of the 4th annual ACM symposium on User interface software and technology, p.155-164, November 11-13, 1991, Hilton Head, South Carolina, United States [doi>10.1145/120782.120799]
• 31: Brad Vander Zanden , Brad A. Myers , Dario A. Giuse , Pedro Szekely, Integrating pointer variables into one-way constraint models, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.161-213, June 1994 [doi>10.1145/180171.180174]
• 32: Bradley T. Vander Zanden , Scott A. Venckus, An empirical study of constraint usage in graphical applications, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.137-146, November 06-08, 1996, Seattle, Washington, United States [doi>10.1145/237091.237111]

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.6 Programming Environments
          Subjects: Graphical environments; Interactive environments
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages
      D.3.3 Language Constructs and Features
          Subjects: Constraints

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

General Terms:
Algorithms, Design, Experimentation, Human Factors, Performance

Keywords:
Constraint experience, constraint satisfaction, constraint usage, eager evaluation, lazy evaluation, one-way dataflow constraints