Introduction to supercompilation

Abstract. We extend positive supercompilation to handle negative as well as positive information. This is done by instrumenting the underly-ing unfold rules with a small rewrite system that handles constraints on terms, thereby ensuring perfect information propagation. We illustrate this by transforming a näıvely specialised string matcher into an optimal one. The presented algorithm is guaranteed to terminate by means of generalisation steps.