计算机类职称论文：应用Pi演算

Pi演算起源于上世纪80年代，由图灵奖得住Robin Milner提出。它是一种描述和分析并发系统的演算模型，是用演算中的归约表示由进程间的相互通信形成的动态演化。以下是小编今天为大家精心准备的计算机类相关职称论文：应用Pi的演算。内容仅供阅读与参考!

应用Pi演算全文如下：

由于Internet与移动通信的快速发展和安全通信的需求，出现了适应种种形式分析目的的一大类应用π-演算(Application π-Calculus)[ ];本文从π-演算出发，对其进行严格的讨论与介绍。

1、基本π-演算与异步π-演算的语法(Syntax)

1.1 名字与进程

设Χ = {x, y, z, . .} 是名字(names)集(可将名字看作是通信中的通道channels of communication)，X，

归纳定义(基本)演算的进程(processes)如下(其中//…为帮助理解的直观说明)：

P:: = 0 //空进程

| P|Q //并发(并行)进程

| !P //复制进程(无穷多次)

| x.P //在通道x上发送y(输出)后执行进程P

| x(y).P //将从通道x上接收的名字赋给y后执行进程P

| νx.P //将名字x限制到进程P中使用，P的私有名字

为减少括号使用，约定：

对于“|”，用左结合，例如“P|Q|R”表示“(P|Q)|R”;

对于x(y).P、x.P与x.P，称x(y)、x或x为P的前缀，P称为前缀的体(body)，为减少括号使用，约定前缀的体向右最大扩展，例如：

vz.x.x.x.x.P表示vz..(x.(x.(x.(x.P))))

1.2 自由与约束的名字

设P、Q为进程，归纳定义名字集合fn(P)如下：

fn(0) = ; //空进程无自由名字

fn(P|Q) = fn(P)  fn(Q);

fn(!P) = fn(P);

fn(x.P) = {x,y}fn(P); //对于输出，x,y是自由名字

fn(x(y).P) = {x}  (fn(P)-{y}); //对于输入，x是自由名字，y不是自由名字

fn(vx.P) = fn(P)-{x} //对于限制，x不是自由名字

称fn(P)为进程P的自由名字集，若xfn(P)，称名字x在进程P中是自由的;如果进程P中的名字x不是自由名字，则称为约束名字，用bn(P)表示P的约束名字集，记nP=fn(P)  bn(P)并称为P的名字集;对a(x).P或(x).P，将在P中自由出现的x称为被a(x)或(x)约束的名字;注意，有P，使fn(P)bn(P)  ，即某个名字x可能同时在P中自由出现与约束出现.

例：在进程

ax.P | a(y).Q | (x)ax.R

里，x既自由出现，也约束出现。

例：进程

ax.(xb.P | xc.R)

中的(xb.P | xc.R)里两处x均被a(x)约束，是a(x)的约束名字，而

ax.(xb.P | (x)ax.R)

中的(x)ax.R里的x不被a(x)约束，不是a(x)的约束名字。

定义：

1 称名字w对进程P是新鲜(fresh)的，若w  nP;

2 自由名字的代入：对任何进程P，进程P[z/x]是将P里每个自由出现的x改为z而得的进程，称为在进程P里对自由名字x进行代入。

3 约束名字的改名：(1)对进程 a(x).P的约束名字x可用z改名并将改名结果记为a(z).P[z/x]，如果zfn(P);(2)对进程 (x).P的约束名字x可用z改名并将改名结果记为(z).P[z/x]，如果zfn(P);

注意：

1 对a(x).P或(z).P改名的结果并不导致a(x).P或(z).P里的任何名字的自由出现变为约束出现;

2 为防止改名失败，可简单地使用新鲜名字来改名，

例：设a(x).P=a(x).(x|x(c)>)，则：可用y改名x，结果为：a(y).(y|y(c)>);但不可用b改名x为a(b).(b|b(c)>)

例：代入 (y(x).0 | a(y).y| (z)y.0)[z/y] 的结果是z(x).0 | a(y).y|(z)y.0或者z(x).0 | a(y).y|(

1550;w)y.0;但不可为：(z(x).0 | a(y).z|(z)y.0)

：a(y).(y|y(c)>);但不可用b改名x为a(b).(b|b(c)>)

1.2 -同余(-congruence)

称P与Q是-同余的并记为PQ，若Q可由P的约束名字改名而得;显然，是自反、对称与传递的关系-等价关系，

例如，下面定义的进程C1与C2是-同余的：x

C1 = a(x).P | a(y).Q | (z)az.R

C2 = a(x).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： (x)0  0，(x)(y)P ≡ (y)(x)P.

SC6： (x)(P|Q) ≡ P|(x)Q, 如果 x fn(P)

例：如果yfn(P)，则 (y)P ≡ P

证明：

P ≡ P|0 SC2

 P ≡ 0|P SC3

 P ≡ (x)0|P SC5

 P ≡ (x)(0|P) SC6

 P ≡ (x)P SC2

这个证明也如下描述：

P ≡ P|0 SC2

≡ 0|P SC3

≡ (x)0|P SC5

≡ (x)(0|P) SC6

≡ (x)P SC2

1.4 归约Reduction rules

定义The main reduction rule which captures the ability of processes to communicate through channels is the following:

x.P | x(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 (ν x)P → (ν x)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(x)描述了计算机的一个内存单元：

MEM(x) = out.MEM(x) + in(y).MEM(y)

The memory cell MEM can either output its contents, x and then continue as MEM(x) (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)

多重匹配：

x<8,3>|x(z1,z2).y→ y[(8,3)/(z1,z2)] = y

同名通道上的多个输出：

x|x|xu.y → x|y 或 x|x|xu.y → x|y

同名通道上的多个输入：

x| xu.y| xu.z → y| xu.z 或 x| xu.y| xu.z→ xu.y|z

私有名字可改名：

x|(z)(z|zu.y) → x|(x)(x|xu.y)

→ x|(x)y→ x|(n)y

x|(x)(x|xu.y) → x|(z)(z|zu.y)

→ x|(n)y→ x|(x)y

通道传送：

x|xu.u→ y

(y)(x|yv.P)|xu.u→ (y)(yv.P)|y→ (y)P[7/v]

(y)(x|yv.P)|xu.u (y)(x|yv.P|xu.u) → (y)(yv.P|y) → (y)P[7/v]

a(x).P | a(y).Q | (z)az.R → (w) (P[w/x] | R[w/z]) | a(y).Q (w是新鲜fresh的)

a(x).P | a(y).Q | (z)az.R → (w) (Q[w/x] | R[w/z]) | a(x).P (w是新鲜fresh的)

2、应用演算

可以引入一类新的特殊的名字，表示进程内的不与其它进程交互的事件，并在进程定义中增加：.P

A sum (P + Q) can be added to the syntax. It behaves like a nondeterministic choice betweenP and Q.

A test for name equality (if x=y then P else Q) can be added to the syntax. Similarly, one may addname inequality.

The asynchronous π-calculus allows only x.0, not x.P.

The polyadic π-calculus allows communicating more than one name in a single action:x.P and x(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 !x(y).P without loss of expressive power. The correspondingreduction rule is

x.P | !x(z).Q → P | !x(z).Q | Q[y/z].

Processes like !x(y).P can be understood as servers, waiting on channel x 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

x.P | x(v).Q → P | Q[R/v].

In this case, the process x.P sends the process R to x(v).Q. Sangiorgi established the surprisingresult that the ability to pass processes does not increase the expressivity 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

External 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.x 解释：

• x(y).P, which binds the name y in P, means "input some name – call it y – onthe channel named x";

• x.P, which binds the name y in P, means "output the name y on the channel namedx";

• 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);

• νx.P, which binds the name x in P, means that the usage of x 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(x).wire //电缆

ATT = wire(x).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(x).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(x) … | ( wire)(wire| ATT) ! wire(x) … | 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 lexically 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。