Compiling FX on the CM-2

Type and effect systems provide a safe and effective means of programming high-performance parallel computers with a high-level language that integrates both functional and imperative paradigms. Just as types describe what expressions compute, effects describe how expressions compute. Types and effects are associated with regions that describe where dynamically-allocated data structures reside in memory. We show how types, regions and effects can be used to discover when global operations on vectors are amenable to data parallelism in the presence of both side effects and higher-order functions. 1 Introduction The functional and imperative programming paradigms are often integrated together within sequential languages such as Common Lisp [11], Scheme [10] or Standard ML [7]. In such languages, implementors must exert care when designing code optimizers since side effects inhibit most of the nice properties of pure functional languages which are put at work in code transformations. Goi..