No abstract available.

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 aboutorder of evaluation of expressionscan 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 calledpath semanticsthat 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.

One of the factor hindering the use of functional languages has been their relatively poor performance in comparison to more traditional languages such as C and Pascal. During the last decade tremendous progress has been made in building implementations of functional languages but the approaches adopted have employed specialist hardware and/or compiler optimisations that have been developed specifically for functional languages. Building specialist hardware may be the best long-term solution but in the short run it is possible to increase the use and acceptance of functional languages by exploiting the performance of commercially available machines. The goal of the project described in this paper has been to design an optimising compiler that produces fast code for functional languages on conventional sequential and parallel machines.

We discuss the problem of efficiently implementing aggregates (contiguous data structures) such as arrays in functional programming systems. Simple changes to an aggregate conceptually involve making a new copy of the aggregate differing only in the changed component, but such copying can be expensive. We present both static and dynamic techniques for avoiding this copying, and argue that they allow one to program functionally using aggregates, without loss of efficiency over conventional programs.1