Polytypic Staging: a new approach to an implementation of Nested Data Parallelism in Scala

This paper describes polytypic staging, – an approach to staging of a domain-specific language (DSL) that is designed and implemented by means of polytypic (datatype-generic) programming techniques. We base our implementation on Lightweight Modular Staging (LMS) framework by extending and making it polytypic. We show how to apply it to a particular domain. The domain is nested data parallelism where data parallel programs are expressed in the DSL embedded in Scala. The paper is organized around a specific DSL, but our implementation strategy should be applicable to any polytypic DSL in general.