Compilation of Haskell Array Comprehensions for Scientific Computing

Authors:

Steven Anderson and Paul Hudak

Abstract:

Monolithic approaches to functional language arrays, such as Haskell array comprehensions, define elements all at once, at the time the array is created, instead of incrementally.  Although monolithic arrays are elegant, a naive implementation can be very inefficient.  For example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests.  If a compiler does not know inter-element data dependences, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array.

Subscript analysis, originally developed for imperative language vectorizing and parallelising compilers, can be adapted to provide a functional language compiler with the information needed for efficient compilation of monolithic arrays.  Our contribution is to develop the number-theoretic basis of subscript analysis with assumptions appropriate to functional arrays, detail the kinds of dependence information subscript analysis can uncover, and apply that dependence information to sequential efficient compilation of functional arrays.

Bibtex:

 @inproceedings{andersonhudak90
    ,author={Anderson, S. and Hudak, P.}
    ,title={Compilation of {H}askell Array Comprehensions
        for Scientific Computing}
    ,booktitle={ACM SIGPLAN Conference on Programming Language Design
        and Implementation}
    ,year=1990
    ,month=Jun
    ,pages={137-149}
    } 

Links:

Arrays-PLDI90.pdf