|
|
When I first started to learn about programming (many more years ago than I care to think about), my idea of how it should work was that it should be like teaching someone how to perform a task. After all, isn't the goal of programming to get the computer to learn some new behavior? And what better way to teach than by example?
So I imagined that what you would do would be to show the computer an example of what you wanted it to do, go through it step by step, have the computer remember all the steps, and then have it try to apply what you showed it in some new example. I guessed that you'd have to learn some special instructions that would tell it what would change from example to example and what would remain the same. But basically, I imagined it would work by remembering examples you showed it and replaying remembered procedures.
Imagine my shock when I found out how most computer programmers actually did their work. It wasn't like that at all. There were these things called "programming languages". The programming languages didn't have much to do with what you were actually working on. You had to write out all the instructions for the program in advance, without being able to see what any of them did. How could you know if they did what you wanted? If you didn't get the syntax exactly right (and who could?) nothing would work. Once you had the program, and you tried it out, if something went wrong, you couldn't see what was going on in the program. How could you tell which part of the program was wrong? Wait a second, I thought, this approach to programming couldn't possibly work!
I'm still trying to fix it.
Over the years, a small but dedicated group of researchers felt the same way, and have developed a radically different approach to programming, called "Programming by Example" (PBE) or sometimes, "Programming by Demonstration" (the user demonstrates examples to the computer). In this approach, a software agent records the interactions between the user and a conventional "direct-manipulation" interface, and writes a program that corresponds to the user's actions. The agent can then generalize the program so that it can work in other situations similar to, but not necessarily exactly the same as, the examples on which it is taught.
It is this generalization capability that makes PBE like "macros on steroids". Conventional macros are limited to playing back exactly the steps recorded, and so are brittle because if even the slightest detail of the context changes, the macro will cease to work. Generalization is the central problem of PBE, and ultimately, should enable PBE to completely replace conventional programming.
Significantly, the first real commercial market for PBE systems might be children! Children are not "spoiled" by conventional ideas of programming, and usability and immediacy of systems for them are paramount. We'll present two systems that have been recently brought to market and are enjoying enthusiastic reception from their initial users. David Smith, Allen Cypher, and Larry Tesler's Stagecast Creator , evolved from Apple's Cocoa/KidSim, brings rule-based programming by example to a graphical grid world. Alexander Repenning and Corrina Perrone-Smith's AgentSheets operates in a similar domain and for a similar audience. Ken Kahn's ToonTalk , a programming system which is itself a video game, uses a radically different programming model as well as a radical user interface. The crucial problem of generalizing examples gets solved in a simple, almost obvious way -- if you remove detail from a program, it becomes more general.
One way in which PBE departs from conventional software is by applying new techniques from artificial intelligence and machine learning. This both opens up a tremendous opportunity, and also some new risks. Brad Myers and Rich McDaniel treat the thorny issue of "how much intelligence?" from their wide experience in building a variety of PBE systems.
Of course, we can't convince people about the value of Programming by Example unless we have some good examples of application areas for it! Next, we move to some application areas that show how PBE can really make a difference. Everybody's current favorite application area is the Web. The Web is a great area for PBE because of the accessibility of a wealth of knowledge, along with the pressing need for helping the user in organizing, retrieving and browsing it. The emerging developments in intelligent agents can help -- but only if users can communicate their requirements and can control the behavior of the agent. PBE is ideal.
Atsushi Sugiura's Internet Scrapbook automates assembling Web pages from other Web sources, and he also explores Web browsers on small handheld devices. Matthias Bauer, Dietmar Dengler and Gabriele Paul present a mixed initiative system -- at each step, either the user or the agent can take action, cooperating to arrive at a "wrapper" which describes the format of Web pages.
Carol Traynor and Marian Williams point out the suitability of PBE for domains that are inherently graphical, like Geographic Information Systems. If you can see it and point to it, you should be able to program it. PBE lets the user see what they are doing, unlike conventional programming languages, where graphical data can only be referenced in a program by filenames and numbers. They illustrate the utility of PBE for "user-programmers" -- those who specialize in the use of a particular application, but also, at least occasionally, have the need to resort to programming. Patrick Girard embeds a PBE system in an industrial-strength Computer-Aided Design (CAD) application. Designers of mechanical, electrical, manfacturing or architectual systems can see the objects they are trying to design directly. Rich McDaniel moves from static graphics to the dynamic world of computer games, showing how interaction techniques can also demonstrate "hidden features" of applications that are not directly reflected in the graphics that the user will eventually see, but are nevertheless crucial.
PBE can automate many common but mundane tasks that tend to consume a frustratingly large fraction of people's time. Good ole text editing remains the application that people spend the greatest amount of time in, and so text editing applications are the target of the next set of PBE systems we'll look at. Tetsuya Masuishi and Nobuo Takahashi use PBE successfully for the common editing task of generating reports. Toshiyuki Masui's Dynamic Macro and PoBox systems use loop detection and a predictive interface to automate repetitive typing and editing, which can be especially important in minimizing typing in small handheld devices or for handicapped users. The systems of Masuishi, Masui, and Sugiura have all been distributed to a large user community in Japan. Tessa Lau, Steve Wolfman, Pedro Domingos and Dan Weld use the time-honored AI technique of version spaces to maintain a space of hypotheses about user actions, illustrating the synergy between work in machine learning and PBE.
Henry Lieberman, Bonnie Nardi and David Wright also put PBE to work for user convenience, in training text recognition agents to recognize by example common patterns of data that occur in the midst of unstructured information. Their PBE system for developing text recognition grammars, Grammex, was the first interactive interface of any kind to make the powerful grammar and parsing technology accessible to end users. Alan Blackwell adds to this general approach a visual syntax for the grammar rules, which he shows increases user comprehension of the resulting programs.
And we shouldn't forget programming environments themselves as a domain for PBE, even if the programming is done in a conventional write-a-file-and-compile-it programming environment. Jean-David Ruvini and Christophe Dony take advantage of the truism that "people are creatures of habit". They have a software agent detect habitual patterns in a conventional programming language environment, Smalltalk, and automate those patterns.
Well, if PBE is so great, how come everybody isn't using it? It's our hope that they soon will. But we realize that PBE represents such a radical departure from what we now know as "programming" that it is inevitably going to take a while before it becomes widespread. Despite the existence of many systems showing the feasibility of PBE in a wide variety of domains, conservatism of the programming community still seems the biggest obstacle.
Signs are growing, however, that PBE might just be beginning to catch on. Commercial PBE environments are beginning to appear, such as the childrens' PBE environments cited above, which are now on the market. But it also makes sense to view more conventional user-programming facilities, such as so-called "interface builders", macros and scripting systems as the "poor man's Programming by Example". Some of these facilities are beginning to evolve in directions that may incorporate elements of the PBE approach. And we will need conventional applications to become more "PBE-friendly" so that PBE systems can use the conventional applications as tools in the same way that a user would operate them manually. Gordon Paynter and Ian Witten show how we might be able to leverage scripting language and macro capabilities that are already present or on the way for applications into full-blown PBE systems. This might facilitate an adoption path for PBE.
In programming, as in theater, timing is everything. Much of the work in PBE is involved with demonstrating how to do something, but equally important is when to do it. David Wolber and Brad Myers explore what they call "stimulus-response" PBE, where we generalize on time and user input, to assure that PBE-programmed procedures are invoked at just the right time. Wolber also compares his PBE animation system to a conventional animation editor/scripting system, Macromind Director, which brings the similarities and differences of PBE versus conventional applications into sharp focus.
We then move on to explore some directions where PBE might be heading in the future. Alexander Repenning and Corinna Perrone-Smith show how we can take PBE a step further, using another important intuitive cognitive mechanism -- analogy. We often explain new examples by way of analogy with things we already know, thus allowing us to transfer and reuse old knowledge. Repenning and Perrone-Smith show how we can use analogy mechanisms to edit programs by example as well as create them from scratch.
Robert St. Amant, Henry Lieberman, Luke Zettlemoyer, and Richard Potter explore what at first might seem like a crazy approach. They actually have the computer simulate the user's visual system in interpreting images on the screen rather than accessing the underlying data. Though it may seem inefficient, it neatly sidesteps one of the thorniest problems for PBE -- coexistence with conventional applications. The approach enables "visual generalization" -- generalizing on how things appear on the screen, as well as properties of the data.
Programming by Example is one of the few technologies that holds the potential of breaking down the wall that now separates "programmers" from "users". It can give ordinary users the ability to write programs while still operating in the familiar user interface. Users are now at the mercy of software providers who deliver shrink-wrapped, one-size-fits-all, unmodifiable "applications". With PBE, users could create personalized solutions to one-of-a-kind problems, modifying existing programs and creating new ones, without going through the arcane voodoo which characterizes conventional programming. In this collection of articles, we hope that the diversity of systems presented, compelling user scenarios, and promising directions for the future of PBE, will convincingly demonstrate the power and potential of this exciting technology.
Foreword to "Your Wish is My Command"
by Ben Shneiderman, University of Maryland
Setting an alarm clock is probably the most common form of programming. Users set a time and then put the clock in alarm mode. Older 12-hour mechanical clocks usually had a special alarm hand that could be moved to the time for the alarm to ring, and then the users turned the alarm switch on. A nice form of direct manipulation programming — easy to learn and use.
Direct manipulation is a term I coined in 1981 to describe the visual world of action in many successful graphical user interfaces such as video games, air traffic control and What-you-see-is-what-you-get word processors. The principles were to:
These principles can lead to interfaces that help novices and experts, prevent or at least reduce errors, and encourage exploration because reversibility is supported. Designers continue to refine and extend direct manipulation, but critics complain that direct manipulation only works for limited tasks. They often ignore the possibility of direct manipulation programming, which was part of the original conception [1, 2].
To explore the possibilities, we built a direct manipulation programming tool in 1984-85 that enables users to create macros for MS DOS. This tool, Direct Manipulation DOS (DMDOS) [3], enabled users to record and view their actions, and then store and replay macros. We were motivated by successful macro facilities for unix, word processors and spreadsheets. These early keyboard-oriented systems led us to joke that "those who ignore history are destined to retype it." We were also inspired by innovative programming-by-demonstration in David Canfield Smith’s Pygmalion [4], graphical macro facilities in Dan Halbert’s SmallStar [5] and Alan MacDonald’s early call for Visual Programming [6]. These pioneers and other innovators believed in the goal of empowering users to create useful programs, extend existing interfaces, and build small just-in-time programs that automated daily tasks.
This important volume of papers carries forward the agenda of making direct manipulation programming (or programming-by-example, programming-by-demonstration, end-user-programming, programming-in-the-user-interface, etc.) a reality. While there have been successes in the intervening years, such as programmable machine tools, visual programming languages, and a variety of macro building programs, widespread adoption is still elusive. Henry Lieberman deserves credit for his long devotion to this topic and for collecting the diverse strategies and application domains in this volume. He and the contributors to this volume remind us all of the breadth of opportunities and depth of ambition.
The allure of direct manipulation programming is its capacity to empower users, while minimizing learning of programming concepts. Researchers continue to seek simple cognitive models for programming that are in harmony with the cognitive model of the existing user interface. Just as the programmable mechanical alarm clock is tied to the familiar model of clock hands, researchers have wanted to build on the visual nature of graphical user interfaces.
This fundamental human-computer interaction challenge has inspired a generation of designers, who have come up with innovative strategies for supporting iteration, conditionals, parameter passing, modular design, pattern matching, and data representation. This treasure chest of strategies is likely to pay off in multiple solutions for direct manipulation programming and related problems. A successful strategy would not only be easy to learn, but also support rapid composition of common programs. Then it would also be easy to invoke, with comprehensible feedback about successful and unsuccessful executions.
One strategy represented in this book is to develop software that recognizes familiar patterns of action and infers a useful program. There may be some opportunities along this path but I prefer the second path of special tools for users to create a program, just as they move the special hand of an alarm clock to set the wake-up time.
A third path, also well represented in this book, is visual programming languages in which the users set out to write a program, but visually instead of textually. Visual programming languages may have a simple basis such as dragging items from a relational table to a screen-based form to create a report program. More elaborate visual programming languages have graphic symbols to represent objects, actions, conditionals, loops, and pattern matching.
A fourth path might be to add history capture environments for every interface. Unix command line interfaces had a history log that allowed users to conveniently review and reuse commands. World-Wide Web browsers support history keeping of page visits with relatively easy review and reuse. Microsoft Word captures a history of actions to support undo operations, but users cannot review the history or save it. Adobe Photoshop 5.0 added a nice history feature for graphic designers, demonstrating that even in complex environments rich history support is possible.
Our current efforts with Simulation Processes in a Learning Environment have emphasized history keeping, enabling users to review their work, replay it, annotate it, and send it to peers or mentors for advice [7]. An immediate payoff was that faculty could run the simulation in exemplary or inappropriate ways and store the histories for students to use as a training aid.
The story of this field and this book is that there is magic and power in creating programs by direct manipulation activities, as opposed to writing code. The potential for users to take control of technology, customize their experiences, and creatively extend their software tools is compelling.
Eighteenth century scientists, like Ben Franklin, experimented with electricity and found its properties quite amazing. Franklin, Faraday, Maxwell, and others, laid the foundation for Thomas Edison’s diverse applications, such as refinements of telegraphy, generators, and electric lighting. This book brings reports from many Franklins, Faradays, and Maxwells who are laying the foundation for the Thomas Edisons, still to come. It is difficult to tell which idea will trigger broad dissemination or whose insight will spark a new industry. However, the excitement is electric.
(Acknowledgement: Thanks to Richard Potter for his comments on my drafts)
1. Shneiderman, B., The future of interactive systems and the emergence of direct manipulation, Behaviour and Information Technology 1, 3, 1982, 237-256
2. Shneiderman, B., Direct manipulation: A step beyond programming languages, IEEE Computer 16, 8, August 1983, 57-69).
3. Iseki, O. and Shneiderman, B., Applying direct manipulation concepts: Direct Manipulation Disk Operating System (DMDOS), ACM SIGSOFT Software Engineering Notes 11, 2, (April 1986), 22-26.
4. Smith, D. C., Pygmalion: A Computer Program to Model and Stimulate Creative Thought. Basel, Stuttgart, Birkhauser Verlag. 1977.
5. Halbert, Daniel, Programming by Example, Ph. D. dissertation, Department of Electrical Engineering and Computer Systems, University of California, Berkeley, CA, Available as Xerox Report OSD-T8402, Palo Alto, CA, (1984).
6. MacDonald, Alan, Visual programming, Datamation 28, 11 (October 1982), 132-140.
7. Plaisant, C., Rose, A., Rubloff, G., Salter, R., Shneiderman, B., The design of history mechanisms and their use in collaborative educational simulations, Proc. Computer Supported Collaborative Learning Conference (December 1999)<
Links to chapters in Adobe PDF format
Foreward
Ben Shneiderman
Novice Programming Comes of Age
David Canfield Smith, Allen Cypher, Larry Tesler
Generalizing by Removing Detail: How Any Program Can Be Created by Working with Examples
Ken Kahn
Demonstrational Interfaces: Sometimes You Need a Little Intelligence; SometimesYou Need a Lot
Brad A. Myers, Richard McDaniel
Web Browsing by Demonstration
Atsushi Sugiura
Programming by Demonstration for Information Agents
Mathias Bauer, Dietmar Dengler, and Gabriele Paul
End Users and GIS: A Demonstration is Worth a Thousand Words
Carol Traynor and Marian Williams
Bring Programming by Demonstration to CAD Users
Patrick Girard
Demonstrating the Hidden Features That Make an Application Work
Richard McDaniel
A reporting tool using programming by example for format designation
Tetsuya Masuishi and Nobuo Takahashi
Composition by Example
Toshiyuki Masui
Learning Repetitive Text-editing Procedures with SMARTedit
Tessa Lau, Steve Wolfman, Pedro Domingos and Daniel S. Weld
Training Agents to Recognize Text by Example
Henry Lieberman, Bonnie A. Nardi and David J. Wright
SWYN: A Visual Representation for Regular Expressions
Alan Blackwell
Learning Users' Habits to Automate Repetitive Tasks
Jean-David Ruvini and Christophe Dony
Domain-independent programming by demonstration in existing applications
Gordon W. Paynter and Ian H. Witten
Stimulus-Response PBD: Demonstrating When as Well as What
David Wolber and Brad Myers
Pavlov: Where PBD Meets Macromedia's Director
David Wolber
Programming by Analogous Examples
Alexander Repenning and Corrina Perrone-Smith
Visual Generalization in Programming by Example
Robert St. Amant, Henry Lieberman, Richard Potter, and Luke Zettlemoyer