back to ... Table of Contents Watch What I Do

Chapter
21

PBD Invocation Techniques:
A Review and Proposal

David S. Kosbie
and
Brad A. Myers

Introduction

The other chapters in this book describe a great diversity of PBD systems. These apply PBD technology to such varied problems as macro creation, picture neatening, widget building, and general-purpose programming. Together they indicate the potential power and relevance of PBD to most end-user tasks. While it is true that these systems use many different and seemingly incongruent paradigms, most in fact share a common structure:

* Program Creation: By some demonstrational technique, the end user creates a program (or a script). The term "program," as used in this chapter, does not refer to the abstract procedure that the end user demonstrates, but to the concrete internal representation that the PBD system generates. This program may never be displayed to the user. It may not even have an explicit symbolic representation! However, at some level, it must exist. After all, PBD is Programming by Demonstration, and what is programming without a program?

* Program Invocation: Once created, the program must be invoked. That is, the PBD system must determine that the program should be executed. Often, this is in response to an explicit end-user action, but this need not be the case. For instance, the PBD system might automatically invoke programs whenever it infers that it is appropriate. Nevertheless, some invocation technique must exist -- otherwise, of what use is the program?

* Program Execution: In this final step, the PBD system must effect the changes which it inferred from the end user's demonstration during program creation (that is, it must "run" the program).

To date, researchers have focused mainly on program creation. Thus, while their systems exhibit an impressive array of distinctive and useful creation techniques, most also use simplistic invocation mechanisms. A notable exception is Richard Potter's work on invocation, both in his Triggers system and his notion of "Just-in-Time" programming (Chapters 17 and 27). Nevertheless, there is evidence that a shift in priorities, giving more serious consideration to the invocation phase, might reap significant rewards for the entire PBD field. To demonstrate this point, we propose two new techniques:

* Generalized Event-Based Invocation; and

* Program Invocation by Demonstration.

These techniques, which are being pursued as part of the KATIE project [Kosbie 93], should significantly empower PBD systems. By reviewing what techniques are presently used, and proposing exciting new alternatives, this chapter is intended to focus the research community on the importance of PBD invocation.

Present Invocation Techniques

The invocation techniques used by current systems can be divided into those which are event-based and those which are not. Although the majority of systems -- including virtually all commercial systems -- strictly use event-based methods, the non-event-based methods are currently more interesting and sophisticated. Whether they are more powerful, however, has yet to be established. The remainder of this section details the various approaches.

Event-Based Techniques

Event-based invocation techniques invoke a program in response to a particular event, such as a keystroke. This class is actually a collection of many ad hoc techniques, including invoking a program in response to:

* Keystrokes: It is common to reserve a bank of keyboard keys (often the "F" keys) so that they can be used to invoke programs. Once bound, the key is termed a "Hot Key."

* Menu Selection: Once a program is created, it can be given a name, and included in a menu of available programs. Selecting a name from this menu invokes the corresponding program.

* Dialog Box Input: Similarly, there might be a dialog box which manages program invocation. If the end user enters a program's name into a particular field of the dialog box, the program is invoked.

* Icon Selection: Some systems attach programs to particular icons, so that selecting the icon invokes the program.

* Time of Day: Some systems, such as HP NewWave [Fuller 89], allow users to specify a particular time when the program should be invoked. At that time, a system-generated clock event invokes the program.

Non-Event-Based Techniques

Several research systems have gone beyond traditional event-based invocation techniques, producing an interesting array of alternatives. These approaches tend to be data-driven -- rather than focus on user-generated events, the systems react to the resulting changes in the underlying data structures. This, of course, presumes that the systems have access to (and knowledge of) the data structures and can also detect precisely when and where these are changed. Approaches of this kind include:

Constraints

Constraint-based PBD systems invoke programs when a certain relationship among application data exists. For example, in Chimera (Chapter 12 and [Kurlander 92]), the user can define a "Nearly-Tangent" constraint which evaluates to "True" whenever a line is within some tolerance of being tangent to a circle. The user can then define a program (demonstrationally, of course) to make the nearly-tangent line completely tangent to the circle. From then on, whenever the "Nearly-Tangent" relationship holds between any line and any circle, the program will be invoked (and the line will become tangent with no further user intervention). Similarly, Triggers (Chapter 17) invokes programs when screen pixel patterns satisfy certain user-defined constraints. Besides inferring constraints for program invocation, Garnet (Chapter 10) further allows programmers to explicitly define such constraints using arbitrary Lisp expressions.

