In Philip Wadler, editor, Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming, pages 94-105, ACM Press, 2000.
Abstract
This paper generalises the flattening transformation - a technique for the
efficient implementation of nested data parallelism - and reconciles it
with main stream functional programming. Nested data parallelism is
significantly more expressive and convenient to use than the flat data
parallelism typically used in conventional parallel languages like High
Performance Fortran and C*. The flattening transformation of Blelloch
and Sabot is a key technique for the efficient implementation of nested
parallelism via flat parallelism, but originally it was severely restricted,
as it did not permit general sum types, recursive types, higher-order
functions, and separate compilation. Subsequent work, including some of our
own, generalised the transformation and allowed higher-order functions and
recursive types. In this paper, we take the final step of generalising
flattening to cover the full range of types available in modern languages
like Haskell and ML; furthermore, we enable the use of separate compilation.
In addition, we present a completely new formulation of the transformation,
which is based on the standard lambda calculus notation, and replace a
previously ad-hoc transformation step by a systematic generic programming
technique. First experiments demonstrate the efficiency of our approach.
Preprint PostScript version (12 pages).
This page is part of Manuel Chakravarty's WWW-stuff.