没有合适的资源?快使用搜索试试~ 我知道了~
基于约束的并发性及其他
理论计算机科学电子笔记162(2006)327-331www.elsevier.com/locate/entcs基于约束的并发性及其他上田和则1,2早稻田大学邮编169-8555东京都新宿区大久保3丁目4-1摘要基于约束的并发是一种简单而优雅的单调移动通道并发形式,其历史始于20世纪80年代初,作为逻辑编程的一个子领域。虽然它几乎没有被认为是过程演算,但它们之间有着密切的联系。在本文中,我们试图传达的本质,基于约束的并发进程演算社区。我们还描述了它是如何顺利地演变成LMNtal(发音为“元素”),一种基于层次图重写的语言模型。关键词:基于约束的并发,并发约束编程,并发逻辑编程,移动性,层次图重写,多集重写,LMNtal。1基于约束的并发基于约束的并发性[4](以下简称CBC),也被称为cc(并发约束)形式主义,是一个简单的并发框架,其特征是(i)异步通信,(ii)通道移动性,(iii)多adicity和数据结构化机制,以及(iv)非严格性(即,计算部分信息)。所有这些功能都源于约束和单赋值(也称为单赋值)的使用。逻辑)变量,用于表示数据和通信。通过向单调存储器告知约束(关于通道的值),将消息写入通道,然后通过询问存储器是否包含特定约束来CBC已经非常稳定;到20世纪80年代中期,所有上述特性基本上都可以在并发逻辑编程语言中以其当前的形式使用1部分由科学研究补助金((B)(2)16300009,优先领域(C)(2)13324050和(B)(2)14085205)、文部科学省和日本学术振兴计划资助。2电子邮件地址:ueda@ueda.info.waseda.ac.jp1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.12.103328K. 上田/电子笔记在理论计算机科学162(2006)3271<$B1<$B,C,P<$−→<$BJ<$B,CJ,P<$22(程序)P::=R的(规则)R::= A:-B(或!(A. (B))(body/进程)B::= G的多集(目标)G::= T 1 = T2 |一(非单原子)A::= p(T1,. ,Tn),p/=' ='(term)T::=(如一阶逻辑)Fig. 1.简化GHC<$B1,C,P<$−→ <$BJ,CJ,P<$(Par)1(讲述)⎛{t1=t2},C,P⎞E |=(C vars(h)(b = h))和vars(h:-B)(vars(b)vars(C))=(问)<${b},C,{h:-B}<$P<$−→ <$B,C<${b=h},{h:-B}<$P <$图二. GHC的约简语义最初。此外,这一概念还通过大量的编程和实施经验进行了测试[2]。受保护的号角子句(GHC)[1]可以被视为体现CBC的最小片段,其简化的语法和小步语义分别如图1和图2所示。这里,三元组B,C,P由过程B,代表存储器的方程的多组C和程序P组成。E表示有限项和原子公式上的标准句法等式理论尽管CBC几乎不被认为是进程演算(我称之为基于名称的并发),但它们之间有着密切的联系。最重要的是,仔细研究基于约束的通信揭示了约束存储的高度局部性,约束存储通常被(错误)理解为全局共享实体。CBC中的频道是第三方无法伪造的新鲜本地名称,新鲜频道只能使用现有频道导出和导入tell操作T1=T2包含进程演算中的两个操作,即输出和通道融合。ask操作还包含两个操作:输入(同步和值传递)和匹配(值检查)。规则的替代语法,!(A.B),表明它结合了问,选择,减少,隐藏和复制。在过程演算方面,π演算的最重要的变体应该是K. 上田/电子笔记在理论计算机科学162(2006)327329(过程)P::= 0 | p(X1,.,Xm) | P,P| {P} | T:-T(工艺模板)T::= 0 | p(X1,.,Xm) | T,T| {T} | T:-T|$ p [ X 1,.|$p[X1,...,Xm|A]|p(*X1,.,*Xn)(残差)A::=[]|*X图三. LMNtal公司是异步π-演算,一些变体包括Lπ和πI限制了名称的使用,以追求更好的语义性质。所有这些目标在CBC都很自然地实现了。一旦适当的类型系统被纳入这两个阵营,基于约束和基于名称的通信表现出更多的相似性。我们已经开发了基于约束的并发模式和线性系统,这些系统与通信的极性和多样性有关,并规定了通信通道的使用方式[4]。π演算的线性类型系统也保证只有一个进程拥有写能力并使用它一次。这两个阵营的这些限制使得破坏性和非破坏性读取之间没有明显的区别2语言模型LMNtal我们最近的工作是设计和实现LMNtal(发音为LMNtal是试图统一CBC和约束处理规则的结果,这是并发逻辑编程的两个显着扩展LMNtal也可以被在Java平台上运行的LMNtal系统现在可以在Web上使用[6]。图3给出了LMNtal的语法,其中预设了两个语法类别,链接(用X表示)和名称(用p表示)。name=是为原子进程保留的,用于连接两个参数。进程P必须遵守以下链接条件:P中的每个链接(不包括规则中出现的链接)最多出现两次。直觉上,0是惰性过程; p(X1,.,Xm)(m≥ 0)是具有m个连接的原子; P,P是称为分子的平行组成;{P}是细胞,是由膜{ }分组的过程; T:-T是过程的重写规则。重写规则必须遵守几个语法条件(细节省略)上可能出现的符号,这是为了保证减少保留链接条件。规则上下文@p用于匹配单元格中的多规则集(可能为空),而流程上下文$p[X1,.,Xm|A](m≥ 0),是匹配单元内除规则之外的进程。流程上下文的参数指定哪些链接可以或必须330K. 上田/电子笔记在理论计算机科学162(2006)327(E1) 0,P<$P (E2)P,Q<$Q,P (E3)P,(Q,R)<$(P,Q),R(E4) P<$P[Y/X]如果X是P的局部链路(E5) PPJP,QPJ,Q(E6) PPJ{P}{PJ}(E7) X=X0(E8)X=YY=X(E9) X=Y,P<$P[Y/X]如果P是一个原子,X在P中自由出现(E10){X=Y,P}<$X=Y,{P}如果X和Y中恰好有一个在P(R1)P−→PJP,Q−→PJ,Q(R2)P−→PJ{P} −→ {PJ}(R3) Q<$P P−→PjPJ<$QJQ−→QJ(R4){X=Y,P}−→X=Y,{P}如果X和Y在{X=Y,P}中自由出现(R5)X=Y,{P}−→{X=Y,P}如果X和Y在P(R6)Tθ,(T:-U)−→Uθ,(T:-U)见图4。LMNtal的结构同余与约化关系自由发生。当残差A的形式为X时,它指定除了必须出现的链接X1,.之外的链接。,Xm可以自由出现,并且其自身绑定到那些可能出现的链接。最终形式p(*X1,.,*Xn)(n > 0),表示原子的聚集体,其多重性由每个Xi所保持的连接数决定。LMNtal的操作语义(图4)由两部分组成,即结构同余(E1)-(E10)和归约关系(R1)-(R6)。注意,(E4)表示α-转化。(E9)计算过程中使用的规则搭配在同一个(R1)–(R3) are standard structural rules,and (R4)–(R5) are the mobility rules of LMNtal的中心规则是(R6)。(R6)中的替换θ(细节省略)用于操作语义设计中的主要挑战是正确处理由链接形成的图结构和由膜形成的层次结构(可能被链接跨越)之间的相互作用。我们给出两个简单的程序示例。用c(cons)节点和n(nil)节点表示的两个列表可以使用以下两个规则连接append(X0,Y,Z0),c(A,X,X0):- c(A,Z,Z0),append(X,Y,Z)append(X0,Y,Z0),n(X0):-Y=Z0多路流合并可以使用膜编写如下:{i(X0),o(Y0),$p[|*Z]},c(A,X,X0):K. 上田/电子笔记在理论计算机科学162(2006)327331c(A,Y,Y0),{i(X),o(Y),$p[|{\fnSimHei\bord1\shad1\pos(200,288)}{\fnSimHei\bord1\shad1\pos(200,288)}这里,左手边的膜记录n(≥1)个输入流,名为i,一个输出流,名为o。 进程上下文$p[|*Z]用于匹配其余的输入流,并将它们传递到右侧。我们在LMNtal中成功表达的程序非常多样-包括按名称调用的lambda演算,异步π演算,bigraphs及其组合,自底向上的解析器,具有图形用户界面的计算器此外,我们在过去二十年中编写的大多数并发逻辑程序,以及表示为交互网络的程序,都是作为LMNtal程序运行的,没有或只有非常小的修改。LMNtal旨在作为一种通用语言,涵盖从广域到嵌入式计算和自组织编程的各种平台,并且有很多正在进行和未来的工作。我们也有兴趣在重写规则的GHC和LMNtal程序中发现的各种对称性。考虑到对称性编写的程序具有重要的属性,如不变量和可逆性,这些属性不仅仅是美,我们相信对称性在我们的编程和程序推理中起着重要的作用。引用[1] Ueda,K.,美国,“守护号角条款”,ICOT技术。报告TR-103,ICOT,东京,1985年。也在LogicProgramming[2] Shapiro,E.是的,Warren,D. H. D、Fuchi,K.,科瓦尔斯基河一、Furukawa,K.,Ueda,K.,美国,Kahn,K. M.,Chikayama,T.和Tick,E.,《第五代计划:个人观点》,ACM Comm.,36(1993),46[3] Ueda,K.,美国,并发逻辑/约束编程:未来10年,在R. 等人(编辑),Springer,1999,53[4] Ueda,K.,美国,资源传递并发程序设计,Proc. TACS 2001,LNCS 2215,Springer,2001,95-126。[5] Ueda, K., 美国 ,LMNtal: A Language Model with Links and Membranes( 英语 : LMNtal: ALanguage Model with Links and Membranes)WMC5,LNCS 3365,Springer,2005,110[6] LMNtal主页,URL:http://www.ueda.info.waseda.ac.jp/lmntal/
下载后可阅读完整内容,剩余1页未读,立即下载
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)