back to ... Table of Contents Watch What I Do
A SmallStar program icon, the program it contains, and the data description sheet for an operand in the program.


Programming by Demonstration
in the Desktop Metaphor

Daniel C. Halbert


SmallStar is a working simulation of the Xerox Star office information system, with programming by demonstration added. I developed SmallStar during 1980-1984 as part of my doctoral research; my motivation was to make it possible for users to program the systems they used.

SmallStar showed that programming by demonstration could be a valuable and practical addition to application software. In this chapter, I will describe the Star and SmallStar systems, and how users create programs by demonstration in SmallStar. SmallStar introduced the idea of data descriptions, which describe the data to be used when running a program recorded by demonstration. I will explain the motivation for data descriptions, and how they are used. I will also show how SmallStar allows conditionals and iteration to be added to a recorded program by editing its transcript. Finally, I will discuss some user tests of SmallStar, and summarize the results of this research.

In my original research, I used the term "programming by example". This book uses "programming by demonstration" to mean the same thing, and I will use that term in this chapter.

Programming by demonstration

A system that provides programming by demonstration satisfies two key criteria: When I first started work on SmallStar, few software applications were using programming by demonstration. Various text editing systems provided "macro" facilities to record sequences of editor commands; Emacs [Stallman 87] is a good example. Programming by demonstration had also been tried with typescript command languages [Waterman 78] [Faught 80a] [Faught 80b]. However, these systems were limited and could record only relatively simple programs.

The pioneering Pygmalion system (Chapter 1) and the Tinker system (Chapter 2) demonstrated more sophisticated use of programming by demonstration, by showing how it could be used in general-purpose programming systems. Pygmalion uses a special visual language in which operations are performed using direct manipulation. Tinker uses Lisp as its base programming language. These systems assume some familiarity with programming and are not directed toward any specific application.

I had different users in mind. I wanted to show that programming by demonstration could be widely understood and employed by users of application software who were not programmers. With programming by demonstration, they could automate the repetitive tasks they performed in their daily work.

The Xerox Star System

SmallStar is based on the Xerox Star system. Star was an ideal starting point for showing the utility of programming by demonstration: it is a general-purpose office system, providing text and graphics editing, filing, printing, mailing, forms processing, and database functions [Smith 82a] [Smith 82b]. Star was also interesting because it has a graphical, direct manipulation user interface; it pioneered the desktop metaphor and the use of icons, and was the forerunner in the commercial use of the mouse as a pointing device.

Figure 1. A Star desktop.

Figure 1 shows a typical Star desktop. The icons on the desktop include documents, folders, file drawers (directories on remote file servers), printers, and in- and out-boxes. Every icon has a name. Two icons may have the same name even if their contents differ. In Figure 1, a document and a folder have been opened; their contents are shown in the two windows.

Star documents can contain text and graphics, tables (with named columns and numbered rows), and fields, which are named regions in the text that hold data.

Along the top of the desktop is a one-line message area that displays errors and informational messages. To the right of the message area is a small box with three horizontal lines, which indicates that a pop-up menu is available at that spot.

Four keyboard commands can be applied to nearly all Star objects. These universal commands are Move, Copy, Delete, and Properties; they apply to the current selection. To delete some text, one selects the text and presses Delete. To copy a document, the user selects the document and then presses Copy. The mouse cursor changes into a small document icon. The user then sets down the copy by clicking the mouse over the desktop, or over, say, a folder; the latter action inserts the copy into the folder.

Pressing the Properties key brings up a dialog box that displays the properties of the current selection, and allows properties to be changed. For instance, if a paragraph is selected, pressing Properties will display a dialog box that describes the paragraph's margins, line spacing, and so forth.

This description does not begin to do justice to Star, which was remarkable in the richness of its functionality at its introduction. Even today, its seamless integration is enviable. Users did not think of it as a collection of different applications, but instead as a powerful, multifunctional whole.

User programming in Star

Star provides a programming language called Cusp (for Customer Programming), so that users can automate the procedures specific to their particular applications. Cusp's commands cover part, but not all of Star's functionality; certain tasks that can be done manually in Star cannot be programmed in Cusp. In the following example of typical Cusp, CreditBalance is the name of a field in a document.

IF CreditBalance > 0 THEN
MOVE THE Document WHOSE NAME IS "Please Pay" TO
THE Printer WHOSE NAME IS "Gutenberg";

A Cusp program can be put into a Cusp button, which lives in a document, and which executes the program when pressed.


