1. INTRODUCTION
When a client hires a programmer, he generally will meet with him to show how he wants the proposed application to behave. Using a graphics editor, scratch paper or even a dinner napkin, he sketches the proposed interface, then walks the programmer through its behaviors, first playing the role of the end-user and showing what actions he can take, then playing the role of the system and showing how it will respond to a particular stimulus.

One goal of our research was to automate this process, to build a software agent that does the job of the human programmer in the above scenario. We envisioned a system that would watch a client demonstrate behaviors, and automatically create the desired application.

Early PBD research systems such as Mondrian [8], Chimera[7], and Eager[2] had worked out many of the problems in creating generalized macro "procedures" from a user's demonstrations, but they did not provide support for specifying when a macro should be invoked. The purpose of these systems was to eliminate repetitive tasks in existing applications, so a standard way of invoking previously recorded macros was sufficent. Our goal, on the other hand, was to allow users to build complete interfaces starting with a blank canvas. Thus, we had to provide mechanisms so that a designer could specify both macros, and the events that triggers them.

By adding PBD macro invocation to the more common PBD facilities for demonstrating macro procedures, we felt we could provide the complement to interface builders like Visual Basic. These popular tools significantly decrease the time and expertise necessary to define the layout of an interface, but the designer must still code its dynamic behavior. For instance, a Visual Basic designer can easily change the static location of an object in the interface by dragging it, but specifying that the object should be moved at run-time in response to some stimulus (e.g., a button click) requires coding.

Our strategy was to provide the designer with a complete set of widget, text, and graphics operations, and allow him to use them both for drawing the interface, and for demonstrating its dynamic behavior (stimuli and response macros). With such a capability, the designer is not restricted to wiring together standard widgets like menus, list boxes, and buttons, but can instead draw arbitrary graphics and demonstrate how they respond to stimuli (we call these application-specific widgets). Such capabilities allow non-programmers to create animated and graphical applications, and not be limited to standard business-type applications.

Armed with these goals, we began building systems based on the process of Programming by Stimulus-Response Demonstration. We began in the early 90's with the first author's DEMO [15] system (along with Gene Fisher) and the second author's Marquise [10] system (along with Richard McDaniel). These systems were then refined into our most recent systems, called Pavlov[16,17] and Gamut [9], respectively.

A Quick Example
Consider how stimulus-response demonstration is used to create a Celsius-Fahrenheit converter in the Pavlov system [16,17]. The designer first draws two thermometers, as shown in Figure 1:

Figure 1. Pavlov Development of a Celsius-Fahrenheit Converter. The menu bar provides some basic graphics and text operations. The control panel in the upper-right is a video-recorder-like mode palette that allows the designer to draw, record stimuli, record responses, or "play" interfaces. The Stimulus-Response Score in the lower right displays a high-level representation of the behaviors that have already been demonstrated.

Note that the thermometers in Figure 1 consist of raw graphics-- they are not widgets with pre-defined behavior. After drawing the thermometers, the designer uses the same drawing operations to demonstrate the interface's behavior. He first tells the system he is demonstrating a stimulus -- he selects Stimulus mode in the control panel-- then drags (resizes) the Celsius indicator ten pixels up. Then, in Response mode, he demonstrates how the system should respond to the stimulus: he stretches the Fahrenheit indicator 18 pixels along the y-axis (he might also modify the text box below the celsius thermometer if he hasn't already demonstrated this behavior previously).

From the demonstrations, the system infers a generalized behavior. In this case it infers that any time the Celsius bar is moved, the Fahrenheit bar should be moved 9/5 (1.8) as much. When the interface is executed, and the end-user moves the Celsius bar, the Fahrenheit bar is moved the proportional amount.

Wait a Second!
An example like the Celsius-Fahrenheit converter inspires more questions than it answers. How does the system know to infer the 9/5 proportion? Can the end-user move the Celsius indicator outside its enclosing box? How would such a restriction demonstrated? If the designer doesn't like what the system infers, can she change it? Can animated behaviors and timing be specified? Can more complex stimuli be demonstrated, like the behaviors of a PacMan character?

