PARALLELIZING IMPERATIVE FUNCTIONAL PROGRAMS - THE VECTORIZATION MONAD

Traditionally a vectorizing complier matches the iterative constructs of a program against a set of predefined templates. If a loop contains no dependency cycles then a map template can be used; other simple de pendencies can often be expressed in terms of fold or scan templates. This paper addresses the template matching problem within the context of functional programming. A small collection of program identities ar e used to specify vectorizable for-loops. By incorporating these progr am identities within a monad, aid well-typed for-loops in which the bo dy of the loop is expressed using the vectorization monad can be vecto rized. This technique enables the elimination of template matching fro m a vectorizing compiler, and the proof of the safety of vectorization can be performed by a type inference mechanism. (C) 1996 Academic Pre ss Limited