[Phil's Home: www.piernot.com]
Published in Proceedings of the Conference on Human-Computer Interaction (HCI '95), 1995, pp. 169-179.

A Model for Incremental Construction
of Command Trees

Philippe P. Piernot*

Knowledge Systems Laboratory
Department of Computer Science
Stanford University
701 Welch Road, Building C
Palo Alto, CA 94304

piernot@ksl.stanford.edu

Marc P. Yvon

Laboratoire d'Intelligence Artificielle de Paris 5
UFR de Mathématiques et d'Informatique
Université René Descartes
45, Rue des Saints-Pères
75006 Paris - France

yvon@math-info.univ-paris5.fr

ABSTRACT

Application histories have been used for a variety of purposes including error recovery, browsing past activities, macro recording and demonstrational interfaces. However, in most systems the history is kept as a simple list of primitive commands, which poorly reflects the user task structure. In this paper we first present Command Trees, an alternate representation of command histories that offers a richer representation and provides better support for undo/redo mechanisms and programming by demonstration. We then introduce a new model to support incremental construction of command trees and an object-oriented application framework that implements this model. An important property of this model is that it is independent of the interaction modality, thus extending its purpose.

KEYWORDS: Application histories, command trees, command parser, undo/redo facilities, demonstrational interfaces.

1 INTRODUCTION

When interacting with the computer, users often reuse previous activities either to consult them, to recover from an error or to reduce repetitive tasks [Greenberg 93]. The system usually supports such reuse by recording user commands in a history list. Unfortunately, lists only provide the user and the system with a linear view of the past interaction, which poorly maps the task structure.

In fact, some systems record a sequence of low-level events, such as keystrokes and mouse actions, as is the case in certain macro recorders (Tempo II [Affinity 91], QuicKeys [CE Software 93]) and certain predictive interfaces (Reactive Keyboard [Darragh 92], Predictive Calculator [Witten 81]). However, low-level events convey few semantics, making it difficult for the system to reliably replay them or to extract meaningful information. Low-level events also make it difficult for the user to picture the whole story: for example, the action of selecting the trash on the desktop is easier to replay and to understand when expressed as "Select Trash" rather than as "Mouse Click at (623,383)". Nevertheless, such histories can be implemented easily -- even across applications -- and can prove very effective [Potter 93].

Another approach records high-level commands, like in some undo/redo facilities (Chimera [Kurlander 90], AIDE [Piernot 93], WeMet [Rhyne 92]), macro recorders (AppleScript [Apple 93a and Apple 93b], HP NewWave [Fuller 89]), predictive interfaces (Edward [Bos 92], Eager [Cypher 91], Metamouse [Maulsby 89]) and programming by example systems (SmallStar [Halbert 84], Chimera, Mondrian [Lieberman 93], Pursuit [Modugno 94], Mike [Olsen 88, AIDE). Some systems (Chimera, Mondrian, Pursuit) take advantage of the fact that high-level commands are recorded to display their history using storyboards; they also use rules to group commands together so that one pane can show more than one command.

Observing that no system has attempted to represent application histories in a more structured way than lists, Kosbie [Kosbie 93] introduced the notion of aggregate events -- events made of other events -- leading to a tree-like representation of the history that we call Command Tree. In this model, low-level events (e.g. "Type Character") are grouped together to form abstract events (e.g. "Type Text") which in turn can be merged and can lead to higher-level events (e.g. "Replace Text") etc. Such aggregate events better reflect the task structure than a stream of low-level or high-level events because they correspond to the decomposition of tasks into sub-tasks: events towards the top of the tree are more general and represent high-level tasks, whereas events towards the bottom of the tree are more specific and represent low-level tasks. Moreover they allow the user and the system to choose the granularity at which they want to manipulate the history. As a consequence, command trees provide a good basis for multiple-level undo/redo operations; for demonstrational interfaces (by recording high-level events, pattern matching algorithms are less sensitive to variations in the way the task is performed); for capturing user intent (by still keeping low-level events, the system knows the details of how a high level event was performed: in some cases, the low-level event appropriately represents the user's intent); and for better visualization (by displaying a feedback closer to the user task).

An example of such a command tree for a text editor is given in Figure 1, the bottom of the figure shows miniature screen snapshots representing the effects of performed primitive commands. The task represented here ("Put Bullets") is replacing the first two characters of line one and two by "* ". The top of the tree is the root command, one of its children is "Edit Text" and consists of two "Replace Text" commands.

Now that one approach to represent histories has been proposed (i.e. aggregate events), we raise in this paper a new problem : how to incrementally build command trees from the user's commands? This issue is important because each time a new command is carried out, histories should be updated accordingly and for the sake of efficiency they should not be totally rebuilt. To solve this problem, we introduce a new model where a command has a prototypical parent which represents its natural abstraction; where the history construction is performed by keeping adopting commands; and where the eventual parent ambiguity is solved by creating partial commands.

The remainder of this paper discusses how we implemented this model in an extremely extensible way in AIDE, an application framework assisting developers in integrating undo/redo and programming by demonstration capabilities in Smalltalk-based applications. We first present the AIDE architecture and its main components: an extensible incremental command parser and command trees. We then present the framework from an implementation point of view. As a proof of concept, examples are drawn from a text editor widget which has been developed using AIDE. Finally, we conclude with some future research directions.

 

2 THE AIDE ARCHITECTURE

2.1 Overview

The AIDE architecture (Figure 2) represents application commands as command trees, objects that understand the do and undo messages and that can contain other commands. These commands are recorded in a history -- itself a command tree -- constructed by the command parser. Thus, when interacting with an AIDE-based application, the user generates a stream of low-level events, which the application transforms into a (primitive) command object and sends to the command parser. The latter adds the event to the history.

The architecture supports either a system-wide history (one command manager for all running applications) or application-specific histories (one command manager per application). Details on how the architecture also supports demonstrational techniques are given in [Piernot 93]. Our focus here is to show how the incremental construction of command trees is achieved. To illustrate this architecture and its associated mechanisms, we consider as an example a text editor widget developed using AIDE that keeps a structured history of the user commands and provides multi-level undo/redo facilities. We describe in the next two sections each of the components in more detail.

2.2 The Command Parser

The command parser is in charge of grouping commands together into more general commands. The parser we developed is incremental, i.e. adding a new command to the history does not force the system to parse everything again -- which would be very inefficient -- and assumes that each command has a prototypical parent. Our parser tries to insert an incoming command into the history by asking the latter to adopt the command. If the command pre-defined parent already exists it is adopted; otherwise, since the command knows its natural abstraction, the parser generates the command parent and tries to include it in the history the same way. For some commands, there may be an ambiguity regarding their prototypical parent; in those cases, the identity of the command parent is only known with the arrival of subsequent commands. There are two approaches to solve this problem: the first one is to pick one of the possible parents as a guess and backtrack if wrong, the other one is to leave the uncertainty with a partial command, whose identification will be assigned later. We have chosen the second option so that the command tree only reflects what the user has done so far.

As an example, in Figure 3 we give a step-by-step description of how the text editor widget commands have been added to the history to form the right side of the tree depicted in Figure 1. To add a new command (C) to the history, the parser first looks for the rightmost branch of the history and tries to determine if any command along this branch could adopt C, going upwards. If the parser finds a command willing to adopt C, it performs the adoption. Two cases can occur at that point: if the adoption generates a new command (i.e. a partial command adopted a new child as in Figure 3b), then the old command is removed from the tree and replaced by the new one; otherwise, C is simply added to the command children. As a result, one by one, each of the command's ancestors updates its arguments to reflect the change that affects one of its children (Figure 3c). If C is not adopted, the parser generates its parent and repeats the process with its parent until an adoption occurs (e.g. in Figure 3d "Type Character" could not be adopted by "Delete Text", however its parent, "Type Text" was adopted by "Replace Text").

 

2.3 Command Trees

As mentioned in the architecture overview section 2.1, command trees represent application commands: as in MacApp [Wilson 90], they are objects that understand the do and undo messages, but they can also contain other commands as well.

In Table 1 we illustrate the set of commands we implemented in the text editor widget. The first column represents the command class, the second one gives the grammar governing how the command can adopt a new child and the last one gives the command prototypical parent (parent command class). For example, the "Select Text" command can have as a child the following commands: "Select Insertion Point" or "Select Range" or "Move Cursor", and as a parent "Replace Text". The "Select Text" parent class is "Partial Command". This command is a temporary one, waiting to adopt another command: this is due to the fact that the potential parent for "Select Text" is either "Replace Text" or "Format Text". If "Partial Command" adopts "Type Text", it generates the "Replace Text" command. If it adopts "Set Font" or "Set Color" or "Set Style" or "Set Size" it generates a "Format Text" command. When a new command is generated by the adoption, the old one (i.e. "Partial Command") gets removed from the tree and the new method is added. To define the command grammar the developers has to define the parentClass and canAdopt methods.

Command trees facilitate the work of programming by demonstration engines because inference is less sensitive to variations in the way the task is performed. In the "Put Bullets" task (Figure 1), the user replaces the first two characters of line one and two by invoking different primitive commands, but both ways lead to the same high-level command ("Replace Text").

 

Command

Rule governing children adoption

Parent Command

Select Ins. Point
Select Range
Move Cursor


No children (primitive command)


Select Text

Select Text

(Select Insertion Point | Select Range | Move Cursor)+

Partial Cmd


Partial Command

Select Text. Can adopt a command whose grand parent can be
Edit Text. If so, adoption result is the parent of the newly adopted command (i.e. adoption result is Replace Text or Format Text)


Edit Text

Type Character

No children (primitive command)

Type Text

Type Text

Type Character+

Replace Text

Delete Selection
Delete Prev. Char.
Delete Next Char.


No children (primitive command)


Delete Text

Delete Text

Select Text?, (Delete Selection | Delete Prev. Char.|Delete Next Char.)+

Replace Text

Replace Text

Select Text? , (Type Text | Delete Text)+

Edit Text

Set Font
Set Color
Set Style
Set Size


No children
(primitive command)


Format
Text

Format Text

Select Text? , (Set Font | Set Color | Set Style | Set Size)+

Edit Text

Edit Text

(Partial Command | Replace Text | Format Text)+

Root Cmd

Root Command

Accepts any command whose parent can be Root Command

None

Table 1. Commands used in the AIDE Text Editor Widget (c? means c occurs 0 or 1 time;
c,d implies c then d; c|d implies either c or d; c+ means c occurs at least 1 time).

Command trees offer better support for undo/redo mechanisms by reducing the time it takes to navigate through the history (either by undoing or by redoing commands). Since we have intermediate commands, we do not need to undo/redo all the primitive commands but instead we can undo/redo the intermediate ones. For example to undo the last four commands of the tree in Figure 1, it is enough to undo the "Replace Text" command. We redefined undo and do methods for all the commands except "Edit Text" (these methods use the arguments of the commands) and are faster than asking their children to undo or do themselves.

3 IMPLEMENTATION

3.1 Command Parser Algorithm

First, the parser keeps a pointer to the last executed command. When commands are undone the command tree is not modified, instead the pointer is updated. When a new command appears, the undone commands are removed from the tree before the new command is added (truncate/redo in the Archer, Conway, Schneider script model [Thimbleby 91]). The parser is encapsulated in the class Command -- as a set of methods-- and its entry point is the add method (algorithm outlined in Figure 4). This means that to add a new command to the history, one sends the add message to the root of the tree with the command to add as an argument.

Due to the recursive nature of our algorithm and to the fact that the parser is encapsulated in the command class, an application can extend the parser by overriding the try to adopt method in its own commands. Thus, the default behavior we described in section 2.2 could be modified to fit the special needs of an application in case they would not be fully addressed by the current parser. This point is specially important with a system-wide history (one history for all the running applications), where an application might want to modify the parser behavior for its own commands, without breaking the rest of the system.

 
 
To add aCommand
  While I try to add aCommand and no adoption occurs,
    I ask aCommand to create its parent and put it into aCommand.
  If the adoption generated a new command,
    I remove the old command and add the new one.
To try to add aCommand
  If I am not a leaf, I ask my last child to try to add aCommand.
  If an adoption occurred,
    If it did not generate a new command, I update my Arguments.
    I return the adoption result.
  Otherwise,
    If I can adopt aCommand, I adopt aCommand and return the result.
    Otherwise, I return that no adoption occurred.

Figure 4. Part of the incremental command parser

3.2 Description of class Command

The class Command (Table 2) is an abstract subclass of class Tree. As such, it inherits all the behavior of trees (it can have children -- sub-commands -- and provides a means to access its descendants) and it adds some methods of its own. Among these methods are do, undo and name which govern the command's execution and return the command's name. To implement a new kind of command, the developer creates a subclass of Command, adds the command arguments as object variables, and redefines some of the methods mentioned above. Moreover, the developer has to decide how commands should be grouped together to form higher level commands. This is done by defining the command's parent class (parentClass method), defining how the command should update its arguments when one child is added to it, removed from it or itself too changes some of its arguments (updateArgs method), and defining the commands it can adopt (canAdopt method). Some methods such as do, undo and canAdopt may not have to be redefined when the default behavior is satisfactory. Thus by default, the do and undo methods go through the command children and send the same message to them. This means that do and undo can be implemented only in primitive commands (commands with no children, i.e. leaves of the command tree). Similarly, the canAdopt(self,cmd) method checks if the receiver can have cmd as child by checking if cmd parent class is the same as the receiver class and thus does not need to be overridden in most cases unless the arguments need to be taken into account.

One major concern related to the implementation of histories is that the command history can be very large. Our solution is to discard children of old commands. For intermediate commands (e.g. "Type Text"), removing their children does not prevent them from being done and undone if they define their own arguments (e.g. text which has been typed), do and undo methods. We implemented this mechanism for all the non primitive commands to provide a faster navigation in the command tree.

 

Class Command subclass of Tree

name(self) Returns the name of self. Should be overridden
do(self) Executes self. Must be overridden at least by primitive commands (leaves).
undo(self) Undoes self. Must be overridden at least by primitive commands (leaves).
parentClass(self) Answers the class self parent should be member of. Must be overridden.
updateArgs(self) Updates self's arguments (using its children). Must be overridden. Called when self children change.
canAdopt(self,cmd) Returns whether self can adopt cmd (uses parentClass).
adopt(self,cmd) Determines the command resulting from the adoption (the receiver or a new command), then adds cmd to the children of the resulting command (uses updateArgs) and finally returns it.
createParent(self) Generates self parent command (uses parentClass and adopt).
add(self,cmd) Adds cmd to self descendants (see Figure 4).
remove(self,cmd) Removes cmd from self descendants

Table 2. Description of the class Command.

4 CONCLUSION

In this paper, we first presented command trees as a better history representation than lists, offering improved support for error recovery mechanisms and demonstrational techniques. We then introduced our model (prototypical command parent, adoption mechanism and partial commands) and showed that it is a practical and an elegant solution to the problem of incrementally constructing command trees. We also presented how we successfully implemented this model in an object-oriented application framework, and we illustrated the framework use through a text editor widget developed with it.

Kosbie [Kosbie 94] adopts a more lightweight approach than ours, by letting the programmer define the command grammar declaratively. To do so the user creates a hieractor which describes under which conditions a high-level event is to be generated. Such conditions include a trigger event, a running event and a stop event. As an example, the hieractor for a button as "Mouse Down" for trigger event, "Mouse Move" for running event, and "Mouse Up" for stopping event. Unfortunately this approach does not take command arguments into account: indeed, in a drawing application it is impossible to state that the "Rotate Object" command can be made of other "Rotate Object" commands, provided that they apply to the same object, and that they have same rotation center. This kind of relation can be expressed in our framework. Also our approach requires more work from the developer, this problem can be alleviated if the developer properly structures the command class hierarchy. An advantage of our approach is that it is not limited to widget-based interfaces and would work for speech or command line interfaces as well.

We are currently using the framework to include programming by demonstration capabilities to a telecommunication application [Yvon 94]. We plan to extend the framework to allow users to retrieve information about past sessions according to certain criteria, such as date, time, etc. We also intend to explore two ideas: the use of storyboards to present the history tree to the user and the use of the model in the context of robotics applications.

ACKNOWLEDGMENTS

We would like to thank Norbert Cot, Tom Gruber and Walter Sujansky for help with this paper. This research is partially sponsored by a grant from the Centre National de la Recherche Scientifique and the Centre National d'Etudes des Télécommunications (project CNET/CNRS/COGNISCIENCE with the LIAP-5 laboratory).

REFERENCES

[Affinity 91] Affinity Microsystems Ltd., Tempo II User Manual, Boulder, CO, 1991.
[Apple 93a] Apple Computer Inc., AppleScript Language Guide, Part Number 030-3994-A, Developer Technical Publications, 1993.
[Apple 93b] Apple Computer Inc., Inside Macintosh: Interapplication Communication, Addison-Wesley, Reading, MA, 1993.
[Bos 92] Bos E., "Some Virtues and Limitations of Action Inferring Interfaces," Proceedings of the ACM Symposium on User Interface Software and Technology, UIST '92, ACM Press, Nov. 1992, pp. 79-88.
[CE Software 93] CE Software Inc., QuicKeys User Manual, West Des Moines, IA, 1993.
[Cypher 91] Cypher A.,"Eager: Programming Repetitive Tasks by Example," Proceedings of CHI '91 (New Orleans, Apr. 28-May 2), ACM, New York, 1991, pp. 33-39.
[Darragh 92] Darragh J. and Witten I., The Reactive Keyboard, Cambridge University Press, New York, 1992.
[Fuller 89] Fuller I., "An Overview of the HP NewWave Environment," HP Journal, Aug. 1989, pp. 6-8.
[Greenberg 93] Greenberg S., "Techniques for reusing activities," The Computer User as Toolsmith : the Use, Reuse, and Organization of Computer-based Tools, Cambridge University Press, New York, 1993, pp. 40-64.
[Halbert 84] Halbert D., "Programming by Example," Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of California Berkeley, 1984. Also published as: Halbert D., "Programming by Example," Technical Report OSD- T8402, Office Systems Division, Xerox Corporation, Dec. 1984.
[Kosbie 93] Kosbie D. and Myers B., "A System-Wide Macro Facility Based on Aggregate Events: A Proposal," Watch What I Do: Programming by Demonstration, Cypher A., ed., MIT Press, Cambridge, MA, 1993, pp. 433-444.
[Kosbie 94] Kosbie D. and Myers B., "Extending Programming By Demonstration With Hierarchical Event Histories," Proceedings East-West Human Computer Interaction '94, St. Petersburg, Russia, August 1994.
[Kurlander 90] Kurlander D. and Feiner S., "A Visual Language for Browsing, Undoing and Redoing Graphical Interface Commands," Visual Languages and Visual Programming, Chang S. ed., Plenum Press, New York, NY, 1990, pp. 257-275.
[Lieberman 93] Lieberman H., "Mondrian: A Teachable Graphical Editor," Watch What I Do: Programming by Demonstration, Cypher A., ed., MIT Press, Cambridge, MA, 1993, pp. 340-358.
[Maulsby 89] Maulsby D., Kittlitz K. and Witten I., "Metamouse: Specifying Graphical Procedures by Example," Proceeding of SIGGRAPH 89, Vol. 23, No. 3, ACM, Boston, Aug. 1989, pp. 127-136.
[Modugno 94] Modugno F. and Myers B., "Pursuit: Visual Programming in a Visual Domain," Technical Report CMU-CS-94-109, Carnegie Mellon University, Pittsburgh, Jan. 1994. Also available in electronic format on the Internet at the following URL: http://www.cs.cmu.edu/afs/cs.cmu.edu/project/garnet/www/pbd-group/papers/cmu-cs-94-109.ps.Z
[Olsen 88] Olsen D. and Dance D., "Macros by Example in a Graphical UIMS," IEEE Computer Graphics & Applications, Jan. 1988.
[Piernot 93] Piernot P. and Yvon M.,"The AIDE Project: An Application-Independent Demonstrational Environment," in Watch What I Do: Programming by Demonstration, Cypher A., ed., MIT Press, Cambridge, MA, 1993, pp. 382-401.
[Potter 93] Potter R., "Triggers: Guiding Automation with Pixels to Achieve Data Access," in Watch What I Do: Programming by Demonstration, Cypher A., ed., MIT Press, Cambridge, MA, 1993, pp. 360-380.
[Rhyne 92] Rhyne R. and Wolf C., "Tools for Supporting the Collaborative Process," Proceedings of the ACM Symposium on User Interface Software and Technology, UIST '92, ACM Press, Nov. 1992, pp. 161-170.
[Thimbleby 91] Thimbleby H., User Interface Design, ACM Press Frontier Series, 1991, chapter 12, pp. 261-286.
[Wilson 90] Wilson D., Rosenstein L. and Shafer D., Programming With MacApp, Addison-Wesley, Reading, MA, 1990.
[Witten 81] Witten I., "Programming by Example for the Casual User: A Case Study," Proceedings of the Seventh Conference of the Canadian Man-Computer Communication Society, CMCCS, Waterloo, June 1981, pp. 105-113.
[Yvon 94] Yvon M., Lefèvre F. and Piernot P., "Adaptive and Demonstrational Interfaces Applied to Telecommunication Services," Proceedings of the East-West International Conference on Human-Computer Interaction, St. Petersbourg, 1994, 49-61, Volume II. 

* Visiting from LIAP-5, Université René Descartes, Paris, France.