（计算机软件与理论专业论文）对象并发演算模型及对象语言语义研究.pdf

攘要 虽然耐向对象语言与技术已被广溅使用，但是嘲向对象语音理论还不完替。 主要纛因蹙，嚣囊对象添蠡还没鸯一个羰广泛认同瓣模型。对予蹶j 莩瑟囱对象溪 占，人们研究得比较多，并取得了许多成果。相反，对于并发面向对象语言，入 们研究得较少。 为了研究并发面向对象语言规制，本文酋先讨论了几季中西向对象语言模测， 然螽滔述了p l 演算军拜a c t o r 模墅两耪并发模垄。程魏基磕上，本文提整了a c t o r 对象演算a o c 。a o c 演算是扩充了a c t o r 机制并且被重新解释了的异步p i 演算。最后，本文用a o c 演算给出了一个对象语言o l 的语义描述。 关键词：对象，a c t o r ，并发，p i 演算，并发面向对象语言 a b s t r a c t a l t h o u g ho b j e c t - o r i e n t e dl a n g u a g e s a n dt e c h n o l o g i e sh a v eb e e nu s e dw i d e l y , t h e t h e o r i e so f o b j e c t - o r i e n t e dl a n g u a g e sa r en o tp e r f e c t t h em a i n r e a s o ni st h a tt h e r ei s n o tac o m m o nm o d e li no b j e c t - o r i e n t e dl a n g u a g e s al o to f r e s e a r c hh a v eb e e nd o n e o ns e q u e n t i a lo b j e c t - o r i e n t e dl a n g u a g e sw i t hm a n ya c h i e v e m e n t s b yc o n t r a r i e s ，l i t t l e r e s e a r c hh a v eb e e nd o n eo nc o n c u r r e n to b j e c t o r i e n t e dl a n g u a g e s i no r d e rt os t u d yt h em e c h a n i s mo fc o n c u r r e n to b j e c t o r i e n t e dl a n g u a g e ，f i r s t l y , s e v e r a lm o d e l so fo b j e c t o r i e n t e dl a n g u a g ea r ei n v e s t i g a t e di nt h et h e s i s a n dt h e n t w ok i n d so fc o n c u r r e n tm o d e l ，p ic a l c u l u sa n da c t o rm o d e l ，a r ee x p o u n d e d o nt h i s c o n d i t i o n ，a c t o ro b j e c tc a l c u l u s ，n a m l ya o c ，i sp r e s e n t e d a o c c a l c u l u si s a s y n c h r o n o u sp i - c a l c u l u sw h i c hi se n r i c h e dw i t ha c t o rm e c h a n i s i ma n dr e i n t e r p r e t e d a tl a s t ，t h es e m a n t i c d e s c r i p t i o no fo b j e c tl a n g u a g eo li sp r e s e n t e dw i t h a o c c a l c u l u s k e yw o r d s ：o b j e c t ，a c t o r ，c o n c u r r e n t ，p i c a l c u l u s ，c o n c u l t e l l to b j e c t - o r i e n t e dl a n g u a g e 刖蟊 童瓢二十世纪六十年代第一个恧囱对象语言s i m u l a6 7 涎生以来，经过三靼 十年的发展，瓣自对象语言技术己棱广泛应用。然穗，面向对象诱富理论却远 米完善。主要原因是，面向对象语言缺乏广为人们接受的理论基础。对于面向对 象语言理论的研究，有各种不同的方法。如果从面向对象语言模型角度看，则大 敬主我稻霹竣觚蹶痔嚣势笈疆令方嚣考惫。 在本文中，我们首先讨论了四种面向对象语青模鹫，即基于操作的模型，基 于l a m b d a 演算的模型，基于a c t o r 的模趔和基于进稷演算的模型。前两个模型 霹矮予礤究蹶露嚣向对象语言，覆基于操佟豹、基于a c t o r 麴帮基予避程演算麴 模型可用于研究并发面向对象语言。由鼗w 觅，基于搽作的模型适瘸箍最广，因 为基于操作的模型容易被人理解、便于谯计算机上实现。基于l a i n b d a 演算的模 裂是人们自然想到的模型，豳为l a m b d a 演算是计算机谣言的基础，并且类型化 l a m b d a 演冀瑗论蔻研究瑟蠢瓣象语言串静类鲍穰念稳镶了缀籍静怒煮。尽管基 于操作的模型釉基于l a m b d a 演算的模型被广泛应用和研究，并且取得了丰硕成 聚，但是在两个模型中消息机制都不被当作基本的机制。在基于操作的模型中， 溃爨凝裁菝理辩为函数漏搦冬棱调委；嚣焱基予l a m b d a 演算藜模型孛，溃惠氛 制被理解为函数施用。因此这两种模型都不能反映对象的本质。 s m a l l t a l k 创始人a l a nk a y 曾经提出酾向对象程序设计三定律【7 j 一切謦对象： 对象通过消患收发稠互通信； 对象有自己的存储。 就是说，消息机制应该是基本的，我们应该从消息机制本身去考虑。 a c t o r 攘型粒避程演算都是基于澄怠穰裁懿，餐楚，a c t o r 是对象，蠢邃程不 是对象。a c t o r 模型的提出悬基于实用考虑的，虽然后米有了一些理论研究1 2 】1 3 】， 假还不完善。然而，p i 演算却有丰富的理论。如果能够将a c t o r 模型和进程演算 鹣缝会著显嚣鹬强者豹绕努，箨么褥兔我秘骚究势发鬣囊薄象语言攥论提供基 础。 在本文中，我们用a c t o r 机制扩充异步p i 演算，并熙从a c t o r 角度解释扩充 后的演算，得到了a c t o r 对象演算a o c ( a a c t o r ，o - - o b j e c t ，c - - c a l c u l u s ) 。 本文提出a o c 演算的目的是想用a o c 演算捕捉a c t o r 对象的特性，研究并发面 向对象语言理论。在给出a o c 演算的语法和语义后，本文用a o c 演算描述了 一些具体问题，特别是描述了一个面向对象语言o l 的语义。a o c 演算的提出， 为我们今后研究并发面向对象语言奠定了基础。 本文得到河南省自然科学基金项目( 0 2 1 1 0 5 0 1 1 0 ) 资助。 第一章引言 1 1 本文背景和目的 第一章引言 面向对象语言并不是什么新的事物，它的历史可以追溯n - - 十世纪六十年 代。当时，挪威奥斯陆大学和挪威计算中心的k r i s t a nn y g a a d 和o l e j o h n d a h l 在进行离散事件模拟程序设计时，对a l g o l6 0 进行了扩展，增加了一些语法描 述结构，最终形成了第一个面向对象语言s i m u l a6 7 ，该语言的问世使人们初 次认识到面向对象思想。 尽管s i m u l a6 7 在市场上并未获得成功，却对后来计算机科学和技术的发 展产生了深远影响，很多人从中受到了启发，纷纷进行各种探讨，设计了各种 各样的面向对象语言，其中最具影响力的是s m a l l t a l k 。实际上，s m a l l t a l k 可 以看作是面向对象思想的集中体现。1 9 8 0 年左右，s m a ll t a ! k - 8 0 的出现使人们 真f 体会到面向对象语言的魅力和优势，集成_ 丌发环境、层次形式的类库为后 来的面向对象语言提供了样板。随着更多面向对象语言的涌现，面向对象语言 和技术被广泛采用，促进了计算机相关技术和产业的巨大发展。 与面向对象语言发展相对比，面向对象语言理论研究的进展却比较缓慢。 最初，以s i m u l a6 7 的出现和发展为契机，特别是二十世纪七十年代。当时， 人们的注意力主要集中于面向对象语言中的类所体现的类型观点，运用抽象代 数方法进行了抽象数据类型的研究，取得了丰富成果。但是，这种方法忽略了 在面向对象语言中对象是封装数据和操作的实体，因此，抽象数据类型的研究 并未解决根本性问题。面向对象语言理论基础的发展的真正转机是在二十世纪 八十年代。 二十世纪八十年代正是面向对象语言及相关技术空前繁荣时期。随着面向 对象语言及相关技术被人们广泛采用，人们r 益感觉到面向对象语言理论基础 研究的紧迫性，纷纷投入大量精力加以研究。l o c ac a r d e l l i 在这方面做了开 创性的工作，是他首先将对象看作带有函数成分的纪录，以之为基础，对多继 承的语义进行了研究“1 。随后，他和p e t e rw a g n e r 一起，对面向对象语言中所 涉及的类型、数据抽象和多型性做了深入的探讨“w 。随着研究的不断深入，人 第一章引言 们对面向对象语言。逐渐有了基本共识，也就是面向对象语占所应该具备的要素， 这样一来就便于人们进一步研究面向对象语言。在这段时期，面向对象语言的 形式语义工作也有了一些重要成果，m a r i ow o l c z k o 第一次比较完整地给出了 一个基于s m a l l t a l k 语法特征的面向对象语言的指称语义汹“3 ”。在研究面向对 象语言时，人们发现继承问题比较难以处理，就从各个角度对继承进行研究， 其中，w i l l i a mc o o k 等人对继承机制进行了深入探讨。他们认为如果把对象看 作自引用结构，那么继承就是一种对自引用结构的修改机制，并认为自引用结 构的修改机制不仅仅适用于解释对象继承，而且可以解释一切自引用结构，这 使人们对面向对象语言理论有了更进一步的认识“”1 。 然而，人们对面向对象语言研究的重心主要倾向于顺序面向对象语言模型。 尽管第一个面向对象语言s i m u l a6 7 具备并发语言特征，但现实是，人们对并 发面向对象语言研究的研究较少。这并非是人们缺乏热情，而是人们在研究并 发面向对象语占的过程中遇到了种种困难。其中的主要困难是。“： 多数并发面向对象语言缺乏定义明确的语义基础，使得我们很难推导语 言的抽象特性； 很难完全集成并发特性与支持封装和重用的面向对象特性； 并发对象的组合性还没有理解清楚。 因此，我们亟待解决的问题是找到合适的并发面向对象语言的模型，借此， 我们才能较好地研究并发面向对象语言的特性。 由于并发行为的复杂性，使得并发模型本身的种类就繁多，但是，针对面 向对象语言而言，比较适用的是a c t o r 模型和基于进程演算的模型，而且 a c t o r 模型中a c t o r 就是对象。就根本而言，a c t o r 模型和基于进程演算的模型 都是基于消息机制的，这说明它们之间有共同之处，因此，我们可以尝试看能 否用a c t o r 模型和基于进程演算的模型来研究并发面向对象语言。 然而，a cl o r 模型和基于进程演算的模型的出发点是不同的。a c t o r 模型是 从实际问题出发的一种模型，侧重于针对各种不同的具体问题给出相应的解决 方案。但是缺乏完善的基础理沦。基于进程演算的模型则是从理论出发的一种 模型，侧重于探究并发系统的基本理论特性。因此，如果将两者结合起来，那 么所得到的模型就会同时具备两者的特性。本文就打算在这一方面进行初步的 尝试。 第一章引言 1 2 本文概要 为了研究并发面向对象语言模型，本文首先在第二章探讨了面向对象语言 的四种模型：基于操作的模型，基于l a m b d a 演算的模型，基于a c t o r 的模型和 基于进程演算的模型。重点考察了这四种模型的基本情况，特别是从消息机制 看待各种模型。随后在第三章，本文介绍了p i 演算和a c t o r 模型的基本情况， 为后面的研究做了铺垫。需要注意的是本文对p i 演算的语法做了调整。本文的 重点是对异步p i 演算扩充以a c t o r 机制而得到了a c t o r 对象演算a o c ，给 出了该演算的语法和语义，并且通过它的使用探讨了a o c 演算的特性，这是第 四章的内容。在第五章，本文给出了对象语言o l ，并用a o c 演算描述了o l 语言+ 的语义。最后一章是对本文的总结和对将来可能的研究的几点考虑。 第二章面向对象语言模型及其讨论 第二章面向对象语言模型及其讨论 在研究程序设计语言州，通常我们需要利用各利，不同的模型。比如，在研 究程序设计语言的语义时，人们可以利刖抽象机研究语言的操作语义，利用函 数变换研究语言的指称语义，利用各种逻辑形式研究语言的公理语义。这就是 说，在研究语言语义的时候，人们必须基于一定的形式模型，而模型可以比较 抽象如函数变换，也可以比较具体如抽象机模型。同样，在描述面向对象语言 语义特性时也存在各种各样的方法。 2 1 基于操作的模型 基于操作的模型是描述语言语义最常用的，当然也可以用来描述面向对象 语言。具体来说，在描述和实现面向对象语言时，为了弄明白面向对象语言程 序运行的基本过程，人们可以按照程序在实现时的可能的执行方式描述面向对 象语言的执行过程，这是面向对象语吉规范常采用的方式。 面向对象语吉程序中有各种各样的对象，其中的对象是封装数据和操作的 实体。对象之间可以相互发消息，收到消息时，对象可以响应消息。在响应消 息时，对象可以修改自己的数据，或者向其它对象发送消息。通常，对象可被 按类分组，每个对象属于特定的类，类可以按层次组织，由此出现了类的继承。 在基于操作的面向对象语言模型中，人们常依据使用命令语言时所形成的 习惯，将消息发送理解为过程或函数调用，对象为响应消息而执行动作的过程 被理解为被调用函数的执行。理解基于操作的面向对象语言模型的关键是弄清 楚对象如何响应消息。 假设考虑单继承情形。当对象响应消息时，系统会根据消息选择符和参数 在当前对象的类中查找匹配的方法，如果查找到了，对象就会执行相应的方法 体。如果在当前对象的类中未查找到匹配的方法，且该类有父类，系统就会到 其父类中去查找待匹配的方法；如果该类没有父类，就表明查找失败。这一过 程可能会直进行，或者查找到匹配的方法执行对应的方法体，或者不再有父 类，这表明查找失败。在执行方法体时，通常方法体持有接收消息的对象的引 第二章面向对象语言模型及其讨论 用。 + 基于操作的模型容易为人所理解，因此许多人借此描述面向对象语言语义。 尽管w o l c z k o 使用指称语义方法给出了基于s m a l l t a l k 语法特征的面向对象语 言的语义，但实际上他使用的还是基于操作的模型1 ”。 在使用基于操作的模型描述面向对象语言语义时，关键是要处理好继承问 题，瞿裕忠等人就是以w o l c z k o 的方法为基础，针对e i f f e 语言继承的特殊情 况，给出了e i f f e l 语言片断的语义”1 。 诚然，基于操作的模型容易为人理解，并被广泛用于面向对象语言和语义 的描述，但是这种模型没有把消息发送和消息处理当作基本操作，而把它们理 解为函数调用和被调用。 2 2 基于l m b d a 演算的模型 实际上，l a m b d a 演算可以被看作最早的程序设计语言，而且人们实际使用 的最早程序设计语言之一的l i s p 就是以l a m b d a 演算为基础设计的。l i s p 也是 第一个函数语言。 人们很早就以l a m b d a 演算为基础来研究程序设计语言了。l a n d i n 在1 9 6 4 年发表的“表达式的机械化处理”一文就是以l a m b d a 演算为基础研究的“，而 且因此奠定了程序语义研究的基础，后来，l a m b d a 演算就成为研究程序语义不 可或缺的形式模型。 在二十世纪八十年代，人们研究了l i s p 语言的各种面向对象特性的扩展， 最后集众家之长，形成了c o m m o nl i s po b j e c ts y s t e m “”。与此同时。人们也 利用l a m b d a 演算的各种形式的扩展来研究面向对象语言的各种语言特性。前面 本文已经提到l u c ac a r d e l l i 和p e t e rw a g n e r 在这方面进行了开创性的工作。 用l a m b d a 演算为基础研究面向对象语言的工作主要是以对类型化l a m b d a 演算”1 进行各种各样的扩展来进行的，借此来解释面向对象语言的各种特性， 如类、对象、方法、封装、消息传递、予类型、基于类的继承、委托、多继承 等等。尽管用类型化l a m b d a 演算的扩展可以解释面向对象语言的不少特性，但 是很多人认为，基于l a m b d a 演算的模型不适于构造面向对象语占的模型。 因为，l a m b d a 演算只有两个基本概念，即函数抽象和函数施用。在l a m b d a 演算中，函数是第一类的，运算是通过函数施用实现的。然而，在面向对象语 占中，对象应该是第一类的，消息传递是唯一的控制结构，并且应该是基本的。 于是，针对这些问题，人们提出了一些可以容纳l a m b d a 演算的新的模型汹1 。 第_ 二章面向对象i ； 言模型及其讨论 2 3 基于a c t o r 的模型 c a r lh e w i t t 在其具有开创意义的“将控制结构看作消息传递模式”文 中第一次提出了a c t o r 模型。然而，现在人们所说的a c t o r 模型是由g u la g h a 描述的”1 。 在a c t o r 模型中有一组称作a c t o r 的对象，它们相互之间可以进行异步消 息发送，每个a c t o r 发送消息后不必等待回答，可以立即处理下一个消息。当 一个a c t o r 收到消息时。至少可以执行三个基本动作：发送消息，创建新的a c t o r 和改变自己的状态和行为。由于该模型基于异步消息处理机制，所以a c t o r 模 型非常适于描述分布式并发系统的程序执行。 2 4 基于进程演算的模型 进程演算是并发系统模型，用于描述和推理并发系统的特性，其中最著名 的是c a r h o a r e 的c s p ( c o m m u n i c a t i n gs e q u e n t i a lp r o c e s s e s ) ”，r o b i n m i l n e r 的c c s ( c a l c u l u so fc o m m u n i c a t i n gs y s t e m s ) 和p i 演算( 移动进程 演算) “9 儿蛐1 。 由于进程演算也是基于消息发送机制的，所以在研究面向对象语言语义时， 人们自然想到进程演算。v a nn g u y e n 和b r e n th a i l p e r n 以c s p 为参考提出了 通用对象模型，以此为基础实现了面向对象环境“。但是，他们的面向对象环 境是顺序的，而参考模型却是并发的。尽管如此，这却给其他研究者以启示。 确实有一些人以进程演算为基础研究基于对象的程序设计语言的语义，如 o s c a rn i e r s t r a s z 分别以c c s 和p i 演算为基础设计了a b a c u s 。2 3 和o c 。”。特别 是o c 集成了p i 演算中的进程概念和l a m b d a 演算中的函数概念，可以被看作 p i 演算和l a m b d a 演算的统。 实际上，f 如m i l n e t 自己曾经提到的，p i 演算本身的发展曾经受到h e w i t t 的a c t o r 模型的启发，这说明两者之问有一定渊源。两者都是基于消息传递机 制，但是，在结合两种模型时我们应注意它们的异同。 2 5 面向对象语言模型讨论 前面一共提到了四种基本模型，即基于操作的模型，基于l a m b d a 演算的模 型，基于a c t o r 的模型和基于进程演算的模型。前两个模型可用于研究顺序面 第二章面向对象语言模型及其讨论 向对象语言，而基于操作的、基于a c t o r 的和基于进程演算的模型可用于研究 并发面向对象语言。由此可见，基于操作的模型适用面最广，主要原因是基于 操作的模型容易被人理解、便于在计算机上实现。基于l a m b d a 演算的模型是人 们自然想到的模型，因为l a m b d a 演算是计算机语言的基础，并且类型化l a m b d a 演算的理论为研究面向对象语言中所出现类的概念提供了很好的起点。尽管基 于操作的模型和基于l a m b d a 演算的模型被广泛应用和研究并且取得了丰硕成 果，但是在两个模型中消息都不被当作基本的机制。在基于操作的模型，消息 机制被理解为函数调用与被调用；在基于l a m b d a 演算的模型，消息机制被理解 为函数施用。因此这两种模型都不能反映对象的本质。 s m a l l t a l k 创始人a l a nk a y 曾经提出面向对象程序设计三定律1 7 】： 一切皆对象； 对象通过消息收发相互通信； 对象有自己的存储。 就是说，消息机制应该是基本的。a c t o r 模型和进程演算也都是基于消息机制的。 那么我们是否可以将两种模型结合来? 这是我们下面将要考虑的问题。因为本 文考虑的是a c t o r 模型和p i 演算的结合，所以我们需要考察两种模型的基本情 况。 第三章，f ：发模型 第三章并发模型 本章将介绍的是两种并发模型，因此我们首先需要了解一下并发、并行、 分布和不确定等几个相关概念。 并发性是指一个系统内部发生的两个事件之间没有先后关系或者指一 个系统内部发生的两个事件的先后次序不确定。 与并发性不同，并行性是指一个程序的几个分量在某一时间段内可以相 对独立地运行，并且通常这种并行运行有一种特定的含义，即各并行分量共享 一片存储区域。 分布性是指一个程序的几个分量在某一时间段内可以相对独立地运行， 并且通常也有特定的含义，即各分布分量之间的协同工作不是通过共享存储， 而是通过交换信息实现的。 不确定性是指一个程序的运行可能会有两种或两种以上的方式，其结果 可能一样，也可能不一样。 并发性、并行性和分和性都是造成不确定性的根源，因此人们提出了各种 模型来研究它们。 3 1 p i 演算 p i 演算是基于命名概念的并发计算模型，由r o b i nm i l n e r 等人在进程演 算c c s 基础上提出的。”。在p i 演算中，最基本的实体是名字主体或进程由名 字构造出来的。 从1 9 8 9 年p i 演算被提出至今，人们已经做了大量工作，取得了丰硕成果。 不仅出现了众多形式的p i 演算。而且有各种语义和代数理论，更重要的是人们 可以用p i 演算编码l a m b d a 演算、值和一些数据结构，这体现了p i 演算的价值。 下面给出基本p i 演算和语义，然后介绍两个变种。 第三章并发模型 3 1 1 p i 演算基本定义 1 p i 演算语法 首先，假定一个名字的集合m 小写英文字母在其上取值，必要时可以带 上下标，这罩名字可以用作端口、变量和常量等等。同时，假定有一个主体标 识符集a ，大写英文字母在其上取值，必要时也可以带上下标，主体标识符可 以带有非负元数，主体本身可以由名字通过一定的组合方式构成。下面给出p i 演算的语法： 进程p ：= n i l无活动 ix l y p输出 lx ? y p 输入 in p沉默 i p i ，p 2并行 ip i + p 2和 i i f x = = y t h e n p 匹配 f x v t h e np不匹配 i l x l e 限制 1a ( y l ，y 。)标识符 标以符定义 a ( x l ，x n ) ：= p ( 这里x i ，x 。两两不同) 2 p i 演算语法解释 由于研究目的不同，本文对p i 演算的语法形式和符号略做调整，下面给出 语法的具体解释。 ( 1 ) 无活动n i l 在p i 演算中对应的符号形式为0 。n i l 表示无活动进程或主体， 即一个不执行任何动作的进程或主体。 ( 2 ) 输出x ! y p 在p i 演算中对应的符号形式为覃y p 。x ! y p 表示进程向名字 x 发送名字y ，然后进程继续如进程p 一样行动。在x ! y p 中，x 被看作是一个 输出端口，或者说是数据发送的目标；y 被看作是发送到目标x 的数据。 ( 3 ) 输入x ? y p 在p i 演算中对应的符号形式为x ( y ) p 。x ? y p 表示进程沿 名字x 接收任意一个名字a ，然后将p 中的特定位置的y 替换为a ，然后进程继 续如被替名后的进程p 一样行动。在x ? y p 中，x 被看作是个输入端口，或 者说是数据可被发送的目标；y 被看作是接收的名字的占位符，在输入完成后， y 被接收到的名字替换。因此可以看出，在这里y 的名字并不太重要，比如可 9 第二章j t 发模型 以被如z 等其它名字所替代。 ( 4 ) 沉默n p 在p i 演算中对应的符号形式为r po n p 表示进程不与环境交互， 而可以自动演化到p 。n p 可以被认为在执行不与外界交互的一些动作。 通常，x ! y p 、x ? y p 和n p 被称作前缀形式，其中x l y 、x ? y 和n 分别被称作 输出前缀、输入前缀和沉默前缀。常用q ，b 等小写希腊字母表示前缀集合中 的元素。 ( 5 ) 并行p l ，p 2 在p i 演算中对应的符号形式为p l i p 2 。p l ，p z 表示进程由两个 并行的进程p i 和p 2 构成。成分进程p l 和p 2 可以独立执行，也可以相互通信。 并行p l ，p 2 的进程间通信需要p l 和p 2 中一个执行输入一个执行输出，并且沿着 相同的名字。 ( 6 ) 和p l + p 2 与p i 演算中的对应符号一致。p i + p 2 表示一个或者象p l 行动或 者象p 2 行动的进程。通常表示一种行为上的选择。 ( 7 ) 匹配i fx = = yt h e np 在p i 演算中对应的符号形式有i fx = yt h e np 、 【x = y p 等。i f x = = yt h e np 表示，如果x 和y 同名则行为将象p ，否则什么都不 做。 ( 8 ) 不匹配i f x y t h e np 在p i 演算中对应的符号形式为if x yt h e n p 。 i fx yt h e np 表示，如果x 和y 不同名则行为将象p ，否则什么都不做。并不 是所有版本的p i 演算中都有匹配和不匹配形式，而且有些版本只有匹配形式。 需要注意的是x = = y 和x y 只表示名字的异同。 ( 9 ) 5 1 $ j i x i p 在p i 演算中对应的符号形式有( v x ) p 、( x ) p 等形式。h p 表示 进程象p ，但x 是局部的。x 不能立即作为外部输入输出端口，但是可以作为p 内部的输入输出端口。x l 卜f x 。i p 表示对p 的多个名字的限制，可以缩写为 i x l ，x nl p 或i x l x n i p 。 ( 1 0 ) 标识符a ( y l ，y 。) 与p i 演算演算中的对应符号一致。每个标识符必须 有定义a ( x i ，x 。) ：= p ( 其中“h ，x n 两两不同) ，n 是a 的元数，这里“：= ”是 定义符号。a ( y l ，y 。) 表示p 中x i ，x 。被卒卒换后的结果。所以，定义a ( x i i ，x 。) ：= p 可被看作进程声明，。l ，x 。可被看作形参，a ( y l ，y 。) 可被看作实参为y l ，y 。 的调用。需要注意的是，这罩形参中的名字是被实参中名字完全替换，形参中 的名字只起占位符的作用。 3 说明和约定 为方便使用，这里还需给出几点说明和约定。 ( 1 ) 主体x ? y n i l 和x l y n i l 后的n i l 可以省略变成x t y 和x l y ，在后面本文会 根据上下文条件使用不同形式。如果不需要输入x ? y p 和输出x ! y p 中y ，这时 0 第二章_ _ f 1 发模型 两者可以记作x 7 p 和x ! p ，表示输入和输出不需要携带参数。 ( 2 ) 在输入形式x ? y p 和限制i y i p 中，p 中的y 是受到约束的，类似于程序 中的形式参数和局部变量。在p 中的y 可以换为某些其它名字，比如z ，则x ? z p 和i z i p 和原来的形式含义相同。象y 这样的名字被称作约束名，而其它的名字 被称作自由名。主体p 的所有约束名被记为b n ( p ) ，所有自由名被记为f n ( p 1 ， 则b n ( p ) uf n ( p ) 表示p 的所有名字，可以记为n ( p ) 。p i 演算语法中各式的b n ( p ) 和f n ( p ) 的求法如表3 1 。 进程或主体约束名b n自由名f n n 订oo x ! y pb n ( p ) x ，y uf n ( p ) x ? y p y u b n ( p ) x ) u ( f n ( p ) - y ” p b n ( p )f n ( p ) p l ，p 2b n ( p 1 ) u ( p 2 )f n ( p i ) uf n ( p 2 ) p l + p 2b n ( v 1 ) u ( p 2 )f n ( p 1 ) uf n ( p 2 ) i f x 一- yt h e npb n c p )b n ( p ) i f x y t h e n ph n ( p )b n ( p ) l x p( x u b n ( p )f h ( p ) - ( x 表3 1 进程或主体的约束名b n 和自由名f n 的求法 ( 3 ) a ( y j ，y 。) 的约束名和自由名由a 的定义决定且在定义a ( x l ，x 。) ：= p 中 要求f n ( p ) c “l ，x 。) 。 ( 4 ) 在拙述输入的缀和标识符时，名字的替换常被提到，因此有必要明确替 换的含义。替换是名字到名字的函数，名字x 到名字y 的替换表示为 y x 。对 主体p 的作用表示为p y x ) ，意思是将p 中的自由名x 换作y ，而其它自由名 保持不变。名字集x i ，x 。到名字集y l ，y 。的同时替换表示为 y l i ，y 。x i ，x 。) ， 要求x i ， x n 两两不同。对主体p 的作用表示为p y l ，y n x i ，x 。) ，意思是将p 中的自由名x i ，x 。换作y t ，y 。，而其它自由名保持不变。 ( 5 ) 为便于书写，本文指定了语法形式的优先次序。前缀、限制、匹配和 不匹配的优先级最高，并行的优先级次之，和的优先级最低，在必要时可以使 用圆括号。 第三章并发模型 3 1 2 p i 演算语义 了解了p i 演算的语法后，接下来给出p i 演算的操作语义。p i 演算的操作 语义可以有各种不同形式，这里采用的方法是先给出p i 演算的结构同余规则， 然后给出操作语义。 1 结构同余 引入结构同余规则的目的是，用结构同余规则可以确定直觉上代表同一功 能的主体。具体说就是，语法结构满足结构同余规则的两个主体被认为是一致 的。利用结构同余规则描述p i 演算语义比较方便。 本文给出的p i 演算的结构同余“s ”是满足如下定律的最小同余： ( 1 ) 如果p 和q 可以相互a l p h a 转换( a l p h a 转换的意思是指p 中约束名可 被换名变为q 或相反) ，则p - = q 。 ( 2 ) 并行满足：交换律p ，q _ - - q ，p ，结合律( p ，q ) r - - p , ( q ，r ) ，并有单位 元p n i l ；p 。 ( 3 ) 和满足：交换律p + q - q + p ，结合律( p + q ) 十r - - - - p + ( q + r ) ，并 有单位元p + n i l = p 。 ( 4 ) 展丌律：如果a ( x l ，x 。) ：= p ，则a ( y l ，y n ) i p y l ，y 。x t ，x n ) 。 ( 5 ) 作用域扩展律： l x n i l ；- n i l i x l ( p , q ) ；p ，i xj q如果x 不属于f n ( p ) x l ( p + q ) - p + i x l q如果x 不属于f n ( p ) l x l ( i f u vt h e np ) i f u = = vt h e ni x l p如果x u 且x o v i x l ( i f u vt h e np ) i i f u o v t h e ni x l p如果x o u 且x v l x l l y l p - = l y l l x l p 根据结构同余规则1 ，a ? x b ! x 和a ? y b ! y 一致。 结构同余规则2 和3 说明并行与和是无序的，因此p q 和q ，p 的意义一致， p ，q ，r 和r ，p ，q 一致，这里次序并不重要。p ，n i l = p 和p + n i l = p 说明n i l 对 并行和组合无任何贡献。 展丌律说明标识符只是标识符定义被用适当参数具体化后的结果。 限制ix l p 的直觉含义是，x 是p 中名字，限定了p 中某些x 的作用范围， 有点儿类似于程序语言的作用域的功能。作用域扩展律的功能是限制l x i 可以放 置于其有效范围内的任何位置，并且限制的次序并不重要。因为n i l 中不含有任 何名字，所以 x n i l n i l 的含义很明确。 第三章并发模型 2 语义 以结构同余规则为基础，接下来可以给出p i 演算操作语义。在给出语义之 前还需要引入两种动作，我们称之为约束输出和自由输入。引入两种动作的目 的是为了定义相关语义规则。 约束输出的形式为x ! l y l p 表示l y l x ! y p ，意思是指y 代表的局部名被沿着x 传递出去，将y 的限制范围扩展到了接收者。例如x ? z q ，1 y l x ! y p 中，右侧的y 的作用域可以扩展到左侧。 语义规则中还引入了一种被称作自由输入的、只用在语义规则中的输入动 作形式x z 。它和普通的输入x ? y 的差别是。普通输入x ? y 的含义是，沿着y 输 入某个名字然后用它替换其后的进程中的y ；而自由输入x z 的含义是，某个进 程接收到一个名字然后变成另外一个进程。 下面是p i 演算的操作语义： q t d p f _ p ，p 与q ，q 兰q u c ts t r 二兰尘2 芝二兰 p 山q i n p u t p r e f i x p a r s u m m a t c h m i s m a l c h 0 p e n c o m r e s 在语义规则中，横线 x ? y 尸三_ 寸p z y 1 a p 兰+ p虾是x ? y 羔坝a ) n f n ( q ) ：。 一d 州a l n = 妇 p ，o 山p ，q 。7 p! 、p p + q j l p | 户生p i f x x t h e n p 与p i 户o p 。 i f x y t h e n p 与p x y 尸二生d 两正五荔“叫 ! 苎! ! ! 望当望： | p ，q jj d ，q 百# 黑y 酬口) 丽瓦二币驴y 鲫刚 的上面是前提，下面是结果，右侧是附加条件。如果 第二章升发模型 横线上没有内容则表示该舰则不需要前提。其中，规则i n p u t 的含义是x ? y p 接收名字z ，然后继续，行为象p z y 。 3 实例 例3 1 ：由规则1 n p u t 得y ! x p 坐_ p ， 由规则p r e f i x 得y ? z q 旦斗q x z ) 再由规则c o m 和结构同余，可得 y ! x p ，y ? z q ，r jp ，q x z ，r 本文以后不再象例1 一样给出步骤的详细说明。当使用结构同余规则推导 时，写“；”：当使用操作语义规则推导时，则写“”。 例3 2 ：y ! x p ，r ，i x l ( y ? z q 。，s ) 5 y ! x p ，r ，i x i i ( y ? z q x y x ) ，s x x ) 5 i x t l ( y ! x p ，r ，y ? z q x x ，s x x ) 斗i x i ( p 。，r ，q x x x z ，s x x ) ( 这罩x i 是新名字) 例3 3 ：1 x l ( y ! x p ，r ) ，y ? z q f xp i ( y ! x p x x ，r x x ) ，y ? z q 5k i ( y ! x 。p x l x ，r x x ，y ? z q ) 斗i x i i ( p x x ，r x x ，q x l z ) 3 1 3 多元p i 演算 当我们使用p i 演算时，可能想一次输入输出多个名字，这时可能认为应该 采用的形式是x ? y 1 x t y 。p 和x ! a 1 x ! a 。q ，但这不能保证消息的正确传递与 接收。正确的解决方案是 x ? ( y l y n ) 。p含义是x ? z z ? y i z ? y 。p x ! a l x ! a 。q含义是i z l ( x ! z z ! a l z ! a n ) q 可以验证上面的方式能使消息j 下确地传递与接收。 随后，人们不再把这仅仅当作缩写而在p j 演算中直接引用，由此得到了多 元p i 演算，而前面所讲的p i 演算，通常被称作一元p i 演算。 多元p i 演算的引入使p i 演算的表达能力更强，产生了许多有趣的结果， 也产生了许多问题【1 9 】。 第- 三章”发模型 3 1 4 异步p i 演算 前面提到的一元和多元p i 演算都是同步p i 演算。所谓同步是指消息发送 方和消息接收方必须以握手方式交流信息，如x ? y p ，x ! z q 中的x ? y p 接收到 z 后才能继续演化，x ! z q 的z 被接收到后才能继续演化。这种情况使得不便于 表达可能存在消息传递时间延迟的问题，如分布式环境下的消息传递问题。 为解决上面的问题，g 6 r a r db o u d o l l 8 1 和k o h e ih o n d a 15 】率先对异步p i 演算 进行了深入研究。经过研究人们还发现，普通p i 演算的一个子演算就可以表示 异步p i 演算。该子演算满足如下要求： 只有n i l 才可以跟在输出前缀后面，即不允许x ! y x ! z 而允许x ! y n i l 或 x ! y 。 输出前缀不可以以“+ ”的无卫士操作数的形式出现，即不允许x ! a + y ? z ， 而允许“x ! a + y ? z 。 用x ! y 可以表示一条被发送但还未被接受的消息。因为上面的第一个要求， 一条已被接受的消息不会被消息的发送者发觉，除非消息的接收者明确向消息 的发送者发送应答。因为上面的第二个要求，一条消息不会消失，除非它被一 个进程接收。 例3 4 ：( 1 ) “( x t y , p ) 表示一个发送消息x t y 并且象p 一样行动的进程 ( 2 ) f y l ( x ! y , y ? z p ) ，x ? z q 5 i y l ( x ! y , y ? z p ，x ? z q ) 。 _ i y i ( y ? z p q y z ) 前面我们看到，在同步条件下，多元消息可被看作一元演算的一种编码形 式。同样，在异步条件下，多元消息也可被看作一元演算的一种编码形式1 1 5 l 。 3 2 a c t o r 模型 a c t o r 模型是开放分布式系统的模型。丌放分布式系统的主要特征是，允 许增加新组件、替换存在的组件、改变组件间的相互联系，但在多数情况下， 系统的功能不会被破坏。这些特征体现了开放分布式系统的功能要求，即在系 统中，每一组件都应是独立的实体，不应对与之相关的其它组件进行直接控制。 为让外部组件使用其功能，每个组件可以向外公歼自己的功能接口，外部组件 只能通过这个接口访问该组件，组件的内部状态会因为功能接口中的操作的执 行而改变。 第三章并发模型 l2 nn + 1 邮件队列 l 悱删蚺少 。 ，滕消息、创建慨。， 发送种 、。一 69 邮件队列 图3 1a c t o r 系统计算示意图 在a c t o r 模型中有各利咯样的对象( 在a c t o r 模型中，对象被称作a c t o r ) ， 这些对象