Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-556-97

Authors:

Date:

January 1997

Pages:

29

Download Formats:

Functional-language compilers often perform

optimizations based on beta and delta reduction.

To avoid speculative optimizations that can blow up the code size,

we might wish to use onlyshrinkingreduction rules guaranteed

to make the program smaller:

these include dead-variable elimination, constant folding,

and a restricted beta rule that inlines only functions that

are called just once.The restricted beta rule leads to a

shrinking rewrite system that has not previously been studied.

We show some efficient normalization algorithms that are immediately

useful in optimizing compilers; and we give a confluence proof

for our system, showing that the choice of normalization algorithm

does not affect final code quality.This technical report will be published as

- Shrinking Lambda Expressions in Linear Time.

Andrew W. Appel and Trevor Jim,J. of Functional Programming.- Substantial revision of previous paper entitled, Making Lambda-Calculus Smaller, Faster

(TR-477-94, November 1994)