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.