Draft of October 10, 2018 (comments please!)
Despite its overwhelming popularity, the array type has serious drawbacks for parallel programming. In brief, array algorithms are unsafe (subject to out-of-bounds errors), weakly compositional, and brittle to change. A generic functor approach solves these problems, resulting in a programming style that is safe and strongly compositional (for code reuse), while robustly describing infinite families of guaranteed-correct algorithmic variations. For CPU-based and (especially) hardware implementations, the generic functor style of programming can perform fairly well. GPUs and their supporting programming models, however, have a very strong bias toward array programming. In particular, they efficiently support only “flat” data parallelism, corresponding to computing over arrays of scalar values. This note describes a design for a programming interface isomorphic to the generic functor composition style and an implementation that maps to efficient GPU-style array computations. The generated computations are guaranteed safe from out-of-bound errors despite using unsafe array operations internally, and the programming model remains elegantly compositional and generic-friendly.