The concept of a supercompiler provides a declarative way of viewing programming and compilation. This contrasts with the common perception of practical programming as “wizardry” that requires an intimate knowledge of a complex compiler and a messy reference manual. Supercompilation allows a programmer to deal only with the mathematical model of a programming problem without concern about efficiency. The generation of an efficient algorithm is then taken care of by the supercompiler. Supercompilation is similar to existing optimizing compilers in that the supercompiler aims to generate optimal target code; but, more important, it also SUPERvises the efficient execution of the code.
The author argues this point through a series of rather lengthy paragraphs in the first few sections and promises to illustrate supercompilation on some examples in the final sections. But first, he defines an applicative language Refal in which the examples will be formulated. Refal was the main subject of a number of previous papers by the same author and one wonders whether it is really necessary to go through two lengthy sections to understand coming examples. Unfortunately, the author does not go into details of strategies of supercompilation, but rather concentrates on Refal and discusses two simple examples of supercompilation performed by the CCNY supercompiler. The first example deals with “driving,” or partial evaluation of function uninstantiated parameters, and the other one demonstrates removing redundancy caused by repeated variable names. Finally, an application of the supercompiler as a compiler for a simple FORTRAN-like language is discussed, and some performance statistics are quoted.
In summary, the concept of supercompilation presented in this paper will appeal mostly to those involved in the methodology and design of “new generation” compilers, especially for applicative languages. Unfortunately, readers working actively in functional programming will most likely find the author discussing matters already covered more deeply elsewhere.