Why is this approach not considered event-based? The short answer is that these systems need not observe the event stream at all. Rather, they can rely on a data-driven mechanism: for example, variables can be annotated with the constraints in which they are included. Whenever a variable changes, the associated constraints can be evaluated, and if any are satisfied, their associated programs can be invoked. It is true, though, that this approach can be simulated by an event-based system: for any given constraint, there are only certain events which might lead to the constraint being satisfied. The system could evaluate the constraint after all such events. The key problem here is in requiring the end user to identify a priori all the potentially relevant events for each constraint. For example, in order to simulate the "Nearly-Tangent" constraint, the end user must identify all the events which might result in a line being nearly tangent to a circle. These include creating, moving, or resizing any line or circle, as well as less obvious events such as changing the thickness of a line. Besides being unwieldy, this process is also unreliable: omitting any of these events may lead to situations where the constraint in fact is satisfied but the program is not invoked. This can be avoided by testing every constraint after every event. This, however, is grossly inefficient. The bottom line is that although constraint-based invocation can be simulated by event-based methods, the techniques are fundamentally distinct and should be handled by a separate mechanism.

Active Values

More generally, systems based on active values invoke programs when the value of a particular variable changes. This approach subsumes constraint-based methods, as the invoked program can be designed to proceed only if the changed variable now satisfies some constraint. In Rehearsal World (Chapter 4), for example, the end user can place a "number performer" (that is, a user-defined numeric variable) on the "stage", and define a "change action" for it. One such change action divides a graphical broom into the number of parts indicated by the number performer. Once this change action is defined, whenever the number performer's value changes, the broom is automatically updated. Similarly, Peridot (Chapter 6) applies active values to the widget building domain.

Automation

In all the techniques mentioned so far, the end user either explicitly invoked the program or detailed the conditions under which the program should be invoked. In either case, the end user played an active role in program invocation. It is possible, however, for the end user to play a passive role. By analyzing the user's general usage patterns, such systems attempt to infer situations under which the inferred program should be invoked. Systems utilizing this approach include the Predictive Calculator (Chapter 3) and Lantern [Lerner 89].

Generalized Event-Based Invocation

Despite the prevalence of event-based invocation techniques, they are actually quite limited in power. With the exception of the time-of-day approach, they all require that every invocation of a program be explicitly initiated by the end user. Furthermore, as these methods are ad hoc, they present numerous inconsistent paradigms, both for end users to master and for PBD system developers to support. To illustrate how this can be limiting, consider the following scenario:

Carl, a typical end user, is annoyed by his word processor -- whenever he does a "Find Word" command, the found word is highlighted and positioned at the top of the screen. The problem, he says, is that he cannot see the lines preceding the selection, and invariably scrolls the text to place the selection in the middle of the page. To remedy this, he uses his off-the-shelf PBD system to create a program which performs the necessary scrolling. Now he only needs to instruct the computer to execute this program whenever he issues a "Find Word" command to the word processor. At this point, he pauses, perplexed...

The point of this scenario is that the program itself was easy to create; the difficulty lies in specifying how to invoke the program. Also, despite the fact that he wishes to invoke his program based upon a certain event occurring, none of the current event-based techniques can satisfactorily accomplish Carl's goal.

These concerns motivate the proposal of a generalized event-based invocation scheme. That is, rather than allowing programs to be invoked by one of a hodgepodge of selected events, it is preferable to allow any event to invoke a program. This approach works best within systems which map low-level user events (such as mouse moves) into high-level events (such as menu selections), as the latter are far more likely to correspond to the intentions of the user. Such systems include KATIE [Kosbie 93], Apple Events [Apple 91], and HP NewWave [Fuller 89], among others. Not only does this subsume all the ad hoc event-based approaches currently in use, it even solves Carl's problem: he could have the "Find Word" high-level event invoke his program. Furthermore, this is just an example of a larger class of problems, including tasks such as:

* Copying files into a short-term backup directory before (the event of) deleting them;

* Executing an initialization sequence upon (the event of) launching an application; and

* Printing out tomorrow's calendar upon (the event of) logging out.

While some existing systems do provide this kind of support for a few selected high-level events, none does so for arbitrary high-level events. Thus, although this technique does not even address the actual kinds of programs which can be created by PBD techniques, it clearly extends the applicability of PBD technology to a whole new class of problems.

Program Invocation by Demonstration

The previous section argues that end users should be able to specify that programs should be invoked based on arbitrary high-level events. This leads to another quandary -- precisely how should the user do the specifying? In the above example, although Carl knows he wants his program invoked whenever he selects "Find Word" from the menu (or from a keyboard accelerator), he must still specify this to the PBD system. One approach is to allow the user to textually enter this information. This, however, requires the user to know both the internal names and relevant syntax of all the actions he performs, which is both impractical and against the spirit of PBD. Moreover, this drawback is independent of whether or not these actions are represented using high-level events, and so is a general problem for all PBD systems.