SmallStar is a reimplementation of part of the Star system. It was impractical to modify Star to add programming by demonstration. I therefore built a simplified version of Star using the Smalltalk programming system. Though SmallStar lacks much of Star's functionality, it implements or simulates documents, folders, file drawers, printers, text editing, tables, and fields. SmallStar's windows and property sheets are simplified versions of those in Star.

Figure 2. A SmallStar desktop.

SmallStar also adds features which Star does not have. Most notably, it has program icons and buttons, which are used to hold programs written by demonstration. Figure 2 shows a typical SmallStar desktop.

Recording programs

I designed the SmallStar recording mechanism to be low overhead, to make it as easy as possible for a user to record a temporary program to do some repetitive task. To write a program by demonstration in SmallStar, a user asks the system to record his or her actions. The user starts the recording process by opening a program icon or button and pressing the Start Recording command in the resulting window (see Figure 3). The Start Recording command can also be invoked from a pop-up menu available from a closed program icon or button. After starting recording, the user goes through the actions of the task to be recorded. When the task is completed, the user invokes the Stop Recording command.

SmallStar not only records the program, but also displays the resulting transcript in a human-readable form. Figure 3 shows a program window containing a very simple program. If the window is open during program recording, SmallStar adds user actions to the program transcript as they are performed.

Figure 3. A program to move a named document out of a folder.

The transcript language is English-like and was inspired by Cusp. It imposes little non-natural-language syntax or semantics on the user. Small pictographs stand for icons and other Star objects, such as text selections, components of tables, and the like. The transcript language is meant to be read, not written; the user cannot write a program without invoking the recording mechanism.

SmallStar records only the user actions that cause state changes, and does not record simple selection of Star objects. For instance, when an icon is selected and deleted, SmallStar simply records the Delete action, instead of the selection of the icon and then the Delete. An earlier version of SmallStar did record Select as an action, but Select actions turned out always to be redundant to the operation of the program; they made the transcript longer but no clearer to the reader.

The user can edit the resulting program in simple ways, by recording new steps at any point in the program or by deleting existing steps. Such edits may make the program impossible to execute, but SmallStar does not attempt to ensure that it will be able to run an edited program.

To execute a recorded program, the user presses Run in the program window, or chooses Run from the program icon or button pop-up menu. Single-stepping the program is also possible, using the First Step (start from the beginning) and Step (continue stepping) commands. If the program encounters an error while running, it stops, displays an error message, and indicates which statement caused the error.

Determining the User's Intentions

A user operates on certain data objects when creating a program by demonstration, but does not necessarily tell the system how or why that data was selected. The user can choose a data object for one of several reasons: It is the last possibility that causes the most trouble in systems that provide programming by demonstration. The user can choose an object, but the system may have no idea why the user made the choice, because the user has not communicated his or her intentions to the system.

This problem is particularly acute when programming by demonstration in a direct manipulation system like Star. In a system with a typescript command language, a user may wish to delete all files ending in ".BAS", and can do so by typing something like "delete *.BAS". However, in a direct manipulation system, the user may simply select all the files ending in ".BAS" from a list and delete them. Suppose the list consisted of the files A.BAS, LETTER.TXT, and A1.BAS. The user would select A.BAS and A1.BAS, and then delete them. The user never gave an explicit search pattern for which files to delete. The system could make a guess, but the pattern could be "*.BAS", "A*.BAS", or even "A*.*". The system cannot know exactly what the user intended.

The problem can be stated in terms of the intensional (choosing by description) and extensional (choosing by direct reference) capabilities of the system. In a typescript system, the user is more likely to give intensional specifications (like "*.BAS"), which describe salient characteristics of the desired data objects. In a direct manipulation system, the user specifies most data objects extensionally by pointing at them.

A program that is recorded by demonstration in a direct manipulation system is therefore often incompletely specified. The user has chosen some data, but the computation to make the choice (a search, a pattern match, etc.) has been done in the user's head, and has not been communicated to the system. Yet it seems natural to the user, since it is exactly what the user would do when performing the task manually.

Somehow the user must communicate this missing intensional information to the system. One common method is to use inductive inference techniques. The system examines the user's choices, and tries to draw conclusions about the data the user chose. The user may do several examples, not just one. The system notes the differences and commonalities between the examples, and tries to determine what the user meant [Bauer 79] [Biermann 76b].

Inductive inference can work well, but if the number of possible interpretations is large, the user may have to give many examples. It may even be impossible for the user to make his or her intentions unambiguous just by giving examples. For instance, consider the list of files given in the example above. If the user deleted A.BAS in one example, and A1.BAS in another, the user's intentions would still be ambiguous, since a number of different search patterns could be derived from these two examples.

