Scalan: polytypic library for nested parallelism in Scala

The paper presents a specialized Scala library to express nested data parallelism in Scala language using its advanced features for polytypic and datatype-generic programming, DSL embedding and type-level programming. The proposed library implements polytypic (type-indexed), non-parametric representations of parallel arrays. The approach is illustrated by a series of increasingly sophisticated examples followed by a description of key implementation details.