An Operational Semantics for the Parallel Language Eden
An Operational Semantics for the Parallel Language Eden
复制标题
并行语言伊甸园的操作语义
DOI：
10.1142/s0129626402000938
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Yolanda Ortega
中科院分区：
文献类型：
--
作者：
Mercedes Hidalgo;Yolanda Ortega
函数式并行语言Eden——适用于描述分布式环境中的并行和并发算法——是Haskell的扩展，具有一组协调特性。本文给出了Eden核的一种形式运算语义，或者更准确地说，给出了具有显式并行性和潜在无限通信通道的λ-微积分的一种形式运算语义。Eden以并行的方式覆盖了Haskell的懒惰特性。这里提出的语义准确地描述了懒惰和渴望之间的相互作用，该语义基于Launchbury的懒惰评估自然语义，并通过两层过渡系统来表达：下层用于每个进程的局部和独立评估，上层用于系统中所有并行进程之间的协调。由于进程是根据需求或推测方式创建的，因此可以使用不同的调度策略——从只允许主线程演进的最小调度策略，到与每个活动绑定并行演进的最大调度策略。
The functional parallel language Eden — suitable for the description of parallel and concurrent algorithms in a distributed setting — is an extension of Haskell with a set of coordination features. In this paper we present a formal operational semantics for the kernel of Eden, or more precisely, for a λ-calculus widened with explicit parallelism and potentially infinite communication channels. Eden overrides the lazy nature of Haskell on behalf of parallelism. This interplay between laziness and eagerness is accurately described by the semantics proposed here, which is based on Launchbury's natural semantics for lazy evaluation, and is expressed through a two-level transition system: a lower level for the local and independent evaluation of each process, and an upper one for the coordination between all the parallel processes in the system. As processes are created either under demand or in a speculative way, different scheduling strategies are possible — ranging from a minimal one that only allows the main thread to evolve, to a maximal one that evolves in parallel every active binding.