Trying to answer such questions is the challenge of our research. This paper introduces what we have learned in building a number of stimulus-response systems (Marquise [9],Gamut [10],DEMO [15], DEMO II [6] and Pavlov [16,17]) over the past decade. Our goal is a system that allows the behavior of any interface to be defined without coding. There has been some significant progress: stimulus-response demonstration can be used to create such complex interfaces as diagram editors, driving simulators, shooting arcades, board games and even PacMan. However, not all of these ideas have appeared in commercial interface builders, and much research is still needed to reach the ultimate goal. 

In this paper, we'll view stimulus-response as a kind of programming language, where the language consists of behavior demonstrations instead of code. Thus, will provide an overview of alternatives for both the syntax and the semantics of stimulus-response languages. We'll also discuss various alternatives for providing feedback to designers so that they can view and edit a high-level representation of the behaviors that have already been specified.

2. THE SYNTAX OF STIMULUS-RESPONSE
The syntax of a stimulus-response system is the mechanism by which a user presents the "example" behaviors to the system. Providing a usable syntax is a challenge because the system is providing the end-user with much more power than most software -- it is allowing him to create software, not just use it. The key difficulty is that a user must performs the action in the development environment for different reasons.

Perhaps the most straight-forward syntax is to provide a video-recorder-like mode palette as shown in Figure 1 and used in DEMO, Pavlov, and Marquise. The designer uses Initial View mode to draw the initial interface. The system keeps a record of the initial state of each graphic, so that it can snap back to it after the designer demonstrates stimuli and responses. This system reverts to this initial state whenever Inital View or Play mode is selected.

In Stimulus mode, the designer plays the role of end-user and demonstrates an event. This event can be as simple as a button-click or key-press or it can be one of the drawing operations (e.g., Move, Rotate). It can also be contextualized, i.e. the designer can demonstrate a graphical condition that must be true before a response is triggered.

Often the stimulus is something the end-user initiates directly at run-time, but not always. For instance, one stimulus might trigger the execution of a series of response operations, and one of those operations in turn might trigger some other respons. Thus the designer would demonstrate two behaviors, the first with an "end-user" stimulus, the second with a "system" stimulus. The different types of stimuli are discussed in detail later in this section.

After a stimulus is recorded, the system automatically changes the mode to Response mode. In this mode, the designer plays the role of the system by executing the operations that should occur in response to the stimulus. To end the response sequence, the designer changes to any other mode. Play mode allows the interface to be executed. In some systems, the development menus and palettes disappear in Play mode, leaving only the target interface.

Eliminating Modes
Conventional interface builders like Visual Basic have two modes--build and test. Envirnoments like the one described above add at least two more to the mix: record stimulus and record response. We have found that users have significant difficulty keeping track of the current mode when these additional modes are added.

Some systems provide alternative syntaxes that eliminate one or more of the modes. Chimera [7] effectively eliminates response mode by recording all actions in a history list and requiring the designer, after-the-fact, to signify which actions in the list should be part of a macro. Such a scheme could be applied to a stimulus-response system by requiring the designer to also signify an operation in the history list as the stimulus.

Peridot [11] provides an on-screen virtual mouse that eliminates some of the need for a stimulus mode. Instead of choosing stimulus mode and using the physical mouse to demonstrate what the end-user might do, the Peridot designer drags the logical mouse to the object and manipulates it.

Gamut [9] eliminates stimulus mode by replacing the four-mode palette with two buttons: "Do Something" and "Stop That" (see Figure 2). When the user performs an action that is supposed to do something and it doesn't, he hits the "Do Something" button. The event just prior to pushing the button is assumed to be the stimulus. The system is then in response mode until the user hits "Done" (the "Done" button appears when the system is in response mode). "Stop That" is used to give negative examples when the system does something wrong-- it also puts the system in response mode, and it tells the system to eliminate the response(s) that were previously recorded.

Besides eliminating stimulus mode, the Gamut scheme also eliminates the distinction between build and test mode by having the system always be in test mode, i.e., any previously defined behaviors are always active, even when the designer is editing.

Figure 2: A Gamut screen creating a board game. The graphics, text, and widget operations are accessed in the menus on the top and left. The behavior control panel in the lower right provides "Do Something" and "Stop That" buttons that both intitate response demonstrations.

