Shrinking lambda expressions in linear time

Andrew W. Appel, Trevor Jim

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)515-540
Number of pages26
JournalJournal of Functional Programming
Issue number5
StatePublished - Sep 1997

All Science Journal Classification (ASJC) codes

  • Software

Cite this