back to ... Table of Contents Watch What I Do
The AIDE Project:
An Application-Independent Demonstrational Environment
Philippe P. Piernot
Marc P. Yvon
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.
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
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
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
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.
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 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
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
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
instantiateMth: #resizeInst:; "name of a method defined in the sender's
class returning an instantiation of a
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
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
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
Figure 2. The dialog between an AIDE-based application and the
AideEvent manager in teaching mode.
Figure 3. The dialog between an AIDE-based application and the
AideEvent manager in macro execution mode.
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.
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
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
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
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
coalesce name from beg. from end
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
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"
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
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).
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.
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.
Uses and Users
Application domain: application-independent
Intended users: non-programmers
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.
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.
Types and sources of information:
Aide has some knowledge about various sequences (textual, graphical, numerical) and about loop creation.
Machine, language, size, date: Smalltalk V on a Macintosh LC, 4000 lines
of documented code, 1992.
* 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.
back to ... Table of Contents Watch What I Do