LISP and Symbolic Computation, 9(4)287-322
A Higher-Order Removal MethodWei-Ngan Chin, Department of Information Systems & Computer Science, National University of Singapore
John Darlington, Department of Computing, Imperial College of Science, Technology & Medicine
|
Abstract: A major attraction of functional languages is their
support for higher-order functions. This facility increases the
expressive power of functional languages by allowing concise and
reusable programs to be written. However, higher-order functions are
more expensive to execute and to analyse for optimisations. To reduce the performance penalties of using higher-order functions, this paper proposes two transformation algorithms which could automatically remove most higher-order functions from functional programs. The first algorithm uses an eta-expansion technique to eliminate expressions which return function-type results. The second algorithm uses a function specialisation technique to eliminate expressions with function-type arguments. Together, they remove higher-order functions by transforming each higher-order program to an equivalent firstorder (or lower-order) program. We shall prove that the two algorithms are terminating (when applied to well-typed programs) and also totally-correct (preserving non-strict semantics). Keywords: program transformation, higher-order removal, eta-expansion, function specialisation, parameter analysis, termination proofs, compiler optimization |
This article is not available online.
![[picture of journal cover]](../LISP.JPG)