Fortunately, textual entry is not necessary: the invoking event can be specified demonstrationally, just as the program itself was! That is, in the program creation phase, the end user would not only demonstrate what the program should do, but also when it should do it. In the above example, prior to creating the program to scroll the text, Carl would separately record his actions while he selected the "Find Word" command. This clearly resolves the specification dilemma in a straightforward and intuitive manner.

This approach is even more promising if the full inferencing power of the PBD system is applied to the invocation demonstration. For instance, the user should be able to demonstrate multiple positive and negative examples of the invoking event. To illustrate, suppose the user of a typical graphical editor wishes to add the behavior that any mouse click in a red rectangle should change that rectangle's color to blue. It is worth noting that none of the existing event-based techniques even allow this behavior, as they cannot invoke programs based on mouse clicks in arbitrary objects. However, using the techniques described here, the user could add the behavior in two easy steps:

1. Demonstrate the invoking event. Suppose the user presented two positive examples (clicking in two different red rectangles), then two negative examples (clicking in, say, a red oval and then a blue rectangle). From this, the inference engine should be able to infer the appropriate event.

2. Demonstrate the program. This step is trivial -- the preceding step restricts the "input" to red rectangles, thereby precluding the need for a conditional in the program itself. So, perhaps in a special define-program mode, the user clicks in a red rectangle to invoke the program demonstration, and then merely sets the rectangle's color to blue.

Some Issues

There are many interesting and difficult issues concerning generalized event-based invocation. This section briefly suggests a few of them.

* Event Parameter Access: How does the invoked program access parameters of the invoking event? Consider the example of backing up deleted files. After being invoked by a "Delete-File" event, the program which does the copying must refer to the actual file that is being deleted, which is a parameter of the "Delete-File" event.

* Event Modification: Should it be possible to modify, or even completely elide, the invoking event? For example, if a program invoked by a "Delete-File" event determines that the file ought not be deleted after all, the program should be able to disable further processing of the "Delete-File" event.

* Event Ordering: It is sometimes necessary to execute the program before the invoking event is processed -- as when copying files before deleting them -- and sometimes after -- as when initializing an application after launching it.

* Other Generalization Schemes: There are situations which the generalized event-based invocation scheme described above does not cover. For instance, invoking based on a sequence of events, or upon either of two events (or, more generally, upon an arbitrary Boolean expression of events).

* Application to Data-Driven Methods: Program invocation by demonstration is not limited to event-based PBD systems. Users of constraint-based systems, for instance, should be able to demonstrate the constraint which, when satisfied, invokes their program. Indeed, Chimera (Chapter 12) already supports this behavior.

* Other Fields: The general issue of declaring when to invoke some procedure is not confined to the PBD field. For instance, in Office-by-Example [Zloof 77], an office automation system, user-written programs are triggered by various events (mail arriving, time alarms going off, and so on). In the field of programming languages, non-explicit method invocation dates back at least to the "pattern-directed invocation" provided by Conniver [McDermott 72], and is prevalent in many modern languages. We are presently studying methods for applying more powerful invocation techniques to the PBD domain.

* Suitable Platform: As earlier mentioned, this approach is most effective on a platform which supports high-level events. Moreover, application developers wishing to utilize these ideas may consider using an architecture which also provides some support for low-level dispatching based on the current event. The list of such systems is numerous and growing, and includes Apple Events [Apple 91], HP NewWave [Fuller 89], TCL [Ousterhout 90], and KATIE [Kosbie 93]. The AIDE system (Chapter 18) also provides this functionality based on the work in KATIE.

State of the Work

Generalized event-based invocation is one facet of the KATIE project [Kosbie 93]. KATIE, a new architecture for improved system-wide, event-based macro facilities, is being developed by the first author as part of his doctoral dissertation at Carnegie Mellon University. Current work focuses on resolving the various issues presented here, and on extending the Aggregate Event model (Chapter 22) to facilitate these techniques.

Conclusions

After detailing program invocation methods in current PBD systems, this chapter proposes two new PBD invocation techniques:

* Programs should be invoked based on any high-level event; and

* Users should be able to specify this event demonstrationally.

Although there are some difficult issues remaining, the proposal may significantly extend the class of problems which can be solved with PBD technology. This leads to perhaps the most important conclusion of this chapter: most current program invocation techniques, and particularly event-based ones, are primitive, ad hoc, and are now serving to limit the potential of this exciting new technology. It is hoped that the research community will take note of the importance -- and rich potential -- of PBD invocation techniques.

Acknowledgments

This research was funded partially by NSF grant number IRI-9020089 and partially by the Avionics Lab, Wright Research and Development Center, Aeronautical Systems Division (AFSC), U.S. Air Force, Wright-Patterson AFB, OH, 45433-6543 under Contract F33615-90-C-1465, Arpa Order No. 7597.

The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Government.



back to ... Table of Contents Watch What I Do