Knowledge Systems Laboratory December 1994 Report No. KSL-94-74
by
Philippe P. Piernot
Marc P. Yvon
KNOWLEDGE SYSTEMS LABORATORY
Department of Computer Science
Stanford University
Stanford, California 94305
This work is funded in part by a grant from the Centre National de la Recherche Scientifique and the Centre National d'Etudes des Télécommunications
Philippe P. Piernot* Marc P. Yvon
Knowledge Systems Laboratory Laboratoire d'Intelligence Artificielle de Paris 5
Department of Computer Science UFR de Mathématiques et d'Informatique
Stanford University Université René Descartes
701 Welch Road, Building C 45, Rue des Saints-Pères
Palo Alto, CA 94304 75006 Paris - France
piernot@ksl.stanford.edu 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 argue that command trees offer a richer representation and provide better support for undo/redo mechanisms and programming by demonstration. We introduce a new model to support incremental construction of command trees and an object-oriented application framework that implements this model.
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 [9]. 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 [1], QuicKeys [5]) and certain predictive interfaces (Reactive Keyboard [7], Predictive Calculator [21]). 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 [18].
Another approach records high-level commands, like in some undo/redo facilities (Chimera [12], AIDE [17], WeMet [19]), macro recorders (AppleScript [2, 3], HP NewWave [8]), predictive interfaces (Edward [4], Eager [6], Metamouse [14]) and programming by example systems (SmallStar [10], Chimera [12], Mondrian [13], Pursuit [15], Mike [16], AIDE [17]). Some systems ( [12], [13], [15] ) 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 [11] introduced the notion of aggregate events -- events made of other events -- leading to a tree-like representation of the history. 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, hierarchical histories provide a good basis for multiple-level undo/redo operations; for better pattern matching for demonstrational interfaces (by keeping high-level commands, inference is less sensitive to variations in the way the task is performed); for capturing user intent (by keeping low-level events too); and for better visualization (by displaying a feedback closer to the user task).
An example of such a hierarchical history 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 hierarchical histories 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 [17], 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 [17]. 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 is a natural continuation 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 right most 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. All the ancestors are then updated as a result (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. They are objects that understand the do and undo messages and they can 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.
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 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 of all, let's point out that 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 [20]). 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 easily extend the parser by overriding the try to adopt method in its own commands. Thus, the default behavior we describe in section 2.2 can be modified to fit the special needs of an application. This previous point is extremely important because in the case of a system-wide history (one history for all running applications), an application may need to modify the parser behavior for its own commands, without modifying the behavior for the rest of the system.
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 itself when one of its children is changed, added, or removed (update 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(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.
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).
4 CONCLUSION
In this paper, we first demonstrated that command trees are a better history representation than lists and offer 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 hierarchical histories. 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.
We are currently using the framework to include programming by demonstration capabilities to a telecommunication application [22]. 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, Allen Cypher, 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
[1] Affinity Microsystems Ltd., Tempo II User Manual, Boulder, CO, 1991.
[5] CE Software Inc., QuicKeys User Manual, West Des Moines, IA, 1993.
[7] Darragh J. and Witten I., The Reactive Keyboard, Cambridge University Press, New York, 1992.
[8] Fuller I., "An Overview of the HP NewWave Environment," HP Journal, Aug. 1989, pp. 6-8.
[15] 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 Universal Resource Locator (URL): <http://www.cs.cmu.edu:8001/afs/cs.cmu.edu/project/garnet/www/pbd-group/paper/cmu-cs-94-109.ps>
[20] Thimbleby H., User Interface Design, ACM Press Frontier Series, 1991, chapter 12, pp. 261-286.