Obtaining Low-Level Control in a High-Level Language : Variant Types in Data-Parallel Array Languages

Abstract

A high-level abstraction sacrifices the ability to exercise low-level control, which can be prob- lematic for performance critical applications. The phenomenon is apparent in data-parallel array languages, which traditionally do not support types with multiple variants. Data-parallelism uses the uniformity between multiple data elements to accelerate the process of operating on large collections of data. Variant types constrain the ability to operate uniformly, which therefore lim- its data-parallelism opportunities in the general case. In the situations where non-uniformity is inherit to the algorithm low-level optimizations are used to mitigate the heterogeneity. In this paper a higher abstraction level variant type is explored, which can capture the low-level control required to implement low-level optimizations in data-parallel languages. A polymorphic variant type is used to represent variance on the type-level, which can be used by data structures to adapt to the variance. Type-level programming is used to derive memory efficient representations for user-defined variant types. Custom memory representations are supported through datatype- generic programming, which automates the (de)construction of variant types. A fully modular variant type is presented, which can exercise low-level control while preserving the ergonomics of an existing high-level architecture. An implementation is provided in the data-parallel language Accelerate, which demonstrates the viability of variant types in a data-parallel context.