Distillation with labelled transition systems

Abstract

In this paper, we provide an improved basis for the “distillation” program transformation. It is known that superlinear speedups can be obtained using distillation, but cannot be obtained by other earlier automatic program transformation techniques such as deforestation, positive supercompilation and partial evaluation. We give distillation an improved semantic basis, and explain how superlinear speedups can occur.