Demonstrating Stimuli
Any of the following stimuli can trigger a response in an interface:

• An end-user manipulating the mouse or keyboard (Physical Operations)
• The execution of some drawing editor operation, such as Move or Rotate (Logical Operations)
• Objects in the interface exhibiting some state or context.
• The passage of time.
• The execution of some application event.

The syntax for demonstrating each of these stimuli are discussed in the following sections.

Physical and Logical Operations
One key aspect of PBD interface builders, as opposed to PBD macro systems that extend existing applications, is that the base system, e.g., the drawing palette, menu and other mechanisms, do not appear at run-time. Thus, unless the designer explicitly demonstrates that the end-users can perform an operation in the target interface, they won't be able to.

For example, during development, the designer can rotate any object by choosing Rotate in the drawing mode palette. But if the designer wants the end-user to be able to rotate that object, she must demonstrate a stimulus-response behavior which maps a mouse-drag to a rotate operation.

Some systems require this physical (mouse-drag) to logical (Rotate) mapping to be explicitly demonstrated. In DEMO [15], when the designer clicks on an object in stimulus mode, she is prompted to choose between the mouse operations up, down, drag, enter, and exit. The designer selects one, then demonstrates the response which should be linked to the chosen stimulus.

Gamut provides special mouse operation icons that can be dragged onto an object to demonstrate the physical operation. These are visible at the left of Figure 2, below the drawing palette. Since there is an icon for each type of operation, no choice dialog is necessary.

If the physical->logical mapping is explicit, the designer needs two demonstrations for behaviors like the Celsius-Fahrenheit program: one to specify the physical mapping:

LeftMouseDrag -> CelsiusBar.Move

and one for the logical mapping:

CelsiusBar.Move -> FahrenheitBar.Move.

Pavlov eliminates the need for two demonstrations in such cases. When the designer moves an object in stimulus mode, the system implicitly infers the drag->Move mapping, and also records that the Move should be mapped to the upcoming response operation(s). The disadvantage of inferring the physical-logical mapping is that sometimes the designer only wants to map a logical stimulus to logical response(s), and doesn't want the physical-logical mapping. For instance, in a shooting arcade game, the designer demonstrates that moving a bullet (and hitting a target), should cause a response of deleting the target. In Pavlov, when the bullet.Move stimulus is demonstrated, the system infers a physical-logical mapping, i.e., that the end-user can move the bullet. To restrict the end-user from doing this, the designer must use the editor to delete the mapping.

Context-Triggered Behaviors
Sometimes the activity in an interface should be executed not in response an operation, but in response to the interface reaching a particular context or state. For instance, in the shooting arcade game, a target should be deleted only when a bullet intersects the target, as shown in Figure 3:

Figure 3. Pavlov Development of an Arcade Game. The condition dialog is in the upper right. It appears when the system identifies a condition during a stimulus demonstration.

Such context-based stimuli are the focus of graphical rewrite systems (see Cypher chapter ), which we characterize as a type of stimulus-response system. Demonstrations in these systems consist of selecting a portion of the interface (a set of cells in the grid) that make up a "before state", then manipulating the objects residing in the selected portion of the grid to show an "after-state".

In terms of stimulus-response, the stimulus is the before-picture instead of an operation. At run-time, the system continually tests to see if the demonstrated "before picture" occurs. When it identifies such a state, it executes the operations required to put the interface in the demonstrated "after state."

Graphical rewrite rule systems restrict context specification (and object movment) to discrete grid coordinates, e.g., a typical behavior might be described as "trigger the response when a dog is one square to the left of a wall"). This grid restriction reduces ambiguity compared to a system that allows arbitrary object relationships, but it also limits the designer.

Both Pavlov and Gamut allow context to be specified without the grid-based limitation. Instead of adding a special "demonstrate context" mode, Pavlov integrates context directly into its stimulus-response model The idea is that an interface does not magically enter a particular state, but will only do so as a result of some operation. Thus, the designer always demonstrates a triggering stimulus operation, but as she does she can demonstrate a condition that must be true for the stimulus to trigger its response.

