Obtaining Low-Level Control in a High-Level Language : Variant Types in Data-Parallel Array Languages
Summary
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.