[Phil's Home: www.piernot.com]
Published in Watch What I Do: Programming by Demonstration, Allen Cypher, MIT Press, Cambridge, MA, 1993, pp. 382-401.

THE AIDE PROJECT:
AN APPLICATION INDEPENDENT
DEMONSTRATIONAL ENVIRONMENT

Philippe P. Piernot and Marc P. Yvon

Ecole des Hautes Etudes en Informatique
Université René Descartes
45, rue des Saints-Pères 75006 Paris - France

piernot@ehei.ehei.fr, yvon@ehei.ehei.fr

 

ABSTRACT

The AIDE project intends to provide developers with a system substrate for application-independent Programming By Demonstration (PbD). The AIDEWORKBENCH allows a developer to add advanced macro capabilities to his Smalltalk-based application (whatever it is) without re-implementing everything from scratch. We first introduce the workbench by describing its general architecture and its main components: high-level events, macros, and an "intelligent" event manager. Then we present SPII, a general purpose graphical editor supporting PbD, which has been implemented using the workbench. A major problem arising in the domain of PbD is how to express users' intentions. Some features of the workbench, particularly well suited to deal with this problem, are also discussed.

KEYWORDS: Demonstrational interfaces, programming by demonstration, macros, high-level events, end-user programming, machine learning.

1. INTRODUCTION

Programming By Demonstration allows the end-user to create parameterized procedures by demonstration in order to extend the application he is working with and to eliminate repetitive tasks [9]. Many such systems have been implemented in various domains [10] including graphic drawing, text editing and formatting, desktop manipulation, user interface creation, robotic assembly tasks and general programming. Moreover, commercial products which include demonstrational aspects, such as Excel 4.0 with its autofill feature or NewWave 4.0 with its agents, are emerging in the mass market.

Even though each PbD system has been written from scratch, requiring tedious coding, most of these prototypes share common components among which we find high-level events, a trace recording feature and a machine learning mechanism. The AIDE project tries to provide the developer with an application-independent Smalltalk-based environment for quickly implementing PbD-aware applications. In section 2 we describe the AIDEWORKBENCH. Section 3 overviews SPII, a general purpose object oriented graphical editor built using this workbench, and gives examples of macros that can be created by demonstration. In section 4 we discuss the way the user can express his intention in AIDE-based applications.

2. A WORKBENCH FOR DEMONSTRATIONAL INTERFACES

Interaction with an application's user interface generates a sequence of elementary mouse and keyboard operations, also called low-level events (eg. mouseMove, mouseButtonDown, keyPressed...). Until the AppleEvent architecture appeared, most applications directly determined their answer to a given stream of incoming events, thus preventing other applications from efficiently communicating with them. For example, the only way a macro recorder such as MacroMaker can control an application is by sending it low-level events. But in the new AppleEvent archictecture [1], the application's user interface sends high-level AppleEvents via the AppleEvent Manager to the application's body for execution. This model of handling input is of great interest for general PBD systems. Indeed, a high-level event (HLE) is a richer way of representing an application command (eg. drawLineFrom: (17,55) to: (187,140)) than the corresponding stream of low-level events (here: mouseButtonDown, mouseMove, mouseMove, ..., mouseMove, mouseButtonUp). An HLE can be more easily manipulated by a learning algorithm, and doesn't solely rely on window coordinates (ie. recording a low-level event such as a click on file "foo.bar" can only be executed again if the file icon absolute coordinates stay the same). An event manager receives HLEs coming from any application, therefore enabling cross-application trace recording, and can control applications by sending them HLEs.

The AIDEWORKBENCH is designed to help software developers to integrate advanced macro recording capabilities to their applications. To do so, the developer has to conform to our model of handling input by sending AideEvents (HLEs of a specific format) to the AideEvent Manager (an event manager including an inference engine).

2.1. Architecture of the AIDEWORKBENCH

Our architecture (see figure 1) is close to the AppleEvent model in that an AIDE-based application is responsible for mapping a stream of low-level events to an AideEvent and sending it to the AideEvent Manager. The AideEvent Manager stores the HLE, merges it if necessary with other HLEs to form a higher-level event, checks if a macro should be invoked by this event (and does so if it is the case), and asks the application to perform the command associated with it. Up to this point, the dataflow is similar to the AppleEvent one. But in the AppleEvent model, the purpose of the AppleEvent Manager is to assist applications in resolving complex object specifiers, whereas the AideEvent Manager goal is to create a program from a user trace by generalizing it, thus the dialog between the application and the AideEvent Manager is different when teaching or executing macros.

When in teaching mode (ie. a macro is being recorded), the event manager asks the application to enrich the event with contextual information ie. information providing semantics to an HLE. Thus, in a word processor, the context associated with the command for selecting a word could contain the word itself, its position from the beginning and the end of the line, its style etc. Then the event manager looks for loops and generalizes HLEs.

When in macro execution mode the AideEvent manager gets generalized AideEvents from the definition of the macro, asks the application to return an instantiation of such an event ("regular" HLE obtained from the generalized one, which the application can then execute), stores it, and passes it to the application for execution.

 

The dialog between an AIDE-based application and the AideEvent manager occurs by the exchange of AideEvents. These, AideMacros, the AideEvent Manager and the generalization process are described next.

2.2. AideEvents

AideEvents form the heart of our system because they convey high-level information about the commands being executed. An AideEvent is a Smalltalk object with a name (describing the associated command), a sender (the application which generated it), and a set of arguments including parameters (used for doing and undoing the command) and contextual information (information about the state of the application after the event has been executed). Moreover, each event refers to specific methods defined in the sender's class, in order to execute/reverse, to generalize/instantiate itself, or to provide contextual information. AideEvents are reported to the AideEvent Manager by trigger methods implemented in the application. These methods are defined outside HLE records since their purpose is to create them. For example, an AideEvent produced by a graphic editor might look like the following:


AideEvent new

  name: 'Resize'; "event name"
  sender: aGraphicEditor; "application which generated this event"
  doArgs: #(4 9 94 79); "arguments used by the doMth (new frame)"
  undoArgs: #(4 9 54 29); "arguments used by the undoMth (old frame)"
  contextArgs: #(90 70
9/5 7/2);
"contextual information provided by the contextMth.
Here, the new size and the ratio
between the new size and the old size."
  doMth: #resizeDo:; "name of a method defined in the sender's class
