Generalizing by Removing Detail

Generalizing by Removing Detail:

How Any Program Can Be Created by Working with Examples

Ken Kahn

Animated Programs

Abstract

A long-standing goal of the programming by demonstration research community is to enable people to construct programs by showing how the desired programs should work on sample inputs. A major challenge is how to make the programs general. Heuristics and inference can generalize recorded actions on sample data in narrow domains but have yet to be much help in general purpose programming. This paper describes a programming system called ToonTalk^® [Kahn 96, Kahn 00] that takes a different approach. In ToonTalk the programmer generalizes recorded actions by explicitly removing details. Children as young as 6 have constructed a wide variety of programs in this manner [Playground 00].

There is a very important interplay between the way in which programs are created and generalized in ToonTalk and the underlying model of computation. A program is executed as a collection of autonomous processes that communicate asynchronously where the behavior of a process is specified by a set of guarded clauses. A clause is constructed by performing operations on a single sample data structure. To make the clause capable of operating on other data structures, the programmer needs only to remove details from the guard or conditional part of the clause.

ToonTalk is built upon the idea of animated programming. Animated programs are not constructed by typing text or by constructing diagrams or stringing icons together. Instead, the programmer is placed as a character in an animated virtual world where programming abstractions are replaced by tangible analogs. A data structure, for example, is a box whose holes can be filled with number or text pads, other boxes, birds, nests, and robots. Birds and nests are concrete analogs of send and receive capabilities on communication channels. A robot is a guarded clause that has been trained by the programmer to take actions when given a box. The thought bubble of a robot displays the guard or conditions that need to be satisfied before the robot will run. To generalize a robot, a programmer needs only to use an animated vacuum to remove details from the box inside the robot’s thought bubble.

A short version of this article appeared in the Communications of the ACM, March 2000.

The full-length version of this article can be found as a chapter in the book Your Wish Is My Command: Programming By Example.

Download the entire paper as an Adobe Acrobat file (PDF) - 7.5MB