Limitations and Missing Features

Libraries

There are various libraries from the previous implementation (feldspar-language and feldspar-compiler) that would be good to port to RAW-Feldspar. These include:

• Repa-style multi-dimensional vectors
  • Many utility functions from there could also be added to the current vector library.
• The Par monad
  • It seems likely that it can be implemented just as a library on top of the concurrency interface.
• Bit vectors

Data parallelism

The previous implementation had some support for generating data parallel code (OpenMP pragmas) from vector computations based on the Pull and Push types (and data parallelism was indeed one of the main motivations of the vector library). Doing this in RAW-Feldspar would require a way to express parallel loops and use these e.g. when folding a pull vector or writing a push vector to memory.

Ideally one would like such data parallelism to play well together with the task parallelism provided by the concurrency interface, so doing this right requires some thought.

Memory allocation

RAW-Feldspar currently allocates all memory on the stack. This is a good default that works well provided the required memory fits in the stack. However, it would be good to also be able to allocate on the heap when needed.

• This can currently be done using foreign calls to malloc and free, but a more integrated approach would be preferred.

(The previous implementation allocates all memory dynamically on the heap.)

Memory safety

The previous implementation maintained a pure semantics by silently allocating and copying arrays when needed. RAW-Feldspar puts much of the memory management in the hands of the user (see Tut4_MemoryManagement.hs), which means that there are more opportunities to shoot oneself in the foot.

The plan is to regain safety using static analysis based on formal verification. This work is currently carried out in a fork.

Exported and non-inlined functions

The previous implementation (until the addition of feldspar-io) only supports writing pure functions, and the compiler generates a corresponding C function to be called from other C code. In contrast, RAW-Feldspar only generates a runnable main definition. RAW-Feldspar should allow the option of exporting functions to other C code.

It would also be good to support non-inlined local functions. For example, using fft twice in a program results in two pieces of similar-looking code. It is often preferred to generate a function definition from fft and call that twice in the program.

Optimization

In the previous implementation, the whole program is a single pure function (that could contain local monadic computations). This means that powerful high-level optimizations (simplification and code motion) are performed over the whole program. In contrast, RAW-Feldspar programs are monadic sequences with pieces of pure expressions occurring under the binds. These expressions are typically quite small (but they may contain pure loops, conditionals, etc.), so the high-level optimizations are only performed for small chunks of the program.

This means that generated code from RAW-Feldspar can contain common sub-expressions and useless variable assignments that would not appear in equivalent programs in the previous implementation.

One solution to this problem is to apply imperative optimizations on the monadic code. However, doing this is currently quite hard since RAW-Feldspar programs use a higher-order representation of monadic code. The way forward is probably to introduce a first-order representation before code generation, and do the necessary optimizations on that representation.

Size-based simplification

The previous implementation used size inference to improve the work of the simplifier for numeric expressions with known upper and lower bounds. For example, the expression a < b can be statically reduced to true if the upper bound of a is known to be less than the lower bound of b. Such cases are important, e.g. to remove bounds checks when compiling for arrays of known size.

Size inference for RAW-Feldspar would be more involved than in the previous implementation due to the heavy reliance on monadic code and mutable data structures. It would seem reasonable to do it as an abstract interpretation of the first-order representation suggested above.