Constructed Product Result Analysis for Haskell

Clem Baker-Finch, Kevin Glynn, and Simon Peyton Jones. Journal of Functional Programming 14(2), March 2004, pp 211-245.

Postscript.

Compilers for ML and Haskell typically go to a good deal of trouble to arrange that multiple arguments can be passed efficiently to a procedure. For some reason, less effort seems to be invested in ensuring that multiple results can also be returned efficiently.

In the context of the lazy functional language Haskell, we describe an analysis, Constructed Product Result (CPR) analysis, that determines when a function can profitably return multiple results in registers. The analysis is based only on a function's definition, and not on its uses (so separate compilation is easily supported) and the results of the analysis can be expressed by a transformation of the function definition alone. We discuss a variety of design issues that were addressed in our implementation, and give measurements of the effectiveness of our approach across a substantial benchmark set.

Overall, the price/performance ratio is good: the benefits are modest in general (though occasionally dramatic), but the costs in both complexity and compile time, are low.


Simon Peyton Jones, simonpj@microsoft.com