On the Place of Supercompilation inside Program Specialization

Research in the field of creating systematical methods for specialization of programs with respect to fixed properties of their arguments, compositional structure and given invariants were started by Russian scientists A.P. Ershov ("mixed computation"), V.F. Turchin ("supercompilation") and Japanese scientist Y. Futamura ("generalized partial computation") in the 1970-ths. To the current moment a huge amount of facts mainly related to the object domain of functional programming languages was accumulated in the literature.

Ideas of supercompilation were mainly being studied on the base of a functional programming language REFAL, although a series of the results were polished on the LISP's experimental base. At present time, along with a number of primitive supercompilers constructed for simplest purely theoretical languages, there exists the only experimental supercompiler SCP4 for a real programming language (REFAL-5). The name SCP4 was suggested by V.F. Turchin as reflecting the history of the supercompilation ideas.

In this paper we consider various approaches to formulation of the specialization task per se. We give a short survey of the main achievements derived (to the given moment) in the field of specialization of functional programs, analyze principal distinctions between supercompilation and other existing methods. We survey the attempts of constructing of supercompilers.