The goal of program transformation is to improve efficiency while preserving meaning. Unfortunately the unfold-fold method itself guarantees neither improvement in efficiency nor total correctness. It is intended for researchers in functional programming languages. The author presents a generic functional language with higher-order functions, lazy data structures, and strict as well as nonstrict application. The language is defined by its syntax and an operational semantics for its evaluation.
Transformation is defined in terms of substitution and equivalence of expressions.
In general, these transformations do not guarantee correctness, although they are based on locally equivalence-preserving steps. A restriction, namely improvement, is needed to guarantee total correctness. Improvement is defined in terms of the cost of evaluating an expression. The proof of the theorem is technically involved, needing several auxiliary definitions and lemmas. However, this part of the paper may be safely skipped if the reader is more interested in the applications.