Organizing Functional Code for Parallel Execution or, foldl and foldr Considered Slightly Harmful

摘要

Alan Perlis, inverting Oscar Wilde's famous quip about cynics, once suggested, decades ago, that a Lisp pro-grammer is one who knows the value of everything and the cost of nothing. Now that the conference on Lisp and Functional Programming has become ICFP, some may think that OCaml and Haskell programmers have inherited this (now undeserved) epigram. I do believe that as multicore processors are be-coming prominent, and soon ubiquitous, it behooves all programmers to rethink their programming style, strategies, and tactics, so that their code may have ex-cellent performance. For the last six years I have been part of a team working on a programming language, Fortress, that has borrowed ideas not only from Fortran, not only from Java, not only from Algol and Alphard and CLU, not only from MADCAP and MODCAP and MIRFAC and the Klerer-May system-but also from Haskell, and I would like to repay the favor. In this talk I will discuss three ideas (none original with me) that I have found to be especially powerful in organizing Fortress programs so that they may be executed equally effectively either sequentially or in parallel: user-defined associative operators (and, more generally, user-defined monoids); conjugate transforms of data; and monoid-caching trees (as described, for example, by Hinze and Paterson). I will exhibit pleasant little code examples (some original with me) that make use of these ideas.