ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



*
 Ǯ ܻ
ժҪһ߼ϵͳ,ڲ״̬Ķ̬ݱʵTrace֮.һµĶ̬ʵи͸õ,رǷװ.Ϊ,Чĸ,ͨЧ̻ķװ,ֻжЧܷʻ޸Ķֵ,ӶTraceģͼ,õģ.Ϊ߼ϵͳ,»˶Ĺ,Trace㹫ϵͳ.ΪӦ,½ʵ˶.
ؼʡ,Ч,,,.
ͼšTP311
Object Calculus 
HUANG Tao,QIAN Jun,ZHOU Huan
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100080)
(Object Technology Center Institute of Software The Chinese Academy of SciencesBeijing 100080)
AbstractAn object-based logic calculus is outlined in this paper, which is built on the trace calculus based on dynamic entities with local states. Compared with dynamic entities, objects have more good properties, such as encapsulation. To formalize the concept of encapsulation, a new concept of valid action is introduced. It is only through these valid actions declared by the very object that the state of the object can be accessed or modified. An axiomatization of the object calculus as an extension of the axiom system of the trace calculus is also contributed in this paper. Finally, the object semantics description and property deduction are shown.
Key wordsObject calculus, valid action, axiomatization, object semantics description, property deduction.
ף1,Trace.TraceеġǾڲ״̬Ķ̬ݱʵ,ʹTraceȿĶ̬ʵĽṹΪ,ԶЩ̬ʵΪ֤.TraceûпǵָһҪԡװ,,Trace㲢һ.ϣ߼ϵͳ.ڶһµĶ̬ʵи,رǷװ,ǱTraceģͼ.Ϊ,Чĸ,ֻͨЧܷʻ޸Ķֵ,ЧִԶ״̬κӰ.
ĵ1۶ķװ,Чĸ,ͽṹ.2TraceĿɿԹϵͳ֮,ӶװԹ,õĹϵͳ.3ڽϾʵĸӦ.45ΪӦ,йض.
1װ
֪,һҪ,װ(encapsulation).װǣֻڶĶ޸ĶԵֵ.ǰ۵ṹ㲢ûпǶķװ.Ϊ۶װ,Чĸ.
1(Ч). Ǧ=(S,F,A,E),һ-ͽṹһgEs1,...,sn,aisi,1in,ǳΪЧ.
ǼΪЧļ,

2(Ч). Ǧ=(S,F,A,E),һXһgEs1,...,sn,ǳg(t1,...,tn)ΪЧ,tiT(,X)si,1in.ЧΪGT.
ЧıԵֵ.Ȼ,ԽԵĺʽʽ,ǿ֤ͨЧ²Ƴ䲻.
3(-ͽṹ). Ǧ=(S,F,A,E),һ-ͽṹΪ-ͽṹҽԷfAs1...sn,s,⶯,,(f)(1e2)=(f)(12).
Trace,ǿԶ妷ṹ.
4(ṹ). һǦ=(S,F,A,E),һṹ
.-ͽṹ
.ֵv={vs}sSE,vsXss
.ټ.
ͬ,ǿԶ͹ʽڦṹϵĽ,Traceȫͬ.ΪԺĴ,ǶһµһµĹʽ,̬;̬ʽ,Ϊ͹ʽӼ.
5(̬). ǦͱX,sS,̬ST(,X)sɶ£
.xXs,xST(,X)s
.fFEs1...sn,sAs1...sn,s,tiT(,X)si,0in,f(t1,...,tn)ST(,X)s
.tT(,X)s,InittT(,X)s,
̬вʱ(X,X)Ͷ(a),Ƶ,¾̬ʽ.
6(̬ʽ). ǦͱX,sS,̬ʽSF(,X)ɶ£
.t1,t2ST(,X)s,t1=t2SF(,X)
.p,qSF(,X),p,pqSF(,X)
.pSF(,X),xXs,xpɳ,xspSF(,X).
ЧĶ֪,ЧӦ־̬;̬ʽ,ЧִûִиöЧһ.һ֤.
1. Ǧ,-ͽṹ,ֵv,Чټ1,2,
(1) v*i(t)=v*i(t)0i|1|
v*i(t)=v*i-1(t)|1|i|1|+|2|+1
(2)i(p)=i(p)0i|1|
i(p)=i-1(p)|1|i||1|+|2|+1
tST(,X)s,pSF(,X),=1e2,ء=12,=(O,v,),=(,v,w),v*ivټϵȻ,v*ivټءϵȻ.
֤1. tĲνй
(1) tx,xXs,
v*i(t)=v*i(x)=v(x)=v*j(x)=v*j(t),
0i|1|+|2|+1,0j|1|+|2|.
(2) tf(t1,...,tn),fFEs1...sn,s,tiT(,X)si,i,1in,ݹɼ,

