23 Representations and Modelling in Problems of Program Formation S. Amarel

In particular, we consider situations where functional properties of a computer program are given in the form of explicit input-output correspondences, and the problem is to synthesize (to form) a program, in a given programming language, that satisfies the given correspondences. The motivation behind the work is twofold: (1) to explore and elucidate schemes for solving formation problems by machine, and (2) to gain further insight into questions of representation in problem solving, to examine their nature and significance in the context of formation procedures, and to clarify the role of models in the solution of formation problems. The present approach to program formation derives from work done several years ago (Amarel 1962a, 1962b), in which we found it conceptually fruitful to view the automatic formation of computer programs that is based on computational examples as a case of automatic theory formation. A theory in an empirical science emerges from a body of observed correspondences and has the function of an intellectual mechanism for explanation and prediction. The theory evolves from a succession of hypotheses that are tested against experience, and attains a degree of stability once it explains with reasonable consistency the given body of observations. The form of a hypothesis capable of emerging in a scientific culture depends on the language, the basic concepts, and the schemas that are available in the culture.