A hierarchy of program transformers

In this paper, we describe a hierarchy of program transformers in which the transformer at each level of the hierarchy builds on top of the transformers at lower levels. The program transformer at the bottom of the hierarchy corresponds to positive supercompilation, and that at the next level corresponds to the rst published de nition of distillation [4]. We then show how the more recently published de nition of distillation [5] can be described using this hierarchy. We see that this moves up through the levels of the transformation hierarchy until no further improvements can be made. The resulting de nition of distillation uses only nite data structures, as opposed to the de nition in [5], and we therefore argue that it is easier to understand and to implement.