Performance of lazy combinator graph reduction

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
73 Downloads (Pure)


The performance of program-derived combinator graph reduction is known to be superior to that of graph reduction based on a fixed set of standard combinators. The major advantage of program-derived combinator reduction is that it uses less transient store than standard combinator reduction. We show on what activities a combinator reduction algorithm spends its execution time. Based on this analysis we show that it depends to a large extent on the application how much faster a program will run if program-derived combinators are used instead of standard combinators. The analysis is based on experimental evidence obtained from a small bench-mark of medium-size functional programs. Performance gains of up to 11 x are reported for target architectures on which each memory reference consumes one unit of time. The results are valid for implementations of combinator graph reduction that use binary graphs.
Original languageEnglish
Pages (from-to)299-329
Number of pages31
JournalSoftware : practice and experience
Issue number3
Publication statusPublished - Mar 1991
Externally publishedYes


  • EWI-1210
  • IR-55881


Dive into the research topics of 'Performance of lazy combinator graph reduction'. Together they form a unique fingerprint.

Cite this