ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



Trace 
 Ǯ ߱
ժҪ¶˻ټ(trace)߼LTrace,һʱ߼Ե,ͬʱҲǡ㡱оĻ.Traceġ̻ڲ״̬ⲿΪĶ̬ʵ,﷨ɶǱʾ.Ǧ=(S,F,A,E)4:SFAͶE.=(S,F)ͨ淶µı,ɽһ,ӶõǦĶ䦲E.ǵͽṹɹڱǦEĴӳͶټĹϵ.E-ݲĽ;ӳڶټȡֵ;ټĹϵִһټԺöǷִ.ڶTrace﷨֮,¸TraceĹϵͳɿ֤. 
ؼʡTrace,,,ټ,,ɿ.
ͼšTP
Trace Calculus
HUANG Tao QIAN Jun NI Bin
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100080)
(Object Technology Center Institute of Software The Chinese Academy of Sciences Beijing 100080)
Abstract A trace-based logic language: LTrace is defined in this paper, which is an extension of the first-order linear temporal logic and serves as cornerstone of the works Object Calculus. The objects in trace calculus represent the dynamic entities endowed with a local state and external actions, and described by an object signature in syntax. An object signature is a 4-tuple =(S,F,A,E) in which S stands for a set of data sorts, F functions, A attributes and E actions. =(S,F) is nothing but a usual signature in the context of algebraic specification. It can be extended to E with the action regarded as a special data sort. The semantics of trace calculus is defined by an object signature semantic interpreting structure I=(A,F,E), which consists of a E- Algebra A giving an interpretation about data parameters, a mapping F evaluating the attributes on an action trace, and a relation E giving a relationship between actions and a trace. Finally, we contribute an axiom system of our trace calculus and outlines its proof of soundness after we define the syntax and semantics of the trace calculus.
Key wordsTrace calculus, object signature, action, trace, axiomatization, Soundness.
80Ժչ.Ŀǰ״,̼˷չĳ,۵оͺڹ̼ķչҪ.ϵͳо,Ȼܶۼ̼ķչԶӰƶ,ڳǿϵͳɿԵȷ,ǲ.ף1оѿʼʹô淶ķоΪԼ.ף2,3,ǽһģͼָ.Ľף2,3ݵĻ֮,ϴ淶4,5ݺʱ߼6,ټ(trace)߼LTrace,һʱ߼Ե.߼ϵͳΪ,ǾͿԹһ߼ϵͳ.
ǰʽģ͵о,Ҫлڴģͻʱģֶ.Ĵģ۴ѧǺ(ͣ,ȱȱĶ̬Ϊ.˾о̬Ľṹ,ж̬.ϵͳй,Աɡ޸ġݱ.,ڿ̻ϵͳ̬ΪԼϵʱ,ôģԱ,ȻҪʱģ͵Ĺ۵.
Ӧָ,ĶָһЩڲ״̬ⲿΪĶ̬ʵ,󷽷еĶ.ûпǶеһҪԡװ,Trace㲢һ.,ǵĿǽһ߼ϵͳ,۶Զ:ǸǵĶ塢ṩ,Է̬ʵĶ̬Ϊ.
ǰ͡ԺͶ4.ͺͺͨ淶µı,״̬޹صϢ,Ƕģ򻷾,˵һıĿ;Բְ״̬Ϣ,ͬͨг;ָöִеĶ.
ֵָ,ǽӦ(Ϊ)(﷨),ͬĹϵָͨһЩضͬ.
ĵ1ڸTrace﷨.2ڸTrace.35ڷֱTraceķ͹.ܽ.
1 Trace﷨
1.1 
1. ǦһԪ(S,F,A,E)
.S(sorts)ļ.
.Fһ,Ҵһӳtype:FS*S.fF,type(f)Ϊf.ɱʾΪԪ.
.A S*S ʶԷŴ.
.E S* ʶĶŴ.
F,AE޼Ҳཻ,S*S.ԪԷӦͨеĳ,ԪԷڴݽṹ.Ȼ,SFͨ淶µıǦ=(S,F).ڵ2,ǽͶϸĽ,ͶĽ״̬޹ص,෴,״̬ص.
ǿԽǹ,EʾĹݵļ.ڶŴEеÿf:s1...sn,庯f:s1...snEõһE,淶ıΪ
Signature E=
Sort E
Functions
f1:s1...sn1E䡡/*f1:s1...sn1E*/
f2:s1...sn2 E䡡/*f2:s1...sn2E*/

End
ΪԺĴ,EʾE䲢֮ʾE.
2. һǦ=(S,F,A,E),E-ΪE=(SE,FE),,
.SE=S{E},һES.
.FE S*SEʶķŴ,ԦءS*,sSE,sS,FE,s=F,s,֮,FE,s=E,Զ亯.
1.2 
XSʶı,X={Xs|sS},XA,F,Eཻ.
3(). ǦͱX,sSE,T(,X)sɶ:
1. xXs,xT(,X)s,
2. InitT(,X)E,
3. fEFs1...sn,sAs1...sn,s,tiT(,X)si,0in,f(t1,...,tn)T(,X)s,
4. aT(,X)E,tT(,X)s,atT(,X)s,
5. tT(,X)s,Xt,X-tT(,X)s.
ǳT(,X)EеΪ,InitΪʼ.
1.3  ʽ
4(ԭӹʽ). Ǧ,X,ԭӹʽAF(,X)ɹɶ:
1. t1,t2T(,X)s,sSE,t1=t2AF(,X),
2. aT(,X)E,enabled(a)AF(,X).
5(ʽ). һǦ,X,ʽF(,X)¹ɶ:
1. pAF(,X),pF(,X),(ÿԭӹʽǹʽ);
2. aT(,X)E,pF(,X),apF(,X);
3. ͨʱ:p,qF(,X),Xp,pq,X-p,p-qF(,X);
4. ͨһ:
(1) p,qF(,X),p,pqF(,X);
(2) pF(,X),xXs,xpɳ,x:spF(,X),ǳxڡx:spF(,X)Լ.
,ǿɰʱ߼ͨõķµȹʽд:pq,pq,pq,t,f,Ep,Gp,pBq,F-p,G-p,x:sp.
һʽp,ԪxXsĳx:sx:sķΧ,xpɳ;֮,xpгԼ.
tT(,X)s,pF(,X),px:s(t)ʾt滻pɳֵx,xXs.ǼtвpԼֵɱԪ.
ֵָ,ͱĳһض(sort),Ϊ,ڲ,ȥӵϢ,x:s pʱǼдΪx p.
2 Trace
Traceһʱṹ.
2.1 
2.1.1 ټ
ټǶִ.ǽΪһ,ɦEıǴеEEжŵĽ,еĽ.ǳEеԪΪ,еԪΪټ.ΪʾһЩйټķź.
6.
.ټʾΪ;
.ء,.aEʾټغ󴮽һa;
.||ʾټصĳ;:||=0,|.a|=||+1;
.1i||,iʾټеĵi,:
(.a)i=i 0i||,
(.a)i=ai=||+1;
.0i||,iرʾټصĳΪiǰ׺,:
0=,
||(.a)=.
ͨʡ.
2.1.2 -ͽṹ
ǵͽṹһڱǦEĴһӳͶټĹϵ.E-ݲĽ;ӳڶټȡֵ;ټĹϵִһټԺöǷִ.
7. һǦ=(S,F,A,E)Ħ-ͽṹһԪ=(,,),
.һE-;
.fAs1...sn,sn0:(f):(s1...sns);
.šE.
,E-ǦE-ʼ.Ÿִеǰ(ԶټĹϵʾ,ָĳһ״̬¸öִǰִеĶе).
2.1.3 Trace-ṹ
8. һǦ=(S,F,A,E),һTrace-ṹ=(,v,):
.һ-ͽṹ=(,,);
.һֵv={vs}sSE,vs:Xss;
.һټ.
ע,ټ滻ͨʱṹе״̬.siΪi״̬,aiΪsi״ִ̬еĶ,öִн״̬תsi+1,,S0s1,...,sisi+1,...,ǿټa0a1...ʱµ״̬s0s1....,,i״̬siֵӳ亯,õv*i,iȾ״̬siµ.
2.2 
ǿģ¾߼ķΪÿһֵ.,Ƕйرĸֵ.
9(ֵ). һǦ=(S,F,A,E),-ͽṹ=(,,),ڱXĸֵؼΪ:v={vs|sSE},vsǱXssӳ.
ǿ¶帳ֵvһټϵȻv*i,iN:
.xXs,v*i=v(x);
.fFEs1...sn,s,tiT(,X)si,i,1in,v*i(f(t1,...,tn))=f(v*i(t1),...,v*i(tn));
.fAs1...sn,s,tiT(,X)si,i,1in,v*i(f(t1,...,tn))=i(f)(v*i(t1),...,v*i(tn));
.aT(,X)E,aInit,tT(,X)s,
.tT(,X)s,v*i(Initt)=v*0t;v*i(Xt)=v*i+1t;v*i(X-t)=v*i-1t,i0.
ǲûиʼInit,Init,ҪInit.
ǿԶ幫ʽֵ.
һTrace-ṹ,ÿԭӹʽF,ǿ¶i(F){t,f},ʾʽF״̬siµֵ:
1. i(t1=t2)=tҽv*i(t1)=v*i(t2);
2. i(enabled(a))=tҽ(i,v*i(a))ʦ.
һTrace-ṹ,ÿʽF,ǿ¹ɶKi(F){t,f},ʾʽF״̬siµֵ:
1. i(p)=tҽi(p)=f;
2. i(pq)=tҽi(p)=fKi(q)=t;
3. i(ap)=tҽ
4. i(Initp)=tҽ0(p)=t;
5. i(Xp)=tҽi+1(p)=t;
6. i(pq)=tҽji(j(q)=t(ikj)k(p)=t);
7. i(X-p)=tҽi0,i-1(p)=t;
8. i(p-q)=tҽji(j(q)=t(ikj)k(p)=t);
9. i(x p)=tҽi(q)=t=(I,v,):v(y)=v(y),y,yxҲ˵,i(p)ʽp״̬siµֵ.
10(ģͺЧʽ). һʽpһTrace-ṹ,i0,i(p)=t,pЧ(Ϊp),Ϊpģ.Trace-ṹ,p,pΪЧʽ(Ϊp) .һʽ,ЧеĹʽȫƱʽp,p,Ϊģ.
11. һTrace-ṹΪʽйʽģ,ƧΪ.
12. һʽһʽp,Чģp,pΪ,Ϊp.
1. qʧ,qҧp,p.
2. p1,...,pnҽ(Gp1...Gpn)q.
3. p,ҧpq,q.
4. p,
1. ap;
2. Initp.
5.pҽ{p}ǿ.
3 Trace
ǸһЩTrace߼.,ǿ֤,һʱʽµ߼Ȼ.
13(ʱʽ). x1,...,xnһʱԭӹʽ,p(x1,...,xn)FLTLBһʱʽ,p1,...,pnTrace,p(p1,...,pn)ΪTraceʱʽʱʽ.p(p1,...,pn)p1,...,pnֱ滻p(x1,...,xn)еx1,...,xný.
6. ʱʽЧʽ.
֤ʡ,ף7. һ,ǿԽһʱʽTraceġ߼.һ,ǿ֤¶:
һʱ,ʽqǹʽp1,...,pn;Traceʽһ滻p1,...,pnqƻ߼ϵ.
14. p1,...,pn,qTrace,p1... pnqʱʽ,qp1,...,pnʱ.
7. qp1,...,pnʱ,p1,...,pnq
Ϊʡƪ,гйTrace߼,֤.
ż
(T1) apaݡp
ͬһ
(T2) InitݣInitpInitp

(T3) a(pq)ܣapaq
(T4) a(pq)ܣapģaq
(T5) a(pq)ܣapţaq

(T6) pqapaq

(T7) aݣInitpInitp
(T8) XInitpInitp
(T9) GInitpInitp
(T10) FInitpInitp
(T11) X-InitpInitp
(T12) G-InitpInitp
(T13) F-InitpInitp
(T14) InitGp(GpG-p)
8. pвԷ
1. pInitp;
2. pap.
15. һtT(,X)s,xXs,t滻ʽpеıxԷʱ(X,F,...)Ͷ(Init,a)ڵ³tеı滻Լ,tpеxǿ滻.
滻Ҫڱxȫֵ,ʱ/ټ޹ص.
9. tT(,X)spеxXsǿ滻,xppx(t).
10. apɳ,aap(Xp).
11. aT(,X)E,xXs,xaɳ,xapa(x p).
12. xInitpInit(x p).
aInit,:
(T15) ap(pXp)
(T16) (pXp)ap
4 Trace
TraceԺ,ǸһʽϵͳйʽƵ.
 
(taut)һʱ߼Ĺʽ
(a1)pappвԷ
(a2)aݣInitpInitp
(a3)XInitpInitp
(a4)X-InitpInitp
(a5)apap
(a6) a(pq)apaq
(a7) x ppx(t)tpеxǿ滻
(a8) InitGpGpG-p
(a9) aapXpapɳ
(a10)xapax pxaɳ
 
(mp) p,pqq
(nex) pXp
(las) pX-p
(act) pap
(emp) pInitp
(inv) Initp,pXpp
(ind) pq,pXppGq
(indp) pq,pX- ppG-q
(gen) pqpx qpxɳ
ûйصȴʵĹ͹.
13(ɿ). pΪһʽ,Ϊһʽ,p,p
֤:Դӧ֤qƵ̽й.
1. pTrace㹫,ɶ6Ͷ8,s(T7),(T8),(T11),(T1),(T3),9,(T14),10Ͷ12,ֱ֪(taut)͹(a1)(a10)Чʽ.,Чp.
2. pʧ,Ȼp.
3. pqqp(mp).򧤩q,qp.ɹɼ觤q, qp.ɶ3ɵçp.
4. pXqq(nex).򧤩q.ɹɼ觤q.=(I,v,)ΪһTrace-ṹ,:r,rΪйʽһȫƱʽ.q,i0,i(q)=t,Զj0,j+1(q)=t,ЧXq.
5. pX-qq(las).򧤩q.ɹɼ觤q.=(I,v,)ΪһTrace-ṹ,:r,rΪйʽһȫƱʽ.q,i0,i(q)=t,Զj0,j-1(q)=t,ЧX-q.
6. pԣaqq(act).򧤩q.ɹɼ觤q.ɶ4ɵçaq.
7. qԣInitrr(emp).򧤩q.ɹɼ觤q.ɶ4ɵçInitq.
8. pɣInitppXp(inv).򧤩ƣInitp,pXp.ɹɼ觤Initp,pXp.K=(I,v,)ΪһTrace-ṹ,:r,rΪйʽһȫƱʽ.:
(1) Initp;
(2) pXp.
(1)ɵ0(r)=t,(2)ɵ0(p)=2(q)=...=i(p)=...=t,p.
9. pqGrqrqXq(ind).򧤩qr,qXq.ɹɼ觤qr, qXq.=(,v,)ΪһTrace-ṹ,:r,rΪйʽһȫƱʽ:
(1) qr;
(2) qXq.
ii(q)=t,(2)ɵi+1(q)=i+2(q)=i+3(q)=...=t,ji,j(q)=t.
(1)ɵj(r)=t,ji.:i(qGr)=t,i0,p.
10. pqGrqrqX-q(indp).(ind).
11. psx r,xsеɳ,sr(gen).򧤩sr.ɹɼ觤sr,=(,v,)ΪһTrace-ṹ,:q,qΪйʽһȫƱʽ.sr.ĳi,i(sx r)=f,i(s)=tKi(x r)==f,һ,ʹái(r)=f,ҡڶxĸֵͬ.ζŶϵıʽq,Сq,ˡsr.sxɳ,С(s)=t,(r)=t,ì.Զi,i(sx r)=t,˧sx r.
Ϊ֤,һдһʱƵ(ʹһʱĹ͹(mp),(nex),(ind)),
(prep) p1,...,pnqqp1,...,pnһʱ﷨
õcut(prep)һʵ.
14(ﶨ). {p}q,֤ʹõGenԪpɳ,µGenԪͿɵçƣInitGpq.
ǻﶨҪ.
15. {p}q,֤δʹPLTLP5ݺ(emp)֤ʹõGenԪpеɳµGenԪͿɵçGpq.
1. pǱʽ,{p}q,򧤩ƣInitGpq.
16. ƣInitGpq,򧤡{p}q.
ǸһЩʹTraceж֤.
(T17) pXpƣInitpp
(T18) XpppInitp
֤:
(T17) (1) InitGInitpp(inv),衢ﶨ
(2) InitpGInitp(a3),(prep) 
(3) InitpInitGInitp(2),(a2),(prep) 
(4) Initpp(1),(2),cut
(T18) (1) Xpp)(pXp)prep
(2) pXp,(1),mp
(3) X p Xp(prep)
(4) p Xp(2),(3),cut
(5) Initݡpp(4),(T17)
(6) InitpInitݡp(a5)
(7) Initpp (5),(6),cut
(8) (Initp p)(pInitp)(prep)
(9) pInitp(7),(8),cut
(T19) paapInitpp
(T20) aapppInitp
2. Initp,paapp.
5 TraceĽһ
һڵĹδйصȴʵĹ,ǽһ֮.ƪ,ֻн֤ʡ,ף7.
t1,t2T(,X)s,aT(,X)E,
(T21) a(t1=t2)(at1=at2)
fFEs1...sn,s,¹ʽЧʽ
(T22) af(t1,...,tn)=f(at1,...,atn
aT(,X)E,tiT(,X)s,i,1in.
Ҳ˵,=źͶŵĽϸ(rigid),״̬/ټ޹ص.
(T23) aݣInitt=Initt
(T24) XInitt=Initt
(T25) X-Initt=Initt
17. 
1. u=v tx(u)=tx(v);
2. u=v px(u)px(v).
18. x,yT(,X)s,pвʱͶ,x=y(ppx(y)).
3. x,yT(,X)s,pxʱͶڳ,x=y(ppx(y)).
(T26) u=v(tx(u)=tx(v))
(T27) u=v(px(u)px(v))
u,vT(,X)s,xXs},tΪһ,pΪһʽ,u,vpеxǿ滻.
19. apɳ,apx(at)px(Xt).
xXs,tT(,X)s,pxʱͶڳ.
,ǵõ¹.
 