Consider again the shooting arcade game. In Pavlov, the designer demonstrates a move of a bullet as the stimulus, but completes the move (releases the mouse) so that the bullet intersects a target (see Figure 3). The system records the move stimulus and identifies conditions, like "intersect", relating the objects in the interface. The system lists textual descriptions of the conditions it finds and asks the designer to choose which should be used as part of the stimulus. In this case, the designer selects "bullet.Intersects(target)" then demonstrates the deletion of the target as the response. At run-time, every time a bullet moves, the system checks the intersect condition, and executes the response only if the condition is true.

Though Pavlov's scheme isn't restricted by a grid basis, it is limited by the set of conditions or relationships (e.g., intersect, encloses, etc.) for which it searches. It also requires the designer to specify AND,OR and NOT relations in a dialog when a condition is complex; in Creator, the designer can specify such complex conditions with a single picture.

Pavlov's model is more efficient than traditional constraint or rewrite rule systems because it only needs to check a particular condition when the triggering event is executed, while those systems check all conditions on every time-stamp. However, it has the disadvantage that a condition must be specified more than once if different stimuli can cause the same result, e.g., there are two objects and movement of either might lead to an them intersecting.

A general goal of Gamut is to eliminate the need for the designer to choose the correct generalization (e.g., condition), as is done in Pavlov. The reasoning is that the representation of context, whether textual or graphical, is inherently complex, so choosing can be difficult. Gamut's philosophy, similar to [5], is to allow the designer to perform multiple demonstrations of the same context. The system then uses AI techniques to infer the intended context from the samples. Gamut also asks the designer to provide hints by selecting objects, post-demonstration, that are relevant to the context. The hints allow more complex conditions to be inferred than are possible in other systems (see McDaniel Chapter).

It should be noted that the idea of demonstrating context has also become important in web information extraction systems. These systems allow designers to build new pages that are composites of information extracted from various other web pages. Because web pages change so rapidly, the difficulty lies in describing the information to be extracted so that even if the web page changes, the description is still valid. Two chapters in this book (Bauer and Sugiura) explore techniques for automatically generating such descriptions from a user's demonstrations.

Time as a Stimulus
Sometimes activity should occur at a certain time, rather than in response to an external event. Gamut allows the designer to drag a special clock widget into the background window, and then demonstrate a tick as a stimulus. Pavlov provides a special stimulus called "beginning of execution" which a designer can specify as the current stimulus. He can then select a time-frame and demonstrate responses which, at run-time, are executed at a particular time.

Structured Text as a Stimulus
Sometimes activity should be triggered when the user types in a piece of structured information. For instance, when a user enters a street address, an interface might automatically open a map with the address as the destination. The work described in (Lieberman chapter) allows a designer to demonstrate example instances of structured types, then automatically builds a grammar that can recognize new instances.

Demonstration Aids: Guide Objects and Ghost Marks
A guide object is one the designer uses during development, but doesn't want to appear at run-time [6]. For instance, the designer might use a directed line to show how a game-piece can move around the board. In Gamut, the designer simply sets an object property to specify that it is a guide object. It then appears in pastel colors during development, and disappears at run-time. In Figure 2, the yellow lines are guide objects to help show where the pieces can move. When the designer drags a game piece along a yellow line, the system can infer that he is demonstrating a move from one end-point of the line to the other (instead of a move by some offset). Thus behaviors such as moving one (or more) squares in a game can be demonstrated.

Gamut also provides a back-stage area in which all objects are guide objects. The objects in this area generally store "computational" information in the form of text boxes or other widgets. By replacing information traditionally stored in program variables, the need to connect an interface to application code is reduced or eliminated.

Marquise introduced the idea of leaving trails, or ghost marks, of the mouse cursor as it is moved, so the designer can hook responses to points on its paths. Gamut extended the idea so that the previous state of an object also appears after it is transformed. Thus, a designer can specify an operation dependent on that previous state, e.g., that ObjectA is moved to the previous location of ObjectB after ObjectB is moved.

