Needed Reductions with Context-Sensitive Rewriting

Author

Salvador Lucas

Abstract

Computing with functional programs involves reduction of terms to normal form. When considering non-terminating programs, this is achieved by using some special, normalizing strategy which obtains the normal form whenever it exists. Context-sensitive rewriting can improve termination and also avoid useless reductions by imposing fixed, syntactic restrictions on the replacements. In this paper, we analyze the efficiency of context-sensitive computations with respect to the notion of needed reduction. As context-sensitive rewriting is complete in performing reductions to a root-stable form, we base our investigation on Middeldorp's theory of root-necessary reductions which is a generalization of Huet and Lévy's theory of (sequential) needed reductions to reductions leading to root-stable form both in sequential and parallel executions.

Keywords

functional programming, needed reductions, replacement restrictions, strategies, term rewriting systems.