5 Unrolled Metaprogramming

In some cases it is desirable to specify an algorithm at a higher level using data structures and associated operations that are not supported on a target platform. E.g. in RAI the C target only supports operations on (nested) linear arrays, which is a straightforward translation of the loop construct.

In this case, ideally one would want to relate the higher level data structures and manipulations to some optimized combination of loops over arrays. A good example of this is the way in which loop fusion is performed in the Feldspar language. Such an approach requires a certain amount of trickery to be implemented. This is not yet possible in RAI.

Meanwhile, there is a simpler way to perform powerful code generation when one drops to manipulation of scalar values. This uses a correspondence between values at the meta level and individual (scalar) variable nodes at the target program level. This approach could be called the generation of flat or unrolled code.

The RAI language contains primitives for array construction and deconstruction that allows this form of flexible code generation to be combined with the C target’s array datastructures. The automatic array unpacking is performed in the map operator.

Keep in mind that while this can lead to efficient implementations if the unrolling exposes optimization opportunities, in general the unrolling can introduce a lot of code duplication if it is applied to large collections of compile-time data. When possible, it’s probably good to stick to consecutive applications of the loop construct to implement multi-pass array algorithms, as this translates to target-side loops over arrays.