back to ...

Chapter
18 The AIDE Project:
An Application-Independent Demonstrational Environment

Philippe P. Piernot
and
Marc P. Yvon

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 a 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 dealing with this problem, are also discussed.

Introduction

Programming By Demonstration allows the end-user to create parameterized procedures by demonstration in order to extend an application and eliminate repetitive tasks [Myers 92d]. Many such systems have been implemented in various domains [Piernot 91] 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 the next section we describe the AIDEWORKBENCH. Then we provide an overview of SPII, a general purpose object-oriented graphical editor built using this workbench, and gives examples of macros that can be created by demonstration. Finally, we discuss the way users can express their intentions in AIDE-based applications.

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 (e.g.. 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 architecture, 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 (e.g.. 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 does not solely rely on window coordinates (i.e. recording a low-level event such as a click on file "foo.bar" can only be executed again if the file icon's 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 integrate advanced macro recording capabilities into 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).

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's goal is to create a program from a user trace by generalizing it. Thus, the dialog between the AIDE-based application and the AideEvent Manager is different when teaching or executing macros.

When in teaching mode (i.e. a macro is being recorded), the AideEvent manager asks the AIDE-based application to enrich the event with contextual information i.e. 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 AideEvent 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 AIDE-based application to return an instantiation of such an event (a "regular" HLE obtained from the generalized one, which the application can then execute), stores it, and passes it to the AIDE-based application for execution.

Figure 1. The Architecture of the AideWorkbench.

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.

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 "contextual information provided by the

9/5 7/2); 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: #resizeGen:; "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: #resizeCxt:; "name of a method defined in the sender's

class filling the contextArgs slot"

mergeMth: #resizeMrg: "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 (see Chapter 22). 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 [Kurlander 90]:

(select)*; select "merge select events"

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

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

x objects"

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 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 Lieberman's Mondrian system, 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.

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.

Figure 2. The dialog between an AIDE-based application and the AideEvent manager in teaching mode.

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.

Figure 3. The dialog between an AIDE-based application and the AideEvent manager in macro execution mode.

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

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 (i.e. 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 -- i.e. 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 accommodate other objects.

Much of the inference engine power resides in the way sequences are handled, which is inspired by Eager [Cypher 91a] and by Michalski's descriptors [Michalski 83]. 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. For instance, the sequence resulting from the match of a linear sequence with an increment of 2 and a linear sequence with an increment of 3 will be an increasing sequence. This last feature is used by the Give Another Example command.

The following shows how three resize HLEs as defined in the "AideEvents" section 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 below.

The SPII Prototype

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.

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 (i.e. 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.

Figure 4. Star Macro: connects the first box in the selection to all the other boxes in the selection.

Table 1. Trace for the Star Macro.

step  figure       event        do       context arguments                       
 #       #         name        args   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 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:

* objects from the second position up to the fourth in the selection list (when starting from the beginning) are being successively selected;

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

* objects from the third position down to the first in the selection list (when starting from the end) are being successively selected.

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

Table 2. Generalization of the Star Macro trace. "2 to lnArgLst 1" stands for "2 to length Argument List by 1".

steps     event       index in argument         
                      list                      
coalesce  name        from beg.  from end    
d                                            
 1        Deselect                           
          All                                
 2        Select      1 to 1     4 to 4 by    const: 1                      
                      by 0       0                                           
 3 6 9    Add Select  2 to 4     3 to 1 by   2 to lnArgLst 1                
                      by 1       -1                                          
 4 7 10   Connect                                                            
 5 8 11   Deselect    2 to 4     3 to 1 by   2 to lnArgLst 1                
                      by 1       -1                                          
12 13 14  Add Select  2 to 4     3 to 1 by   2 to lnArgLst 1                
                      by 1       -1

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.

Figure 5. The Complete Graph Macro creates a Complete Graph from a set of boxes.

Specifying Users' 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 [Maulsby 89b] uses construction tools such as a sweep-line when sorting objects. SmallStar [Halbert 84] and Leda [Mima 91] enable the user to explain how to choose a target object using a data description mechanism, and they also allow the user to explicitly define control structures. Moctec [Maulsby 92a] 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 intent.

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, the user 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 and Kurlander's search and replace [Kurlander 92b]. In the SPII prototype (see the figure at the beginning of the chapter), the first menu is an option to look for objects satisfying or not satisfying the search pattern. The second line describes the search pattern itself and is composed of three elements: a property (e.g. 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:

Figure 6. Find Smallest Black Rectangle Macro.

1. Deselect All

2. Search
Select items 'verifying:'
'class' 'is' 'Rectangle'
from: 'outside the selection' "since the selection is empty,
Sort them by 'any order' search in the whole window"

3. Search
Select items 'verifying:'
'color' 'is' 'black'
from: 'inside the selection' "search should occur in the
Sort them by 'size' 'increasing x' already selected rectangles"

4. Deselect all elements but the first
one in the selection list

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 an algorithm into 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).

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 the "AideMacros as user-defined AideEvents" section, 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).

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 [Kurlander 90] and anticipation [Cypher 91a]. 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.

Acknowledgments

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.

AIDE

Uses and Users

Application domain: application-independent

Intended users: non-programmers

User Interaction

How does the user create, execute and modify programs?
The user turns on recording and gives an example of the procedure. Each command is recorded and displayed in a VCR-like window (enabling unlimited-depth undo).
The user can specify data descriptions through a search dialog box.
The user can modify incorrect generalizations by giving additional examples. Undo can be applied to macros.
Macros can be selected from a menu or attached to a high-level event.

Inference

Inferencing:
Aide tries to merge high-level events of the same class into a new event of the same class with generalized arguments. Loops are detected by finding a sequential pattern between two or more events.

Types of examples: Multiple examples

Program constructs: Parameterized procedures; loops, but no nested loops; no conditionals.

Knowledge

Types and sources of information:
Aide has some knowledge about various sequences (textual, graphical, numerical) and about loop creation.

Implementation

Machine, language, size, date: Smalltalk V on a Macintosh LC, 4000 lines of documented code, 1992.

Notable features

* An unlimited undo/redo capability (works for macros).
* Search dialog for specifying the user's intent.
* Can be easily extended to cope with various application domains thanks to object-orientedness.
* The current selection is used both as a macro argument list and as a return value.