Transformations of FP program schemes

Abstract
The perceived inefficiency in execution functional programming languages has been an obstacle to their widespread acceptance. Consequently, algorithms are often coded for efficient execution at the expense of clarity. This compromises the functional style, which is the prime advantage of such languages. We argue that high-level program transformations can relieve the programmer from concern for efficiency in many instances. We present several transformations applicable to FP program schemes, and show how these may be proven using fixpoint induction. We also show how specific subalgebras may be exploited to develop more specialised transformations, and suggest that this may be the most fruitful direction for further efforts to take. Comparison with earlier work on transformations reveals that the use of variables in LISP-like languages has often interfered with the identification of superficially dissimilar programs as instances of a common scheme. A variable-free notation such as FP has proven easier to work with.

This publication has 0 references indexed in Scilit: