Observations on the interaction between coding and efficiency knowledge in the PSI Program Synthesis System

摘要

This paper discusses how the synthesis phase of the PSI system constructs programs from high level program models by using coding knowledge and efficiency knowledge. In our preliminary implementation, these knowledge bases are separated into distinct modules, the coding expert and the efficiency expert. We describe how the coding expert uses rule-based programming knowledge to produce alternative algorithm and data structure choices, and how the efficiency expert selects the best choice by estimating the costs of the alternatives using analysis of algorithm techniques. Communication between the modules centers around descriptions of partially developed programs which are produced by the coding expert and analyzed by the efficiency expert. Our system has implemented several small programs. From our experience with these modules, we conclude that there is a strong interaction between coding and efficiency knowledge which necessitates a corresponding complexity inthe communication mechanism.