Readings in Artificial Intelligence and Software Engineering

By Charles Rich

Readings in Artificial Intelligence and Software Engineering covers the main techniques and application of artificial intelligence and software engineering. The ultimate goal of artificial intelligence applied to software engineering is automatic programming. Automatic programming would allow a user to simply say what is wanted and have a program produced completely automatically. This book is organized into 11 parts encompassing 34 chapters that specifically tackle the topics of deductive synthesis, program transformations, program verification, and programming tutors. The opening parts provide an introduction to the key ideas to the deductive approach, namely the correspondence between theorems and specifications and between constructive proofs and programs. These parts also describes automatic theorem provers whose development has be designed for the programming domain. The subsequent parts present generalized program transformation systems, the problems involved in using natural language input, the features of very high level languages, and the advantages of the programming by example system. Other parts explore the intelligent assistant approach and the significance and relation of programming knowledge in other programming system. The concluding parts focus on the features of the domain knowledge system and the artificial intelligence programming. Software engineers and designers and computer programmers, as well as researchers in the field of artificial intelligence will find this book invaluable.

• Language: English
• Publisher: Elsevier Science
• Release date: Jun 28, 2014
• ISBN: 9781483214429

Book preview

READINGS IN ARTIFICIAL INTELLIGENCE AND SOFTWARE ENGINEERING

Charles Rich

Richard C. Waters

Massachusetts Institute of Technology, Artificial Intelligence Laboratory

MORGAN KAUFMANN PUBLISHERS, INC.

Table of Contents

Cover image

Title page

Copyright

ACKNOWLEDGMENTS

INTRODUCTION

I: Deductive Synthesis

Chapter 1: Introduction to Deductive Synthesis

Chapter 2: A Deductive Approach to Program Synthesis

Publisher Summary

MOTIVATION

SPECIFICATION

BASIC STRUCTURE

SPLITTING RULES

TRANSFORMATION RULES

RESOLUTION

THE RESOLUTION RULES

THE POLARITY STRATEGY

MATHEMATICAL INDUCTION AND THE FORMATION OF RECURSIVE CALLS

A COMPLETE EXAMPLE: FINDING THE QUOTIENT OF TWO INTEGERS

THE FORMATION OF AUXILIARY PROCEDURES

GENERALIZATION

COMPARISON WITH THE PURE TRANSFORMATION-RULE APPROACH

ACKNOWLEDGMENTS

Chapter 3: Top-Down Synthesis of Divide-and-Conquer Algorithms

ABSTRACT

1 Introduction

2 A Simple Example

3 Derived Antecedents

4 SPECIFICATIONS

5 Design Strategies for Simple Algorithms

6 The Form and Function of Divide-and-Conquer Algorithms

7 Design Strategies for Divide-and-Conquer Algorithms

8 Concluding remarks

Appendix A

ACKNOWLEDGMENT

II: Program Verification

Chapter 4: Introduction to Program Verification

Chapter 5: Mechanical proofs about computer programs

Publisher Summary

1 INTRODUCTION

2 A MATHEMATICAL APPROACH

3 THE GYPSY ENVIRONMENT

4 AN EXAMPLE

5 TRIAL APPLICATIONS

6 CONCLUSION

Appendix A. Formal proof of lemma extend_separation

Appendix B. Formal proof of verification conditionseparator#3

Discussion

Chapter 6: PROOF CHECKING THE RSA PUBLIC KEY ENCRYPTION ALGORITHM

Publisher Summary

1 Introduction

2 A Sketch of the Theorem-Prover

3 Correctness of CRYPT

4 Fermat’s Theorem

5 Invertibility of CRYPT

6 Sample Input to the Theorem-Prover

7 Conclusion

III: Transformational Approaches

Chapter 7: Introduction to Transformational Approaches

Chapter 8: An Experimental Program Transformation and Synthesis System

ABSTRACT

1 Introduction

2 Languages and Formalism Used

3 System Structure

4 Synthesis

5 Generalisation and Sub-function Synthesis

6 Eureka Elimination

7 Conclusion

ACKNOWLEDGMENTS

Chapter 9: Program Development as a Formal Activity

Abstract

I INTRODUCTION

II TRANSFORMATION RULES

III CORRECTNESS OF TRANSFORMATIONS

IV TRANSFORMATIONAL SEMANTICS

V THE ROLE OF ABSTRACT DATA TYPES

VI THE ROLE OF ASSERTIONS

VII AN EXTENDED EXAMPLE: THE WARSHALL ALGORITHM

VIII CONCLUDING REMARKS

ACKNOWLEDGMENT

Chapter 10: An Experiment in Knowledge-based Automatic Programming

ABSTRACT

1 Introduction

2 Overview of the Knowledge Base

3 Sample Programs

4 A Detailed Example

5 Implementation

6 Discussion

7 Approaches to Automatic Programming

8 Assessment

ACKNOWLEDGEMENTS

Chapter 11: On the Efficient Synthesis of Efficient Programs

ABSTRACT

1 Introduction

2 Background

3 A Framework for Efficient Program Synthesis

4 An Overview of the LIBRA Implementation

5 An Example of LIBRA in Operation

6 Methods for Controlling Search in Program Refinement

7 Prototypes

8 Estimating Execution Costs

9 Adding New Efficiency Knowledge

10 Results

11 Related Research

12 Conclusions

ACKNOWLEDGMENT

Chapter 12: Reusability Through Program Transformations

Abstract

I INTRODUCTION

II ABSTRACT PROGRAMS

III REFINEMENT OF ABSTRACT PROGRAMS TO CONCRETE PROGRAMS

IV SOME EXPERIENCE WITH REUSING ABSTRACT PROGRAMS

V THE PROGRAMMING SUPPORT ENVIRONMENT

VI CONCLUSIONS AND FUTURE DIRECTIONS

Chapter 13: Program Developments: Formal Explanations of Implementations

ABSTRACT

1 INTRODUCTION: TRANSFORMATIONAL IMPLEMENTATION

2 DEVELOPMENT LANGUAGE PROPERTIES

3 THE DEVELOPMENT LANGUAGE

4 THE DEVELOPMENT PROCESS

5 REPLAY OF DEVELOPMENTS

6 THE UNDERLYING PROGRAM MANIPULATION SYSTEM: POPART

7 STRUCTURES EXPRESSED IN THE PADDLE LANGUAGE

7.2 Simplifications

7.3 Conditioning

7.4 The Development Process: A Simple Example

7.5 Text Compression: An Extended Example Development

8 PROBLEMS AND FUTURE RESEARCH

Acknowledgments

IV: Natural Language Specifications

Chapter 14: Introduction to Natural Language Specifications

Chapter 15: Automatic Programming Through Natural Language Dialogue: A Survey

Abstract

Introduction

NPGS

ISI

MIT

IBM

Comparison

Research issues

Acknowledgments

Chapter 16: Protosystem I—An automatic programming system prototype

Publisher Summary

INTRODUCTION

A MODEL OF THE PROGRAM WRITING PROCESS

EFFICIENCY ENHANCEMENT IN SYSTEM DEVELOPMENT

THE DEVELOPMENT OF PROTOSYSTEM I

THE PROTOSYSTEM I DATA PROCESSING SYSTEM MODEL AND THE SYSTEM SPECIFICATION LANGUAGE

THE TRANSLATOR AND THE DATA SET LANGUAGE

THE DESIGN CRITERION AND THE JOB COST ESTIMATOR

THE QUESTION ANSWERER

THE OPTIMIZING DESIGNER

STAGE 4: CODE GENERATION

CONCLUSION

ACKNOWLEDGMENTS

Chapter 17: Informality in Program Specifications

Abstract

I INTRODUCTION

II ATTRIBUTES OF SUITABLE PROCESS - ORIENTED SPECIFICATION LANGUAGES

III WHY OPERATIONAL SPECIFICATIONS ARE HARD TO CONSTRUCT

IV SEMANTIC CONSTRUCTS IN NATURAL LANGUAGE SPECIFICATION

V DESIRABILITY OF INFORMALITY

VI RESULTS

VII DESCRIPTION OF THE PROTOTYPE SYSTEM

V: Very High Level Languages

Chapter 18: Introduction to Very High Level Languages

Chapter 19: An Automatic Technique for Selection of Data Representations in SETL Programs

Publisher Summary

1 INTRODUCTION

2 THE SETL LANGUAGE AND ITS BASING SYSTEM

3 AN AUTOMATIC DATA REPRESENTATION SELECTION ALGORITHM

Chapter 20: Automating the Selection of Implementation Structures

Abstract

I INTRODUCTION

II FORMALISMS

III ALTERNATIVE IMPLEMENTATION - STRUCTURE GENERATION

IV SUMMARY AND CONCLUSIONS

APPENDIX

ACKNOWLEDGMENT

Chapter 21: KNOWLEDGE-BASED PROGRAMMING SELF APPLIED

ABSTRACT

§1 Introduction

§2 Specification of the Rule Compiler

§3 Extensions to the Rule Compiler

Acknowledgements

Chapter 22: IMPLEMENTING SPECIFICATION FREEDOMS

Abstract

1 Introduction

2 Specification in Gist

3 Mappings

3.6 Total information

4 Concrete examples of Gist

5 Case study

6 Related work

7 Conclusions

Appendix 1. Package router specification

VI: Programming by Example

Chapter 23: Introduction to Programming by Example

Chapter 24: A Methodology for LISP Program Construction from Examples

ABSTRACT

1 Introduction

2 A Sample Synthesis

3 Synthesis Theorems

4 Variable Addition

5 Two Additional Examples

6 System Capabilities and Limitations

7 Conclusion

ACKNOWLEDGMENTS

Chapter 25: Programming by Examples

ABSTRACT

1 Introduction

2 A Computation Description Language

3 The Synthesis Algorithm

4 Concluding Remarks

Appendix I

ACKNOWLEDGMENTS

VII: Intelligent Assistants

Chapter 26: Introduction to Intelligent Assistants

Chapter 27: TOWARD INTERACTIVE DESIGN OF CORRECT PROGRAMS

Publisher Summary

CONCLUSION

APPENDIX

Chapter 28: A Designer/Verifier’s Assistant

Abstract

I INTRODUCTION

II BRIEF SCENARIO

III SUGGESTING WHAT TO DO NEXT

IV PREVIEWING THE EFFECTS OF CHANGES

V REASONING ABOUT CHANGES

VI CONCLUSION

APPENDIX A RELATIONS IN A MODEL

APPENDIX B A SAMPLE MODEL

ACKNOWLEDGMENT

Chapter 29: The Programmer’s Apprentice: A Session with KBEmacs

Abstract

I INTRODUCTION

II SCENARIO

III EVALUATION

IV CAPABILITIES

V IMPLEMENTATION

VI RELATED WORK

VII FUTURE DIRECTIONS

ACKNOWLEDGMENT

Chapter 30: Kestrel Institute: REPORT ON A KNOWLEDGE-BASED SOFTWARE ASSISTANT

ABSTRACT

§1 EXECUTIVE SUMMARY

§2 PROBLEMS AND SOLUTIONS

§3 KBSA INTERNAL STRUCTURE

§4 SUPPORTING TECHNOLOGY AREAS

ACKNOWLEDGMENTS

VIII: Programming Tutors

Chapter 31: Introduction to Programming Tutors

Chapter 32: Intelligent Program Analysis

Abstract

1 Introduction

2 Finding the Plan

3 Program Synthesis

4 Program Generation Models

5 Analysis Policy

6 The Analysis Process

7 Value Equivalence

8 Construct Equivalence

9 Error Analysis

10 Expression Errors

11 Conditional Clause Reversal

12 Predicate Errors

13 Loop Iteration Errors

14 The Missing EXIT Statement

15 An Example

16 Experience

17 Applications

Appendix. A Simple Programming Language Model

Chapter 33: PROUST: Knowledge-Based Program Understanding

Abstract

I INTRODUCTION:MOTIVATION AND GOALS

II THE ROLE OF PLANS IN PROGRAM UNDERSTANDING

III A TYPICAL PROBLEM IN PROUST’S DOMAIN

IV RELATING GOALS TO CODE VIA PLANS

V THE UNDERSTANDING PROCESS:AN EXAMPLE OF PROUST IN ACTION

VI PERFORMANCE:PRELIMINARY RESULTS

VII CONCLUDING REMARKS

IX: Programming Knowledge

Chapter 34: Introduction to Programming Knowledge

Chapter 35: On Program Synthesis Knowledge

ABSTRACT

1 Introduction

2 Overview of Programming Knowledge

3 The Divide-and-conquer or Partitioning Paradigm

4 Internal Representation of Sets

5 Singleton Split

6 Refinement Diagram for Sorting Programs

7 In-place Sorting

8 Equal-size Split

9 Conclusions

ACKNOWLEDGMENTS

10 Appendix

Chapter 36: Program Abstraction and Instantiation

Publisher Summary

1 INTRODUCTION

2 OVERVIEW

3 A DETAILED EXAMPLE

4 PROGRAM TRANSFORMATIONS

5 DISCUSSION

ACKNOWLEDGMENTS

Chapter 37: A Formal Representation For Plans In The Programmer’s Apprentice

ABSTRACT

1 Introduction

2 The Plan Calculus

3 A Situational Calculus

4 Plans

5 Relations Between Plans

6 Final Remarks

Chapter 38: Empirical Studies of Programming Knowledge

Abstract

I INTRODUCTION: MOTIVATION AND GOALS

II BRIEF DESCRIPTION OF BOTH EXPERIMENTAL TECHNIQUES

III GENERATING PLAN-LIKE AND UNPLAN-LIKE PROGRAMS

IV DETAILED DESCRIPTION OF STUDY I: FILL-IN-THE-BLANK

V DETAILED DESCRIPTION OF STUDY II: RECALL

VI CONCLUDING REMARKS

ACKNOWLEDGMENTS

X: Domain Knowledge

Chapter 39: Introduction to Domain Knowledge

Chapter 40: The Draco Approach to Constructing Software from Reusable Components

Abstract

I INTRODUCTION

II THE ORGANIZATIONAL CONTEXT OF DRACO

III WHAT COMPRISES A DOMAIN DESCRIPTION?

IV DIFFERENCES IN DEFINITION FROM OTHER APPROACHES

V AN EXAMPLE DOMAIN ORGANIZATION

VI SOFTWARE COMPONENTS AND THE REFINEMENT PROCESS

VII DOMAIN SPECIFIC SOURCE-TO-SOURCE PROGRAM TRANSFORMATIONS

VIII WHAT CAN BE SAID ABOUT THE POWER OF THE DRACO METHOD?

IX CONCLUSIONS