(3) tf(t1,...,tn),fAs1...sn,s,tiT(,X)si,i,1in,ݹɼ,

(4) tԣInitt,tT(,X)s,ݹɼ,
v*i(t)=v*i(Initt)=v*0(t)=v*0(t)=v*j(Initt)=v*j(t)
0i|1|+|2|+1,0j|1|+|2|
2. p﷨ṹй
(1) pt1=t2,t1,t2T(,X)s

(2) pԣInitq,t1,t2T(,X)s,ݹɼ,

1. Ǧ,-ͽṹ,ֵv,Чټ1,2,,pSF(,X),=1e2,ء=12,=(,v,),=(,v,ء).
2. Ǧ,-ͽṹ,ֵvټ,,pSF(,X),=1e2,ء=12,=(,v,),=(,v,ء),ءΪӦڦضЧټ.
ɴ˿ɼ,Ҫ֤ṹ=(,v,)һ̬ʽģ,ֻҪ֤ӦĽЧĽṹ=(,v,ء)Ǹùʽģͼ.
ӦЧ,ǿԶһ±xG,ֵΪһ±XG,gEs1,...,sn,xgXG,ֵΪ{|aisi,1in}.
1. pΪ̬ʽ,pSF(,X),xGxGpap,,apɳ.
2. (1) pgEpxG(xg),(2) gExgpxG(xg)p.
֤.
2
ף1ѾTraceĹ.籾˵,ϣһ߼ϵͳ.ڶһµĶ̬ʵи,װ,ǱTraceģͼ.
3. pΪ̬ʽ,pSF(,X),xGxGpXp.
4. tΪ̬,tSF(,X),xGpx(xGt)px(Xt).xXs,pxʱͶڳ.
,ֵõһµĹ,ʹǿԽеĶ滻Ϊʱ.
5. (a=xG)p,1in(ati=ti)pp.pF(,X),eT(,X)E,tiST(,X)si,1in,xGpɳ.
֪,Ҫ֤һĹʽ,ǿ֤ͨЧ(ʱʽ)߶־̬(ʱʽ).ƪ,ʡ϶֤.ף2.
ǿԽ345ΪµĹ͹,ӶTrace㣬õװԵĶ.ӵĹ͹.
(enc1)xGxGpXp,pSF(,X),
(enc2)xGpx(xGt)px(Xt),tST(,X)s,xXs,
pxʱͶڳ,
(enc)(a=xG)p,1in(ati=ti)pp,
tiSF(,X)si,1in,xGpɳ.
3
ǰѾ˶﷨,Ϊ,Ӧö֤.
7(). һһԪ(,D),
.һ
.D={p|pF(,X)},Xһ
ĹʽFһȺ,ͨЩɷΪõĹ(Ӧڳĺpost-condition)ʼĹִеıҪĹ(Ӧڳǰpre-condition)ԼһЩ̬ԼĹȲ.,һֹǹݲֵ,ͨ淶µĹ,ֱӼ.
ڶǲûֱӸΪ,ǸΪ(ҲΪԼ),̬ԺͶ̬/ʱ.
һ,˵.,ߺ߹һ.3PRODUCER,CONSUMERBUFFER̻ӦĽṹΪ.
ObjectSingature PRODUCER=
Sorts ITEM,BOOL
Functions
true,false BOOL