in charge of performing the command. In this
example, resizing an object in the window"
  undoMth: #resizeUndo:; "name of a method defined in the sender's class
responsible for reversing the command. In this
case, restoring the object size"
  generalizeMth: #resizeGeneral:; "name of a method defined in the sender's class
returning a generalized event by coalescing it
with another one (overrides the default behavior)
  instantiateMth: #resizeInst:; "name of a method defined in the sender's class
returning an instantiation of a generalized event"
  contextMth: #resizeContext:; "name of a method defined in the sender's class
filling the contextArgs slot"
  mergeMth: #resizeMerge: "name of a method defined in the sender's class
that tries to merge this event with previous ones"

In this example, the trigger method would test whether an object handle is clicked, and if so, would draw a rubber-band rectangle until the mouse button is released. Then, it would generate an HLE where the do/undo args slots would be filled, and send it to the AideEvent Manager for processing.

AideEvents act in a very simple fashion: when they receive messages from the AideEvent Manager like do, undo, fillContextArgs, generalize or instantiate, they just call the appropriate method of the application.

Moreover, AideEvents can be composed of other AideEvents, thus allowing multiple level undo/redo and adding robustness to the inference engine. This idea of aggregate HLEs came from David Kosbie's model. For example, successively moving the same object will create a "global move" AideEvent from the object's original position to its last position, and this global event will contain elementary move AideEvents. This allows the user to adjust the position of an object after moving it, without disturbing the inference engine which will only take into account the "global move" HLE. AideEvents are executed and merged with the higher-level AideEvent until a non-mergeable event arrives. The way events are merged to form higher-level events is described by a method referenced in the HLE mergeMth slot and defined in the sender's class. We use the same kind of regular expression rules as in [4]:

