Continuation-based transformations for coordination languages

Coordination languages for parallel and distributed systems specify mechani sms for creating tasks and communicating data among them. These languages t ypically assume that (a) once a task begins execution on some processor, it will remain resident on that processor throughout its lifetime, and (b) co mmunicating shared data among tasks is through some form of message-passing and data migration. In this paper, we investigate an alternative approach to understanding coordination. Communication-passing style (CmPS) refers to a coordination semantics in which data communication is always undertaken by migrating the continuation of the task requiring the data to the process or where the data resides. Communication-passing style is closely related to continuation-passing styl e (CPS), a useful transformation for compiling functional languages. Just a s CPS eliminates implicit call-realm sequences, CmPS eliminates implicit in ter-processor data communication and synchronization requests. In a CmPS-tr ansformed program, only continuations (i.e., control contexts) are trans tr ansmitted across machines: all synchronization and data communication occur s locally. Besides providing significant optimization opportunities, CmPS i s a natural representation for implementations on networks of workstations. This paper presents several operational semantics for a coordination langua ge that supports first-class (shared) distributed data repositories. The co mputation sub-language considered is an untyped call-by-value functional la nguage similar to pure scheme. The first semantics describes a conventional synchronous message-passing implementation; the second is a formulation of a CmPS implementation: and, the third refines this implementation to suppo rt computation migration, a technique to lazily migrate control state. Usin g computation migration, an implementation "distributes" a continuation amo ng multiple machines reducing bandwidth requirements needed to support thre ad mobility. We prove the equivalence of all three systems and describe opt imizations and implementation issues that arise from using a CmPS-driven co ordination language. (C) 2000 Published by Elsevier Science B.V. All rights reserved.