Para-functional programming: a paradigm for programming multiprocessor systems


Paul Hudak and Lauren Smith


One of the most important pragmatic advantages of functional languages is that concurrency in a program is implicit -- there is no need for special constructs to express parallelism as is required in most conventional languages.  Furthermore, it is fairly easy for compilers to automatically determine the concurrency as a step toward decomposing a program for execution on a suitable parallel architecture.  Yet it is often the case that one knows precisely the optimal decomposition for execution on a particular machine, and one can never expect a compiler to determine such optimal mappings in all cases.  This paper is concerned with ways to allow the programmer to explicitly express this mapping of program to machine, by using annotations that, given a few minor constraints, cannot alter the functional semantics of the program.  We show through several detailed examples the expressiveness and  conciseness of the resulting "para-functional" programming methodology, using an experimental language called ParAlfl based on our ideas.  We also give a formal denotational description of the mapping semantics using a notion of execution trees.


    ,author={Hudak, P. and Smith, L.}
    ,title={Para-functional programming: a paradigm for programming
            multiprocessor systems}
    ,booktitle={12th ACM Symposium on Principles of Programming Languages}