(select)*; select "merge select events"
(move)*; move "merge move events operating on the same objects"
(resize)*; resize "merge resize events operating on the same objects"

2.3. AideMacros as user-defined AideEvents

AideMacros are user-defined procedures operating on an ordered collection of arguments. We hardly differentiate between AideEvents and AideMacros. They both have a name, arguments, can be done and undone etc. In fact, the AideMacro class is implemented as a subclass of AideEvent. Teaching a macro is initiated by choosing either the Record New Macro or Give Another Example menu options, giving a name, demonstrating the macro on a concrete example, and at last selecting the Stop Recording menu entry. In our system, the user may explicitly call a macro by selecting it in the application's "Macro menu", as well as associate an AideEvent with a macro. In this last case, the macro will be triggered each time the corresponding AideEvent is sent to the event manager, either before, after or instead of this HLE (whereas in David Kosbie's architecture macros can be invoked by any event). The ability to provide more than one example trace for a given macro (using the Give Another Example command) allows the user to correct some incorrect generalizations.

As in Mondrian, the argument list is the ordered collection of the objects selected before invoking the macro. Then, the returned value consists of the selection list after the macro execution. Consequently it is possible to chain macros, arguments being passed through the selection list. Macros can call other macros and support recursion. When a macro is executed, generated AideEvents are passed to the AideEvent Manager which stores them as sub-events of the call-macro event (this means that during macro execution each AideEvent is merged with the call-macro HLE). Therefore, the results of a macro invocation can be undone by successively undoing the sub-events. To prevent double execution of a macro when redoing it, the sub-events are redone instead of the macro itself. We think that the capability to undo macros is crucial.

2.4. The AideEvent Manager

Each time an AIDE-based application receives a low-level event, it checks whether it is possible to generate an HLE by using one of the application trigger methods. If so, it creates a new instance of AideEvent, fills its doArgs and undoArgs slots (perhaps interacting with the user, as in the resize command example), and then passes it to the AideEvent Manager. The latter stores the incoming event in the user's trace list, merges it with another event if possible, triggers a macro if necessary, and sends the HLE back to the application for execution. If a macro is triggered by the AideEvent, it is performed before, instead of, or after the HLE, according to the user's choice. The application executes the HLE by performing the method whose name and arguments are respectively in the doMth and doArgs slots of the HLE. The application then gives control to the event manager.

When the system is in teaching mode, it has the following additional steps (see figure 2 which illustrates the dataflow between an AIDE-based application and the AideEvent Manager). First the AideEvent Manager asks the application for contextual information (by calling the contextMth), receives back an enriched HLE, then searches loops and tries to generalize the HLE by comparing it with previously recorded HLEs (using a default generalization scheme or the event generalizeMth). Contextual information plays an important role because it helps the inference engine to guess the user's intentions. At last, the generalized HLE is stored in the macro definition and the AideEvent Manager waits for other incoming HLEs.

 

The behavior of the event manager in macro execution mode is depicted in figure 3. Here, the AideEvent Manager picks up a generalized event from the macro definition, sends it to the application for instantiation (by a call to the instantiateMth which gives values to arguments), gets back a "regular" AideEvent, stores it, and merges it with the call-macro HLE. Then it passes the HLE again to the application for execution and picks up another generalized event until the end of the macro is reached.

 

This AideEvent Manager also supplies a VCR-like interface (see the figure at the beginning of the chapter) in order to browse the user's trace and to undo/redo commands across applications.

2.5. The generalization process

When generalizing a trace to create a macro, the AideEvent Manager first tries to find loops by coalescing enriched high-level events. Two events can be coalesced if they have the same name (ie. they represent the same command) and the same sender, and if this does not create a branch exiting a loop. The second step consists of generalizing arguments - ie. finding variables and constants. To do so, the system tries to infer various sequences, based on previous arguments values. The sequences that are recognized include numeric sequences (constant, linear, increasing, decreasing), string sequences (common substrings, days, months), point sequences (consisting of two numeric sequences), and class sequences. The set of sequences can be easily extended to accomodate other objects.

