计算机类职称论文：应用Pi演算
Pi演算起源于上世纪80年代，由图灵奖得住Robin Milner提出。它是一种描述和分析并发系统的演算模型，是用演算中的归约表示由进程间的相互通信形成的动态演化。以下是学习啦小编今天为大家精心准备的计算机类相关职称论文：应用Pi的演算。内容仅供阅读与参考!
应用Pi演算全文如下：
学习啦在线学习网 由于Internet与移动通信的快速发展和安全通信的需求，出现了适应种种形式分析目的的一大类应用π-演算(Application π-Calculus)[ ];本文从π-演算出发，对其进行严格的讨论与介绍。
1、基本π-演算与异步π-演算的语法(Synta_)
1.1 名字与进程
学习啦在线学习网 设Χ = {_, y, z, . .} 是名字(names)集(可将名字看作是通信中的通道channels of communication)，??_，
归纳定义(基本)?演算的进程(processes)如下(其中//…为帮助理解的直观说明)：
P:: = 0 //空进程
| P|Q //并发(并行)进程
| !P //复制进程(无穷多次)
学习啦在线学习网 | _.P //在通道_上发送y(输出)后执行进程P
| _(y).P //将从通道_上接收的名字赋给y后执行进程P
| ν_.P //将名字_限制到进程P中使用，P的私有名字
学习啦在线学习网 为减少括号使用，约定：
对于“|”，用左结合，例如“P|Q|R”表示“(P|Q)|R”;
对于_(y).P、_.P与?_.P，称_(y)、_或?_为P的前缀，P称为前缀的体(body)，为减少括号使用，约定前缀的体向右最大扩展，例如：
学习啦在线学习网 vz._._._._.P表示vz..(_.(_.(_.(_.P))))
学习啦在线学习网 1.2 自由与约束的名字
学习啦在线学习网 设P、Q为进程，归纳定义名字集合fn(P)如下：
fn(0) = ?; //空进程无自由名字
fn(P|Q) = fn(P) ? fn(Q);
fn(!P) = fn(P);
fn(_.P) = {_,y}?fn(P); //对于输出，_,y是自由名字
fn(_(y).P) = {_} ? (fn(P)-{y}); //对于输入，_是自由名字，y不是自由名字
学习啦在线学习网 fn(v_.P) = fn(P)-{_} //对于限制，_不是自由名字
学习啦在线学习网 称fn(P)为进程P的自由名字集，若_?fn(P)，称名字_在进程P中是自由的;如果进程P中的名字_不是自由名字，则称为约束名字，用bn(P)表示P的约束名字集，记nP=fn(P) ? bn(P)并称为P的名字集;对a(_).P或(?_).P，将在P中自由出现的_称为被a(_)或(?_)约束的名字;注意，有P，使fn(P)?bn(P) ? ?，即某个名字_可能同时在P中自由出现与约束出现.
例：在进程
a?_?.P | a(y).Q | (?_)a?_?.R
里，_既自由出现，也约束出现。
例：进程
a?_?.(_?b?.P | _?c?.R)
中的(_?b?.P | _?c?.R)里两处_均被a(_)约束，是a(_)的约束名字，而
a?_?.(_?b?.P | (?_)a?_?.R)
中的(?_)a?_?.R里的_不被a(_)约束，不是a(_)的约束名字。
定义：
1 称名字w对进程P是新鲜(fresh)的，若w ? nP;
学习啦在线学习网 2 自由名字的代入：对任何进程P，进程P[z/_]是将P里每个自由出现的_改为z而得的进程，称为在进程P里对自由名字进行代入。
学习啦在线学习网 3 约束名字的改名：(1)对进程 a(_).P的约束名字_可用z改名并将改名结果记为a(z).P[z/_]，如果z?fn(P);(2)对进程 (?_).P的约束名字_可用z改名并将改名结果记为(?z).P[z/_]，如果z?fn(P);
注意：
1 对a(_).P或(?z).P改名的结果并不导致a(_).P或(?z).P里的任何名字的自由出现变为约束出现;
2 为防止改名失败，可简单地使用新鲜名字来改名，
例：设a(_).P=a(_).(_|_(c)>)，则：可用y改名_，结果为：a(y).(y|y(c)>);但不可用b改名_为a(b).(b|b(c)>)
例：代入 (y(_).0 | a(y).y| (?z)y.0)[z/y] 的结果是z(_).0 | a(y).y|(?z)y.0或者z(_).0 | a(y).y|(
1550;w)y.0;但不可为：(z(_).0 | a(y).z|(?z)y.0)
学习啦在线学习网 ：a(y).(y|y(c)>);但不可用b改名_为a(b).(b|b(c)>)
1.2 ?-同余(?-congruence)
称P与Q是?-同余的并记为P??Q，若Q可由P的约束名字改名而得;显然，??是自反、对称与传递的关系-等价关系，
例如，下面定义的进程C1与C2是?-同余的：_
C1 = a(_).P | a(y).Q | (?z)a?z?.R
C2 = a(_).P | a(y).Q | (?w)a?w?.R
学习啦在线学习网 1.3 结构同余(structural congruence)
学习啦在线学习网 定义：对进程P,Q,R，定义结构等价关系“?”为满足下列性质的最小等价类：
SC1： 若P??Q，则P?Q，
SC2： P|0 ? P //自反
学习啦在线学习网 SC3： P|Q ? Q|P, //交换
学习啦在线学习网 SC4： P|(Q|R) ? (P|Q)|R //结合
SC5： (?_)0 ? 0，(?_)(?y)P ≡ (?y)(?_)P.
SC6： (?_)(P|Q) ≡ P|(?_)Q, 如果 _ ?fn(P)
例：如果y?fn(P)，则 (?y)P ≡ P
证明：
学习啦在线学习网 P ≡ P|0 SC2
学习啦在线学习网 ? P ≡ 0|P SC3
? P ≡ (?_)0|P SC5
学习啦在线学习网 ? P ≡ (?_)(0|P) SC6
? P ≡ (?_)P SC2
这个证明也如下描述：
P ≡ P|0 SC2
≡ 0|P SC3
学习啦在线学习网 ≡ (?_)0|P SC5
≡ (?_)(0|P) SC6
≡ (?_)P SC2
学习啦在线学习网 1.4 归约Reduction rules
定义The main reduction rule which captures the ability of processes to communicate through channels is the following:
_.P | _(z).Q → P | Q[y/z]
where Q[y/z] is the process Q www.51lunwen.com/jsjzy/ where the name y has been substituted to the namez. There are 3 more rules, one of which is
学习啦在线学习网 If P → Q then also P|E → Q|E.
It says that parallel composition does not inhibit computation. Similarly, the rule
学习啦在线学习网 If P → Q then also (ν _)P → (ν _)Q
ensures that computation can proceed underneath a restriction.
Finally we have the structural rule
学习啦在线学习网 If P ≡ P' → Q' ≡ Q, then also P → Q .
•
示例
内存单元：如下定义的进程MEM(_)描述了计算机的一个内存单元：
学习啦在线学习网 MEM(_) = out.MEM(_) + in(y).MEM(y)
The memory cell MEM can either output its contents, _ and then continue as MEM(_) (i.e. as itself), or input ano
学习啦在线学习网 ther value, y, and then continue as MEM(y), as itself but with another content
服务器：
学习啦在线学习网 服务器S传出通道a，客户接受通道a，并用这个通道传送d
学习啦在线学习网 通道是公开的情况：
b.S | b(c).c. P → S|a.P
通道是私有的情况：
(?a)(b.S | R) | b(c).c. P → (?a)(b.S | R | b(c).c. P )
学习啦在线学习网 → (?a)( S | R | a.P)
多重匹配：
学习啦在线学习网 _<8,3>|_(z1,z2).y→ y[(8,3)/(z1,z2)] = y
学习啦在线学习网 同名通道上的多个输出：
_|_|_u.y → _|y 或 _|_|_u.y → _|y
同名通道上的多个输入：
_| _u.y| _u.z → y| _u.z 或 _| _u.y| _u.z→ _u.y|z
私有名字可改名：
_|(?z)(z|zu.y) → _|(?_)(_|_u.y)
→ _|(?_)y→ _|(?n)y
_|(?_)(_|_u.y) → _|(?z)(z|zu.y)
→ _|(?n)y→ _|(?_)y
通道传送：
_|_u.u→ y
(?y)(_|yv.P)|_u.u→ (?y)(yv.P)|y→ (?y)P[7/v]
(?y)(_|yv.P)|_u.u? (?y)(_|yv.P|_u.u) → (?y)(yv.P|y) → (?y)P[7/v]
a(_).P | a(y).Q | (?z)a?z?.R → (?w) (P[w/_] | R[w/z]) | a(y).Q (w是新鲜fresh的)
a(_).P | a(y).Q | (?z)a?z?.R → (?w) (Q[w/_] | R[w/z]) | a(_).P (w是新鲜fresh的)
2、应用?演算
可以引入一类新的特殊的名字?，表示进程内的不与其它学习啦在线学习网进程交互的事件，并在进程定义中增加：?.P
学习啦在线学习网 A sum (P + Q) can be added to the synta_. It behaves like a nondeterministic choice betweenP and Q.
学习啦在线学习网 A test for name equality (if _=y then P else Q) can be added to the synta_. Similarly, one may addname inequality.
The asynchronous π-calculus allows only _.0, not _.P.
学习啦在线学习网 The polyadic π-calculus allows communicating more than one name in a single action:_.P and _(y1,y2,...).P. It can be simulated in the monadic calculus by passing the name of aprivate channel though which the multiple arguments are then passed in sequence.
Replication !P is not usually needed for arbitrary processes P. One can replace !P withreplicated or lazy input !_(y).P without loss of e_pressive power. The correspondingreduction rule is
_.P | !_(z).Q → P | !_(z).Q | Q[y/z].
学习啦在线学习网 Processes like !_(y).P can be understood as servers, waiting on channel _ to be invoked by clients.Invokation of a server spawns a new copy of the process P[a/y], where a is the name passed by the client to the server,during the latter's invokation.
学习啦在线学习网 A higher order π-calculus can be defined where not names but processes are sent through channels. Thekey reduction rule for the higher order case is
_.P | _(v).Q → P | Q[R/v].
学习啦在线学习网 In this case, the process _.P sends the process R to _(v).Q. Sangiorgi established the surprisingresult that the ability to pass processes does not increase the e_pressivity of the π-calculus: passing a process Pcan be simulated by just passing a name that points to P instead.
Properties
学习啦在线学习网 Turing completeness
学习啦在线学习网 Bisimulations
See also
• Calculus of CommunicatingSystems
• Communicating seque
学习啦在线学习网 ntialprocesses
学习啦在线学习网 • Calculus of BroadcastingSystems
• Ambient calculus
学习啦在线学习网 • Join calculus
学习啦在线学习网 References
• Robin Milner : Communicating and Mobile Systems: thePi-Calculus, Springer Verlag, ISBN0521658691
• Davide Sangiorgi and David Walker: The Pi-calculus: A Theory of Mobile Processes, Cambridge University Press, ISBN 0521781779
学习啦在线学习网 E_ternal links
• Citations from CiteSeer
• PiCalculus on the C2 wiki
ip calculus, name, pi calcuus, free, pi caculus, rule, pic alculus, one, picalculus, channel, i calculus, binds, pi clculus, turing, pi claculus, passing, pi calculsu, model, p calculus, added, pi alculus, sangiorgi, p icalculus, active, pi aclculus, input, pi calculu, concurrently, pi caclulus, defined, pi calculs, structural, pi caluclus, channels, , passed, pi calcluus, simulated, pi calulus, invokation, pi calclus, case, pi calcuuls, walker
1._ 解释：
学习啦在线学习网 • _(y).P, which binds the name y in P, means "input some name – call it y – onthe channel named _";
学习啦在线学习网 • _.P, which binds the name y in P, means "output the name y on the channel named_";
• P|Q, means that the processes P and Q are concurrently active (this is the constructionwhich really gives the power to model concurrency to the π-calculus);
• ν_.P, which binds the name _ in P, means that the usage of _ is "restricted" to theprocess P;
• !P means that there are infinitely many processes P concurrently active (this construction might not bepresent in the definition of the π-calculus but it is needed for the π-calculus to be turing complete ), formally !P → P |!P;
学习啦在线学习网 • 0 is the null process which cannot do anything. Its purpose is to serve as basis upon which one builds otherprocesses.
•通信通道-(参考：01 lecture21-pi.ppt)
学习啦在线学习网 Speaker = air
Phone = air(_).wire //电缆
ATT = wire(_).fiber //光纤
System = Speaker | Phone | ATT
进程间的通信导致归约(reduction):
学习啦在线学习网 Speaker | Phone ? wire
wire| ATT ? fiberComposing these reductions we get:
Speaker | Phone | ATT ? fiber
学习啦在线学习网 无限制通道是可视的，Anybody can monitor an unrestricted channel:Consider that we define
WireTap = wire(_).wire.NSA
–Copies the messages from the wire to NSA
–Possible since the name “wire” is globally visible
不难看出：
WireTap | wire| ATT ? wire.NSA| ATT
学习啦在线学习网 ? NSA| fiber
OOPS !
•The restriction operator “(?c) p” makes a f
学习啦在线学习网 resh channel c within process p.
学习啦在线学习网 – ? is the Greek letter “nu”–The name “c” is local (bound) in p
学习啦在线学习网 •Restricted channels cannot be monitored.
wire(_) … | (? wire)(wire| ATT) ! wire(_) … | fiber
学习啦在线学习网 •The scope of the name “wire” is restricted
学习啦在线学习网 •There is no conflict with the global “wire”•Restriction
学习啦在线学习网 –is a binding construct (like ?, 8, 9, ...)
学习啦在线学习网 –is le_ically scoped
–allocates a new object (a channel)
(?c)p is like “let c = new Channel() in p”••In particular, c can be sent outside its scope.
–But only if “p” decides so
–Communicating Sequential Processes (CSP) (Hoare, 1978)
学习啦在线学习网 –Calculus of Communicating Systems (CCS) (Milner, 1980)
–The Pi calculus (Milner, 1989 and others)
[15] R. Milner, A calculus of communicating systems, Lecture Notes in Computer Science, vol. 92, Springer, Berlin, 1980.
[16] Milner, R., www.51lunwen.com/jsjzy/ Communication and Concurrency, Prentice Hall, 1989
[AG97] Martin Abadi and Andrew D. Gordon. A calculus for cryptographic protocols: The spi calculus. In Proceedings of the Fourth ACM Conference on Computer and Communications Security, Zurich, pages 36{47. ACM Press, April 1997。
计算机类职称论文：应用Pi演算
