Text File

Aucbvax.2310 fa.works utzoo!duke!decvax!ucbvax!works Thu Jul 16 09:39:46 1981 Programming by example >From Halbert@PARC-MAXC Thu Jul 16 09:36:00 1981 Here is a short description of programming by example. I have gotten requests from a LARGE number of WorkS subscribers requesting it.

------------------------------

Since a few people have mentioned programming by example and the work I've done on it specifically, I will try to give a brief outline of what it is, and what I've done:

At its simplest, programming by example is just recording a sequence of commands to a system, so that the sequence can be played back at a later time, to do the same or a similar task. The sequence forms a program. The user tells the system, "Remember what I am doing". The system executes the user's commands normally, but also remembers them.

The user has created a program by giving an example what he wants the program to do. However, the statements in his program are the same as the normal system commands. The user does not have to learn some programming language with its attendant syntax and semantics; instead he can do his programming -in the user interface- of the system, which he already has to know anyway in order to operate the system.

In addition, he has written the program by performing, concretely, an example of what the program is supposed to do. Since he can easily verify whether he did his example correctly, he can be fairly confident his program will work. He does not have to understand his program abstractly.

Naturally, straight line programs without parameters are not very interesting. Once the user has written a program he may want to -generalize- it. He may want to print file Y, instead of the file X he used in his example. So the system has to provide a way for him to to change the constants in his programs to variables, and specify how these variables are to be bound (e.g. by prompting the user, by looking for similar data, etc.)

The user may also want to insert conditional or looping constructs into his program. There are various ways, which I will not go into here, of inserting these constructs into programs using programming-by-example techniques.

I would emphasize that this kind of programming by example does not use inductive inference techniques used in AI, in which the user does several examples, and the system inductively determines what has changed from example to example (e.g. 1+2, 5+2, hmm, first operand must be a variable; or a[1], a[2], a[3], hmm, looks like a loop stepping through the array).

The seminal work in programming by example was done by Dave Smith of Xerox in his Stanford Ph.D. Thesis. Gael Curry did similar work in which the examples given by the user could contain abstract as well as concrete data values. Certain industrial robots can be programmed by example by guiding them through the task they are to perform. Here at Xerox, I have added programming by example to a prototype of Star. The system provides program generalization and an iteration mechanism as well as simple command recording. I have written up this work and my ideas on programming by example so far in a Master's project report done for U.C. Berkeley. I intend to continue and extend this work into a Ph.D. thesis.

References:

Daniel C. Halbert. An Example of Programming by Example. Master's project report, University of California, Berkeley, and internal report, Xerox Corporation, Office Products Division, Palo Alto, CA.

David C. Smith. Pygmalion: A Computer Program to Model and Stimulate Creative Thought. Ph.D. thesis, Stanford University, 1975 and Birkhauser Verlag, 1977.

Gael A. Curry. Programming by Abstract Demonstration. Ph.D. thesis, University of Washington, Seattle. Technical Report No. 78-03-02. March, 1978.

Henry Lieberman and Carl Hewitt. A Session with Tinker: Interleaving Program Testing with Program Writing. Conference Record of the 1980 LISP Conference, Stanford University, August, 1980. [describes a programming by example system for Lisp]

Michael A. Bauer. Programming By Examples. Artificial Intelligence 12: 1-12 (May 1979). [describes inductive inference techniques].

Copies of my report are available on request.

Dan Halbert Xerox Corporation Office Products Division 3450 Hillview Avenue Palo Alto, California

or

Halbert@PARC-MAXC (preferred) (or csvax.halbert@Berkeley)

--Dan -----

----------------------------------------------------------------- gopher://quux.org/ conversion by John Goerzen <jgoerzen@complete.org> of http://communication.ucsd.edu/A-News/

This Usenet Oldnews Archive article may be copied and distributed freely, provided:

1. There is no money collected for the text(s) of the articles.

2. The following notice remains appended to each copy:

The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman.