Communications of the ACM
Home/Magazine Archive/March 2000 (Vol. 43, No. 3)/Programming By Example: Generalizing By Removing Detail/Full Text
Communications of the ACM
Programming By Example: Generalizing By Removing Detail
A long-standing goal of the programming by demonstration (PBD) research community is enabling programmers and nonprogrammers alike to construct computer programs by showing how they should work on sample inputs. Instead of relying on generalization heuristics, ToonTalk, a PBD system I have been developing since 1992 to make programming more like the way children play, enables the programmer to construct arbitrary programs by recording actions on sample data and then explicitly removing details from data structures. Children as young as six have constructed a variety of programs in this manner (see www.ioe.ac.uk/playground).
Especially important is the interplay between the way programs are created and generalized in ToonTalk and ToonTalk's underlying model of computation. A program is executed as a collection of autonomous processes that communicate asynchronously; the behavior of a process is specified through a set of guarded clauses consisting of a guard and a body. The actions of the body can be performed only if the conditions of the guard are met. A clause is constructed from operations performed on a single sample data structure. To make the clause able to operate on other data structures, the programmer need only remove details from the guard part of the clause.
ToonTalk is built on the idea of "animated programming." Animated programs are not constructed by typing text, creating diagrams, or stringing icons together. The programmer is a character in an animated virtual world in which programming abstractions are replaced by their tangible analogs. For example, a data structure is represented as a box; holes in the box can be filled with numbers, text, other boxes, birds, nests, or robots. Birds and nests in turn are concrete analogs of "send" and "receive" operations on the program's communication channels. A robot is a guarded clause that can be trained by the programmer to take action when given a box. The robot's thought bubble displays the guard, or conditions that have to be satisfied before the robot can run. To generalize a robot, a programmer needs to use only an animated hand-held vacuum cleaner to remove details from the box inside the robot's thought bubble (see Figure 1).
As an example, imagine some children want to build a game that needs a scorekeeper. Many game elements have to concurrently update and query the score. The children decide the scorekeeper should be an active object; therefore, a team of robots works on a box containing a number pad corresponding to the score and a nest where requests to read or alter the current score arrive. After constructing the box, the children construct a message to change the score and give it to the bird that owns the nest.
The bird flies to the nest and fills it with the message, resulting in the box [[change -2] 10], which represents a score of 10 and a request to decrement it by 2. The children give this box to a fresh robot, then guide it to pick up the -2 and drop it on the 10. A mouse with a big hammer, responsible for arithmetic operations, smashes them together to produce 8. The children then guide the robot to pick up the vacuum cleaner and suck up the "change" message.
The robot is now fully trained but works only when the score is 10 and the message to change it contains -2. To generalize the program, the children use the vacuum cleaner to erase the 10 and -2 in the robot's thought bubble, so the robot works for any score and any change message containing an arithmetic operation. The children then train another robot to handle requests that seek out and bring back the current score. The children put the two robots together as a team, placing them on the back of a number to finish creating a game component that keeps the score.
The programmer is a character in a virtual world in which programming abstractions are replaced by their tangible analogs.
Appropriate Computation Model
An appropriate computation model greatly simplifies the task of building a PBD system. ToonTalk's computation model has no nested conditionals, no complex conditionals, no nonlocal variables, and no subroutine calls, but ToonTalk is nonetheless an expressive high-level programming language. Each of these common programming abstractions would interfere with the PBD process. Much of ToonTalk's power and simplicity comes from the fact that once a robot starts working, it is just executing "straight line" code, without conditionals or procedure calls. Any "variable references" are resolved either to the box the robot was given or to some local temporary variables that are "concretized" as objects the robot was trained to place on the floor.
Return values from procedures in a PBD system interfere with a top-down programming style due to the difficulty of representing the result of running an undefined procedure. ToonTalk's procedure-call equivalent—spawning a process that gives a bird the result value—presents no such difficulties. The bird's nest represents the return value, even if the robots computing the result value have yet to be defined. Recursion occurs when robots spawn processes to run copies of themselves. Operations that alter data structures also present difficulties when programming is performed in a top-down style in a PBD system. These difficulties do not arise in ToonTalk, because all side effects are limited to message communication; there is no sharing of data structures.
ToonTalk makes the process of PBD even more tangible by providing concrete animated analogs of every computational abstraction. Everything in ToonTalk can be seen, picked up, and manipulated. Even such operations as copying and deleting data structures are expressed through animated tools.
The same objects and tools are used, whether training robots or manipulating objects directly. These modes are distinguished visually by whether the programmer is controlling a programmer persona on the floor of a ToonTalk house or the contents of a robot's thought bubble. The same skills and way of thinking are used in both modes.
Difficult Fun
Programming is a cognitively challenging task. A programmer needs to design a program's architecture, break large tasks into manageable pieces, choose wisely among a range of data structures and algorithms, and, once the program is constructed, track down and fix the inevitable bugs. Enabling the programmer to do these tasks while manipulating tangible objects representing sample input helps reduce some of the complexity. Only the difficult fun remains.
©2000 ACM 0002-0782/00/0300 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2000 ACM, Inc.
No entries found