################################################ # # # ## ## ###### ####### ## ## ## ## ## # # ## ## ## ## ## ### ## ## ## ## # # ## ## ## ## #### ## ## ## ## # # ## ## ###### ###### ## ## ## ## ### # # ## ## ## ## ## #### ## ## ## # # ## ## ## ## ## ## ### ## ## ## # # ####### ###### ####### ## ## ## ## ## # # # ################################################ The following paper was originally presented at the Third Annual Tcl/Tk Workshop Toronto, Ontario, Canada, July 1995 sponsored by Unisys, Inc. and USENIX Association It was published by USENIX Association in the 1995 Tcl/Tk Workshop Proceedings. For more information about USENIX Association contact: 1. Phone: 510 528-8649 2. FAX: 510 548-5738 3. Email: office@usenix.org 4. WWW URL: https://www.usenix.org ^L TclProp: A Data-Propagation Formula Manager for Tcl and Tk* Sunanda Iyengar Joseph A. Konstan Department of Computer Science University of Minnesota Minneapolis, MN 55455 {iyengar, konstan}@cs.umn.edu Abstract TclProp is a data propagation formula manager for Tcl and Tk. It supports and enforces one-way declarative relationships among variables. If, for example, we enter the formula A = B + C, whenever B or C changes, A is also updated to reflect the new sum. TclProp also supports triggers -- code to be executed when one of a set of variables changes. And, TclProp includes a mechanism for linking variables to object attributes (e.g., the enabled/disabled status of a button) so these attributes can be used in formulas and triggers. This paper presents an example of how data propagation formulas can simplify programming and presents the design and implementation of TclProp 1.0, an implementation built in Tcl. Introduction Data-propagation formulas allow programmers to declaratively specify relationships among program variables (or object attributes) by defining a variable (or attribute) to be a function of other variables and attributes. Whenever a variable or attribute changes, the system automatically re-evaluates the appropriate functions to update dependent values. This style of declarative programming has proven to be extremely useful in Lisp-based systems such as Garnet [1] and Picasso [2], but has generally not existed in C-based systems. This paper presents the design and implementation of TclProp, a data-propagation formula manager for Tcl and Tk [3]. The popularity of Tcl and Tk has grown tremendously since their introduction, in a large part because of the ease with which applications can be constructed using Tcl scripts and Tk widgets. Tk directly provides all of the features needed to implement many application interfaces through its widgets, geometry managers, event binding mechanism, and event handling loop. Many Tk widgets also allow Tcl variables to link to particular widget attributes (e.g., the text of an entry or the pressed state of a check box) to better support interactive programs that manipulate data values and display them to the user for editing. Tcl and Tk do not, however, provide direct support for declarative relationships among variables and object attributes. And, Tk widgets do not allow all of there attributes to be linked to variables for user programming. These two failures are addressed by TclProp. TclProp introduces three new Tcl commands: TclProp_formula, TclProp_trigger, and TclProp_make_var. These commands establish relationships among variables, between variables and code, and between variables and object attributes, respectively. In version 1.0 of TclProp, the commands are all implemented directly in Tcl, and therefore can be loaded into any compiled tclsh or wish. We are currently investigating C-based implementations, both as extensions and as changes to the Tcl core, to examine their performance ramifications. The rest of this paper is organized as follows. The next section discusses the history of and need for declarative data-propagation and introduces an example application to show how formulas can simplify interface implementation. The following section presents the TclProp commands and discusses their use and implementation. The remaining sections discuss our experiences with TclProp 1.0, including performance results, and present our plans for future work in this area. Background and Motivation There has been a long history of constraint-based programming starting with Sutherland's Sketchpad in the early 1960's [4] and stretching through Thinglab and Thinglab II [5, 6] and later systems with more advanced constraint models [7]. These systems define a network of constraints, i.e., relationships among values, that would be solved to find a set of values that satisfied the constraints. If no such set of values exists, the constraint solver attempts to produce the best possible solution by violating the fewest (or least important) constraints. Constraint programming is a very powerful model for a range of problems. A simpler subset of constraint programming, however, is powerful enough for a range of interface problems and is much easier to implement efficiently. This subset consists of one-way data propagation, i.e., a set of formulas that define one value in terms of other values. To illustrate data propagation, consider the rule: A = B + C With one-way data propagation, this rule states that any change in B or C should result in A being re-assigned the new sum. But, a change to A does not result in any change in B or C (so the rule does not enforce that A is always the sum of B and C). Multi-way data propagation can be achieved by including multiple rules. Inequality relationships are not supported. This simpler model of constraints as data propagation has been very successful in the Garnet and Picasso systems. Garnet, in particular, places data propagation data propagation at the very heart of its object system and makes liberal use of these constraints both internally and at the application program level. Picasso added data propagation during the middle of its development, and uses it mostly in high-level framework objects and at the application level. It is this model that we hope to emulate with TclProp. Video Poker Consider the example of a video poker application. While the application is visually simple, there is a great deal of complexity in the details of the buttons and display fields. Consider the sequence of images below: The active status of each button changes based on the state of the game. For example, the bet buttons are only active when betting is appropriate. Some of the buttons even change their labels as the game progresses. The buttons below each card change among blank (between hands), "HOLD" (when active), and "held" (when inactive). Knowing the right interface isn't hard -- this application basically copies common features of casino games. Implementing that interface with procedural callbacks is hard, though. Consider one of the more simple examples -- the code associated with the "BET ONE" button. If written in a procedural callback, the "BET ONE" button's command must do the following: * check whether the game was displaying a payout and, if so, reshuffle the deck, display the backs of cards, clear the payoff window, and enable the deal button. * decrement the bankroll. * increment the amount bet. * check whether the bankroll is zero and, if so, dis- able the betting buttons. * check whether the bet is now the maximum bet and, if so, deal (which involves disabling the bet buttons, dealing five cards, enabling the five hold buttons and setting their text string to "HOLD", disabling the deal button, enabling the stand and draw but- tons, and updating the appropriate internal data structures). Parts of this can be factored out into procedures (such as deal), but the main message is that each button adds tremendous complexity. Consider adding a "bet same as last time" button. We would need to decide which code to copy from the other buttons, and we would have to find all places where the bet buttons are enabled or disabled to make sure this new button was handled. And it isn't as simple as handling all bet buttons the same way, since the "bet same as last time" button would need to be disabled when the bankroll is smaller than the last bet. Data propagation formulas greatly simplify the implementation by allowing us to declaratively state the relationships among program values. We can see that the game really has three modes: bet, play, and payout. By making the mode a variable, we can define relationships more easily. For example, the enabled status of the "BET ONE" button can be expressed as: the "BET ONE" button is enabled when the mode is bet or payout and the bankroll is greater than 0. Its action is simply: decrement the bankroll and increment the bet. Similarly, the deal button is available when the mode is bet and the bet is greater than 0. The text of the rightmost hold button is blank if the game mode is not draw, held if the fifth card is held (a reference to an array entry), and HOLD otherwise. The one remaining complexity is that there are still certain active parts of the program that do not neatly decompose into formulas. These can be accommodated through the use of a trigger construct that executes arbitrary code when a value changes. For example, when the bet changes, check whether the mode was pay and this bet increases above zero, if so change the mode to bet. Also, check whether the bet is the maximum bet and, if so, set the mode to draw. This trigger and one more for mode changes (which handle dealing cards and calculating payouts) complete the application interface. In summary, the use of data propagation greatly simplifies building the interface. And, by distributing application code to the affected objects, it also simplifies changing the interface. The next section describes the TclProp commands that support this style of programming. TclProp 1.0: Commands and Implementation TclProp 1.0 has three data propagation commands:* TclProp_formula TclProp_trigger TclProp_make-var [-read ] [-write ] [-rf ] TclProp_formula defines a formula such that whenever a listed source variable changes, the destination variable is set to the result of the formula code. For example, to implement the rule A = B + C, one would write: TclProp_formula A {B C} {expr $B + $C} Similarly, for the video poker example, the text string of the fifth button, which could be linked through the - textvariable option to the variable b5text, could be declared as: TclProp_formula b5text {mode holds(5)}\ {if [string compare $mode draw]\ {quote ""} elseif\ $holds(5) {quote held} {quote HOLD}} One should read this as: b5text depends on the mode and the 5th element of holds. Its value is the empty string when the mode is not draw, and when the mode is draw its value is held when holds(5) is true, HOLD otherwise. The quote function simply returns the argument passed to it -- it is Lisp syntax we introduced as a way to clearly express avoiding evaluation. TclProp_trigger defines a trigger on a variable or set of variables. When the variable or variables change, the code is executed. For example, to print out "Hello" whenever the variable A changes, one would write: TclProp_trigger A {puts Hello} Triggers with multiple variables should have a list of variables included rather than a single variable. TclProp_make_var creates a new global variable and links it to code. It is generally used to link a variable to an object attribute that doesn't already have an automatic linkage. The reason these variables are necessary lies in the implementation of formulas and triggers. Tcl has a trace facility that can call a specified routine when a variable is updated (or read), but does not have a similar facility for arbitrary object attributes. Accordingly, we needed to add a mechanism to link arbitrary attributes to a variable. For example, to create the variable b5able that will have a 1 value when .button5 is enabled, and a 0 value when it is disabled, and will propagate changes to the button, one would write: TclProp_make_var b5able \ -read {string compare \ [lindex [.button5 configure \ -state] 4]\ disabled} \ -write {if $b5able \ {configure .button5 -state \ normal}\ {configure .button5 -state \ disabled}} \ -rf 1000 This code creates a new global variable, establishes a link that will update the button's state whenever the variable is changed, and established polling every 1000 milliseconds to check the button state and update the variable. The variable b5able can now be used in any formula or trigger. In this application, the read part is unnecessary (since the button states are not changed except through formulas) and would be omitted to avoid the polling overhead. Implementation The implementation of TclProp is based heavily on the use of the Tcl trace command and tables. The main table for formulas has three columns: the dependent variable, the dependee variable, and the formula code to execute. When a formula is entered, a new record is created for each dependee. For example, if there are two formulas: TclProp_formula A {B C D} {expr $B +\ $C + $D} TclProp_formula D B {quote $B} then the table would look as follows: Dependent Dependee Formula Code A B {expr $B + $C + $D} A C {expr $B + $C + $D} A D {expr $B + $C + $D} D B {quote $B} In addition, each dependee variable is given a write- trace procedure (only once per variable) that checks whether there is a real change and whether this is a loop and if not: looks up the variable in the table, collects all of the entries, and assigns to each dependent the result of evaluating the formula code. Triggers are implemented in the same table by leaving out the dependent variable. The action specified is to execute the code without assigning the result anywhere. The write actions for TclProp_make_var are implemented as triggers, and the read actions are implemented separately using after. The after command sets the variable to the result of evaluating the code and then places itself on the after queue with the delay specified by the user. There is one critical implementation issue that affects the expressiveness of the system: how loops are handled. There are several common ways of handling loops in one-ay data propagation systems. Most systems prevent evaluation of a formula when the variable, though written to, doesn't actually change value. This will allow many loops to reach a steady state, though it can lead to infinite loops when dealing with oscillating relationships or floating-point numbers. For this reason, many systems also detect loops and prevent them from iterating more than a fixed number of times. TclProp 1.0 prevents evaluation when a variable has not actually changed and also limits looping to one iteration by forbidding any dependee to consult the table more than once in a "loop." This is implemented by keeping a list of dependees that have consulted the table and a global variable that is set to true when the first formula or trigger is activated and then cleared (along with the list) when that same activation exits. Experiences and Performance Results Our initial experiences with TclProp 1.0 have been very pleasing. Discussions with others who have used data propagation systems have shown excitement at the prospect of having the same technique available in Tcl. More important, Tcl programmers who had never used data propagation or constraints have been able to make productive use of TclProp fairly quickly. And, several programmers have indicated that TclProp is just the tool they needed, though they didn't know it at the time. Initial performance results are promising, though not exciting. The overhead for a formula with minimal code is approximately 3 milliseconds. We know that we can probably hand-optimize this to between 1.5 and 2 ms, but that more dramatic changes will require moving parts of the implementation into C. Nonetheless, even at 3 ms, the performance is good enough for most applications that we have seen, though not nearly good enough to implement formula-based geometry management, for example. We have not seen a major impact on performance through the use of TclProp_make_var, but we have only used a small number of variables at any time. We do not believe that the "synthetic variable" solution is viable for heavy use if object attributes are to serve as triggers and formula sources, but it does fill a gap in the meantime. The next section discusses some of our plans that would impact performance in both areas. Evaluation Quoting In developing and using TclProp 1.0, we encountered one area where the system was hard to use. When doing translations (e.g., between a boolean value and a pair of strings) we found it awkward to use the Tcl if, because if expects statements that are evaluated. A typical case is the button text for the hold buttons. The formula used is: TclProp_formula b5text {mode holds(5)} \ {if [string compare $mode draw] \ {quote ""} \ elseif $holds(5) \ {quote held} \ {quote HOLD}} Which required us to create a procedure quote that returned its argument. We expect that this is not an uncommon concern, despite the alternative of using the conditional expression in Tcl.* While Tcl has extensive quoting support at the parser level, it does not have the same support at the execution level. We think that something similar to quote should be standardized. This should also have the benefit of easing the transition to Tcl for Lisp programmers. Plans for Future Work While we are pleased with TclProp 1.0, and hope that many people are able to use it, there are several improvements that we consider important enough to start working towards now. First, we need to better explore other techniques for including object attributes as first-class entities in formulas. The current mechanism is awkward and can be improved syntactically (perhaps with a syntax to represent an object attribute in the formula and trigger commands and a table of implementations for read and write). More important, though, will be a more in-depth implementation. We are looking at expanding the trace facility to handle configurations of Tk widgets, and we expect that the long-term solution involves increasing the number of traceable actions and standardizing on an object model that will be used to represent Tk widgets as objects. To this end, we are also implementing formulas involving slots of Tcl-DP shared objects [8]. We are also actively monitoring the progress of object extensions to Tcl to determine whether they warrant and can support an implementation of TclProp. Second, we are investigating the performance benefits of moving the main implementation to C. We expect that we can achieve at least a fourfold improvement and will have to balance the improved performance against the inconvenience of needing a special interpreter. In the future, we hope either to include TclProp in the core of Tcl, or to have dynamic loading of a TclProp extension. When dealing with non-variables (i.e., trace extensions), we will have to determine whether dynamic loading is able to replace existing C code. Finally, we plan to explore adding more advanced constraint-handling techniques to TclProp. The simple model implemented here can be extended in many ways including support for indirect constraints through pointer variables [9], support for locking variables, and support for multi-way inequality constraints. We do not expect all of these to apply to Tcl variables in general (particularly global variables), but they may apply to objects constructed in Tcl. TclProp 1.0 is available for public use. Interested users may find the TclProp source code, the video poker application, and documentation on our World-Wide- Web site: "https://www.cs.umn.edu/research/GIMME/". References 1. B. A. Myers, et.al., "Comprehensive Support for Graphical, Highly-Interactive User Interfaces: The Garnet User Interface Development Environ- ment," IEEE Computer, November 1990. 2. L.A. Rowe, et. al. "The Picasso Application Frame- work," Proceedings of ACM SIGGRAPH Sympo- sium on User Interface Software and Technology, Hilton Head, SC, November 1991. 3. J.K. Ousterhout. Tcl and the Tk Toolkit. Addison- Wesley, Reading, MA, 1994. 4. I. E. Sutherland. "Sketchpad: a Man-Machine Graphical Communication System", AFIPS Sum- mer Joint Computer Conference, 1963. 5. A. H. Boring and R. Duisberg. "Constraint-Based Tools for Building User Interfaces," ACM Transac- tions on Graphics, October 1986. 6. J. Maloney, et.al. "Constraint technology for user interface construction in Thinglab II," Proceedings of the 1989 ACM Conference on Object Oriented Programming systems, Languages, and Applica- tions, New Orleans, October 1989. 7. M. Sannella. "Sky Blue: A Multi-Way Local Propa- gation Constraint Solver for User Interface Con- struction" Proceedings ACM SIGGRAPH Symposium on User Interface Software and Tech- nology, November 1994. 8. B. C. Smith, et.al. "Tcl Distributed Programming," Proc. of the 1993 Tcl/TK Workshop, Berkeley, CA, June 1993. 9. B. Vander Zanden, et.al. "The importance of Pointer Variables in Constraint Models," Proceed- ings of ACM SIGGRAPH Symposium on User Interface Software and Technology, Hilton Head, SC, November 1991.