Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Knowledge-based programming: an overview of data and control structure refinement
Goldberg A., Kotik G.  Software validation: inspection-testing-verification-alternatives (, Darmstadt, West Germany,3091984.Type:Proceedings
Date Reviewed: Nov 1 1985

This paper presents an overview of research on automatic programming at Kestrel’s CHI project. The long-term goal of the project is to develop methods for generating efficient low-level implementations of high-level program specifications, and to explore the application of AI techniques for building systems that embody these methods. The emphasis is on the representation and use of programming knowledge for data structure selection and for control structure refinement. The approach to program development involves using a very-high-level language for program specification and a compiler in the form of an AI system for knowledge-based program synthesis. Much of the knowledge used by the system is in the form of program transformati- on rules. The paper stresses that an important feature of the system is the ability to provide effective guidance on how to choose and apply appropriate sequences of program transformation rules.

The paper describes key features of the very-high-level language, called V, which was developed for CHI. It is noteworthy that program transformation rules, as well as various CHI tools, are written in V. This provides an interesting bootstrapping property for system development.

The high-level data types used in V are set-theoretic constructs. The approach to the selection of data structure implementations that correspond to source data constructs is presented in considerable detail. The basic idea is that a good collection of possible target-level implementations of data structures can be generated by composition of a small number of primitive, representational methods. Each method is specified as a set of transformation rules written in V. An important part of the research in this project is the study of various factorizations of representational knowledge into small sets of primitive methods. This work is of basic significance to programming and to AI. The ideas and techniques developed in this area are illustrated in the paper via examples of data structure implementations for sets and mappings.

The main techniques of control system refinement discussed in the paper are finite differencing and loop fusion. Also, an interesting discussion of the Store-vs-Compute problem is presented in the context of low-level program implementations. There is a broad spectrum of knowledge, from algorithm design to optimization techniques, that the project plans to capture for implementing control system refinement. Work in this area has not advanced as far as work in data structure implementation.

This is a well-written and interesting paper. It describes one of the major current efforts at the interface between AI and programming. This work represents a significant application of AI, and it is also directly relevant to programming theory and to the practice of software design.

Reviewer:  S. Amarel Review #: CR109610
Bookmark and Share
 
Program Synthesis (I.2.2 ... )
 
 
Program Transformation (I.2.2 ... )
 
 
Very High-Level Languages (D.3.2 ... )
 
 
Miscellaneous (D.2.m )
 
 
Programming Languages And Software (I.2.5 )
 
Would you recommend this review?
yes
no
Other reviews under "Program Synthesis": Date
Automated program synthesis (videotape)
Kant E., University Video Communications, Stanford, CA, 1990. Type: Book
Mar 1 1992
On complete sets of samples for generalized regular expressions
Kinber E. Theoretical Computer Science 91(1): 101-117, 1991. Type: Article
Jan 1 1993
On synthesis of scheduling algorithms
Gupta R., Srivastava V. Information Processing Letters 19(3): 147-150, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy