Extracting the essence of distillation

Abstract

In this paper, we give a re-formulation of our previously defined distillation algorithm, which can automatically transform higherorder functional programs into equivalent tail-recursive programs. Our re-formulation simplifies the presentation of the transformation and hopefully makes it easier to understand. Using distillation, it is possible to produce superlinear improvement in the run-time of programs. This represents a significant advance over deforestation, partial evaluation and positive supercompilation, which can only produce a linear improvement.