Distillation

Abstract

In this paper, we present a new transformation algorithm called distillation which can automatically transform higher-order functional programs into equivalent tail-recursive programs. Using this algorithm, it is possible to produce superlinear improvement in the runtime of programs. This represents a significant advance over the supercompilation algorithm, which can only produce a linear improvement. Outline proofs are given that the distillation algorithm is correct and that it always terminates.