Demonstrating Responses
A response is any action that creates, transforms, or deletes an object in an interface. Though most PBD research systems are based on fairly rudimentary graphics editors, the idea is that a commercial system would provide a full range of graphic and text editing capabilities, and even access to a database and its operations.

Pavlov combines PBD with some animation mechanisms that allow timing to be specified on behaviors. Using Pavlov's timeline, the designer can specify a time-stamp, relative to the stimulus, for a demonstrated response. Pavlov also provides a special mode, similar to one in MacroMedia's Director, called Real Time Response mode. When this mode is chosen, the system records a sequence of time-stamped operations (an animation path) as the designer demonstrates an operation. The designer can also specify animation by stipulating that a response be executed periodically at run-time.

Pavlov also allows a designer to specify the direction (nose) of an object using a guide object. Consider, for instance, the development of a driving simulator:

Figure 4. A Driving Simulator Built in Pavlov. The arrow on the car is a guide object denoting the direction of the car.

After drawing the car, accelerator slider bar, and steering wheel, the designer specifies the "nose" of the car by manipulating a special guide object representing its direction. She then demonstrates a stimulus of moving the accelerator slider bar, and a response of moving the car, and marks the response as periodic. Because the car has a notion of direction, its movement is restricted -- the designer can only demonstrate that it moves forward or backward relative to the direction vector. In Pavlov, the response is recorded not as a Move(x,y), but as a (periodic) MoveForward operation. At run-time, the car goes faster or slower as the accelerator is manipulated.

3. THE SEMANTICS OF STIMULUS-RESPONSE
The generalization or inference machine of a stimulus-response system interprets the meaning of the examples a designer provides through demonstration. It takes demonstrated stimulus-response examples as input, and outputs behaviors that, if represented as code, would appear something like:

On StimulusObject.Stimulus(<formal parameters>)
{
	if (checkcontext)

		Operation(<ResponseObject>,<other response parameters>)
		...
  	}

Some major challenges in interpreting the examples are:

• Which object(s) is the designer signifying with her demonstrations?
• What should the parameters of the response operation(s) be?
• How should context modify the inferred behavior?

There are two main methods of generalization, based on whether the system allows more than one example of a behavior to be demonstrated. Pavlov generalizes from a single example, in the tradition of early PBD systems like SmallStar[4] and Chimera[8]. In AI terms, such single example systems are known as explanation-based learning systems.

The philosophy behind using single examples is to keep the inferencing simple so the designer can understand it, and then provide a second-level editor that allows the designer to modify generalizations easily. Single example systems use as much domain knowledge as they can so that the single "guess" is as accurate as possible.

Gamut generalizes from multiple examples. In AI terms, multiple example systems are known as empirical learning systems. Because more information is provided with multiple examples, these systems can infer more complex behaviors and need not rely on domain knowledge. However, it is more difficult for the designer to understand what the system is doing, and the syntax is also complicated as a demonstration can conceivably be performed to either edit, refine, or append (add another response) to a particular behavior.

The chapter by Myers, McDaniel, and Wolber (see chapter x) discusses generalization for PBD systems in general, focusing on the question of how much intelligence should be incorporated. This section explores generalization in the context of stimulus-response systems specifically.

Object Descriptor Problem
Perhaps the most important problem in generalizing from examples is the object descriptor problem [4] -- determining the object or objects that the designer intends to signify when he demonstrates an action on an example object. In terms of the generated code template shown at the top of this section, the problem consists of how to describe the "StimulusObject" and "ResponseObject" of the code.

Sometimes no generalization need occur, as there is a one-to-one correspondence between the demonstrated object and the intended run-time object. For example, in the Celsius-Fahrenheit example, FahrenheitBar is the demonstrated response object, and it is the intended run-time object as well. FahrenheitBar is an example of a constant object descriptor.

In some cases, however, the designer intends the demonstration object to be representative of some set of objects, or some single object that cannot be described with a constant. When the demonstration object is a dynamically allocated object, the object can't be described with a constant. Consider, for instance, the dynamically created bullets in an arcade game. A particular development-time bullet won't appear at run-time, because no bullets appear until a stimulus occurs. When a action is demonstrated on a bullet (e.g., movement), a non-constant descriptor must be inferred for it.

