TY - JOUR
T1 - Shrinking lambda expressions in linear time
AU - Appel, Andrew W.
AU - Jim, Trevor
PY - 1997/9
Y1 - 1997/9
N2 - 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 only shrinking reduction 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.
AB - 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 only shrinking reduction 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.
UR - http://www.scopus.com/inward/record.url?scp=0031321492&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031321492&partnerID=8YFLogxK
U2 - 10.1017/S0956796897002839
DO - 10.1017/S0956796897002839
M3 - Article
AN - SCOPUS:0031321492
SN - 0956-7968
VL - 7
SP - 515
EP - 540
JO - Journal of Functional Programming
JF - Journal of Functional Programming
IS - 5
ER -