This paper shows how call-by-need supercompilation can be recast to be based explicitly on an evaluator, contrasting with standard presentations which are specified as algorithms that mix evaluation rules with reductions that are unique to supercompilation. Building on standard operational-semantics technology for call-by-need languages, we show how to extend the supercompilation algorithm to deal with recursive let expressions. Despite its remarkable power, the transformation is simple, principled and fully automatic. Supercompilation is closely related to partial evaluation, but can achieve strictly more optimising transformations [6] . The key contributions of this paper are as follows: • Inspired by Mitchell's promising results [7] , we cast supercompilation in a new light, showing how to design a modular supercompiler that is based directly on the operational semantics of the language (Section 3). Viewing supercompilation in this way is valuable, because it makes it easier to derive a supercompiler in a systematic way from the language, and to adapt it to new language features. Previous work intermingles evaluation and specialisation in a much more complex and ad-hoc way. • As an example of this flexibility, we show how to supercompile a call-by-need language with unrestricted recursive let bindings, by making use of a standard evaluator for call-by-need (Section 4). This has two advantages: Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. , previous supercompilers for lazy languages have dealt only with nonrecursive let bindings. HOSC is also able to deforest this example, but at the cost of sometimes duplicating worksomething that we are careful to avoid. Because recursion is not special, we do not need to give the program top-level special status, or λ-lift the input program. • We perform an empirical evaluation of our supercompiler (Section 5), in particular comparing it to Mitchell's supercompiler [7] . The source code for the implementation, the Cambridge Haskell Supercompiler (CHSC), is available online 1 . Our supercompiler reduces benchmark runtime by up to 95%, with a mean reduction of 26%. The best way to understand how supercompilation works is by example. Let's begin with a simple example of how standard supercompilation can specialise functions to their higher-order arguments: A supercompiler evaluates open terms, so that reductions that would otherwise be done at runtime are performed at compile time. Consequently, the first step of the algorithm is to reduce the term as much as possible, following standard evaluation rules: At this point, we become stuck on the free variable zs. The most important decision when designing a supercompiler is how to proceed in such a situation, and we will spend considerable time later explaining how this choice is made when we cover the splitter in Section 3.5. In this particular example, we continue by recursively supercompiling two subexpressions. We intend to later recombine the two subexpressions into an output term where the case zs remains in the output program, but where both branches of the case have been further optimised by supercompilation.
As was shown in REF , supercompilation can be based on an evaluator which tries to reduce an open term to head normal form.
Supercompilation by evaluation
Haskell '10
Computer Science