Functions Compute, Relations Co-ordinate

Manuel Chakravarty

Parallel implementations of declarative languages suffer from two problems: first, the lack of an explicit, but declarative notion of parallelism; and second, latency that is induced by remote data accesses. We get a declarative notion of parallelism by a combination of functional and relational programming elements, where purely functional expressions denote step-at-a-time computations, whereas relations express co-ordination of sequential computations. The essence of such languages is captured by an extension of the lambda calculus---called D---that adds co-ordinating relations. D has an abstract semantics, which is realized by an encoding into linear logic, and a parallel operational semantics, which is derived from the abstract one.

To tackle the second problem, namely latency induced by remote access, an integration of multi-threading into the Spineless Tagless G-machine is proposed. It uses the freedom in the evaluation order, which is guaranteed by the semantics, to overlap different communication operations and computation with communication.