Automatic Construction of Special Purpose Programs

摘要

According to the usual formulation of the automatic programming task, one starts with a specification of a programming problem, and seeks to automatically construct a program satisfying that specification. This paper concerns a different style of automatic programming. Rather than defining the class of programming problems to be dealt with by the language in which those problems are formulated, we instead consider classes of problems defined in ordinary mathematical terms. Also, our aims are different from the traditional aims of automatic programming in that we are interested primarily in increasing the efficiency of computations, rather than in transferring the burden of programming from human to computer. Let alpha(p, x, y) be a ternary predicate. Suppose that in the course of some large computation we are obliged to repeatedly compute values of y with alpha(p, x, y) from given values of p and x. Suppose further that in the sequence of p's and x's to be treated, p changes slowly and x rapidly. Then we seek to automatically synthesize a fast special purpose program A sub p for each p; A sub p is expected to compute a y with alpha(p, x, y) when given x as input. We present one example of special purpose automatic programming in detail, namely, a method for synthesizing special purpose programs for eliminating the hidden surfaces from displays of three dimensional scenes. (Hidden surface elimination is one of the central problems in three dimensional computer graphics). In a test of the method, a synthetic program specialized to treating a particular scene - but from an arbitrary point of view - proved to be an order of magnitude faster than the best available general purpose algorithm. (Author)