对π演算（Pi演算）理解的常见错误 

                                郝克刚 2011.6.14.

 

随着为蓬勃发展的软件技术奠定坚实科学基础的需求与日俱增，目前业界学习和研究π演算模型的人也愈来愈多。在我最近审阅有关π演算的稿件中，发现一些常见的错误。我把它综合列举如下，放在博客上，同大家共享。

 

1．要读经典原著。

目前业界有些人有个不好的做法，就是在自己的文章中，按照自己的理解来定义π 演算，结果五花八门，令人无可适从，而且常有错误，使谬误流传。最好的方法就是读经典原著和引用原著的原始定义。如π 演算的创始人Milner的原著： Milner R. Communicating and mobile systems : The π-calculus ，Cambridge University Press , 1999.。最近林惠民院士将此书翻译出版，Milner还专门为此中译本写了序言，对中国学者有较高的期待。我想此书的出版会对改善这种状况有很大的帮助。

 

2．不一定发表了的文章都是正确的。

最近就遇见一件事。一位作者投的稿，作为该文理论基础的（第2节）实际上依赖的是他自己曾经发表过的一篇论文。为了审稿我就找来了原文看了看。该文虽然是正式发表的，但是此文并没有经过严格的专业评审，其中有些论证和结论我认为是明显错误的，不能作为推论的基础。最后否定了此稿。

另外，我发现有些人的论文的错误，不是他们自己发明的，而是引用他人有错误的论文。所以引用他人的论文必须要仔细审定。

 

3．“۰”并不是通常意义下的顺序算子

π演算中，符号“۰”并不是通常意义下的顺序算子，而是用来连接前缀动作和后继进程的算子。前缀动作不是进程。把两个进程表达式 p,q 用“۰”连起来所形成的 p۰q并不是π演算中合法的表达式。π 演算中两个进程的顺序执行，是将p, q分别加以改造然后用并行算子“|”组合来实现的。改造的方法是使得 p完成后发一个信息（这对p有要求，并不是所有的进程都可以如此改造，如不终止的进程就不行），q执行前接受一个信息。

 

4．p+q 并不是π演算中合法的表达式。

π 演算中两个进程的和p+q只有在 p和 q都是带前缀的进程时，才是合法的表达式，一般情况下p+q并不是π演算中合法的表达式。也就是说

∑_i∈I P_i 一般不是π演算中合法的表达式。π演算的语法定义中和式中的项必须是带前缀的表达式，不是任何进程表达式P_i都可作为式中的项。正确的表达应该是

   ∑_i∈I π_i . P_i

从语义上讲，两个进程的和并不像Petri网中如果某位置中有托肯，其后继的两个转移任意之一均可执行（无条件），在π演算中进程π₁.P₁+π₂ .P₂中只有π₁（或π₂）的前缀通道匹配时（有条件）才能归约，这是不完全等同的。

 

5．π演算能不能描述系统的真并发行为

有人在同Petri网比较时认为“π演算不能描述系统的真并发行为…”，“π演算以交织语义(interleaving semantics)为基础，并发活动在π演算描述看来也是序列化的，不能很好地刻画真并发行为，可能会失去模型真正的因果性(causality information )。”其实这是一个误区。对于Petri网来说，如果执行中每次只允许一个变迁激发，它描写的也只是交叠语义，只有在允许每次激发可以是一个步，步是一组可激发的却不冲突的变迁的多重集（bag）时，才描写了真并发语义。同样的，对于π演算来说，如果归约执行中每次只允许执行一个适用的归约规则，它描写的是交叠语义，但是如果归约执行中每次允许执行一组适用但不冲突的归约规则的多重集时，他就描写了真并发语义。在这点上Petri网和π演算并无本质的区别。

  

对π演算（Pi演算）理解的常见错误.doc

 

 

转载本文请联系原作者获取授权，同时请注明本文来自郝克刚科学网博客。
链接地址：https://m.sciencenet.cn/blog-506146-455055.html

上一篇：一篇有关π演算论文的评审意见
下一篇：请玩玩我设计的魔方游戏。