Up Next
Go up to Writing Parallel Programs
Go forward to Structure of the Paper

Evaluation Strategies

Evaluation strategies use lazy higher-order functions to separate the two concerns of specifying the algorithm and specifying the program's dynamic behaviour. A function definition is split into two parts, the algorithm and the strategy, with values defined in the former being manipulated in the latter. The algorithmic code is consequently uncluttered by details relating only to the parallel behaviour.

The primary benefits of the evaluation strategy approach are similar to those that are obtained by using laziness to separate the different parts of a sequential algorithm [Hughes, 1983]: the separation of concerns makes both the algorithm and the dynamic behaviour easier to comprehend and modify. Changing the algorithm may entail specifying new dynamic behaviour; conversely, it is easy to modify the strategy without changing the algorithm.

Because evaluation strategies are written using the same language as the algorithm, they have several other desirable properties.

Evaluation strategies have been implemented in GpH and used in a number of large-scale parallel programs, including data-parallel complex database queries, a divide-and-conquer linear equation solver, and a pipelined natural-language processor, Lolita. Lolita is large, comprising over 60,000 lines of Haskell. Our experience shows that strategies facilitate the top-down parallelisation of existing programs.

{trinder,hwloidl,simonpj}@dcs.gla.ac.uk, kh@dcs.st-and.ac.uk

Up Next