APPENDIX

Chapter 41: A Perspective on Automatic Programming

Abstract

The Task Domain: Quantitative Log Interpretation

Initial Studies

The Role of Domain Knowledge

The Perspective

An Experimental Approach

ϕNIX

Chapter 42: Knowledge Representation as the Basis for Requirements Specifications

Publisher Summary

The need for representing knowledge

Multiple levels of description

Current research directions

XI: Artificial Intelligence Programming

Chapter 43: Introduction to Artificial Intelligence Programming

Chapter 44: DATAMATION®: POWER TOOLS FOR PROGRAMMERS

Publisher Summary

POWER TOOLS FOR PROGRAMMERS

The implementation disasters of the 1960s are slowly being succeeded by the design disasters of the 1980s

Redundancy protects the design from unintentional change — but it’s equally well protected against intentional change

Conventional programming technology restrains the programmer; exploratory systems amplify him

The programming languages used in exploratory systems minimize and defer constraints on the programmer

Chapter 45: Perspectives on Artificial Intelligence Programming

Publisher Summary

Programming Styles

Use of Multiple Paradigms

Programming Environments

Narrow Knowledge-Based Systems

Directions and Themes Revisited

BIBLIOGRAPHY

INDEX

Copyright

Acquisitions Editor and President Michael B. Morgan

Permissions and Coordinating Editor Jennifer Ballentine

Production Manager Mary Borchers

Copy Editor Maggie Duncan

Cover Designer Beverly Kennon-Kelley

Typesetting Shirley Tucker and Valerie Brewster

Production Assistants Debra Kern and Lisa de Beauclair

Library of Congress Cataloging-in-Publication Data

Readings in artificial intelligence and software engineering.

Bibliography: p.

Includes index.

1. Artificial intelligence–Data processing.

2. Electronic digital computers–Programming.

3. Programming languages (Electronic computers)

I. Rich, Charles, 1951– . II. Waters, Richard C.

Q336.R43 1986 006.3 86-18627

ISBN 0-934613-12-5

Morgan Kaufmann Publishers, Inc.

95 First Street, Los Altos, California 94022

© 1986 by Morgan Kaufmann Publishers, Inc.

All rights reserved.

Printed in the United States of America

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopying, recording, or otherwise—without the prior written permission of the publisher.

90 89 88 87 5 4 3 2

ACKNOWLEDGMENTS

The editors would like to thank Cristina Ciro for her help in preparing the bibliography and index, and Robert Balzer, David R. Barstow, Daniel Bobrow, Martin Feather, Susan Gerhart, Cordell Green, Sol Greenspan, Elaine Kant, Jack Mostow, Beau Sheil, Elliot Soloway, and Richard Waldinger for their comments on chapter selections.

The editors would also like to thank the publishers and authors for permission to reprint copyrighted material in this volume:

Figure 1 (of the introduction) is reprinted from CACM 1(4), 1958, p. 8. Courtesy of the Association for Computing Machinery, Inc.

Zohar Manna and Richard Waldinger, A Deductive Approach to Program Synthesis, ACM Trans. on Prog. Lang. and Sys. 2(1), 1980, 90–121. Copyright © 1980, Association for Computing Machinery, Inc. All rights reserved. Reprinted by permission of ACM and the authors.

Douglas R. Smith, Top-Down Synthesis of Divide-and-Conquer Algorithms, Artificial Intelligence 27(1), 1985, 43–96. Copyright © 1985, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the author.

Donald I. Good, Mechanical Proofs About Computer Programs, Philos. Trans. R. Soc. Lond. 312(1522), 1984, 389–409. Copyright © 1984, Royal Society of London. All rights reserved. Reprinted by permission of the Royal Society of London and the author.

Robert S. Boyer and J Strother Moore, Proof Checking the RSA Public Key Encryption Algorithm, The American Mathematical Monthly 91(3), 1984, 181–189. Copyright © 1984, The Mathematical Association of America. Reprinted with the permission of the MAA and authors.

John Darlington, An Experimental Program Transformation and Synthesis System, Artificial Intelligence 16, 1981, 1–46. Copyright © 1981, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the authors.

Manfred Broy and Peter Pepper, Program Development as a Formal Activity, IEEE Trans. on Software Eng. SE-7(1), 1981, 14–22. Copyright © 1981, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

David R. Barstow, An Experiment in Knowledge-Based Automatic Programming, Artificial Intelligence 12, 1979, 73–119. Copyright © 1979, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the authors.

Elaine Kant, On the Efficient Synthesis of Efficient Programs, Artificial Intelligence 20, 1983, 253–306. Copyright © 1983, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the author.

Thomas E. Cheatham, Jr., Reusability Through Program Transformations, IEEE Trans. on Software Eng. SE-10(5), 1984, 589–594. Copyright © 1984, IEEE. All rights reserved. Reprinted by permission of IEEE and the author.

David S. Wile, Program Developments: Formal Explanations of Implementations, CACM 26(11), 1983, 902–911. Copyright © 1983, Association for Computing Machinery, Inc. All rights reserved. Reprinted by permission of ACM and the author.

George E. Heidorn, Automatic Programming Through Natural Language Dialogue: A Survey, IBM J. Res. Develop. 20(4), 1976, 302–313. Copyright © 1976, International Business Machines Corporation. All rights reserved. Reprinted by permission of IBM and the author.

Gregory R. Ruth, Protosystem I: An Automatic Programming System Prototype, AFIPS Conference Proceedings, National Computer Conference, Anaheim, CA, 1978, 675–681. Copyright © 1978, AFIPS. All rights reserved. Reprinted by permission of AFIPS and the author.

Robert M. Balzer, Neil Goldman, and David Wile, Informality in Program Specifications, IEEE Trans. on Software Eng. SE-4(2), 1978, 94–103. Copyright © 1978, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

Edmund Schonberg, Jacob T. Schwartz, and Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, ACM Trans. on Prog. Lang. and Sys. 3(2), 1981, 126–143. Copyright © 1981, Association for Computing Machinery, Inc. All rights reserved. Reprinted by permission of ACM and the authors.

Lawrence A. Rowe and Fred M. Tonge, Automating the Selection of Implementation Structures, IEEE Trans. on Software Eng. SE-4(6), 1978, 494–506. Copyright © 1978, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

Cordell Green and Stephen Westfold, Knowledge-Based Programming Self Applied, Machine Intelligence 10, Chichester: Ellis Horwood Ltd, Halsted Press, 1982, Copyright © 1982, Ellis Horwood Ltd. All rights reserved. Reprinted by permission of Ellis Horwood and the authors.

Martin S. Feather and Phillip E. London, Implementing Specification Freedoms, Science of Computer Programming 2, 91–131, Amsterdam: North-Holland Publishing Company, 1982. Copyright © 1982, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the authors.

Phillip D. Summers, A Methodology for LISP Program Construction from Examples, JACM 24(1), 1977, 161–175. Copyright © 1977, Association for Computing Machinery, Inc. All rights reserved. Reprinted by permission of ACM and the author.

Michael A. Bauer, Programming by Examples, Artificial Intelligence 12, 1979, 1–21. Copyright © 1979, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the authors.

Robert W. Floyd, Toward Interactive Design of Correct Programs, Information Processing 71, 1971, 7–11. Copyright © 1971, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the author.

