On the Efficient Synthesis of Efficient Programs*

Elaine Kant,     Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA 15213, U.S.A.

R.M. Burstall


Efficiency is a problem in automatic programming—both in the programs produced and in the synthesis process itself. The efficiency problem arises because many target-language programs (which vary in their time and space performance) typically satisfy one abstract specification. This paper presents a framework for using analysis and searching knowledge to guide program synthesis in a stepwise refinement paradigm. A particular implementation of the framework, called LIBRA, is described. Given a program specification that includes size and frequency notes, the performance ...

Get Readings in Artificial Intelligence and Software Engineering now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.