Arrays, Non-Determinism, Side-Effects, and Parallelism: A Functional Perspective

Authors:

Paul Hudak

Abstract:

Purely functional incremental updates to arrays, executed in a non-deterministic manner, are shown to achieve the same effect (in both efficiency and functionality) as parallel assignments to imperative arrays.  The strategy depends only on the ability of a compiler to recognize that incremental updates to functional arrays can be done destructively (an optimization often called “copy-avoidance” of “single-threaded arrays”).  Special “pseudo-functional syntax” is introduced that captures typical array-update patterns.  This syntax falls somewhere between the purely functional and (im)purely imperative, and makes the inferencing problem fairly easy.  If nothing else, the work represents an interesting intellectual exercise in the relationship between non-determinism, side-effects, and parallelism, and  tends to blur the traditionally clear-cut distinction between functional and imperative languages.

Bibtex:

 @InProceedings{huda87b
    ,key={hudak}
    ,author={Hudak, P.}
    ,title={Arrays, Non-Determinism, Side-Effects, and Parallelism:
            A Functional Perspective}
    ,booktitle={Proceedings of the Santa Fe Graph Reduction Workshop}
    ,organization={Los Alamos/MCC}
    ,year=1986
    ,month=Oct
    ,publisher={Springer-Verlag LNCS 279}
    ,pages={312-327}
    } 

Links:

arrays_journal.pdf