Mark S. Moriconi, A Designer/Verifier’s Assistant, IEEE Trans. on Software Eng. SE-5(4), 1979, 387–401. Copyright © 1979, IEEE. All rights reserved. Reprinted by permission of IEEE and the author.

Richard C. Waters, The Programmer’s Apprentice: A Session with KBEmacs, IEEE Trans. on Software Eng. SE-11(11), 1985, 1296–1320. Copyright © 1985, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

Cordell Green, David Luckham, Robert Balzer, Thomas Cheatham, and Charles Rich, Report on a Knowledge-Based Software Assistant, Rome Air Development Center, Technical Report RADC-TR-83-195, 1983, 1–50. This article is the final report written by Kestrel Institute for the Rome Air Development Center on contract F30602-81-C-0206. Opinions expressed therein, unless otherwise specifically indicated, are those of the authors. They do not purport to express the views of the Rome Air Development Center, the Air Force Systems Command, the Department of the Air Force or any other department or agency of the United States Government. The report is available from the National Technical Information Service under the accession number AD-A134699. Only portions of the report are included here: the title page, table of contents, abstract, pages 1–5 and 7–50, acknowledgments and references. Reprinted by permission of Rome Air Development Center and the authors.

Gregory R. Ruth, Intelligent Program Analysis, Artificial Intelligence 7, 1976, 65–85. Copyright © 1976, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the author.

W. Lewis Johnson and Elliot Soloway, PROUST: Knowledge-Based Program Understanding, IEEE Trans. on Software Eng. SE-11(3), 1985, 267–275. Copyright © 1985, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

Cordell Green and David R. Barstow, On Program Synthesis Knowledge, Artificial Intelligence 10, 1978, 241–279. Copyright © 1978, North-Holland Publishing Company. All rights reserved. Reprinted by permission of North-Holland and the authors.

Nachum Dershowitz, Program Abstraction and Instantiation, ACM Trans. on Prog. Lang. and Sys. 7(3), 1985, 446–477. Copyright © 1985, Association for Computing Machinery, Inc. All rights reserved. Reprinted by permission of ACM and the author.

Charles Rich, A Formal Representation for Plans in the Programmer’s Apprentice, Proc. of the 7th Int. Joint Conf. on Artificial Intelligence, Vancouver, Canada, 1981, 1044–1052. Copyright © 1981, IJCAI. All rights reserved. Used by permission of IJCAI and the authors; copies of the proceedings can be obtained from Morgan Kaufmann Publishers, 95 First St., Suite 120, Los Altos, CA 94022. This version was reproduced, by special arrangement, from On Conceptual Modeling, edited by Michael L. Brodie, John Mylopoulos, and Joachim W. Schmidt, New York: Springer-Verlag, 1984, 243–269.

Elliot Soloway and Kate Erlich, Empirical Studies of Programming Knowledge, IEEE Trans. on Software Eng. SE-10(5), 1984, 595–609. Copyright © 1984, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

James M. Neighbors, The Draco Approach to Constructing Software from Reusable Components, IEEE Trans. on Software Eng. SE-10(5), 1984, 564–574. Copyright © 1984, IEEE. All rights reserved. Reprinted by permission of IEEE.

David R. Barstow, A Perspective on Automatic Programming, AI Magazine (Spring), 1984, 5–27. Copyright © 1984, David R. Barstow. All rights reserved. Reprinted by permission of the author.

Alexander Borgida, Sol Greenspan, and John Mylopoulos, Knowledge Representation as the Basis for Requirements Specifications, IEEE Computer (April), 1985, 82–90. Copyright © 1985, IEEE. All rights reserved. Reprinted by permission of IEEE and the authors.

Beau Sheil, Power Tools for Programmers, Datamation (February), 1983, 131–144. Copyright © Technical Publishing Company, A Dun and Bradstreet Company, 1983. All rights reserved. Reprinted by permission of DATAMATION® magazine and the author.

Daniel G. Bobrow and Mark J. Stefik, Perspectives on Artificial Intelligence Programming, Science 231, 1986, 951–957. Copyright © 1986, American Association for the Advancement of Science. All rights reserved. Reprinted by permission of Science and the authors.

INTRODUCTION

The overlap between artificial intelligence and software engineering has been an active area of research for many years. (For other overviews of this area see [Barr and Feigenbaum 82], [Biermann, Guiho, and Kodratoff 84], [Green 85], and [Mostow 85].)

The application of artificial intelligence to software engineering is of interest from at least two perspectives. On the one hand, it is of pragmatic importance to the software engineer. Artificial intelligence techniques hold the promise of achieving order of magnitude improvements in programmer productivity and program reliability.

On the other hand, software engineering has proven to be a stimulating domain for artificial intelligence research. Attempts to apply artificial intelligence techniques to the programming task have motivated further developments in knowledge representation and automated reasoning.

This volume is a collection of thirty-four archival papers covering the spectrum of work in this area. The papers are grouped into eleven sections according to the main technique (e.g., deductive synthesis, program transformations) or application focus (e.g., program verification, programming tutors) of each paper. Since many papers are relevant to more than one section, each section is introduced by a short discussion which ties together the papers in the section and points out other related papers in the volume. An extensive bibliography can be found at the back of the volume.

Automatic Programming

The ultimate goal of artificial intelligence applied to software engineering is automatic programming. In the limit, automatic programming would allow a user to simply say what is wanted and have a program produced completely automatically. However, it is unlikely that this kind of performance will be achieved soon. As a result, fully automatic programming has sometimes been derisively referred to as automagic programming.

A much more modest level of automatic programming has, in a sense, existed for a long time. Figure 1 reproduces a chart from the April 1958 issue of the Communications of the ACM. The chart lists the availability of automatic programming systems for various computers of the time. Most of the systems listed are what are now called assemblers, a few (notably FORTRAN for the IBM 704) are compilers. The use of the term automatic programming in Figure 1 may seem inappropriate. However, it is actually quite reasonable. In comparison with programming in absolute hexadecimal, compilers are magic.

Fig. 1 Communications of the ACM Volume 1 #4, April 1958, p. 8.

To obtain a clearer understanding of what automatic programming is, consider more carefully the phrase a user simply says what is wanted. In particular, ask the following questions: Who is the user? What does the user say? How is what the user says different from writing a program? Depending on how these questions are answered, several different kinds of automatic programming systems can be envisioned. (For an influential early overview of these issues see [Balzer 73].)

Suppose that the accounting department of a large company has perceived the need for a program. Figure 2 shows the agents that are involved in the creation of the needed program. At the current time, all of these agents are people. Eventually, one or more of these agents may be replaced by an automatic programming system.

Fig. 2 Hierarchy of Agents Producing an Accounting System.

Note that Figure 2 is not intended to imply a commitment to any particular view of the programming process. The main goal of the figure is to highlight the different kinds of knowledge that are involved in different parts of the process.

At the top of the hierarchy is a manager who quite likely has only a rudimentary knowledge of accounting. The manager’s job is to perceive the need and initiate the process by creating a brief, vague requirement. The term vague is used here to highlight the fact that the only way this requirement can succeed in being brief is for it to also be incomplete, ambiguous, and/or inconsistent.

The next agent in the hierarchy is an accounting expert. The accounting expert’s job is to take the manager’s vague requirement and create a detailed requirement that is more or less complete, unambiguous, and consistent. A key feature of this requirement is that it is couched in terms of the basic vocabulary of accounting and is intended to be evaluated by other accountants. Thus near the top of the hierarchy, accounting knowledge plays a crucial role.

The third agent in the hierarchy is a system analyst/designer. The analyst/designer’s job is to design the basic architecture of the program and to translate the requirement into a detailed specification. A key feature of this specification is that it is couched in terms of the vocabulary of programming rather than accounting. The system analyst/designer must have both extensive knowledge of programming and at least a basic understanding of accounting in order to interface between the upper and lower parts of the hierarchy.

The agent at the bottom of the hierarchy is a programmer. The programmer’s job is to create code in a high level language based on the detailed specification. The programmer is not expected to know anything about accounting. The bottom of the hierarchy is primarily concerned with programming knowledge.

Figure 2 also implicitly defines four different levels at which automatic programming might be applied. At the lowest level, the programmer is the user of an automatic programming system (a compiler), which automatically converts high-level code into machine executable code. In this case, what the user says is obviously a program.

At the next level up, the analyst/designer could use an automatic programming system that takes specifications as input. Using this system, the analyst/designer would express himself in some kind of formal specification language. This language would probably be similar to a programming language except that it would directly support abstract concepts such as quantifiers and sets without forcing the analyst/designer to specify how they should be implemented.

Going one level higher, the accounting expert could use an automatic programming system that produced programs directly from requirements. The accounting expert might express himself either in English or in some more formal requirements language. In either case, this is the first level at which the input to the automatic programming system would be something significantly different from a program. The automatic programming system would be replacing the analyst/designer as well as the programmer. As such it would need to have extensive knowledge of program design, as well as considerable knowledge of accounting.

At the highest level, the manager could converse directly with an automatic programming system in free-form English. As mentioned above, this is the ultimate goal of automatic programming. Notice that at this level most of the hard problems have nothing to do with programming. The system would be replacing the accounting expert and would itself have to be an accounting expert. The primary activity of the system would be helping the manager figure out exactly what was wanted in the context of accounting.

Cutting the Problem Down

Fully automatic programming is too big a problem to be solved in a single step. In order to provide avenues of attack, researchers have cut the problem down in a number of different ways. The various approaches lead to different kinds of intermediate products and results.