(ae1) at=ttвԷ
(ae2) aݣInitt=Initt
(ae3) XInitt=Initt
(ae4) X-Initt=Initt
(ae5) a(t1=t2)(at1=at2)
(ae6) af(t1,...,tn)=f(at1,...,atn)fFEs1...sn,s
(eq1) x=x
(eq2) x=y(ppx(y))pвʱͶ
6  
Ľϴ淶һʱ߼һԵTrace.ۺ˵,Trace.
(1) Ƕ﷨ĳ.
(2) ͳһʱģͺʹģ,ԻڶǵĦE-Ϊ,ʱ߼ڦE-ϵԽ.
(3) 붯ϵĽ.ʹǿԷؿ̻Ч.
(4) һϵйƵ,һɿTrace.һʱ.䲿㡢һνԼʱ֮Ĺϵ.
Traceڲ״̬Ķ̬ʵ弰Ϊ.ǵĿǽһϵͳ.,TraceĻ֮,һǶе,ǽһо,ڱĵƪ:㣨񣩣򣩡з.
עоõȻѧ.
ͨѶϵ:, 100080,йѧԺоѧʵ
߼飺,1965,оԱ,ҪоΪ,,ֲ,Լ.
Ǯ,1966,ʿ,ҪоΪרۺͼ,ֲ,ʽ.
߱,1969,ʿ,ҪоΪרۺͼ,ģͼ.
ߵλΡйѧԺоѧʵҡ100080
Ǯ߱йѧԺо  100080
ο
1 ,,.ۺΪԼ.ѧ,1993,16(11):889897
(Feng Yu-lin, Li Jing, Huang Tao. Object semantics theory and behavior constraint deduction. Chinese Journal of Computers, 1993,16(11):889897)
2 ,,.ʽģ.ѧ,1995,6:207212
(Huang Tao, Feng Yu-lin, Li Jing. Model of object formal semantics. Journal of Software, 1995,6(Supplement):207212)
3 ,,߱.Լָ.ѧ,1996,7(10):577586
(Huang Tao, Feng Yu-lin, Ni Bin et al. Object description language and its denotation description. Journal of Software, 1996,7(10):577586)
4 Beeri C. Recent trends in data type specification. Astestiano E, Reggio G, Tarlecki A eds. Bulk Types and Query Language Design. LNCS 906, Berlin: Springer-Verlag, 1995
5 Ehrig H, Mahr B. Fundamentals of Algebraic Specifications 1: Equations and Initial Semantics. Berlin: Springer-Verlag, 1985
6 Kroger Fred. Temporal Logic of Programs. Berlin: Springer-Verlag, 1987
7 .ʽо ۲ʿѧλģ. Ϸ:йƼѧ,1994
(Huang Tao. Theoretical research on object formal semantics Ph.D. Thesis. Hefei: University of Science and Technology of China, 1994
1997-12-12յԭ,1998-09-04յ޸ĸ
