Making Lambda Calculus Smaller, Faster
Report ID:
TR-477-94
Authors:
Date:
October 1994
Pages:
9
Download Formats:
Abstract:
Some optimizations are speculative: they improve execution speed most
but not all of the time, or they trade off faster execution for an
increase in code size. Other optimizations, such as dead-variable
elimination and algebraic simplification, are guaranteed to both
reduce code size and speed execution. It makes sense to group all of
these ``contracting'' optimizations together in a single phase of a
compiler. This paper describes an efficient implementation of these
optimizations for a language based on the lambda calculus, where a
particularly interesting optimization of this sort is inlining for
those functions called only once. And we prove that our contracting
rewrites are confluent.