One avenue of attack is to work up from the bottom of Figure 2. For example, a great deal of work has been directed toward automatically going from specifications to code. One important research approach in this area has been to develop so-called very high level languages (see [Schonberg, Schwartz, and Sharir, Chapter 14], [Green and Westfold, Chapter 16], and [Feather and London, Chapter 17] and systems to support them (see [Barstow, Chapter 7], [Kant, Chapter 8], and [Rowe and Tonge, Chapter 15]).

The complementary avenue of attack is to work down from the top of Figure 2. Work in this area has focused on converting free-form English into formal requirements (see [Balzer, Goldman, and Wile, Chapter 13] and on the representation of the knowledge in a requirement (see [Borgida, Greenspan, and Mylopoulos, Chapter 32] and [Greenspan, Borgida, and Mylopoulos 86]). Although not very much effort has been expended in this direction to date, this approach may turn out to be particularly important. Errors made early in the program development process are the most costly. In addition, while there are many specialized editors and other tools for program implementation, there are currently very few tools that help with requirements acquisition. As a result, an automatic system whose output was a reliable requirements document would be of great value, even if the remainder of the software process was manual.

Another way to cut down the automatic programming problem is to take a vertical slice through Figure 2. Given a narrow enough domain, one can construct a completely automatic programming system. This is done by designing a special-purpose problem-oriented language and implementing a special-purpose program generator, which compiles this language. The user creates and modifies programs in the special-purpose language without ever having to look at the programs produced. Numerous examples of program generators exist for various business and scientific applications (see [Horowitz, Kemper, and Narasimhan 85] for a survey). This is a second sense in which automatic programming exists today.

The main drawback of current program generators is their inflexibility. They work beautifully within their domain of expertise and not at all even a fraction outside of it. The only way to stretch a program generator beyond its intended domain is to manually modify the code produced by the generator. However, this is undesirable for two reasons. First, with most generators, the code created is intended only for compilation and is nearly unreadable. Modification of this kind of code is extremely error-prone. Second, a key benefit of program generators is that the output program can be modified to keep up with changing requirements by simply modifying the high-level input and rerunning the generator. Unfortunately, once the output of the generator has been manually modified, it has to be remodified each time the generator is rerun.

The main goal of research within the program generator approach has been to cover ever-broader domains with more flexibility at the boundaries. The Draco system [Neighbors, Chapter 30] and the ΦNIX system [Barstow, Chapter 31] illustrate progress in this direction.

A second kind of vertical slice through the automatic programming problem is to provide partial automation at many levels. At a minimum, such a system would perform bookkeeping and other mundane tasks. Going beyond this, it could supply varying degrees of automation for different programming tasks, such as implementation, testing, or requirements analysis. The Designer/Verifier’s Assistant [Moriconi, Chapter 21], the Programmer’s Apprentice [Rich and Shrobe 78] [Waters, Chapter 22], and the Knowledge-Based Software Assistant [Green, Luckham, Balzer, Cheatham, and Rich, Chapter 23]) are examples of this approach. An attractive feature of the assistant approach is that it makes it possible to take immediate advantage of incremental improvements in automation of different kinds.

Theorem-Proving Techniques

Techniques for automatically finding (or helping to find) proofs of theorems has been an early and active area of artificial intelligence research. (For a survey of this research, see [Siekmann and Wrightson 83] , [Bledsoe and Loveland 84], or [Wos et al., 84]). As soon as programming languages were given a firm mathematical basis by Floyd [1967] and others, attempts began to apply automatic theorem-proving techniques to the programming task. This has been done primarily in two forms: deductive program synthesis and program verification.

Deductive Synthesis

Deductive program synthesis is based on the observation that constructive proofs are equivalent to programs because each step of a constructive proof can be interpreted as a step of computation. For example, in a constructive proof, whenever case analysis is used, an explicit method for computing which case holds in any particular situation must be supplied. In contrast, a nonconstructive proof need show only that, taken together, the cases cover all possible situations. (For a more technical discussion of the relation between constructive proofs and programs, see [Constable 71].)

A constructive theorem prover can be used to derive a program from its specification as follows. Suppose that the program to be derived takes an input x and produces an output y. Further, suppose that the specifications of the program state that a precondition P(x) should be true of the input and that a postcondition Q(x,y) will be true of the output. This specification is converted into the following theorem, which is given to the theorem prover.

The process of constructive proof, in effect, discovers a method for finding y for any given x. A program that implements this method can either be constructed incrementally during the proof process or extracted from the proof as a separate post-phase. One might observe that this approach has translated one hard problem, namely automatic programming, into another hard problem, namely automatic theorem proving.

Deductive synthesis has been shown to work on a number of examples (see [Manna and Waldinger, Chapter 1] or [Dershowitz 85]). However, at the current state of the art, it is limited to the production of small programs with specifications that can be easily formalized in a logical language. Synthesis is limited to small programs, because large programs correspond to large proofs. Current theorem provers cannot discover large proofs, because they are unable to effectively control the process of searching for a proof in the space of possible deductions.

An area of work closely related to deductive synthesis is automated algorithm design. The distinction between ordinary program synthesis and algorithm design is mostly one of degree. Ordinary program synthesis, in effect, typically combines more or less standard algorithms. In contrast, algorithm design seeks to discover totally new algorithms.

Most of the work on algorithm design is set within the general framework of deductive synthesis (see [Bibel 80], [Barstow 82], and [Smith, Chapter 2]). It differs from ordinary deductive synthesis primarily in the system’s depth of understanding. In order to support real discovery, an automatic algorithm design system needs to have a very detailed representation of the mathematical properties of the data objects involved.

An alternate approach to algorithm design has been to try to duplicate the methods used by human designers. This has lead to work on modeling human designers [Kant 85] and to investigations of the role of analysis and symbolic execution in the design process [Steier and Kant 85].

Program Verification

Given a program and its formal specification, an automatic theorem prover (either constructive or nonconstructive) can be used to verify that the program satisfies the specification. This is typically done using one of two symmetrical methods. In the first method, the precondition is passed forward over the program, yielding a logical formula describing the net effect of the program. This is done a statement at a time by combining the precondition with the axioms describing the behavior of the statement. Each step yields a new logical formula that embodies the sum total that is known to be true after the statement. Once a logical formula describing the interaction of the program as a whole with the precondition has been obtained, an automatic theorem prover is used to verify that the postcondition follows from this logical formula. The second method operates in a reverse way by passing the postcondition backward over the program and then proving that the resulting logical formula is implied by the precondition.

Like deductive synthesis, automatic program verification is limited by the fact that current automatic theorem provers cannot prove theorems that require large proofs. Two approaches have been taken to increase the size of program that can be automatically verified. First, the theorem prover can be given special-purpose knowledge (i.e., lemmas) about particular areas of programming to help it verify programs in that area. Second, human interaction can be used to guide the theorem prover. In the limit, this approach reduces the theorem prover to the role of a mechanical proof checker. (For an overview of program verification see [Boyer and Moore 85]. For a collection of current research papers see [Verkshop 85]. For examples of using an automated verification system, see [Boyer and Moore 79] and [Polak 79].)

Because of the great cost and effort currently required to verify a program, the main applications to date have been small, highly critical programs, such as communication protocols (see [Sunshine et al., 82] and [Good, Chapter 3]) and security algorithms (see [Boyer and Moore, Chapter 4]). Another important application area has been the verification of reusable datatype implementations (see [Gerhart et al., 80]).

In the discussion above, both deductive synthesis and automatic program verification are described in an all or nothing way. Given a complete specification, a complete program is derived. Given a complete program and a complete specification, a proof is derived. It is not clear whether automatic theorem provers will ever advance to the point where either of these monolithic approaches will succeed when applied to programs of commercial size. In light of this, these approaches are gradually being replaced by the view that verification and synthesis should be applied to various subproblems throughout the program development process. For example, from the viewpoint of programmer productivity, it makes good sense to verify individual properties of a program design as early as possible. As another example, the PRL system [Bates and Constable 85] combines aspects of deductive synthesis and program verification to support individual steps of program construction.

Transformational Approaches

The most active area in automatic programming research currently is the use of transformations to support program construction. A program transformation takes a part of a program and replaces it with a new (transformed) part. Typically, a program transformation is correctness preserving, in that the new part of the program computes the same thing as the old part. The purpose of a transformation is to make the part better on some scale (e.g., more efficient or more concrete). For example, a transformation might be used to replace X**2 with X*X. (For surveys of transformational research see [Partsch and Steinbruggen 83] and [Feather 86].)

As usually implemented, a program transformation has three parts. It has a pattern that matches against parts of a program to determine where to apply the transformation. (The program being transformed is often written in a wide-spectrum language [Bauer et al., 78], which contains a mixture of conventional and specification-like constructs.) It has a set of applicability conditions, which further restrict the places where the transformation can be applied. (In many transformational systems, the applicability conditions are expressed in a logical language and theorem proving is used to determine whether or not they are satisfied in a given situation.) Finally, a transformation has a (usually procedural) action that creates a new program part to replace whatever the pattern matched.

There are two principal kinds of transformations: vertical and lateral. Vertical transformations define an expression at one level of abstraction in terms of an expression at a lower level of abstraction–for example, defining how to enumerate the elements of a vector using a loop. Lateral transformations specify an equivalence between two expressions at a similar level of abstraction–for example, specifying the commutativity of addition. Lateral transformations are used principally to promote efficiency and to set things up properly so that vertical transformations can be applied.

The first use of transformations was based on the notion that, in most programs, there is natural trade-off between efficiency and clarity. It is often possible to write a program in such a way that it directly mirrors its intent and is therefore self-evidently correct. Unfortunately, such a program is usually very inefficient. Lateral transformations can then be used to convert a clear but inefficient program into an efficient one.

The transformational system of Burstall and Darlington [Burstall and Darlington 77] [Darlington, Chapter 5] uses a small fixed set of powerful general-purpose lateral transformations in order to improve the efficiency of programs. Their system has demonstrated the feasibility of allowing a programmer to gain the benefit of clarity without paying the price of inefficiency.

The most common use of transformations is as the basis for transformational implementation [Balzer 81]. These systems approach the notion of self-evidently correct programs from a different direction by converting programs in an easily readable, very high level, wide-spectrum language into an efficient, directly executable form. This is done by iteratively applying a set of vertical and lateral transformation rules until all of the specification-like constructs in the initial program have been replaced (implemented) by conventional constructs. In contrast to the system of Burstall and Darlington, these systems use large libraries of special-purpose transformations.

In many ways, a transformational implementation system can be viewed as a special kind of program generator. The principal difference between transformational implementation systems and program generators is that the knowledge of how to implement programs is represented in a library of transformations rather than in a procedure. This makes it easier to extend and modify a transformational implementation system; however, it brings up a new problem: controlling the application of transformations.

The main difficulty in controlling the application of transformations is that, in a typical situation, many different transformations are applicable, and different results will be obtained depending on which transformation is chosen. For example, if two transformations are both applicable to the same part of a program, applying either one may modify the program in such a way that the other is no longer applicable. Choosing to apply one transformation rather than the other amounts to making an implementation decision.

With regard to vertical transformations, the control problem is typically not too severe because in most situations only one or two transformations will be applicable to a given abstract expression. However, the selection of lateral transformations is typically quite difficult and has to rely on manual control.

Existing transformational implementation systems can be divided into two classes: those that are relatively limited in power but require no user guidance and those that are capable of very complex implementations but only under user guidance. TAMPR [Boyle and Muralidharan 84] and PDS [Cheatham, Chapter 9] use simple control strategies and restrictions on the kinds of transformations that can be defined in order to obviate the need for user guidance. PDS is particularly interesting because of its emphasis on having the user define new abstract terms and transformations as part of the programming process.

The PSI system [Green 77] was one of the first systems to use a transformational implementation module for complex implementation. PSI’s transformational module [Barstow, Chapter 7] operated without guidance, generating all possible low-level programs. It was assumed that another component [Kant, Chapter 8] would provide guidance as to which transformations to use. Work on complex transformational implementation systems is active both at the Information Sciences Institute, University of Southern California, (see [Balzer 85]) and the Kestrel Institute (see [Smith, Kotik, and Westfold 85]). A key focus of both these efforts has been to reduce the need for user guidance of the transformation selection process (see [Feather 82], [Fickas 85], and [Wile, Chapter 10]).

Another important classification dimension in program transformation research is between efforts that focus on the correctness-preserving nature of transformations (e.g., [Broy and Pepper, Chapter 6]) and efforts that focus on the knowledge representation aspect of transformations (e.g., [Barstow, Chapter 7]). This is not to say that Barstow does not care if his transformations produce incorrect programs, or that there is no knowledge represented by Broy and Pepper’s transformations. Rather, there is a significant difference of emphasis. The correctness-preserving approach emphasizes the formal logical basis of transformations, which makes verification possible. The knowledge representation approach emphasizes the use of transformations as a vehicle for codifying programming knowledge.

Specification Techniques

As mentioned above, a principal issue in automatic programming is what language the user employs to describe the desired program. Much research has focused on three kinds of user interfaces: natural language, very high level programming languages, and examples of behavior.

Natural Language Specifications

The ultimate in automatic programming would be to support user input in unrestricted natural language. Protosystem-I [Ruth, Chapter 12] was a notable early attempt in this direction. Several other early systems for automatic programming using natural language input are surveyed in [Heidorn, Chapter 11].

The main lesson of this early work is that the essential difficulty with natural language specifications is not the syntax or semantics of natural language per se, but rather the informality people use when communicating about a task. The essential problem is not understanding, for example, that the inputs to the program are means the same as the program’s inputs are, but rather understanding that when the user says something like

The RATS transmission times are entered into the schedule.

the user really means something like

Each RATS clock transmission time and transmission length is made a component of a new transmission entry which is entered into the transmission schedule.

(This example is taken from [Balzer, Goldman, and Wile, Chapter 13] See also [Ginsparg 78], [McCune 79], and [McCune 80].)

In response to this lesson, most automatic programming researchers now try to separate natural language processing issues (see [Grosz, Webber, and Sparck Jones 86] for a survey) from informality issues (see [Balzer, Goldman, and Wile, Chapter 13]). The current focus of automatic programming research has shifted toward designing new kinds of formal languages in which the syntactic processing is straightforward but semantic informality is allowed. Many of these new formalisms are being developed under the rubric of very high level languages.

Very High Level Languages

The archetype of a very high level language is SETL (see [Dewar, Grand, Liu, and Schwartz 79], [Freudenberger, Schwartz and Sharir 83], and [Schonberg, Schwartz and Sharir, Chapter 14]). SETL supports most of the standard constructs of any Algol-like programming language. In addition, it supports two convenient universal data structures–tuples and sets. For example, a mapping is treated as a set of 2-tuples. SETL also supports the use of universal and existential quantifiers in a program. For example, the following is the form for a SETL statement for performing some computation on every element of the set S.

The goal of providing such expressive facilities is to free the programmer from having to think about the detailed design of data structures. The SETL compiler will decide how data structures should be implemented. This decrease in what the programmer has to worry about is a key to the productivity gains that should be obtained by the use of very high level languages.

As it is currently evolving, the V language [Green and Westfold, Chapter 16] is in many ways similar to SETL. The GIST language [Feather and London, Chapter 17] is representative of a more ambitious direction in research on very high level languages. The goal of GIST is to provide the expressiveness of natural language while imposing formal syntax and semantics. Two examples of capabilities provided in GIST that distinguish it from SETL-like languages are: historical reference (the ability to refer to past process states) and constraints (restrictions on acceptable system behavior in the form of global declarations). (For a general discussion of other desirable features of a specification language, see [Balzer and Goldman 79].)

Not surprisingly, the more advanced features that you put into a very high level language, the harder it is to compile (and to some extent, understand, see [Swartout 83]). Compilers for SETL and V are both at least partially implemented. In contrast, although it is an active area of research (see [Fickas 85]), a GIST compiler has not yet been constructed.

When compiling languages such as SETL and V, the paramount problem is deciding how to implement the abstract data structures in the program. These decisions are needed not only to represent the data, but also to decide how to use loops to implement quantifiers in the program. Several researchers (e.g., [Low 78] and [Rowe and Tonge, Chapter 15]) have focused on the problem of data structure implementation separate from the details of any specific very high level language.

The SETL compiler operates in a procedural fashion somewhat similar to a conventional optimizing compiler. At the current time it is only moderately successful at producing efficient code. In order to make implementation choices that lead to more efficient run-time performance, the SETL compiler will have to perform a deeper analysis of the input program. Perfecting this analysis is the current focus of SETL research. Meanwhile, a declaration language is provided that the programmer can use to tell the SETL compiler how to implement particular sets. Although this is an appealing compromise in the spirit of incremental automation, it is less than satisfactory in practice. The problem is that if the full expressive power of SETL is used in writing a program, it can be very difficult for a programmer to figure out what to recommend.

The currently favored technique for compiling very high level languages is to use a program transformation system to remove the very high level constructs. For example, this approach is used for the V language [Green and Westfold, Chapter 16]. As discussed above, such transformational systems require advice on what transformations should be applied where. Unfortunately, as in the case of explicit declarations, it can be very difficult for a programmer to come up with the needed advice.

Another important trend in very high level languages is toward specialized languages for particular application areas. For applications like business data processing [Cheng, Lock, and Prywes 84], quite high level languages have been developed that can be successfully compiled using reasonably straightforward techniques.

Programming by Example

An appealing specification idea, rather different from those discussed above, is to describe a program via examples of its behavior. The appeal of this approach is that, like natural language, even people who have no knowledge of programming are familiar with examples as an descriptive technique. Further, individual examples are easy to understand and modify.

The difficulty with programming by example is that, although examples are easy to understand by themselves, the program produced has to be more general than strictly implied by the examples given. It would be trivial to construct a program that duplicated the examples given and did nothing else. What is wanted is a program which operates on whole classes of input data in a manner analogous to, but more general than, the examples. The difficulty with generalization is that there are always many ways to generalize any set of examples.

The main effort in any programming by example system is therefore directed toward finding an appropriate level of generalization. For example, consider the program specified by the following input-output pair.

It is pretty clear from this example that the input is a list and the items in this list are doubled and reversed in the output. However, it would probably be an over-generalization to assume that doubling and reversing should be applied to elements of the input list that are themselves lists. On the other hand, it would probably be an under-generalization to assume that the input must be of length four. (See [Smith 82] and [Michalski, Carbonell, and Mitchell 83] for a discussion of generalization in the general context of machine learning.)

Early work on programming by example (see [Hardy 75], [Shaw, Swartout, and Green 75], and [Siklossy and Sykes 75]) was ad hoc in nature. This changed with the work of Summers [Chapter 18] who established theoretical foundations for the field. Most subsequent work (for example see [Biermann 78] and [Kodratoff and Jouannaud 84]) is based on Summers’s approach.

Most of the work on programming by example uses Lisp as the target language (for a survey see [Smith 84]). The reason for this is not intrinsic to any of the techniques, but rather because of the fact that the Lisp programming environment facilitates writing programs that operate on programs.

Although it initially created a good deal of excitement, programming by example now appears to be of only theoretical interest. The problem is that the techniques do not scale up to programs of realistic complexity. Unfortunately, as input-output pairs become more complex, the problem of generalizing them appropriately becomes astronomically more complex.

There are basically only two ways to cut the generalization problem down to a manageable size. First, more examples can be provided in order to reduce ambiguity, including examples of intermediate computation steps (see [Biermann 72], [Biermann and Krishnaswamy 76], and [Bauer, Chapter 19]). Unfortunately, when the number of examples becomes too large, this becomes an inefficient means of specification as compared with other formal techniques. Alternatively, assumptions can be built into the programming-by-example system about about the class of programs that can be produced. For example, [Andreae 85] synthesizes robot programs from examples. The system described in [Hedrick 76] assumes that the synthesized program must be a rule-based production system. Unfortunately, when the structural assumptions begin to get this strong, the programming-by-example system ends up being essentially a special kind of program generator.

A different approach to using examples is illustrated by the Tinker system [Lieberman and Hewitt 80]. Tinker does not attempt to generalize the examples automatically but rather provides a program development environment, which helps the user perform the generalization. In this context, the input-output examples are perhaps better thought of as test cases.

Intelligent Assistants

Most of the systems described above attempt to completely automate parts of the programming task. Another approach is to assist programmers rather than replace them. An advantage of this approach is that it makes it possible to construct useful systems even while the ultimate goal of automatic programming remains out of reach.

An intelligent assistant is an active agent in the programming process. In the near term, the machine will act as a programmer’s junior partner and critic, keeping track of details and assisting with the routine aspects of the programming process, allowing the programmer to concentrate on the more difficult parts. As research in artificial intelligence progresses, however, it will be possible to shift more and more tasks from the programmer to the machine.

Research on intelligent assistants has uncovered two key issues. The first issue is the division of labor between the programmer and the assistant: How are the programmer and the machine going to succeed in cooperating and communicating? This brings up a second key issue: It would be impossibly tedious for the programmer to explain each instruction or decision to the assistant from first principles. Rather, the programmer needs to rely on a body of shared knowledge in order to communicate concisely.

At minimum, an intelligent assistant must understand the technical vocabulary of programming, including such terms as search, stack, side-effect, and so on. As will be discussed further below, an important part of research on automatic programming generally is concerned with identifying and codifying the specific knowledge that is required for the machine to participate in particular programming tasks.

The evolution of research on intelligent assistants has been marked by a series of influential thought papers, which proposed architectures for programming assistants of various kinds. This series of proposals started with [Floyd, Chapter 20], continued through the A system [Winograd 73], the Programming Apprentice [Hewitt and Smith 75], and the Lisp Programmer’s Apprentice [Rich and Shrobe 78], and ends most recently with the Knowledge-Based Software Assistant [Green, Luckham, Balzer, Cheatham, and Rich, Chapter 23].

Prototype implementations of intelligent programming assistants include the Designer/Verifier’s Assistant [Moriconi, Chapter 21], which emphasizes the theorem-proving capabilities of the machine, and KBEmacs (the Knowledge-Based Editor in Emacs) [Waters, Chapter 22], which emphasizes the use of a knowledge base of standard programming forms in program construction. Prototype assistants have also been constructed in the areas of program testing [Chapman 82] and project management [Kedzierski 82].

Programming Tutors

A specialized kind of intelligent programming assistant is a programming tutor. In this application, the assistant helps a novice programmer to learn programming rather than helping a expert programmer to construct programs. An interesting aspect of this application is that, in contrast with those above, the assistant is expected to know much more about programming than the user. (For a collection of papers on intelligent tutoring systems in general, see [Sleeman and Brown 82].)

A key function of a programming tutor is to examine a program written by a student programmer, find any errors in it, and then explain the errors to the student in a way that will help the student learn. In order to identify errors in a program, some theory of what errors can occur is required. The various programming tutors that have been constructed (and proposed) differ primarily in the way in which knowledge about errors is represented and in the way errors are identified.

The first system capable of finding a wide range of errors in student programs was the analyzer of [Ruth Chapter 24]. This system relies on a grammar to specify what algorithms are expected in student programs. The grammar is used to parse student programs. Any deviation between a program and what is specified by the grammar is reported as an error. A key problem with this approach is that it is easy for a program to fail to match the grammar even though it is, in fact, correct.

Recently, [Zelinka 86] has proposed using a somewhat similar approach except that the grammar and parsing are applied to a more abstract, graphlike program representation rather than to the program text. This significantly increases the ability of the system to recognize when two programs are equivalent.

An alternate approach to finding errors is to explicitly represent what is wrong instead of what is right. For example, the MENO-II system [Soloway et al., 83] contains a precompiled library of specific bug patterns. The Sniffer system [Shapiro 81] used a library of bug recognition procedures. In the system described in [Adam and Laurent 80] knowledge about errors is encoded in the form of graph transformations. A problem with the bug library approach is that if a program contains errors, but these errors are not in the library, then the program will appear correct to the system.

A third approach to detecting errors is to compare what a program does with its specification. This can be done either via symbolic evaluation (see [Laubsch and Eisenstadt 81]) or by comparing logical descriptions of the behavior (see [Lukey 80]). The Proust system [Johnson and Soloway, Chapter 25] combines recognition, reasoning about specifications, and knowledge about specific bugs.

A final area of investigation stimulated by the desire for intelligent tutors has been basic artificial intelligence research on the role of goals and plans in problem solving (see [Goldstein 75] and [Miller 82]).

Knowledge Representation

A recurring theme in the whole area of artificial intelligence and software engineering is: What is the knowledge that programmers know, and how can it be effectively represented in an automatic system? What programmers know can be naturally divided into two parts: programming knowledge and domain knowledge.

Programming Knowledge

The following facts illustrate the range of programming knowledge from the very basic and simple to the more specialized and complex.

(1) A stack can be implemented using an array and a pointer by. …

(2) Tail recursion can be converted to iteration by. …

(3) The convex hull of a set of points can be efficiently determined by …

This kind of knowledge has to do with the conventional objects of computer science (such as control constructs, arrays, and graphs) and their associated algorithms and implementation relationships. It is the knowledge found in computer science text books such as [Knuth 73] and [Aho, Hopcroft, and Ullman 74].

Knowledge representation has always been a central concern of artificial intelligence research (for an overview see [Brachman and Levesque 85]). Work on representing programming knowledge has been able to take considerable advantage of knowledge representation techniques developed in the context of other tasks. Programming has also served as a driving force for new work on representation. In particular, the following desiderata have been identified for the representation of programming knowledge (see [Rich and Waters 83]).

• Expressiveness. The representation must be capable of capturing a wide variety of programming knowledge, including both data abstractions and procedural abstractions.

• Convenient Combination. The methods for combining units of knowledge should be easy to implement and the properties of combinations should be evident from the properties of the parts.

• Semantic Soundness. The representation must be based on a mathematical foundation that allows correctness conditions to be stated.

• Machine Manipulability. It must be possible to manipulate the representation effectively and efficiently using computer tools.

• Programming Language Independence. The formalism should not be dependent on the syntax of any particular programming language.

Many different representations have been used for programming knowledge. One common approach is to use programming language schemas (see [Wirth 73], [Gerhart 75], [Basu and Misra 76], and [Misra 78]). Unfortunately, this approach has severe drawbacks with regard to expressiveness, convenient combination, and language independence.

Other researchers have used flowchart schemas (see [Ianov 60] and [Manna 74]), which have greater language independence but are still quite limited in expressiveness and have only somewhat improved combination properties.

The dominant current approach to representing programming knowledge is to use program transformations (see [Green and Barstow, Chapter 26] and [Barstow, Chapter 7]). Since transformations are usually stated in terms of the syntax of a particular programming language, they are not language independent. Also, because they typically have a procedural component, transformations have problems with regard to semantic soundness. However, transformations are much more expressive and more easily combined than schemas.

The work described in [Rich, Chapter 28], [Rich 82], and [Rich 85] uses a hybrid representation that combines features of program transformations and flowchart schemas with predicate calculus. This approach has