Attributes
item ITEM
waiting BOOL
Actions
produce(ITEM)
put(ITEM)
End
itemڴ,waitingָǷڵȴѴõ.ЩԵֵߵĶΪı.
Ϊ,Ƿմ淶+,Ǧ1ɶǦһЩS1,F1,ԷA1ͶE1ɣǿдΪ
1=+(S1,F1,A1,E1)
(S1,F1,A1,E1)һǸ.=(S,F,A,E),1=(S+S1,F+F1,A+A1,E+E1),С+ʾཻ.
ObjectSignature CONSUMER=ITEM+BOOL+
Sorts
Attributes
item ITEM
waiting BOOL
Actions
consume(ITEM)
get(ITEM)
End
ֵָ,еĶ,ԷŵȵֵĺǾֲڶǵ.
ObjectSignature BUFFER=ITEM+INT+
Sorts
Attributes
count INT
Actions
put(ITEM)
get(ITEM)
End
ǸһġBUFFER,еȸġһġBUFFER.
PRODUCERĹΪ
produce(i)Ч
p1produce(i)item=i
p2produce(i)waiting=t
put(i)Ч
p3put(i)waiting=f
ʼ
p4Initwaiting=f
produce(i)ִеıҪ
p5enabled(produce(i))waiting=f
p6enabled(put(i))(item=i)(waiting=t)
p7waiting=tFput(item)
ע,,p1produce(i)item=i,ʵӦΪ
enabled(produce(i))(produce(i)item=i),
Ȼ,ֻͨĺϷΪ,ǿֻ̻ϷΪԼ,ʱǼӦĶӦ״̬,Ӷд.,ǿͨ¹Ӧ⴦,Ӷﵽģ黯Ҫ.
,Ϊ,һ¹ʽaT(,X)E,ʽa˶aִ,aǰõ,Ҷк.ʽ,
aenabled(a){q|qΪapat1=t2ĳ}.
һṹ=(I,v,),i(a)=tҽ(i,v*i(a))v*i(a)=i+1,ʽaΪ浱ҽڵǰ״ִ̬ӦĶ.
CONSUMERĹΪ
consume(i)Ч
c1consume(i)waiting=f
 get(i)Ч
c2get(i)item=i
c3get(i)waiting=t
 ʼ
c4Initwaiting=f
 consume(i)ִеıҪ
c5 enabled(consume(i))(item=i)waiting=t
 get(i)ִеıҪ
c6 enabled(get(i))waiting=f
 ̬Լ
c7 waiting=tFcconsume(item)
BUFFERĹΪ
put(i)Ч
b1put(i)count=count+1
 put(i)Ч
b2get(i)count=count-1
 ʼ
b3Initcount=0
 put(i)ִеıҪ
b4 enabled(put(i))(countsize)
 get(i)ִеıҪ
b5 enabled(get(i))(count0)
 ̬Լ