Much of the inference engine power resides in the way sequences are handled, which is inspired by Eager [2] and by Michalski descriptors [7]. A sequence is created by giving its two first values, then adding other values for example. In the case of a linear descriptor, giving 4 and 9 as first and second values would create the linear sequence 4 to 9 by 5. Adding 14 as a third value would update this sequence to 4 to 14 by 5. Now if 15 was the fourth value, the sequence would become an increasing sequence from 4 to 15. For class sequences, the class attribute is a structured descriptor and the rule used is the climbing generalization tree rule. Moreover, sequences can be matched with other sequences, allowing generalization between two generalized macro traces. This last feature is used by the Give Another Example command.

The following shows how three resize HLEs can be generalized:

event doArgs undoArgs contextArgs  
resize #(4 9 94 79) #(4 9 54 29) #(90 70 9/5 7/2)
resize #(2 2 94 58) #(2 2 25 18) #(92 56 4 7/2)
resize #(6 3 94 73) #(6 3 50 23) #(88 70 2 7/2)
 
resize #(? ? 94 ?) #(? ? ? ?) #(? ? ? 7/2)

The generalized event is obtained by combining all of the arguments (doArgs, undoArgs and contextArgs) from the first event with the corresponding arguments from the second and third events. In this case the generalized event interpretation is that the user resizes objects so that their bottom-right x coordinate equals 94 and their height is 7/2 times higher than the old one. A more complex example is given in section 3.2.

3. THE SPII PROTOTYPE

3.1. Overview

SPII, which stands for Smalltalk-based Predictive Iconic Interface, is a generic object-oriented graphical editor dealing with user interface creation, technical drawing and graph editing. In this editor, the user can select, deselect, move, resize, create, delete, edit and connect objects by direct manipulation. These objects are geometric shapes, interface widgets or user-defined. We used SPII for an application consisting of setting-up a local area network in a computer room as well as for creating a CAD program specialized in cooling circuitry for a satellite. SPII is built on top of the AIDEWORKBENCH and makes profitable use of its macro facilities.

3.2. Macros in SPII

Figure 4 illustrates the teacher creating the Star macro, given as input the current ordered selection list (figure 4a). The task consists of connecting the first box in the list to the remaining boxes of the list. The teacher begins by deselecting all the boxes and selecting box A, which was previously the first element in the selection list (figure 4b-c). Then, for each remaining box (ie. B, C, D), the teacher successively selects the box, calls the connect command and deselects the box (figure 4d-f). At the last step (figure 4g), the user reselects the elements B, C, D; thus, the macro output contains the same elements as the input after they have been connected. This same macro can be used again for selection lists of different sizes.

Table 1 shows the user's trace which is a collection of enriched HLEs. Step 0 represents the selection list before recording the macro. For the other steps, we give the event name, the doArgs (name of the objects being manipulated) and the contextArgs. In the "context arguments" column, indexes "from beg." and "from end" refer to the position of the objects being selected or deselected, starting from the beginning or the end of the initial selection list (step 0). Other context arguments also exist for the select/deselect commands but they have been dropped because they were not significant in this example. Such arguments include object properties like class, position, color, size etc. In the Star macro, the criterion for selecting/deselecting objects was their index in the initial selection list, but because of the other context arguments, other criteria could have been objects whose name ends with ".bak" and/or whose color is black.

 

 

 

step
#

Figure
#

Event
name

Do
args

context arguments

index in argument list

       

from beg.

from end

0

4a

   

#('A' 'B' 'C' 'D')

1

4b

Deselect All #()    
2

4c

Select #('A')

1

4

3

4d

Add Select #('B')

2

3

4

4d

Connect #()    
5

4d

Deselect #('B')

2

3

6

4e

Add Select #('C')

3

2

7

4e

Connect #()    
8

4e

Deselect #('C')

