Parallel exponentiation of concrete data structures

Abstract: "Berry and Curien, building on Kahn and Plotkin's theory of Concrete Data Structures and sequential functions, have defined a sequential exponentiation of Concrete Data Structures. Their construction gives rise to an appealing model of sequential algorithms and a functional programming language CDS0, exhibiting some interesting semantic properties, such as: loss of extensionality; a notion of program equivalence sensitive to computation strategy; a lazy, coroutine-like semantics; full abstraction; identification of syntax and semantics. We propose to develop a similar model of concurrent computation by formulating an appropriate notion of parallel algorithm and generalizing their construction to a parallel exponentiation, while retaining analogous semantic properties.The introduction of parallelism into this setting raises several interesting issues, such as the existence, nature and properties of a satisfactory model of parallel computation employing parallel algorithms; ideally one would like to obtain a cartesian closed category with appropriate notions of parallel application, currying and composition. We hope that our ideas will yield insights into the proper mathematical treatment of parallel programming. We present here our notion of parallel algorithm and our parallel exponentiation of Concrete Data Structures. We motivate carefully the ideas behind our construction, and we explain how it can be viewed as a natural generalization of the Berry-Curien construction.We introduce application and currying operations suitable for our parallel setting. In order to justify our ideas and to place our work into context, we show some properties of our construction, and give a variety of examples. Finally, we indicate some directions for further research on issues raised by our model."