b6 put(i)Fget(i)
ֵָ,ǽ˶ִеıҪ,ΪͬͨǻڶĹ,Ҳ˵,ܹͬͬĶ.ִʱʹúǿ,ôǽһ¶ʱ,ͿܵĲһ.һʱ,ִеⲿ,ҽйظöıҪ,ӶṹҪ.ͨ,ǽaִеıҪΪ
enabled(a)pre(a)
pre(a){q|enabled(a)q}.
öob1,...,obn¶ʱ,
enabled(a)1inprei(a)p(ob1,...,obn)
p(ob1,...,obn)˸ĶaӦʱͬ(һĳһִܹ,ҽ֮ͬͨŵĶѽӦ״̬,ͬĶǰ,ʱвͬĶִиӦĶ).
,ЩװԳ,ֻбĶ޸Ķ.
4
ǽʽΪΪԼ(constraints)ʽ,̻.ҪĲкܶ,ЩԿԷΪȫ(safety)/(invariance)Ժͻ(liveness).
4.1ȫ
ֱϽ,ȫָǡ¼ᷢ.ȷе˵,ȫ˼(޵)ǰ׺һҪ.
ȫԿɱʾΪpGq.
p=t,ʽɱʾΪGq.
ע,õȫ,Gqq.
漰Ķ״̬,ȫֿɷΪ̬ȫԺͶ̬ȫ.
̬ȫԼֻ漰һ״̬,硰ָǸһ̬ȫԼ,ʾΪcount0.ͨ,̬ȫԼвʱ.
̬ȫԼ漰״̬,ڽ3ĶINC
(1)add1i=i+1
(2)add2i=i+2
(3)Initi=0
a(ai0)һ̬ȫԼ,漰״̬,aִǰiֵaִкiֵ.
4.1.1 ȷ(partial correctness)
ȷָһa(enabled),aǰԺⲿ,Ҷaִֹ,aĺ.ǵĶ,ǰԺͺԶΪһֳֵ,ԭ.ڶʵнľʵ,Ҳ˵,ʵֽ֤ȷ.
4.1.2 (mutual exclusion)
ǹе,һض(ͬһͬһ޸,֮)ڶʾԲִейع,ǶΪǻ.صĶΪǿɲִе.BUFFER,ʹput(i)get(i)Բִ,ӦΪ
b1䣺put(i)count=count+1
b2䣺get(i)count=count-1
b3䣺put(i),get(j)count=count
b4䣺Initcount=0
b5䣺 enabled(put(i))(countsizen)
b6䣺 enabled(get(i))(count0)
ɲִе,ǿɽǵϿһԭӶ(Ӧĳ).ԭӶִ߲(ʱӦ¼),ִ(ʱӦ¼).
4.1.3 (deadlock freedom)
ûжִ,ԱʾΪenabled(xa1)...enabled(xan),a1,...,anΪöж.ԿɱʾΪpre(xa1)...pre(xan).ע,ʹpre(xai),enabled(xai),ǳڽṹҪ,ܶⲿ.
4.2
ָǡĳ¼ջᷢ.һ̶,ԿȫԵĶż,ҪĳЩǰĳԵõ.
ԿɱʾΪpFq.
,ԡaִԺbԺĳһʱִСɱʾΪaFb.
4.3ƽ
ƽ(fairness)Ҳһֻ.ƽζaִ,ôԺĳһʱִ.ƽֿɷΪƽ(weak fairness)ǿƽ(strong fairness).
ƽָaִǰһֱǿִе,ִ.ʾΪ
(Fa)(Fpre(a)).
ǿƽָ,aִǰοִ,ִ.ʾΪ
(Fca)(FGcpre(a)).
5
ʹöʱ,ͨʹúĹ͹,Ȼʹһʱ.ΪͨĶеĹҪǺĹ.
ĿǰΪֹ,ǲûʹԭӹʽenabled(a)a.ǽʹǽ.Ϊ,һµĹ͹.
5.1ȫ
ǰгĹƵûпǵеĶӦǷִ((enabled)).Ҫ㰲ȫ,Ҫеÿ,Ӧټǰȫټ(safe trace).
8(ȫټ). Ǧ,-ͽṹ,ټسΪȫټҽi,(i,i+1)ʦ.
Ҳ˵,е⶯(enabled).
гĹƵƵĽټ,ƵĽͬڰȫټ.
ڶ԰ȫټ,󵽴ĳһ״ֻ̬Ӧʱſɷ,ǿԼٶÿִǰ,Ӷǰõ.µĹ
(safe1) a(enabled(a)ģapXp,
(safe2)Initp,a(enabled(a)pap)p,
(safe3) a(enabled(a)pxat))px(Xt),tST(,X)s,xXs,
pxʱͶڳ.
ٿǵװ,
(safe4) xG(enabled(xG)ģxGp)Xp,pSF(,X),
(safe5) Initp,xG(enabled(xG)pxGp)p,
(safe6) xG(enabled(xG)pxxGt))px(Xt),tST(,X)s,xXs,
pxʱͶڳ,
(safe7) (a=xG)p,1in(enabled(a)ģati=ti)pp.tiST(,X)si,1in,xGpɳ.
ЩĿɿȻ,enabled(a)enabled(xG)ģͼ.
1BUFFERcount0.
֤(safe5),ֻ֤
1Init(count0)
2 enabled(put(i))count0put(i)(count0)
3 enabled(get(i))count0get(i)(count0)
ڡ1,С(1)Initcount0(b3)
(2)Init(count0)(1),0,ݡrigid
ڡ2,С(1)put(i)(count0)
put(i)(count0) 0,ݡrigid
count+10 (b1,滻)
(2)count0count+10
(3)count0put(i)(count0)(1),(2)
ڡ3,(1)get(i)(count0)
get(i)count0 0,ݡrigid
count-10b2,滻
(2)count0count-10
(3)count0get(i)(count0) (1),(2)
(4)enabled(get(i))count0(b5)
(5)enabled(get(i))get(i)(count0)(3),(4)
5.2
ͨ,۵Ļ㰲ȫµĻ.,ǿڰȫټۻ,йذȫĹȻ.,ݹʽa,¶ЩΪĹ͹.
6. (live1) aenabled(a).
7. (live2) a(apXp).
8. (live3) a(px(at)px(Xt)),tST(,X)s,xXs,pxʱͶڳ.
9. (live4) pFa,aqpFq.
2PRODUCERwaiting=tF(waiting=f).
֤(1) put(i)waiting=fp3
(2) put(i)(waiting=f)(1),=,fϸ
(3) put(item)(waiting=f) (2),(prep),(a7)
(4) waiting=tF put(item) p7
(5) waiting=tF(waiting=f)(3),(4),(live4)
3PRODUCERproduce(i)F put(i).
֤(1) produce(i)produce(i)waiting=tʽproduce(i)Ķ
(2)produce(i)waiting=tproduce(i)(waiting=t) =,tϸ
(3) produce(i)produce(i)(waiting=t) (1),(2),cut
(4) produce(i)X(waiting=t)(live2)
(5) produce(i)X(item=i)(4)Ƶ
(6)a(aitem=itemģawaiting=waiting)kput(k)lproduce(l)װ
(7) waiting=titem=i
 a(awaiting=tģaitem=i)kput(k)lproduce(l)(6),(eq2),(prep)