3

2

9

4f

Add Select #('D')

4

1

10

4f

Connect #()    
11

4f

Deselect #('D')

4

1

12

4g

Add Select #('B')

2

3

13

4g

Add Select #('C')

3

2

14

4g

Add Select #('D')

4

1

Table 1. Trace for the Star Macro.

Table 2 illustrates the generalization of the enriched HLEs. The AideEvent Manager finds a first loop by coalescing steps 3/6/9, 4/7/10 and 5/8/11, and a second loop by coalescing steps 12/13/14. Each step is stored in a list corresponding to the trace, the loops being represented by sublists. In this case, the list is:

(DeselectAll Select (AddSelect Connect Deselect) (AddSelect))

In the latter loop (see the last line of Table 2), the generalization of the "from beg." context argument is that:

whereas the generalization of the "from end" argument is that:

By combining both generalized indexes when replaying this HLE, the AideEvent Manager will issue events selecting objects whose position goes from the second one to the last one in the selection list (starting from the beginning).

 

steps
coalesced

event
name

index in argument list

 

from beg.

from end

 
1 Deselect All      
2 Select

1 to 1 by 0

4 to 4 by 0

 const: 1
3 6 9 Add Select

2 to 4 by 1

3 to 1 by -1

 2 to length argList by 1
4 7 10 Connect      
5 8 11 Deselect

2 to 4 by 1

3 to 1 by -1

 2 to length argList by 1
12 13 14 Add Select

2 to 4 by 1

3 to 1 by -1

 2 to length argList by 1

Table 2. Generalization of the Star Macro trace.

The second example (figure 5a-f) emphasizes how to create more complex macros by calling previously defined macros and passing arguments through the selection list. Here we want to create a complete graph by using the Star macro and iterating over a set of boxes. This macro works on cases that do not have exactly 4 inputs.

 

4. SPECIFYING USER'S INTENTIONS IN AN AIDE-BASED APPLICATION

Inferring the user's intentions is a crucial problem for Programming By Demonstration. Nevertheless, sometimes making the right inference is intractable for current learning algorithms, even if more than one example is supplied. That is why various techniques have tried to provide the user with the ability to guide the PbD system. Metamouse [6] uses construction tools such as a sweep-line when aligning objects. Smallstar [3] and Leda [8] enable the user to explain how he chooses a target object using a data description mechanism, and they also allow the user to explicitly define control structures. Moctec [5] enables the user to relate objects by popping up a contextual menu. We now present how the user can take advantage of some features of an AIDE-based application to specify his intentions.

4.1. Showing how to choose an object  

We have decided to encourage the developer to implement a powerful search command in his or her application by supplying a default one. With such a tool, the user can find objects sharing common properties. To do so, he has to specify a search pattern to the system by creating a sentence using popup menus in a dialog box, such as in the System 7 finder. In the SPII prototype (see the figure at the beginning of the chapter), the first menu indicates whether the object he is looking for has to verify or not the search pattern. The second line describes the search pattern itself and is composed of three elements: a property (eg. name, location, size, color, class), a predicate (startsWith, endsWith, contains, leftOf, rightOf, topOf, bottomOf, is, =, >, isSubclassOf) and a value. In the next line, the user specifies where the search should occur (inside the already selected elements or outside the selection). The last line presents the choice of sorting the items in a specific order: the first word describes which property is significant while the second word indicates the desired type of sorting. Relatively complex queries (containing and, or, not operators) can be created by combining calls to the search command. When this command is invoked, a high-level event is generated. This event conveys information on why an element has been selected. For example, in order to find the smallest black rectangle in the whole window, the user could:

 

1. Deselect All

2. Search
  Select items 'verifying:'
'class' 'is' 'Rectangle'
from: 'outside the selection'
Sort them by 'any order'


"since the selection is empty,
search in the whole window"
3. Search
  Select items 'verifying:'
'color' 'is' 'black'
from: 'inside the selection'
Sort them by 'size' 'increasing x'


