Readings in Artificial Intelligence and Software Engineering

Readings in Artificial Intelligence and Software Engineering

by Charles Rich, Richard C. Waters
Released June 2014
Publisher(s): Morgan Kaufmann
ISBN: 9781483214429

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description


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.

Table of contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright
  5. ACKNOWLEDGMENTS
  6. INTRODUCTION
  7. I: Deductive Synthesis
    1. Chapter 1: Introduction to Deductive Synthesis
    2. Chapter 2: A Deductive Approach to Program Synthesis
      1. Publisher Summary
      2. MOTIVATION
      3. SPECIFICATION
      4. BASIC STRUCTURE
      5. SPLITTING RULES
      6. TRANSFORMATION RULES
      7. RESOLUTION
      8. THE RESOLUTION RULES
      9. THE POLARITY STRATEGY
      10. MATHEMATICAL INDUCTION AND THE FORMATION OF RECURSIVE CALLS
      11. A COMPLETE EXAMPLE: FINDING THE QUOTIENT OF TWO INTEGERS
      12. THE FORMATION OF AUXILIARY PROCEDURES
      13. GENERALIZATION
      14. COMPARISON WITH THE PURE TRANSFORMATION-RULE APPROACH
      15. ACKNOWLEDGMENTS
    3. Chapter 3: Top-Down Synthesis of Divide-and-Conquer Algorithms
      1. ABSTRACT
      2. 1 Introduction
      3. 2 A Simple Example
      4. 3 Derived Antecedents
      5. 4 SPECIFICATIONS
      6. 5 Design Strategies for Simple Algorithms
      7. 6 The Form and Function of Divide-and-Conquer Algorithms
      8. 7 Design Strategies for Divide-and-Conquer Algorithms
      9. 8 Concluding remarks
      10. Appendix A
      11. ACKNOWLEDGMENT
  8. II: Program Verification
    1. Chapter 4: Introduction to Program Verification
    2. Chapter 5: Mechanical proofs about computer programs
      1. Publisher Summary
      2. 1 INTRODUCTION
      3. 2 A MATHEMATICAL APPROACH
      4. 3 THE GYPSY ENVIRONMENT
      5. 4 AN EXAMPLE
      6. 5 TRIAL APPLICATIONS
      7. 6 CONCLUSION
      8. Appendix A. Formal proof of lemma extend_separation
      9. Appendix B. Formal proof of verification conditionseparator#3
      10. Discussion
    3. Chapter 6: PROOF CHECKING THE RSA PUBLIC KEY ENCRYPTION ALGORITHM
      1. Publisher Summary
      2. 1 Introduction
      3. 2 A Sketch of the Theorem-Prover
      4. 3 Correctness of CRYPT
      5. 4 Fermat’s Theorem
      6. 5 Invertibility of CRYPT
      7. 6 Sample Input to the Theorem-Prover
      8. 7 Conclusion
  9. III: Transformational Approaches
    1. Chapter 7: Introduction to Transformational Approaches
    2. Chapter 8: An Experimental Program Transformation and Synthesis System
      1. ABSTRACT
      2. 1 Introduction
      3. 2 Languages and Formalism Used
      4. 3 System Structure
      5. 4 Synthesis
      6. 5 Generalisation and Sub-function Synthesis
      7. 6 Eureka Elimination
      8. 7 Conclusion
      9. ACKNOWLEDGMENTS
    3. Chapter 9: Program Development as a Formal Activity
      1. Abstract
      2. I INTRODUCTION
      3. II TRANSFORMATION RULES
      4. III CORRECTNESS OF TRANSFORMATIONS
      5. IV TRANSFORMATIONAL SEMANTICS
      6. V THE ROLE OF ABSTRACT DATA TYPES
      7. VI THE ROLE OF ASSERTIONS
      8. VII AN EXTENDED EXAMPLE: THE WARSHALL ALGORITHM
      9. VIII CONCLUDING REMARKS
      10. ACKNOWLEDGMENT
    4. Chapter 10: An Experiment in Knowledge-based Automatic Programming
      1. ABSTRACT
      2. 1 Introduction
      3. 2 Overview of the Knowledge Base
      4. 3 Sample Programs
      5. 4 A Detailed Example
      6. 5 Implementation
      7. 6 Discussion
      8. 7 Approaches to Automatic Programming
      9. 8 Assessment
      10. ACKNOWLEDGEMENTS
    5. Chapter 11: On the Efficient Synthesis of Efficient Programs
      1. ABSTRACT
      2. 1 Introduction
      3. 2 Background
      4. 3 A Framework for Efficient Program Synthesis
      5. 4 An Overview of the LIBRA Implementation
      6. 5 An Example of LIBRA in Operation
      7. 6 Methods for Controlling Search in Program Refinement
      8. 7 Prototypes
      9. 8 Estimating Execution Costs
      10. 9 Adding New Efficiency Knowledge
      11. 10 Results
      12. 11 Related Research
      13. 12 Conclusions
      14. ACKNOWLEDGMENT
    6. Chapter 12: Reusability Through Program Transformations
      1. Abstract
      2. I INTRODUCTION
      3. II ABSTRACT PROGRAMS
      4. III REFINEMENT OF ABSTRACT PROGRAMS TO CONCRETE PROGRAMS
      5. IV SOME EXPERIENCE WITH REUSING ABSTRACT PROGRAMS
      6. V THE PROGRAMMING SUPPORT ENVIRONMENT
      7. VI CONCLUSIONS AND FUTURE DIRECTIONS
    7. Chapter 13: Program Developments: Formal Explanations of Implementations
      1. ABSTRACT
      2. 1 INTRODUCTION: TRANSFORMATIONAL IMPLEMENTATION
      3. 2 DEVELOPMENT LANGUAGE PROPERTIES
      4. 3 THE DEVELOPMENT LANGUAGE
      5. 4 THE DEVELOPMENT PROCESS
      6. 5 REPLAY OF DEVELOPMENTS
      7. 6 THE UNDERLYING PROGRAM MANIPULATION SYSTEM: POPART
      8. 7 STRUCTURES EXPRESSED IN THE PADDLE LANGUAGE
      9. 7.2 Simplifications
      10. 7.3 Conditioning
      11. 7.4 The Development Process: A Simple Example
      12. 7.5 Text Compression: An Extended Example Development
      13. 8 PROBLEMS AND FUTURE RESEARCH
      14. Acknowledgments
  10. IV: Natural Language Specifications
    1. Chapter 14: Introduction to Natural Language Specifications
    2. Chapter 15: Automatic Programming Through Natural Language Dialogue: A Survey
      1. Abstract
      2. Introduction
      3. NPGS
      4. ISI
      5. MIT
      6. IBM
      7. Comparison
      8. Research issues
      9. Acknowledgments
    3. Chapter 16: Protosystem I—An automatic programming system prototype
      1. Publisher Summary
      2. INTRODUCTION
      3. A MODEL OF THE PROGRAM WRITING PROCESS
      4. EFFICIENCY ENHANCEMENT IN SYSTEM DEVELOPMENT
      5. THE DEVELOPMENT OF PROTOSYSTEM I
      6. THE PROTOSYSTEM I DATA PROCESSING SYSTEM MODEL AND THE SYSTEM SPECIFICATION LANGUAGE
      7. THE TRANSLATOR AND THE DATA SET LANGUAGE
      8. THE DESIGN CRITERION AND THE JOB COST ESTIMATOR
      9. THE QUESTION ANSWERER
      10. THE OPTIMIZING DESIGNER
      11. STAGE 4: CODE GENERATION
      12. CONCLUSION
      13. ACKNOWLEDGMENTS
    4. Chapter 17: Informality in Program Specifications
      1. Abstract
      2. I INTRODUCTION
      3. II ATTRIBUTES OF SUITABLE PROCESS - ORIENTED SPECIFICATION LANGUAGES
      4. III WHY OPERATIONAL SPECIFICATIONS ARE HARD TO CONSTRUCT
      5. IV SEMANTIC CONSTRUCTS IN NATURAL LANGUAGE SPECIFICATION
      6. V DESIRABILITY OF INFORMALITY
      7. VI RESULTS
      8. VII DESCRIPTION OF THE PROTOTYPE SYSTEM
  11. V: Very High Level Languages
    1. Chapter 18: Introduction to Very High Level Languages
    2. Chapter 19: An Automatic Technique for Selection of Data Representations in SETL Programs
      1. Publisher Summary
      2. 1 INTRODUCTION
      3. 2 THE SETL LANGUAGE AND ITS BASING SYSTEM
      4. 3 AN AUTOMATIC DATA REPRESENTATION SELECTION ALGORITHM
    3. Chapter 20: Automating the Selection of Implementation Structures
      1. Abstract
      2. I INTRODUCTION
      3. II FORMALISMS
      4. III ALTERNATIVE IMPLEMENTATION - STRUCTURE GENERATION
      5. IV SUMMARY AND CONCLUSIONS
      6. APPENDIX
      7. ACKNOWLEDGMENT
    4. Chapter 21: KNOWLEDGE-BASED PROGRAMMING SELF APPLIED
      1. ABSTRACT
      2. §1 Introduction
      3. §2 Specification of the Rule Compiler
      4. §3 Extensions to the Rule Compiler
      5. Acknowledgements
    5. Chapter 22: IMPLEMENTING SPECIFICATION FREEDOMS
      1. Abstract
      2. 1 Introduction
      3. 2 Specification in Gist
      4. 3 Mappings
      5. 3.6 Total information
      6. 4 Concrete examples of Gist
      7. 5 Case study
      8. 6 Related work
      9. 7 Conclusions
      10. Appendix 1. Package router specification
  12. VI: Programming by Example
    1. Chapter 23: Introduction to Programming by Example
    2. Chapter 24: A Methodology for LISP Program Construction from Examples
      1. ABSTRACT
      2. 1 Introduction
      3. 2 A Sample Synthesis
      4. 3 Synthesis Theorems
      5. 4 Variable Addition
      6. 5 Two Additional Examples
      7. 6 System Capabilities and Limitations
      8. 7 Conclusion
      9. ACKNOWLEDGMENTS
    3. Chapter 25: Programming by Examples
      1. ABSTRACT
      2. 1 Introduction
      3. 2 A Computation Description Language
      4. 3 The Synthesis Algorithm
      5. 4 Concluding Remarks
      6. Appendix I
      7. ACKNOWLEDGMENTS
  13. VII: Intelligent Assistants
    1. Chapter 26: Introduction to Intelligent Assistants
    2. Chapter 27: TOWARD INTERACTIVE DESIGN OF CORRECT PROGRAMS
      1. Publisher Summary
      2. CONCLUSION
      3. APPENDIX
    3. Chapter 28: A Designer/Verifier’s Assistant
      1. Abstract
      2. I INTRODUCTION
      3. II BRIEF SCENARIO
      4. III SUGGESTING WHAT TO DO NEXT
      5. IV PREVIEWING THE EFFECTS OF CHANGES
      6. V REASONING ABOUT CHANGES
      7. VI CONCLUSION
      8. APPENDIX A RELATIONS IN A MODEL
      9. APPENDIX B A SAMPLE MODEL
      10. ACKNOWLEDGMENT
    4. Chapter 29: The Programmer’s Apprentice: A Session with KBEmacs
      1. Abstract
      2. I INTRODUCTION
      3. II SCENARIO
      4. III EVALUATION
      5. IV CAPABILITIES
      6. V IMPLEMENTATION
      7. VI RELATED WORK
      8. VII FUTURE DIRECTIONS
      9. ACKNOWLEDGMENT
    5. Chapter 30: Kestrel Institute: REPORT ON A KNOWLEDGE-BASED SOFTWARE ASSISTANT
      1. ABSTRACT
      2. §1 EXECUTIVE SUMMARY
      3. §2 PROBLEMS AND SOLUTIONS
      4. §3 KBSA INTERNAL STRUCTURE
      5. §4 SUPPORTING TECHNOLOGY AREAS
      6. ACKNOWLEDGMENTS
  14. VIII: Programming Tutors
    1. Chapter 31: Introduction to Programming Tutors
    2. Chapter 32: Intelligent Program Analysis
      1. Abstract
      2. 1 Introduction
      3. 2 Finding the Plan
      4. 3 Program Synthesis
      5. 4 Program Generation Models
      6. 5 Analysis Policy
      7. 6 The Analysis Process
      8. 7 Value Equivalence
      9. 8 Construct Equivalence
      10. 9 Error Analysis
      11. 10 Expression Errors
      12. 11 Conditional Clause Reversal
      13. 12 Predicate Errors
      14. 13 Loop Iteration Errors
      15. 14 The Missing EXIT Statement
      16. 15 An Example
      17. 16 Experience
      18. 17 Applications
      19. Appendix. A Simple Programming Language Model
    3. Chapter 33: PROUST: Knowledge-Based Program Understanding
      1. Abstract
      2. I INTRODUCTION:MOTIVATION AND GOALS
      3. II THE ROLE OF PLANS IN PROGRAM UNDERSTANDING
      4. III A TYPICAL PROBLEM IN PROUST’S DOMAIN
      5. IV RELATING GOALS TO CODE VIA PLANS
      6. V THE UNDERSTANDING PROCESS:AN EXAMPLE OF PROUST IN ACTION
      7. VI PERFORMANCE:PRELIMINARY RESULTS
      8. VII CONCLUDING REMARKS
  15. IX: Programming Knowledge
    1. Chapter 34: Introduction to Programming Knowledge
    2. Chapter 35: On Program Synthesis Knowledge
      1. ABSTRACT
      2. 1 Introduction
      3. 2 Overview of Programming Knowledge
      4. 3 The Divide-and-conquer or Partitioning Paradigm
      5. 4 Internal Representation of Sets
      6. 5 Singleton Split
      7. 6 Refinement Diagram for Sorting Programs
      8. 7 In-place Sorting
      9. 8 Equal-size Split
      10. 9 Conclusions
      11. ACKNOWLEDGMENTS
      12. 10 Appendix
    3. Chapter 36: Program Abstraction and Instantiation
      1. Publisher Summary
      2. 1 INTRODUCTION
      3. 2 OVERVIEW
      4. 3 A DETAILED EXAMPLE
      5. 4 PROGRAM TRANSFORMATIONS
      6. 5 DISCUSSION
      7. ACKNOWLEDGMENTS
    4. Chapter 37: A Formal Representation For Plans In The Programmer’s Apprentice
      1. ABSTRACT
      2. 1 Introduction
      3. 2 The Plan Calculus
      4. 3 A Situational Calculus
      5. 4 Plans
      6. 5 Relations Between Plans
      7. 6 Final Remarks
    5. Chapter 38: Empirical Studies of Programming Knowledge
      1. Abstract
      2. I INTRODUCTION: MOTIVATION AND GOALS
      3. II BRIEF DESCRIPTION OF BOTH EXPERIMENTAL TECHNIQUES
      4. III GENERATING PLAN-LIKE AND UNPLAN-LIKE PROGRAMS
      5. IV DETAILED DESCRIPTION OF STUDY I: FILL-IN-THE-BLANK
      6. V DETAILED DESCRIPTION OF STUDY II: RECALL
      7. VI CONCLUDING REMARKS
      8. ACKNOWLEDGMENTS
  16. X: Domain Knowledge
    1. Chapter 39: Introduction to Domain Knowledge
    2. Chapter 40: The Draco Approach to Constructing Software from Reusable Components
      1. Abstract
      2. I INTRODUCTION
      3. II THE ORGANIZATIONAL CONTEXT OF DRACO
      4. III WHAT COMPRISES A DOMAIN DESCRIPTION?
      5. IV DIFFERENCES IN DEFINITION FROM OTHER APPROACHES
      6. V AN EXAMPLE DOMAIN ORGANIZATION
      7. VI SOFTWARE COMPONENTS AND THE REFINEMENT PROCESS
      8. VII DOMAIN SPECIFIC SOURCE-TO-SOURCE PROGRAM TRANSFORMATIONS
      9. VIII WHAT CAN BE SAID ABOUT THE POWER OF THE DRACO METHOD?
      10. IX CONCLUSIONS
      11. APPENDIX
    3. Chapter 41: A Perspective on Automatic Programming
      1. Abstract
      2. The Task Domain: Quantitative Log Interpretation
      3. Initial Studies
      4. The Role of Domain Knowledge
      5. The Perspective
      6. An Experimental Approach
      7. ϕNIX
    4. Chapter 42: Knowledge Representation as the Basis for Requirements Specifications
      1. Publisher Summary
      2. The need for representing knowledge
      3. Multiple levels of description
      4. Current research directions
  17. XI: Artificial Intelligence Programming
    1. Chapter 43: Introduction to Artificial Intelligence Programming
    2. Chapter 44: DATAMATION®: POWER TOOLS FOR PROGRAMMERS
      1. Publisher Summary
      2. POWER TOOLS FOR PROGRAMMERS
      3. The implementation disasters of the 1960s are slowly being succeeded by the design disasters of the 1980s
      4. Redundancy protects the design from unintentional change — but it’s equally well protected against intentional change
      5. Conventional programming technology restrains the programmer; exploratory systems amplify him
      6. The programming languages used in exploratory systems minimize and defer constraints on the programmer
    3. Chapter 45: Perspectives on Artificial Intelligence Programming
      1. Publisher Summary
      2. Programming Styles
      3. Use of Multiple Paradigms
      4. Programming Environments
      5. Narrow Knowledge-Based Systems
      6. Directions and Themes Revisited
  18. BIBLIOGRAPHY
  19. INDEX

Product information

  • Title: Readings in Artificial Intelligence and Software Engineering
  • Author(s): Charles Rich, Richard C. Waters
  • Release date: June 2014
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9781483214429