(8) waiting=titem=i
X(waiting=titem=i)kput(k)lproduce(l)(l)(7),(a9),(prep)
(9) produce(l)waiting=f(live1),p5
(10) waiting=tlproduce(l)(7),(gen),(prep)
(11) k(put(k)k=item)(live2),p6,(gen),(prep)
(12) waiting=titem=iX(waiting=titem=i)put(item)(8),(10),(11),(prep)
(13) waiting=tFput(item)p7
(14) waiting=titem=i(waiting=titem=i)Uput(item)(12),(13),(prep)
(15) waiting=titem=iFput(i)(14),(prep)
(16) produce(i)Fput(i)(4),(5),(15),(prep)
Ƿ,֤߳.Ϊ,ǿ¹֤.
10.
(live5) (penabled(a)at=tģap)xb(x),pFbx(t)pt=u((pt=u)
Ubx(u)).
3.
(live6) (penabled(a)at=tģap)xb(x),cct=uģcp,pFbx(t)
cX((pt=u)Ubx(u)).
Ȼ.
6 
Ľϴ3ݺʱ߼4ݷ,Χƶķװ,ڶʽ۷һЩо.Ҫ£
(1) ЧЧĸ.ֻӦṩĶЧ.
(2) ͽṹ.ֻжЧ޸Ķ,ͽṹϷӳķװ.
(3) .
(4) ϵͳΪԼʽ,ϵͳİȫԺͻƵ.
*оõȻѧ͹863߿ƼĿ.
ͨѶϵˣ, 100080,йѧԺоѧоʵ
߼飺,1965,ʿоԱ,ҪоΪ,,ֲ,Լ.
Ǯ,1966,ʿ,ҪоΪۺͼ,ֲ,ʽ.
ܻ,1976,ʿ,ҪоΪۺͼ,ֲ.
ߵλΣǮܻйѧԺоѧоʵҡ100080
ΣǮܻйѧԺо  100080
οף
1ݻ,Ǯ,߱.Trace.ѧ,1999,10(8):790799
(Huang Tao, Qian Jun, Ni Bin. Trace calculus. Journal of Software, 1999,10(8):790799)
2ݻ.ʽо۲ʿѧλģ.Ϸ:йƼѧ,1994
(Huang Tao. Theoretical research on object formal semantics Ph.D. Thesis. Hefei: University of Science and Technology of China, 1994)
3Ehrig H, Mahr B. Fundamentals of Algebraic Specifications 1: Equations and Initial Semantics. Berlin: Springer-Verlag, 1985
4Kroger Fred. Temporal Logic of Programs. Berlin:Springer-Verlag, 1987
ոڣ1997-12-12޸ڣ1998-09-04
