In describing evaluation strategies, we have exploited several aspects of the Haskell language design. Some of these are essential, whereas others may perhaps be modelled using other mechanisms. For example, some support for higher-order functions is clearly needed: strategies are themselves higher-order functions, and may take functional arguments.
Lazy evaluation is the fundamental mechanism that supports the separation of algorithm from dynamic behaviour: essentially it allows us to postpone to the strategy the specification of which bindings, or data-structure components, are evaluated and in what order. Operationally, laziness avoids the recomputation of values referred to in both the algorithmic code and the strategy. Although we have not yet studied this in detail, the work on control abstraction by Crowl and Leblanc, plus other work referred to above, does suggest that enough of the characteristics of lazy evaluation could be captured in an imperative language to allow the use of evaluation strategies in a wider context than that we have considered.
In defining evaluation strategies, we have taken advantage of Haskell's type class overloading to define general evaluation-degree strategies, such as rnf. If general ad-hoc overloading is not available, then a number of standard alternative approaches could be taken, including:
In either case, support can be provided as functions or language constructs. Neither approach is as desirable as that taken here, since they limit user flexibility in the first case, or require code duplication in the second.
As with any powerful language construct, evaluation strategies can be abused. If a strategy has an evaluation degree greater than the strictness of the function it controls, it may change the termination properties of the program (note that unlike first-class schedules, however, this is still defined by the normal language semantics). Similarly it is easy to construct strategies with undesirable parallelism, e.g. a strategy that creates an unbounded number of threads. Adding a strategy to a function can also greatly increase space consumption, e.g. where the original function incrementally constructs and consumes a data structure, a strategic version may construct all of the data structure before any of it is consumed. Finally, strategies sometimes require additional runtime traversals of a data structure. In pathological cases care must be taken to avoid multiple traversals, e.g. when a small part of a large data structure has been changed, or with accumulating parameters. Many unnecessary traversals could be avoided with a runtime mechanism that tags closures to indicate their evaluation degree.
This paper has focussed on the use of evaluation strategies for parallel programming, but we have also found them useful in other contexts. Strategies have been used for example in Lolita to force the evaluation of data structures that are transferred from Haskell to C (see Section *). Furthermore, they can cause a reduction in heap usage in cases where the strictness analysis is overly conservative and the normal evaluation would hang on to data that can be safely evaluated.
The separation of behavioural and algorithmic code provided by strategies suggests that they can be used to model the context in which a certain function is used. For example, in a sequential profiling setting strategies can define the evaluation degree of a function. The performance of the function can then be measured in the given context. Also, when tuning parallel performance, a driver strategy can define the pattern of parallelism generated in a certain context. This facilitates the testing of parts of the program in isolation.