Eliminating Intermediate Lists in pH using Local Transformations
Jan-Willem Maessen · 1994
The extensive use of lists in functional programming languages exacts a cost penalty for important operations such as array construction. In addition, because lists are linear data structures, it is difficult to generate and traverse them efficiently in parallel given a purely-functional environment. Three common methods of traversal---left and right fold, and reduction---can be described in terms of map and reduce operations yielding higher-order functions; these higher-order functions can be represented entirely at compile time. This thesis examines this representation of list traversal, describes its implementation in the desugaring phase of the compiler for pH (an implicitly-parallel, mostly-functional dialect of the language Haskell). This approach to desugaring gives rise to a set of rules for compiling list comprehensions efficiently, and to a pair of functions unfold and synthesize which can be immediately eliminated if the lists they generate are traversed by folding or reduc...