There are also cases when a non-constant descriptor is appropriate even though the demonstration objects itself is statically created. For example, consider a board game which has a group of pieces that are statically created. When the designer demonstrates moving a piece, he may be signifying that the piece whose turn it is, at run-time, be moved, and is using the particular piece as a representative of that concept.

Pavlov is a single example system, so it only infers non-constant descriptors for demonstrations on dynamic objects, since those must be generalized into non-constants. Pavlov includes a number of heuristics to guide its generalization of dynamic objects. The most simple inference is that the dynamic demonstration object represents all instances, at run-time, that have been created by the same stimulus. For example, suppose that the bullets in an arcade game are created by pressing the up-arrow key. If the designer demonstrates a stimulus of clicking a button, and a response of changing a particular bullet's color to blue, Pavlov infers that at run-time, clicking the button changes the color of all bullets (created by an up-arrow).

Pavlov does identify special cases that use more distinguishing descriptors. For instance, if a transformation is demonstrated in the same response sequence as a creation (e.g., a bullet is created then moved), then the object descriptor will be "the same instance as the one just created". If a response is demonstrated on the same object as the stimulus, the inferred descriptor is "the same instance as the stimulus." Pavlov will also infer if a particular condition should identify which instances are chosen (e.g., all rectangles that are green). In practice, Pavlov's special rules and condition identifier cover a wide range of behaviors. But no matter how many heuristics are used, the system will sometimes guess wrong using only a single example. In these cases, second-level editing or coding is necessary.

Because Gamut uses multiple examples, it can infer non-constant descriptors for static and dynamic objects. After the first example a constant descriptor is generally inferred, but as more examples are provided the system analyzes the properties of the examples objects to infer more complex descriptors.

Gamut also reduces the number of required examples by asking users to give hints about which of the many interface objects are important. With hints, the system can infer object descriptors that depend on objects that are not directly modified by the example action itself. Consider, for example, a two-player board game which has a red piece, a blue piece, and a toggle specifying whose turn it is. To specify the behavior, the designer first sets the toggle to one setting and demonstrates moving the red piece. He then sets the toggle to another setting and demonstrates moving the blue piece. At this point the system knows a non-constant descriptor is needed to describe the piece that should be moved, but it doesn't know where to start. Thus, it asks the designer to select what auxiliary objects, besides the piece, that the behavior depends on. If the designer is clever enough to select the toggle, the system can infer an object descriptor such as "the red piece if the toggle is on, the blue piece if the toggle is off".

