* 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.
* 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.
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.
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.
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.
* 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.
* 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.
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.