A Transformation System Combining Partial Evaluation with Term Rewriting

This paper presents a new approach to optimizing functional programs based on combining partial evaluation and rewriting. Programs are composed of higher-order primitives. Partial evaluation is used to eliminate higher-order functions. First-order rewriting is used to process the transformation. Laws about the higher-order primitives that are relevant for the optimizations are automatically extracted from a library and transformed into first-order terms using partial evaluation. Such a combination of a partial evaluation system and an intrinsically first-order rewriting tool allows a form of higher-order rewriting at a first-order level. This way, it is possible to automate deforestation of higher-order programs. Introduction The so-called Squiggol [10] style for program construction is a high-level programming technique that consists of building a program by composing primitives or other functions while taking into account well-known laws on the primitives. Functions are usually defi..