Transformations for Efficient Evaluations in Functional Programming


Salvador Lucas


Rewriting is a suitable mechanism to implement functional programming languages. The definition of efficient evaluation strategies is a natural concern in this setting. Recently we have shown that, by imposing some simple restrictions on the replacements which are allowed for the arguments of functions, we can obtain efficient head-evaluations of terms in a certain class of programs. We are also able to completely evaluate terms, but in this case, the efficiency of computation can be compromised. This paper concerns the definition of program transformations that enable efficient but still complete evaluation of function calls.


evaluation, functional programming, program transformation, term rewriting