TitleThe Next 700 Program Transformers
Publication TypeConference Paper
Year of Publication2022
AuthorsHamilton G
EditorDe Angelis E, Vanhoof W
Conference NameLogic-Based Program Synthesis and Transformation
PublisherSpringer International Publishing
Conference LocationCham
ISBN Number978-3-030-98869-2

In this paper, we describe a hierarchy of program transformers, capable of performing fusion to eliminate intermediate data structures, in which the transformer at each level of the hierarchy builds on top of those at lower levels. The program transformer at level 1 of the hierarchy corresponds to positive supercompilation, and that at level 2 corresponds to distillation. We give a number of examples of the application of our transformers at different levels in the hierarchy and look at the speedups that are obtained. We determine the maximum speedups that can be obtained at each level, and prove that the transformers at each level terminate.