計(jì)算機(jī)類職稱論文：應(yīng)用Pi演算
Pi演算起源于上世紀(jì)80年代，由圖靈獎(jiǎng)得住Robin Milner提出。它是一種描述和分析并發(fā)系統(tǒng)的演算模型，是用演算中的歸約表示由進(jìn)程間的相互通信形成的動(dòng)態(tài)演化。以下是學(xué)習(xí)啦小編今天為大家精心準(zhǔn)備的計(jì)算機(jī)類相關(guān)職稱論文：應(yīng)用Pi的演算。內(nèi)容僅供閱讀與參考!
應(yīng)用Pi演算全文如下：
由于Internet與移動(dòng)通信的快速發(fā)展和安全通信的需求，出現(xiàn)了適應(yīng)種種形式分析目的的一大類應(yīng)用π-演算(Application π-Calculus)[ ];本文從π-演算出發(fā)，對(duì)其進(jìn)行嚴(yán)格的討論與介紹。
1、基本π-演算與異步π-演算的語(yǔ)法(Synta_)
1.1 名字與進(jìn)程
設(shè)Χ = {_, y, z, . .} 是名字(names)集(可將名字看作是通信中的通道channels of communication)，??_，
歸納定義(基本)?演算的進(jìn)程(processes)如下(其中//…為幫助理解的直觀說(shuō)明)：
P:: = 0 //空進(jìn)程
| P|Q //并發(fā)(并行)進(jìn)程
| !P //復(fù)制進(jìn)程(無(wú)窮多次)
| _.P //在通道_上發(fā)送y(輸出)后執(zhí)行進(jìn)程P
| _(y).P //將從通道_上接收的名字賦給y后執(zhí)行進(jìn)程P
| ν_.P //將名字_限制到進(jìn)程P中使用，P的私有名字
為減少括號(hào)使用，約定：
對(duì)于“|”，用左結(jié)合，例如“P|Q|R”表示“(P|Q)|R”;
對(duì)于_(y).P、_.P與?_.P，稱_(y)、_或?_為P的前綴，P稱為前綴的體(body)，為減少括號(hào)使用，約定前綴的體向右最大擴(kuò)展，例如：
vz._._._._.P表示vz..(_.(_.(_.(_.P))))
1.2 自由與約束的名字
設(shè)P、Q為進(jìn)程，歸納定義名字集合fn(P)如下：
fn(0) = ?; //空進(jìn)程無(wú)自由名字
fn(P|Q) = fn(P) ? fn(Q);
fn(!P) = fn(P);
fn(_.P) = {_,y}?fn(P); //對(duì)于輸出，_,y是自由名字
fn(_(y).P) = {_} ? (fn(P)-{y}); //對(duì)于輸入，_是自由名字，y不是自由名字
fn(v_.P) = fn(P)-{_} //對(duì)于限制，_不是自由名字
稱fn(P)為進(jìn)程P的自由名字集，若_?fn(P)，稱名字_在進(jìn)程P中是自由的;如果進(jìn)程P中的名字_不是自由名字，則稱為約束名字，用bn(P)表示P的約束名字集，記nP=fn(P) ? bn(P)并稱為P的名字集;對(duì)a(_).P或(?_).P，將在P中自由出現(xiàn)的_稱為被a(_)或(?_)約束的名字;注意，有P，使fn(P)?bn(P) ? ?，即某個(gè)名字_可能同時(shí)在P中自由出現(xiàn)與約束出現(xiàn).
例：在進(jìn)程
a?_?.P | a(y).Q | (?_)a?_?.R
里，_既自由出現(xiàn)，也約束出現(xiàn)。
例：進(jìn)程
a?_?.(_?b?.P | _?c?.R)
中的(_?b?.P | _?c?.R)里兩處_均被a(_)約束，是a(_)的約束名字，而
a?_?.(_?b?.P | (?_)a?_?.R)
中的(?_)a?_?.R里的_不被a(_)約束，不是a(_)的約束名字。
定義：
1 稱名字w對(duì)進(jìn)程P是新鮮(fresh)的，若w ? nP;
2 自由名字的代入：對(duì)任何進(jìn)程P，進(jìn)程P[z/_]是將P里每個(gè)自由出現(xiàn)的_改為z而得的進(jìn)程，稱為在進(jìn)程P里對(duì)自由名字進(jìn)行代入。
3 約束名字的改名：(1)對(duì)進(jìn)程 a(_).P的約束名字_可用z改名并將改名結(jié)果記為a(z).P[z/_]，如果z?fn(P);(2)對(duì)進(jìn)程 (?_).P的約束名字_可用z改名并將改名結(jié)果記為(?z).P[z/_]，如果z?fn(P);
注意：
1 對(duì)a(_).P或(?z).P改名的結(jié)果并不導(dǎo)致a(_).P或(?z).P里的任何名字的自由出現(xiàn)變?yōu)榧s束出現(xiàn);
2 為防止改名失敗，可簡(jiǎn)單地使用新鮮名字來(lái)改名，
例：設(shè)a(_).P=a(_).(_|_(c)>)，則：可用y改名_，結(jié)果為：a(y).(y|y(c)>);但不可用b改名_為a(b).(b|b(c)>)
例：代入 (y(_).0 | a(y).y| (?z)y.0)[z/y] 的結(jié)果是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)
?。篴(y).(y|y(c)>);但不可用b改名_為a(b).(b|b(c)>)
1.2 ?-同余(?-congruence)
稱P與Q是?-同余的并記為P??Q，若Q可由P的約束名字改名而得;顯然，??是自反、對(duì)稱與傳遞的關(guān)系-等價(jià)關(guān)系，
例如，下面定義的進(jìn)程C1與C2是?-同余的：_
C1 = a(_).P | a(y).Q | (?z)a?z?.R
C2 = a(_).P | a(y).Q | (?w)a?w?.R
1.3 結(jié)構(gòu)同余(structural congruence)
定義：對(duì)進(jìn)程P,Q,R，定義結(jié)構(gòu)等價(jià)關(guān)系“?”為滿足下列性質(zhì)的最小等價(jià)類：
SC1： 若P??Q，則P?Q，
SC2： P|0 ? P //自反
SC3： P|Q ? Q|P, //交換
SC4： P|(Q|R) ? (P|Q)|R //結(jié)合
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
這個(gè)證明也如下描述：
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 .
•
示例
內(nèi)存單元：如下定義的進(jìn)程MEM(_)描述了計(jì)算機(jī)的一個(gè)內(nèi)存單元：
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
服務(wù)器：
服務(wù)器S傳出通道a，客戶接受通道a，并用這個(gè)通道傳送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
同名通道上的多個(gè)輸出：
_|_|_u.y → _|y 或 _|_|_u.y → _|y
同名通道上的多個(gè)輸入：
_| _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、應(yīng)用?演算
可以引入一類新的特殊的名字?，表示進(jìn)程內(nèi)的不與其它進(jìn)程交互的事件，并在進(jìn)程定義中增加：?.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
進(jìn)程間的通信導(dǎo)致歸約(reduction):
Speaker | Phone ? wire
wire| ATT ? fiberComposing these reductions we get:
Speaker | Phone | ATT ? fiber
無(wú)限制通道是可視的，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。
計(jì)算機(jī)類職稱論文：應(yīng)用Pi演算
