D-Clean: 分布式函数式编程的可执行语义及其分布式系统设计

可在www.sciencedirect.com在线获取理论计算机科学电子笔记279（3）（2011）85-95www.elsevier.com/locate/entcsD-Clean1的通用可执行语义ViktoriaZso'k2埃奥特维奥斯·洛兰德大学信息学院程序设计语言与编译器系匈牙利布达佩斯Pieter Koopman3 Rinus Plasmeijer4奈梅亨计算与信息科学研究所荷兰奈梅亨摘要D-Clean原语是一级公民，允许在集群上协调动态工作分布。 计算通过中间件系统自动分布在网格上。程序员控制生成的盒子中的计算节点和生成的通道上的通信。为了获得关于协调原语如何工作的高度抽象的描述，需要可执行语义的通用模型本文提供了一个更一般的版本的模拟真正的并行计算的D-Clean扩展的清洁语言。首先，以抽象的方式给出每个D-Clean原语的可执行语义定义。其次，我们描述了一个图形系统，生成可视化的最大并行量的计算方案。 最后，我们陈述可执行描述的属性为D-Clean和D-Box设计的分布式系统。关键词：D-Clean，可执行语义，分布式函数式编程，骨架。1引言Distributed Clean [8，19]或D-Clean是Clean[16]在clus- ter上的分布式扩展这个并行系统的目的是协调功能性编程任务的集群使用高级协调语言参数化的功能性编程计算节点。然而，设计的协调模型也可以与其他编程语言实现的计算一起工作。由TA′MOP-4.2.1/B-09/1/KMR-2010-0003提供1份支持2电子邮件：zsv@inf.elte.hu3电子邮件：pieter@ru.cs.nl4电子邮件：rinus@ru.cs.nl1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.04086诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）D-Clean是分布式系统的顶层。它具有协调作用，用于定义并行计算方案，骨架。 使用D-Clean，程序员通过高级协调语言指示如何将分布式计算放置到与经由通信信道连接的D-Box计算盒相对应的生成的计算节点中(bu通信工具）。D-Box语言是基于Petri网设计的中间层语言[3]。盒子的任务是计算包装到分布式计算图的节点中的函数。这些盒子被编译成Clean程序，它们根据完善的协议通过通道进行通信。通道和盒子生成是分布式系统的一部分，但是这里特别忽略了盒子，专注于更高级别语言D-Clean的原语语义的定义。功能计算节点由定义良好的、相对少量的特定D-Clean原语协调，并应用于数据流。根据为计算的评估而生成的框的输入-输出协议这两种语言的语义在[8]中有非正式的描述。在本文中，首先，我们使用Clean作为描述语言，从真实的分布式环境中抽象出来，并省略了盒子和通道生成的细节，给出了一个更通用和可执行的语义描述在一些D-Clean示例中，获得了并行性的高速提升（参见[20]中[9]中描述的问题的D-Clean在这里，我们将主要强调通用的和可执行的描述的操作语义的D-Clean语言原语。可执行的语义允许我们描绘的潜在数量的并行图形以及。预期的并行性（类似于真实的分布式系统）将通过为定义良好的分布式计算并行生成的盒子和通道的图形可视化来实际的并行量以及因此的加速取决于许多因素，例如通道创建的顺序、一个通道上的工作量、通道中的数据检索和数据存储的速度、分布式图中描述的计算的复杂性。尽管如此，在设计具有良好加速的D-Clean程序时，有关潜在并行量的信息是一个有价值的工具因此，使用可执行语义的分布式计算的可视化提供了在真正的分布式系统本文的组织如下：首先，我们给出了D-Clean原语和它们的可执行语义，然后，我们描绘图形化的D-Clean程序，最后，我们制定可视化的例子的可执行语义的属性。2D-Clean原语及其可执行语义在最初的分布式系统中，D-Clean协调原语通常有两个参数：函数表达式（或函数表达式列表）和序列诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）87→→输入和输出通道。协调原语在指定的输出通道上返回结果协调原语的签名，即输入和输出通道的类型根据嵌入的Clean表达式的类型来推断。在这里，在可执行语义版本中，我们使用DExpr代数类型定义D-Clean原语，将D-Clean表达式转换为DFun可执行表达式（仅在可视化时需要字符串信息//DClean表达式的类型，一个函数或函数的组合：：DExprab=FString（ab）| D（DFun（Ch a））（Ch b））原语可以是Clean函数（或函数的组合），也可以是由Clean函数参数化的D-Clean表达式，这些函数放置在并发评估和执行的框中。在语义上，原语是一个状态转换函数，将输入状态转换为输出状态。//每个DClean表达式都是一个状态转换函数：：DFuna b：=a State→（b，State）在这里，我们对真实的分布式世界进行了一些抽象，忽略了盒子生成的细节，只指定了已建立的通信通道。因此，D-Clean程序的描述和健全性检查，在实际的分布式系统编程之前，更容易通信信道的定义很明确，只需给它们编号。可以使用两种通道：用于一个线程通信的单通道，以及用于模拟多个并行计算线程上的数据传输的多通道。//单通道，用于简化编号：：Cha：==（Int，a）//多通道，定义为单个通道：：MCha：==[Cha ]2.1DStart和DStop原语DStart原语的任务是通过为分布式图的输入数据流生成通信通道来开始构建分布式计算。它没有输入通道，只有输出通道。DStart基元将其输入函数与输入数据流一起，并开始计算。结果被发送到输出通道。每个D-Clean程序至少包含一个DStart原语。使用Clean函数的功能描述如下：DStart：：a（DFunab）State（b，State）DStart a expr state=expr a stateD-Clean程序中必须包含的另一个协调原语是DStop原语。该原语的任务是终止所有的通信通道，并保存计算过程的结果。它有函数表达式所需的输入通道，但没有输出通道。88诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）→→→→每个D-Clean程序至少包含一个DStop原语，它是D-Clean程序的最后一个元素，即过程网络的最后一个元素。该函数用于原语的语义如下：DStop：：（a，State）（a，State）DStop（结果，状态）=（结果，takeWorld状态）哪里takeWorld（ n，t）=（ n， reverset）为了确保在任何可执行的D-Clean程序中包含这两个原语，我们构建了一个名为DExec的包装器。因此，DExec立即将DStart和DStop强制原语合并到一个封装中。 它将Clean的“正常”世界提升DExec：：a（DFun a b）（a，（b）国家）DExec a expr=（a，DStop（ DStart a expr（0，[]）DExec与>>=组合子一起使我们能够以一元方式编写D-Clean程序模拟（>>=组合子重命名绑定操作）。（>>=）infixl1（>>=）f g：=f在下面，我们使用mkFunBox来生成对应于计算节点的盒子：mkFunBox：：String（a→b）→ DFun（Ch a）（Ch b）|toString b如前所述， mkFunBox创建的盒子在原始分布式系统中并发运行。这里mkFunBox指定原语将被放置在生成的盒子的计算节点中。这些盒子使用完善的协议通过信道进行通信。在下文中，每个D-Clean原语的细节将与可执行签名一起给出2.2DApply原语及其变体DApply原语类允许将其参数函数应用于分布式计算的数据流。定义了几个版本，因为它们代表了D-Clean分布式系统的核心原语。最简单的一种是在单线程计算中使用的DApply，即将一个函数参数应用于单个输入通道的数据流DApply：：String（ab）DFun（Cha）（Chb） | toString b DApply name fun = mkFunBox name fun然而，在大多数情况下，当计算中需要多个线程时，使用DApply原语，在我们的可执行语义中通过通道的MCh多功能应用程序可以在两个变体中完成。第一个变体DApplyN是最通用的变体。它可以在分离的计算线程的不同数据流上应用不同的函数表达式。诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）89→→→要应用的函数序列在表达式列表中给出，指定为[DExpr a b]。原语的操作类似于zip函数，即它从函数序列中获取一个函数表达式，并将其应用于来自输入的流入列表的对应对数据流显然，两个序列的长度应该相等，以便具有适当的函数和数据流匹配。正如多通道输入数据类型所暗示的，输入数据流在单独的计算线程上并行。DApplyN：：[DExpr a b]DFun（MCha）（MChb）|toStringbDApplyN funs=DExpr funs哪里DExpr：：[DExprab ]（MCha）状态（MChb，Stat e）|toStringbDExpr[][]state=（[ ]，state）DExpr[]inflowsstate=abort“run-time error”状态（result，state）=mkFunBox namefunistate（results，state）= DExprfuns is state=（[result：results]，state）DExpr[Ddfun：funs ][i：is]state（result，state）= dfunistate（results，state）= DExprfuns is state=（[result：results]，state）如果一个线程只从传输数据的输入通道中获取数据流，而不对它执行操作，那么应该在计算线程的相应位置上的函数列表中提到id第二种变体DApply1在不同的计算线程上应用相同的函数参数n次，每个线程都有自己的数据流，即每个通道都对不同的数据流进行操作。DApply1：：（DExpr a b） DFun（MCha）（MCh b）|toStringbDApply1 expr=λ流入→DApplyN（重复n（长度流入）（dexpr）流入从定义中可以观察到，它使用最一般的变体DApplyN，重复地对输入数据流应用相同的expr。然而，这种重复是对单独计算线程上并发函数应用的模拟。2.3D适用特殊情况从分布式应用程序的经验中衍生出来，一些特殊的DApply原语情况很方便，因此我们将它们定义为具有自己名称的独立原语。在可执行语义版本中，我们可以使用DApply变体之一来定义它们。DMap实用工具原语与DMap 2一起是基本的分布式映射操作，而DReduce、DProduce和DFilter是具有一些限制的DApply2.3.1DMap实用程序基元DMap是众所周知的标准映射库函数的分布式版本的D-Clean变体是一个计算节点，它将参数表达式应用于90诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）→→→→传入数据流的每个元素。 DMap的参数函数必须是 一个元素级可处理的函数。可以观察到，DMap是DApply的一个特例，其中一个有趣的参数应用在单个线程上（即，它具有单通道输入）。DMap：：（ab） DFun（Ch[a]） （Ch[b]）|toString b DMap fun = DApply "DMap" (map fun)对于多通道输入，定义了DMap 2原语。由于它的多重性，它可以很容易地表达使用DApply1原语与并发应用的乐趣参数上的n个不同的线程与自己的数据流的通道输入。DMap 2：：（ab） DFun（MCh[a]）（MCh[b]）|toStringb DMap2fun=DApply1（F“Map 2”（map fun））2.3.2具有限制的DApply实用程序原语以下三个实用程序原语是DApply的特殊情况，对输入数据流有一些类型限制。DReduce是一种实用原语。DReduce的有效表达式必须减少输入数据流的维度，即输入是转换成一个数据流的数据流列表，以用于输出。DReduce：：（[b] →a）→ DFun（MCh [b]） （百万美元a）|toString a与DReduce相反的是DProduce实用程序原语，其中DFun参数表达式必须增加输出数据流的维度，它只是将一个输入数据流转换为一个数据流列表D产生：：（a→[b]） →DFun（MCha）（ MCh[b]） | toString bDFilter是DApply的一种特殊情况，与上述方法相比，其方式不同。它根据类似于filterClean函数的filter（布尔）表达式过滤输入数据流。D过滤器：：（a →布尔值）→DFun（MCh[a]）（MCh[a]）|toString a2.4DDivide原语DDivide原语有一个DFun表达式作为参数，它根据分隔符参数函数将输入数据流分成几个部分。在分割之后，它将输入数据流广播到具有各自计算任务的不同计算线程上。划分的主要类型特征在通道参数的类型中给出：输入数据流在单个通道上传输，而输出将在多个通道上传输。可以观察到，所有输出数据流都具有相同的类型。DDivideD版本动态地确定它需要闪烁的计算线程的数量，并将数据流传输给它们。D划分D：：（a→[b]）→DFun（Ch a）（毛里求斯卢比b） | toString b诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）91DDivideS是一个静态分频器。这个原语被称为静态分频器，因为线程数（n）在编译时是已知的，并且它作为参数提供给数据流分频器函数。DDivideS：：（Int [a] → [[a]]） Int→DFun（Ch [a]） （MCh [a]） | toString a2.5DMESCO原语DDivide的对应物是DMCup原语，它从多通道的输入通道收集输入数据流，并为输出线程的单个通道建立唯一的输出数据流。所有输入通道必须具有相同的类型。DMS2 ：：（[b]→a）→ DFun（MCh b）（Ch a） |toString a在分布式计算中，当需要分发或收集数据流时，上述两个原语非常有用。2.6原始成分在最初的D-Clean系统中，我们也设计了组合语言原语，它们也在可执行语义模型中定义。 一个典型的例子是DLinear基元，用于在基元的流水线中更容易地合成D线性：：（管道a b）→DFun（Ch [a]）（Ch [b]）|toStringb&toString a该原语特别用于数据驱动的框架，其中数据量和组合函数的数量决定了问题实现的类型3视觉化D-Clean程序在分布式系统中执行的可视化对于分析执行结果和调试复杂的分布式程序具有重要意义。可执行语义提供了一个工具来理解分布式计算是如何完成的，省去了中间件的细节：为计算节点和通信通道生成盒子。分布式程序在应用于实际的分布式系统之前，可以通过图形化的方式进行绘制和可视化，以测试其执行的语义。对于每一种语言原语，我们都提供了这样的可视化，这使得分布式程序的创建更加灵活。让我们考虑一下著名的农场骨架的例子。在这里，我们用我们的可视化方法来说明这个问题，通过并行计算简单的任务。在输入数据流上完成DMap操作之后，主计算节点应用静态除法。在每个sparkled线程上，由工作节点执行单独的操作，之后主节点再次合并子结果。92诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）→开始w=dumpGraph（DExec myval myflow）w哪里myval= [1..第10页]myflowi=DMapinc（0，i）>>= DDivideD（除以3）>>= DApplyN[F“mapinc”（地图inc），D（λiDMapinci>>=DMapinc），F“id”id]>>=DMP-flattenFig. 1. 农场示例可视化在其可视化中（参见图1。）我们可以观察到输入数据流如何在执行它们自己的单独任务的工作者之间被划分为3个部分最后，主机将子结果收集到最终数据流中。更多的骨架例子可以在[19]中找到。4一些性质和变换由于通道的行为在某种意义上类似于列表，我们可以应用一些类似列表的转换。这些转换可以用来改变D-Clean程序的操作行为，以及引入新的通道。对于列表，我们有类似于例如mapfo mapgmap（fog）的等价物（更多列表属性请参见[4]）。两种语言结构的指称语义是相等的，这意味着对于所有函数f和g以及所有参数列表，这些表达式产生相同的结果。不过，有一个操作上的困难-诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）93因为MAP_F_O_MAP_G产生在MAP（F_O_G）中被省略的中间列表。因此，后一种表达方式预计在操作上更有效。类似于这个列表转换，我们可以通过以下转换来改变在通道上操作的函数的数量：DApply1（ F“f” f）>>= DApply1（ F“g”g）→ DApply1（ F“fg”（g o f））当我们使用变换将几个不同的函数应用于通道时，也可以实现此效果：DApplyN[F“f1”f1，. 。 ，F“fn”f n ]>>=DApplyN[F“g1”g1，. 。 ，F“gn”g n ]ADapplyN[F“fg1”（g 1of1） ，. 。 ，F“fgn”（g nofn）]以类似的方式，我们可以将DApplyN和DApply的组合转换为DApplyN的单个应用。DApplyN[F“f1”f1，. 。 ，F“fn”f n ]>>= DApply1（ F“g”g）ADapplyN[F“fg1”（gof1） ，. 。 ，F“fgn”（gofn）]反之，我们可以有：DApply1（ F“f”f）>>=DApplyN[F“g1”g1，. 。 ，F“gn”g n ]ADapplyN[F“fg1”（g 1of） ，. 。 ，F“fgn”（g nof）]我们在这里展示的最后一个转换涵盖了将Clean中的普通列表处理函数提升到D-Clean中的n个通道上的通道处理构造。映射f表≡DDivideD（ divide n）（0，list）>>= DApply1（ F“f”f）>>=DMRQID应用于代码的转换应始终保持第2节中定义的语义。5相关工作几个相关的作品可以列举不同的共同点。早些时候，Clean中的并行和分布式计算在两篇博士论文中报道：[11]和[18]。第一个是在并行超级计算机上测试Clean程序，而第二个是基于使用并行函数求值注释在一台计算机内对函数的部分进行并发求值。我们在D-Clean系统中的方法强调在集群的不同计算机上运行的独立Clean在Clean中引入的iTasks的可执行语义存在于 和iData属性测试使用[12]的基于模型的测试工具G st），而使用函数作为规范的全自动测试则在[13]中。iTask已编程94诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）基于Web，由集中式服务器应用程序协调。D-Clean程序被放置在使用Petri网规则操作的计算盒其他几种函数式语言有不同类型的并行计算（例如Eden [1]和[2]，或JoCaML [6]）。Haskell方言的并行函数语言的比较在[14]中完成，并在[15]中在集群上进行测试。它们基于不同的固有过程定义，而我们的方法使用单独分发的，单独可执行的程序。两本研究书籍对骨骼文献很重要：[7]和[17]。第一个说明了几个函数式编程框架应用程序，而第二个则更多地是该主题的理论方法。D-Clean系统的主要特点是集群上的分布式框架应用程序，这在上述两本书中没有出现。并行数据流问题及其实现的比较可以在[10]中找到。我们的数据流编程更复杂。分布式环境使用两种协调语言，用于使用中间件服务在系统的两个不同层上进行数据流操作。设计用于可视化算法及其执行的图形函数数据流语言例如存在于NiMo（Nets In Motion）[5]中。我们对可执行语义的可视化更侧重于解释D-Clean语言原语含义的细节。6结论在本文中，我们给出了一个可执行的语义D-Clean在更一般的方式。D-Clean是Clean的扩展，是一种用于集群上原语的功能描述使得能够理解在D-Clean的真实分布式系统中计算什么以及如何进行计算。图形可视化可用于描述所做的工作量在并行执行中，计算在节点（盒子）中进行，通信在通道上进行。最后，我们已经制定了D-Clean原语语义的可执行定义的属性引用[1] Berthold ， J： Explicit and Implicit Parallel Functional Programming Concepts and Implementation ，PhDThesis，PhilippsUni versit？atMarburg，2008.[2] Berthold，J.，Klusik，U.，卢根河，Priebe，S.，Weskamp，N.：Eden的高级过程控制，In：Ko s ch，H.， BéoszoérményiL.， Hell wagner，H. （Eds.）：第九届国际欧洲标准化委员会第一次会议Conference，Euro-Par 2003，Proceedings，Klagengland，Austria，August 26-29，2003，SpringerVerlag，LNCS Vol. 2790，pp. 732-741[3] 贝斯特，E.，霍普金斯河P.：B（PN）2-一种基本Petri网程序设计表示法，见：Bode，A.，里夫，M.，Wolf，G.（Eds.）：欧洲并行体系结构和语言，第五届国际PARLE会议，PARLE'93，会议记录，德国慕尼黑，1993年6月14-17日，Springer Verlag，LNCS第694卷，第100页。379-390.[4] 伯德，R.：介绍使用Haskell的函数式编程（第二版）。Prentice Hall，1998年。ISBN 0-13-484346-0。诉Zsók et al. /Electronic Notes in Theoretical Computer Science 279（3）（2011）95[5] Clerici，S.， 佐尔坦 角，Prestigiacomo ， G.： NiMoToons ：a Totally Graphic Programme Tuning andExperimentation Electronic Notes in Theoretical Computer Science（ENTCS），Volume 258 Issue 1，December 2009，pp. 93比107[6] Fournet，C.，Le Fessant，F.，马兰杰湖Schmitt，A.：JoCaml：A Language for Concurrent Distributedand Mobile Programming，In：Johan Jeuring，Simon Peyton Jones（Eds）：Advanced FunctionalProgramming，4th International School，AFP 2002，Oxford，Revised Lectures，，2003，Springer，LNCS 2638，pp. 129比158[7] Hammond，K.，Michaelson，G.（Eds.）：并行函数式编程研究方向，Springer Verlag，1999。[8] Hor v'athZ.， 她叫Z， 和ZsokV.：分布式清洁的协调语言。 ActaCy berneti ca，17（2）：247 -271，2005 .[9] 霍瓦特Z Zso'kV.，Serrarens，P.，Plasmeijer，R.： 并行清洁，数学和计算机建模中的并行元素可编程函数38，Pergamon，2003年，pp. 865-875[10] Johnston，W. M.，汉娜JRP米勒，R.J.：数据流编程语言的进展，ACM Computing Surveys36（1），ACM Press，2004年3月，pp.1-34[11] Kesseler，M.H.G.：函数式语言在具有分散式记忆体的平行机器上的实作，博士论文，奈梅亨天主教大学，1996年。[12] Koopman，P.和Plasmeijer，R.：高阶函数的自动测试。在N. Kobayashi（编辑）第四届亚洲编程语言与系统研讨会论文集APLAS第4279页11月8日至10日，澳大利亚悉尼，148-2006年。史普林格出版社[13] Koopman，P.和Plasmeijer，R.：全自动测试，以功能为规范。在中欧函数式编程学校，LNCS第4164卷，pp。35-61，布达佩斯，匈牙利，4-16，2006年7月。史普林格出版社[14] Loidl ， H-W. ， Rubio ， F. ， 斯 凯 夫 ， N.， Hammond ， K.， Horiguchi ， S.， Klusik， U.， 卢 根 河 ，Michaelson ， G.J. ，佩尼 亚河 ，Pri e b e， S. 200.R e b'onPortillo ， A'.J. ，Trinder ， P. W. ：ComparingParFunctionalLanguages ： Programming and Performance ， Higher-Order and SymbolicComputation 16（3），Kluwer Academic Publishers，2003年9月，pp. 203-251[15] Loidl，H-W.，Klusik，U.，Hammond，K.，卢根河，Trinder，P.W.：GPH和Eden：在Beowulf集群上比较两种并行函数语言，在：Gilmore，S。(Ed.)：函数式编程的趋势，卷。2，Intellect，2001，pp.39比52[16] 普拉斯梅耶尔河和van Eekelen，M.： Concurrent Clean语言报告（2.0版），12月12日。2001年http://www.cs.ru.nl/clean/.[17] Rabhi，F.A.，Gorlatch，S.（Eds.）：并行和分布式计算的模式和方法，Springer Verlag，2002年。[18] Serrarens，P.R.：分布式函数计算中的通信问题，博士论文，奈梅亨天主教大学，2001年1月。[19] Zs'okV.， 她叫Z， Horv'ath，Z.：在D-Clean和D-Box中设计分布式计算系统。在中欧函数式编程学校，LNCS第4164卷，pp。223[20] Zs'okV.， 她叫Z， Horv'ath，Z.：D-Clean 中分布式元素处理实现的改进 在2007年第10届编程语言和软件研讨会的会议记录中，SPLST，2007年6月14日至16日，匈牙利，第10页。256-264，Eüotv�os Uni versityPress，2007年。