"search should occur in the
already selected rectangles"
4. Deselect all elements but the first
  one in the selection list  

Figure 6. Find Smallest Black Rectangle Macro.

4.2. Helping to find control structures 

Constructs such as nested loops subroutine calls and recursion are difficult to infer, so giving the system a hint can be very useful. In an AIDE-based application, the ability to call a macro from another macro allows the user to divide his algorithm in smaller parts, thus alleviating the inference engine task. For example, the user could have taught the complete graph macro without creating the star macro. But the example size would have increased and the inference engine would have had to guess nested loops instead of simple ones. We also think "dividing macros" is more natural than explicitly adding control structures (as in Leda or Smallstar).

4.3. Providing the proper arguments & bounding the search 

However, explicitly providing arguments to a command is sometimes the only viable solution. Since the event recording mechanism works across applications, complex relationships between objects can be specified by copying and pasting from one AIDE-based application to another one. We plan to implement a SMARTCALCULATOR - essentially the same as Halbert's calculator in Smallstar - using the workbench, so that the user will be able to create formulas linking objects together.

As we explained in section 2.3, the selection list before a macro creation represents the focus of interest. Much inference is done with respect to this list. This is a very convenient way to narrow the search space when looking for contextual information (in SPII, scanning objects is done in the selection list rather than in the whole window).

5. CONCLUSION 

Other features will be added to the current AIDEWORKBENCH, which is still being improved, such as conditionals, default contexts, visual feedback mechanisms like graphical histories [4] and anticipation [2]. Moreover, besides SPII, another AIDE-based application, the SMARTBROWSER, is being implemented. This application extends the Smalltalk programming environment by supplying advanced macro capabilities to the class hierarchy browser (a tool used to create and delete classes, define and edit methods). Implementing new prototypes of different application classes - using the workbench - will allow us to make the AIDEWORKBENCH as generic as possible.

ACKNOWLEDGEMENTS 

Major support for the work described in this paper was provided by the Centre National de la Recherche Scientifique and the Centre National d'Etudes des Télécommunications. For help with this paper, we would like to thank our thesis advisor Norbert Cot, as well as Eric Ghestem and Isabelle Borne. We gratefully acknowledge the key role Allen Cypher has played in helping us develop these ideas.

REFERENCES 

  1. Apple Computer, Inside Macintosh, Vol. 4, Addison-Wesley.
     
  2. Cypher A., "Eager: Programming Repetitive Tasks by Example," Proceedings of SIGCHI '91, ACM, New Orleans, May 1991, pp. 33 - 39.
     
  3. Halbert D., "Programming by Example," Technical Report OSD-T8402, Xerox Office Systems Division, December 1984.
     
  4. Kurlander D. and Feiner S., "A Visual Language for Browsing, Undoing and Redoing Graphical Interface Commands," Visual Languages and Visual Programming, Plenum Press, New York, 1990.
     
  5. Maulsby D., "Prototyping an Instructible Interface: MOCTEC," Proceedings of SIGCHI '92, ACM, Monterey, May 1992, pp. 153 - 154.
     
  6. Maulsby D. and Witten I., "Teaching a Mouse How to Draw," Proceedings of Graphics Interface '89, London Ontario Canada, June1989, pp. 130 - 137.
     
  7. Michalski R., "A Theory and Methodology of Inductive Learning," Machine Learning, An Artificial Intelligence Approach, Morgan Kaufmann, 1983.
     
  8. Mima Y., "A Visual Programming Environment for Programming by Example abstraction," Proceedings of IEEE Workshop on Visual Languages '90, Kobe, Japan, October 1991, pp. 132 - 137.
     
  9. Myers B., "Demonstrational Interfaces: A Step Beyond Direct Manipulation," IEEE Computer, Vol. 25, No. 8, August 1992, pp. 61 - 73.
     
  10. Piernot P. and Yvon M., "Interfaces Graphiques Intelligentes: Le Cas des Interfaces Démonstrationnelles," Internal Document, Ecole des Hautes Etudes en Informatique of Paris, December 1991.