On the relation between functional and data parallel programming languages
Per Hammarlund, Björn Lisper · 1993
Data parallel programming is becoming an increasingly important tool for exploiting parallelism in data-intensive applications, especially on SIMD and vector computers.Many algorithms appearing in such applications are very succinctly expressed in data parallel languages: this indicates that data parallel programming can be a powerful abstract programming paradigm rather than just a syntax for explicit programming of SIMD computers.The data parallel languages in practical use today are, however, exponents of exactly the latter point of view: even though they incorporate some elements of abstraction, their semantics are all to some extent based on a SIMD execution model.Therefore it is hard to use these languages to express algorithms in the problem domain in an abstract, machine-independent way.This is likely to make programming in these languages more errorprone and programs less portable than if they had been designed with a more clean-cut abstract semantics.Here, we present some mathematical definitions of data parallel primitives that can be used to guide the design of data parallel languages wit h a higher level of abstraction.The key idea is to view data parallel entities as tabulated functions where the tables are stored in a distributed fashion.Operations on data parallel entities are then simply operations on functions, just as operations in pure functional languages.An interesting observation is that also traditional data structures, like lists and arrays, are covered by our view.This illustrates the level of abstraction achieved.An especially interesting possibility is to integrate data parallel and higher order functional languages.Data parallel entities are then iust a Particular class of functions that can .be represented in a pa~ticular way.We believe that such languages are very suitable as specification languages for data parallel algorithms.