Specifying intentions in SmallStar

The example given above illustrates the basic problem with inductive inference. The system can guess what the user means, but it cannot be sure. It cannot read the user's mind. Because of this, I chose not to use inference techniques to try to determine the user's intentions in choosing a particular data object. Instead, during program recording, SmallStar chooses a reasonable intensional description for the object. SmallStar's choice may or may not match the user's intentions; if it does not, the user should change the description during or after recording.

Data Descriptions

In SmallStar, an intensional description for a data object is called a data description. Data descriptions are fundamental to the operation of programming by demonstration in SmallStar. They allow a user to specify his or her intentions about which data SmallStar should use when it runs a program.

SmallStar programs, such as the one shown in Figure 3, consist of operations, like Move and Copy, and operands, like the documents and folders listed in the program. The operands do not refer to data objects directly; instead they point to data descriptions. There are no constants in a SmallStar program. Every data object has a corresponding data description. Data descriptions are editable; the user may change them after recording the program.

As a program is being recorded, the system creates a data description for every newly referenced object. The system chooses a reasonable default description for the object. The choice is fixed, and does not change based on the example being given. For instance, SmallStar always assumes that icons are chosen because of their names. In an earlier version of SmallStar, the user had to specify the choice as the program was being recorded. This turned out to be distracting and intrusive, so I adopted the current technique of making a default choice during recording.

The program in Figure 3 contains references to two different data descriptions created during program recording. One description specifies a folder named "Negotiations"; the other is for a document named "Treaty". SmallStar originally chose descriptions that specify these icons by name. However, the user could later change these descriptions to choose the icons by other criteria.

Descriptions are created for all the objects referenced by the user during program recording, including those that are referenced indirectly. For instance, if the user selects a document in a folder, SmallStar creates a data description for the folder as well as the document. Every item on the path to an object is included, and the descriptions on a path are linked. Thus, in Figure 3, the description for the document contains an (invisible) reference to a description for the folder that contains it. When the program runs, SmallStar looks for a document named "Treaty" inside a folder named "Negotiations".

If an object is used more than once in a program, a new data description is not created for each use of that object. Instead, the second and subsequent references to the object all point to the same data description. If the user selects a use of a data description, all other uses of that description are outlined in gray. In Figure 3, the first use of the description for "Negotiations" is selected, and its other uses are highlighted.

When a SmallStar program runs, it uses its data descriptions to find the data objects needed by the program. The first time a data description is referenced, SmallStar searches for an object that matches the description, and remembers that object. If more than one object matches the description, one is chosen arbitrarily. Later uses of that same description skip the search process and use the object already found. The reuse of data descriptions is a fundamental heuristic. If the user refers to a data object more than once, the system assumes the uses are connected in intent; it does not assume that a second use of the same object is accidental. This heuristic works very well. Rarely does a user refer to the same object for a completely different purpose. However, exceptions occur, and there is a way to defeat the heuristic. Suppose, for instance, a user records a program to print two documents on two printers, and uses the same printer to print both documents when giving the example. Subsequently, the user may wish to use the same program to print on separate printers. The user can edit the program and change the second use of the printer to refer to a new, separate description. Conversely, there is also a way to merge two different operands so that they use the same description.

Data description sheets

As mentioned, users can change data descriptions after they have been created by SmallStar. To see and edit a data description, the user selects an operand in the program that uses the description and presses the Properties key. A window opens that resembles a property sheet, called a description sheet. The user may then look at the detailed description, and change it to suit his or her needs. If the user changes the description, the references to the description in the program transcript will change to reflect the new description.
Figure 4. A document data description sheet.

A number of different kinds of descriptions are provided for each kind of data object. The choices are listed in the description sheet. Some kinds of descriptions take parameters of various kinds, and those are listed as well. Inapplicable choices are grayed out. As an example, Figure 4 shows a data description sheet for a document. The main description choices are listed in the Choose using item; they are NAME, POSITION, PROMPT, and ANY.

If NAME is chosen, the system looks for a document whose name matches the pattern given in the Name Pattern parameter. The pattern may be a simple text string (here, "Treaty"), or may be a pattern such as "Chapter*", which would match any document whose name begins with "Chapter". Since icon names need not be unique, the Version choice further narrows the possibilities by allowing the user to specify date and time information constraining when the document contents were last changed.

If POSITION is chosen, the user can choose the FIRST or LAST document in a folder. Position on the desktop is not well-defined (there is no labeled grid), so this choice is displayed only when the document is inside a container such as a folder.

