Path analysis and the optimization of nonstrict functional languages

Abstract

The functional programming style is increasingly popular in the research world, but functional languages still execute slowly relative to imperative languages. This is largely because the power and flexibility of functional languages restrict the amount of information readily available to the compiler, hindering its ability to generate good code. This article demonstrates that information about order of evaluation of expressions can be statically inferred for nonstrict functional programs and that optimizations based on this information can provide substantial speedups at runtime. We present an exact, nonstandard semantics called path semantics that models order of evaluation in a nonstrict, sequential functional language, and its computable abstraction, path analysis . We show how the information inferred by path analysis can be used to implement destructive aggregate updating, in which updates on functional aggregates that are provably not live are done destructively. We also demonstrate a new approach to strictness analysis and show that strictness analysis is subsumed by path analysis. Benchmarks are presented.