Response Parameter Descriptors
In addition to the object parameter, PBD systems must infer the other parameters of an operation (see the "<other response parameters> in the code at the top of this section). For example, a move operation has both the object to be moved (as discussed above), and the position to which it moves. Again, the simplest inference is that the parameter is constant, but even in this situation there is ambiguity: did the designer intend the destination demonstrated, or the offset demonstrated (that is, move to this location, or move by this amount)? Single example systems must guess in this situation. Multiple example systems can distinguish after two examples.

Inferring constant parameters is hardly the most challenging issue. For instance, the position to which a board game piece should be moved in Figure 2 might be described as "take the number on the dice and move that number of spaces clockwise around the board from where the piece used to be." Such a parameter can be inferred by Gamut. The following sections discuss various techniques that can be used for generalizing non-constant parameters.

Linear Proportions
Pavlov takes advantage of the observation that many interface behaviors have response parameters that are proportional to the corresponding stimulus parameters. The Celsius-Fahrenheit converter is one example -- when one gauge is transformed, the other one should be transformed 5/9 (9/5) as much. Another examples is a diagram editor in which moving a node should cause all lines connected to it to be reshaped by the same amount.

Pavlov uses the heuristic that when a stimulus and response are both transformations (e.g., Moves), each response parameter is inferred to be proportional to the corresponding stimulus parameter. As with object descriptors, Pavlov also watches for special cases. For instance, if the designer demonstrated a Move(20,0) as a stimulus, and a Move(0,40) as a response, it maps the non-zero second parameter of the response to the non-zero first parameter of the stimulus.

InferenceBear [5] infers other linear combinations of parameter values from multiple examples of the desired behavior. This eliminates the need for hard-wired special cases, but requires the user to carefully choose the examples. Furthermore, InferenceBear can take into account properties of the object that do not participate in the action (Pavlov only analyzes the demonstrated stimulus and response objects). For instance, in the shooting arcade game, Inference Bear can infer after multiple examples that the parameters of the bullet creation depends on the location of the gun, though the gun is not part of the stimulus or response.

Complex Parameters
Gamut adds even more inferencing power by using decision trees and other AI algorithms, and by allowing the designer to provide hints to help the system generalize the parameters. For instance, after the first example of a bullet creation was provided, Gamut would ask the designer to point out objects that are important. The designer would select the gun, and Gamut would use this to infer the correct create response parameters, i.e., that the bullet should be created directly above the gun. In this way, hints can allow the system to "guess" the correct behavior more quickly than in systems that don't ask the designer for extra help.

Gamut can also compute the parameters using values from many objects. Examples include setting the color of an object based on the color of a palette, or computing the position of the board game piece using the dice as mentioned above. As a result, Gamut can be used to create complete applications such as a Turing machine, Tic-Tac-Toe, or a PacMac game.

4. FEEDBACK AND EDITING
When a PBD system infers a program from a designer's demonstration, it doesn't always infer the program that the designer intended. One solution is to allow the designer to demonstrate more examples until, hopefully, the system infers the intended program. But with such a scheme, the designer can never be sure what program the system has inferred, and can feel lost not knowing what to do next. Another approach is to ask the designer questions that will hopefully disambiguate the examples. However, our experience with such systems suggest that users have great difficulty answering such questions, and generally choose "yes" if given a choice, assuming the computer is right, even when it isn't.

It is clear from our experience that the designer really needs to see some representation of the inferred program, and be able to edit it. Here lies the dilemma, called the PBD representation problem: since the goal of PBD is to allow people that aren't programmers to create programs, the system probably shouldn't represent a program as conventional computer code (C++, Java, etc.). Even special purpose scripting languages, like that generated by DEMO and Inference Bear, are difficult for end-users.

One solution is to present a graphical, story-board representation of the inferred programs [7,8,10]. Figure 5 shows one from Pursuit [10] that represents copying all the files edited TODAY in the papers folder that end in ".tex".

Figure 5. A Pursuit Storyboard. It shows a file manipulation program created by demonstration in Pursuit.

Storyboards allow a designer to see what the system has recorded and what generalizations it has made. These "programs" can also be edited by moving tiles around, deleting them, or selecting them and re-demonstrating the particular operation.

The Stimulus-Response Score
Unlike Pursuit, stimulus-response systems must provide a representation which includes the triggering stimulus. In Pavlov, a dialog is provided that allows the designer to select an object and a "current stimulus":

Figure 6. The Pavlov Editor showing an animation path triggered by a button-click. In this example, the "current stimulus" is a LEFTCLICK on Rect0. The displayed response is an animation path (a series of moves) involving Ellipse0.

When the stimulus is changed, either with the dialog or by a stimulus demonstration, the corresponding timeline (middle of Figure 6) shows only the responses corresponding to that stimulus. The designer can edit the parameters of each response (x and y in Figure 6) and can click "Add/Edit Condition" to view and edit a graphical condition on the stimulus.

Because there is a timeline for each stimulus, and because operations, not object states, are recorded, the designer can specify interfaces in which objects behave asynchronously. Such asynchronous behavior cannot be specified, without programming, in conventional animation systems like Director.

For instance, consider an interface in which two objects follow their respective animation paths in response to button clicks on two different buttons. In Director, the animation paths of each object must be stored in separate parts of the single timeline (e.g., frames 2-20, and frames 21-50, respectively). At run-time, when a button-click occurs, the system changes the global time-frame to the corresponding animation path. Whatever animation paths were already in progress are stopped, as each object has a fixed state in the new time-frame. The only way to specify such interfaces in Director is through by-passing the timeline with Lingo puppet code.

With Pavlov, the animation paths are stored in separate timelines corresponding to each button-click. When an event (click) occurs, all the time-stamped operations in a timeline are readied for execution, along with other operations from other timelines. The operations are then executed, in order by time-stamp and independent of the timeline from which they arrived. Thus, in the example, both objects can follow their paths asynchronously. The reader is referred to [17] for a more detailed description of the differences between Director and Pavlov.

It should be noted that Pavlov's stimulus-response score is not used only to view and edit behaviors after the fact, but is integrated into the demonstration environment. For instance, the designer can choose a current stimulus in the score, instead of demonstrating it, if he knows its name and he doesn't need to graphically specify parameters for it. As mentioned above, he can also use the timeline in the score to specify timestamps prior to demonstrating responses.

5. SUMMARY
Many people use software, but few can create it. One of the only areas of creation open to most people is to build static web pages with one type of stimulus: the button click on a link. Stimulus-response systems can open up creativity by allowing people to build applications that come alive, both for the Web and for the desktop.

Our research has introduced some of the alternatives of stimulus-response system design, in terms of syntax, semantics, and feedback. The next step, we believe, is detailed empirical testing between alternatives, either through research or the widespread use that would occur if stimulus-response technology were added to a popular interface builder.

REFERENCES
1. Cypher, A.,Halbert,D., Kurlander,D., Lieberman, H., Maulsby, D., Myers, B. Turransky, A., eds. Watch What I Do: Programming by Demonstration. Cambridge, MA: The MIT Press, 1993.

2. Cypher, A., "Eager: Programming Repetitive Tasks by Example", Proceedings of CHI '91, ACM, New Orleans, May 1991, pp. 33-39.

3. Director 7.0, Macromedia, Inc., www.macromedia.com.

4. Halbert, D., "Programming by Example," Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley.

5. Frank, M.R. and Foley, J.D. “A Pure Reasoning Engine for Programming By Demonstration,” in Proceedings UIST'94: ACM SIGGRAPH Symposium on User Interface Software and Technology. 1994. Marina del Rey, CA: pp. 95-101.

6. Fischer, G.L, Busse, D.E., and Wolber, D. "Adding Rule-Based Reasoning to a Demonstrational Interface Builder", In Proceeding of UIST'92, pp. 89-97.

7. Kurlander, D. and Feiner, S., "Inferring Constraints from Multiple Snapshots", ACM Transcations on Graphics, May, 1991.

8. Lieberman, H., "Mondrian: A Teachable Graphical Editor", in Watch What I Do: Programming by Demonstration, Allen Cypher, ed., MIT Press, 1993.

9. McDaniel R., Myers, B., "Getting More Out Of Programming-By-Demonstration." Proceedings CHI'99: Human Factors in Computing Systems. Pittsburgh, PA, May 15-20, 1999. pp. 442-449.

10. Modugno, F., Corbett, A.T., and Myers, B.A., “Graphical Representation of Programs in a Demonstrational Visual Shell -- An Empirical Evaluation.” ACM Transactions on Computer-Human Interaction, 1997. 4(3): pp. 276-308.  

11. Myers, B.A., “Creating User Interfaces Using Programming-by-Example, Visual Programming, and Constraints.” ACM Transactions on Programming Languages and Systems, 1990. 12(2): pp. 143-177.

12. Myers, B., McDaniel,R.,Kosbie, D.,"Marquise: Creating Complete User Interfaces By Demonstration", Proceedings of INTERCHI '93, Amsterdam,April,1993,pp.293-300.

13. Smith, D.C., Cypher A., "KidSim: End-User Programming of Simulations", Proceedings of CHI ‘95,May 1995, pp.27-34.

14. Visual Basic, Microsoft, "msdn.microsoft.com/vbasic".

15. Wolber, D., and Fisher, Gene, "A Demonstrational Technique for Developing Interfaces with Dynamically Created Objects." Proceedings of UIST ‘91, pp. 221-230, November 1991.

16. Wolber, David, "An Interface Builder for Designing Animated Interfaces", Transactions on Computer-Human Interface( TOCHI), December 1997.

17. Wolber, David, "A Multiple Timeline Editor for Designing Multi-threaded Applications", Proceedings of the User Interface and Software Technology (UIST) Conference, San Francisco, California, 1998.