PROMPT requests SmallStar to ask the user to choose a document when the program runs. This makes the document a parameter in the program. The editable Prompt item specifies the text to use when asking.

Finally, ANY specifies that the user does not care which item is picked. For a single item, this is not very useful, but later I will show how this choice is used to indicate set iteration.

Consider this example of the use of a description sheet. Suppose the user wants to write a program that will move the first document out of the "Negotiations" folder. When the user first records the program, SmallStar will record the program shown in Figure 3, which specifies the document "Treaty" by name; that is the default. The user must change this description to reflect his or her intent. To do so, the user selects the description for "Treaty" in the program, opens its description sheet, changes the description from NAME to POSITION, and makes sure that Position is set to FIRST. After the user presses Done, the data description changes, and the program transcript is updated. The resulting program is shown in Figure 5.

Figure 5. A program to move the first document out of a folder.

As mentioned, data descriptions offer a simple alternative to multiple-example inductive inference, especially in systems where multiple examples are inconvenient or impossible to demonstrate. During user trials of SmallStar, I found that data descriptions were easy for users to understand.

One issue with data descriptions is that possible descriptions for a data object are chosen from a limited menu of possibilities. In SmallStar, I attempted to cover a number of possibilities on each description sheet, but the choices are by no means exhaustive. The user may want to use some description that is not covered by the description sheet.

A way around this problem, not implemented in SmallStar, would be to extend description sheets to allow new descriptions to be specified. However, some method must be provided for programming the search algorithms for new kinds of descriptions. If the system were powerful enough, the searches could be programmed by demonstration. But this will not always be possible in many systems, including SmallStar. Some other programming language may need to be provided. Unfortunately, users must then learn that language. The advantage of being able to program by demonstration, in the user interface of the system, will then be compromised.

Control Structure

So far, I have discussed writing straight-line programs by demonstration. However, much of the power of a computer comes from its ability to repeat actions and to choose what to do based on some test. SmallStar provides functionality for writing program loops that perform set iteration, and for adding if-then conditionals to a program recorded by demonstration. In both cases, the user makes these additions to a straight-line program by editing the program after it has been recorded.

Set iteration

To produce a program that iterates over a set of data objects, a SmallStar user first records an example that operates on a single element of the set. When I described how data descriptions work, I said that a data description searches for a single data object that matches the given description. In fact, the data description actually generates a set of all the objects that match the description. In a straight-line program, only the first object in the set is used. But the user can easily transform the program so that it operates over all the items that match a data description.

As an example, consider again the simple program of Figure 3, which moves a single document out of a folder named "Negotiations". Suppose the user instead wanted to move all the documents out of the "Negotiations" folder. The user would start by recording a program that moved just one document out of the folder. The resulting program would resemble Figure 3. The user would then edit the data description for the document, choosing the ANY choice in the description sheet (see Figure 4).

After the user changed the description sheet, the program would look like Figure 6. When this program runs, the data description for the document will generate a set consisting of all the documents in the folder, since any and all documents match the description. But until the user adds a loop to the program, only the first document in the set would be moved by the program.

To edit the program to add a loop, the user selects the statements that form the body of the loop, and invokes Repeat... from the pop-up menu in the program window. The selected statements are wrapped in a loop, and the transcript is updated. The program with the added loop is shown in Figure 7.

In Figure 7, the loop statement is present, but the set to iterate over has not yet been specified; hence there is a blank space labeled -fill this in-. The user then indicates which description will generate the iteration set, by selecting the "Negotiations-any" document description in the program, pressing the Move or Copy key, and dropping the result into the -fill this in- space. The final program is shown in Figure 8.

Now there are two references to the "Negotiations-any" data description: one is in the Repeat statement, and the other is in the Move statement. Selecting one would highlight the other. Interestingly, there is no iteration variable like that found in a typical for-each construct. For instance, there is no variable like the "D" in "For each document D in Negotiations do Move D to the Desktop." The data description both substitutes for the variable and describes the iteration set.

Figure 6. Program to move any document out of a folder.

Figure 7. Adding a set iteration loop to a program.

Figure 8. Program to move all the documents out of a folder.


Set iteration is easy to add to a program recorded by demonstration. There is still a single path through the program. Conditionals are more difficult. A conditional means there is a fork in the program; some piece of the program may not be executed when the program runs. This means that when giving an example, the user may not include some necessary piece of the final program.

To solve this problem, some programming by demonstration systems require the user to give multiple complete examples. The user records different examples that cover all the alternate paths in the program, and specifies predicates that choose between the paths. I did not choose this method for SmallStar. Instead, the user records a single straight-line program, and then edits it to add if-then-style conditionals. Program steps that were not recorded in the initial example are added later as necessary by recording extra actions. This saves the effort of having to construct and record a complete example for the alternate program paths.

