Browse Prior Art Database

SOME RULES FOR THE AUTO MATIC SYNTHESIS OF PROGRAMS

IP.com Disclosure Number: IPCOM000128300D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 47K

Publishing Venue

Software Patent Institute

Related People

Cordell Green: AUTHOR [+4]

Abstract

A set of rules (or facts) about program synthesis is presented. The rules are about the process of programming, and are sufficient for the synthesis of an insertion sort program. The use of the rules to write a short LISP program is described. Taken together, the rules are an ernbodiment of a detailed theory which explains one small part of the programrining process. The s, ize of the set of rules suggests the complexity of the process of writing programs and indicates that much work will be required to codify significant amounts of programming knowledge as a step toward the development of program-understanding systems.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SOME RULES FOR THE AUTO MATIC SYNTHESIS OF PROGRAMS

Cordell Green and David Barstow Stanford Artificial Intelligence Laboratory Stanford, California USA

ABSTRACT

A set of rules (or facts) about program synthesis is presented. The rules are about the process of programming, and are sufficient for the synthesis of an insertion sort program. The use of the rules to write a short LISP program is described. Taken together, the rules are an ernbodiment of a detailed theory which explains one small part of the programrining process. The s, ize of the set of rules suggests the complexity of the process of writing programs and indicates that much work will be required to codify significant amounts of programming knowledge as a step toward the development of program-understanding systems.

INTRODUCTION

This paper may be viewed as a sequel to an earlier paper [11, in whicH we tried to exhibit the knowledge required by a computer system in order to synthesize a simple insertion sort program. In this paper, we present the results of an attempt to codify that knowledge in the form of an explicit system of rules. Although there are other ways in which this knowledge might ge available to a computer system (e.g., derivable through some kind of inference applied to more general knowledge), the rules presented here seem to express the information used in the process of writing one simple program. As such, the rules constitute one detailed part of a theory of programming. A more complete theory could provide the basis for a knowledge-based program-understanding system. . The rules presented here are about the process of programming, rather than about program semantics. Thus one of the rules states that one method of generating all elements in a stored set is to first select a method for saving the state of the generator, then write the body, then the initializer, and so on. Additional rules elaborate how to achieve each subgoal. The subjects of this set of rules include tha synthesis of transfer programs (in which the elements of one ordered set are transferred and possibly re-ordered into a new ordered set), generators of elements and positions in ordered sets, constructors of sets, search strategies, tests for correctness of a position, etc. Also included are the lower-level programming rules (for the LISP language) that are necessary to actually code the program. The complete set of. rules has in fact been used to synthesize 'the intended program in an implementation which is basically a rule-testing system. This implem. entation is described 'at the end of the paper. It may seem strange that so many rules are used for one simple program. The number and complexity of these rules has resulted frorn a desire to adequately reflect the amount of knowledge needed for this particular synthesis and from an effort to minimize the amount of remodeling required to add more knowledge. Des ' oit...