Structured Generic Programming in Eden

Parallelism has always been a main, yet hidden, source of processor power. As a result of the limited amount of implicitly exploitable small-scale parallelism (for example on the instruction-level) and ever-growing needs for more computational power, parallel techniques break their way from a minor matter to a major feature in both hardware and software. Due to their complexity, such parallel systems are getting increasingly difficult to control with conventional programming languages. Therefore, more abstract high-level approaches move into focus. Eden is a representative of these approaches which integrates constructs for remote evaluation into the standard functional language Haskell. It strikes a balance between full and no parallelism control and delivers good speedups while providing a high-level style of programming. In this thesis we equip Eden with three language features to raise the abstraction level even more: 1) Meta-programming, which means that programs manipulate other programs, will be used to define static preprocessing steps coded in Haskell for enhancing Eden programs. This supports portability of the Eden compiler, as some transformations can be pulled out of the foreign Haskell implementation. 2) Generic programming raises parametric to structural polymorphism and allows to write functions which are valid for all data structures. We will present a reduced, structure-oriented approach to generic programming tailored for Eden's needs. Using this approach, very general parallel schemes are defined. 3) Demand control is a basic requirement if a lazy functional language is faced with parallelism. The contradictory aims of postponing evaluations and simultaneity of evaluations enforces demand control in favour of parallelism. We present a set of means to do that. In functional programs, evaluation progress is determined by a mix of control structures and data dependencies. Accordingly, parallel functional programs can roughly be classified into data-oriented and control-oriented ones. Firstly, we will present generic methods for partitioning data structures as well as generic versions of the parallel map function. Secondly, we will show methods to manage the omnipresent streams as well as parallel schemes for dealing with irregular task sizes and long communication distances. To conclude, we will summarise all methods shown in a program developing guide for Eden