计算机类职称论文：应用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。