Consider a simple example. The user receives a filled-in mailing form ( Figure 9), which is to be printed for use in the mail room.

Normally, items are shipped by fourth-class mail. However, if an item weighs less than one pound, it is shipped by first-class mail. The user wants to write a program to automate this policy.

To do so, the user first writes a program that unconditionally changes "Fourth" to "First" in the Class field in the mailing form, and then prints the form. The user then selects the statements that should be executed conditionally. Figure 10 shows the program, with those statements selected.

Using the pop-up menu in the program window, the user wraps the statements in an if statement. The edited program is shown in Figure 11.

The user has not yet specified the predicate for the if statement. The user selects the predicate (- fill this in- = -fill this in-), and opens its property sheet.

Figure 9. A mailing form.

Figure 10. The mailing form program, before the addition of the conditional.

Figure 11. The mailing form program. The conditional is not yet filled in.

Figure 12. Property sheet for the conditional in the mailing form program.

Figure 13. The completed mailing form program. The conditional has been specified.

The user then selects the contents of the Weight field in the mailing form and invokes a Make Description command. The description created is "Mailing Form-Weight-all"; it specifies all the text in the Weight field. The user puts this description in the property sheet as the first operand. The user changes the second operand to "1" (one pound), and finally changes the operator from "=" to "<". The resulting property sheet is shown in Figure 12.

When the user closes the property sheet, the program changes, and is shown in Figure 13.

Figure 14. The calculator window.

The conditional property sheet only allows for simple comparisons. To construct more complicated predicates, the user can use a special calculator that has been augmented with relation and Boolean operators ( Figure 14), and then test the result with an if statement.

SmallStar provides only for if-then, not if-then-else conditionals. If-then-else must be simulated by testing the negation of a predicate. Since only one branch of the conditional can be recorded at a time, the user must record the steps in the other branch at a later time.

SmallStar's provision for conditionals is adequate, but not entirely satisfactory. The user must decide which program steps will be executed conditionally. In addition, recording new steps in a program may require extra setup of SmallStar data objects.

Other control structure

SmallStar does not provide while loops or procedure calls, but both could be added easily. For procedure calls, the main issue is how to pass arguments. In the calling program, the user could select data objects to be passed; in the called program, data description sheets could specify that an object is a procedure argument.

User Trials

In order to show that programming by demonstration could be used by typical Star users, I performed informal user trials of SmallStar with five users. I demonstrated the system to each of them, and asked each to think of a task to program by demonstration. If the user could not think of one, I suggested a task. Each user then attempted to record a program for the task. The users were usually successful, sometimes with a small amount of coaching. These user trials were by no means controlled experiments, but they pointed up both the successful aspects and the problems of SmallStar.


The research that went into creating SmallStar produced several notable contributions to the study of programming by demonstration: * Control structure can be added by editing a program after it has been recorded, if the programming mechanism provides the user with a readable static representation of the recorded program.

Considerably more information about SmallStar can be found in my doctoral dissertation [Halbert 84]. It covers the evolution of SmallStar in detail, including earlier versions and blind alleys.

SmallStar shows how it is possible to add sophisticated, practical programming by demonstration to a richly functional, end-user commercial software system. I hope that future researchers and software designers will find its ideas and techniques useful in their work.


Uses and Users

Application domain: Office information system

Intended users: Users of application software who are not programmers

User Interaction

How does the user create, execute and modify programs?
The user creates a program by telling the system to Start Recording user actions.
The recorded program is displayed in a scripting language that includes icons for various types of objects, such as folders and text selections.
The user can run a program or step through it one action at a time.
The user can modify a program transcript by deleting steps or recording new steps. SmallStar does not check for validity of the resulting program.


No inferencing.
SmallStar chooses an initial data description for every object used during recording. The choice is fixed, and does not vary based on the example. SmallStar can display a description sheet listing alternative data descriptions for an object, so that the user can then choose the appropriate description.

Program constructs:
Variables (via data descriptions). If an object appears more than once in a program, all references to it use the same data description.
Set iteration and conditionals can be added by hand to a recorded program.


Types and sources of information:
Fixed set of reasonable, useful alternative data descriptions for each kind of object. This set is not exhaustive. The most likely choice is used for the initial data description (for instance, choosing a document by its name).


Machine, language, size, date: Xerox Dorado, Smalltalk-80, 1984.

back to ... Table of Contents Watch What I Do