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



̳м¼͵Ĵ
ǿ
ժҪͨͺͳ֮ת,ƹĶ.һ,һͿԲһĳ͵Ӽ.ʹü¼ģͳΪ.Ϊ֮ĵ̳йϵ,ɭ͹ĸ.˵ʽ,֤˵ʽгʼģ.
ؼʡ,ʽ,̳,¼.
ͼšTP311
Algebraic Description for Record Model with Single Inheritance
HE Zi-qiang
Department of Computer Science and Engineering Beijing University of 
Aeronautics and Astronautics Beijing100083
AbstractIntroducing the type transformation functions between subtypes and supertypes, the definition of order-sorted algebra is generalized. According to this definition, a type needn't be a subset of its supertype, and a record model may form an order-sorted algebra. The concept of forest-order signature is introduced for describing single inheritance relation between types. A new meaning of equation is given. It is proved that an equational theory has its initial model.
Key wordsOrder-sorted algebra, equational theory, single inheritance, record.
͵Ĵ͵Ĺ淶ʵַ뿪.һ淶һ,ʵǸ۵һģ.Ϊ˽ͺͻƺͼ̳,Goguenˣ1ݰѶƹΪ.Ϊ,ǳ͵Ӽ,͵Ԫؼǳ͵Ԫ.,״̬ʾΪ¼,Ǽ¼ļ.Cardelliˣ2,3ݶԼ¼ͽо.ڼ¼,ͳ˾г͵֮,и.еļ¼򵥵ؾǳеļ¼.Ϊʹ¼еͳΪӼ,Bruceˣ4Ȼ֮Ĳֵȼ۹ϵ,¼еԪضΪȼ.Ľ취Ȼ,ʹ⸴ӻ.ʵ,ͶԳ͵ļֻ̳ҪһҪʹóԪص,ʹ͵Ԫ.,Ҫͺͳ֮һת,еԪתΪеԪ.ʹͲһǳ͵Ӽ,¼ܹ,ʹо¼,͹ĵʽۿƻĽ,ʽ۵ģͿûʵ.
ǳ͵Ӽ,תǰӳ,ǶͳΪGoguen.,ƹGoguen.
ֻ֮ĵ̳йϵ.ڵ̳,һͲֱӳ,̳֮йϵĹ˹ͼͼϵɭ.,ǰѱﵥ̳Ե͹Ϊɭ͹.Ϊ˱֤ʽгʼģ,˿ɾɭ͹ĸ,ʹöÿ,ڱʾԪصĻ.
1ɭ͹ʹ
(S,)ƫ,sʾܵĶԳƱհ,ܱʾsԷݱհ.s1,s2S.s1s s2,s1s2ɱȽ.,s1s2ͨ.
1. (S,)ƫ.SɱȽϵԪs1s2,SԪs3,ʹs3s1s3s2,(S,)ɭ.
Ϊ͵ĵ̳йϵ,һûжһֱӳ,ɭ򼯱͵ĵ̳йϵ.
ԽSϵĶԪϵܺ͡sع㵽ŴļS*:
s1...sns1...sm iff n=ms1s1...snsn,
s1...sns s1...sm iff n=m s1s s1...sns sn.
2. ɭ͹һԪż(S,,),(S,)һɭ,һؼ{w,swS*,sS},µ:
w1,w2S*,s1,s2S,w1,s1ɦw2,s2w1w2,s1s2.
SеԪسΪ,w,sеԪسΪ.ҡʦw,s,˵wֵs,Ϊ:ws,:šsΪ:s,Цǿմ.{wwS*,sSʹҡʦw,s}Ϊҵȼ,Ϊar().ҵȼжһԪ,ƦǶ̬.
3. ɭ͹(S,,):
w1,w2ar()w1s w2,w1w2w2w1,
ͳ(S,,).
. (S,,)ɭ͹,,wS*.{wwar(),ww}ǿ,СԪ,ΪwϵС.
֤:ֻ֤üһ.wǿմ,üǵԪؼ{}.wǷǿմs1...sn.s1...sn,s1...snar(),s1...sns1...sn,s1...sns1...sn,ÿin,sisi,sisi,(S,)ɭ֪,sis si.,s1...sns s1...sn.(S,,)ĵó,s1...sns1...sns1...sns1...sn.
ڼϴ{AssS},As1...snʾAs1...Asn.
4. (S,,)A3Ԫż:

ÿAsǷǿռ,Ϊ.s1s2,As1ΪAs2,ҲAs2As1ĳ.As1As2תAs1s2:As1As2,w,sеұʾ.
(1) ÿsS,AssSϵĺͬӳ䣻
(2) s1s2,s2s3,As1s3As1s2As2s3ĸϺAs2s3As1s2
(3) ҡʦs1...sn,sɦs1...sn,ss1...sns1...sn,ÿ(x1,...,xn)As1...sn,

5. A(S,,),s,s1,s2S,s1s,s2s,a1As1,a2As2.As1s(a1)=As2s(a2),a1a2As,Ϊa1=Asa2.
6. AB(S,,).h={hs:AsBssS}:
(1) s1,...,sn,sS,ҡʦs1...sn,s,
,һ(x1,...,xn)As1...sn;
(2) s1s2,Bs1s2(hs1(x))=hs2(As1s2(x)),һxAs1,
hΪAB̬ͬӳ.̬ͬӳhеÿhs˫,hΪͬӳ.ڴABͬӳ,ABͬ.
2ʽۺĳʼģ
Լ漰ɭ͹,ÿԪΨһSԪΪ,(S,,)AеĸֵvsıԪAsеԪΪֵ.
7. ɭ͹(S,,)tso(t):
(1) xΪsıԪ,xΪs;
(2) ҡʦs1...sn,s,t1,...,tn,s1...snǦҵso(t1)...so(tn)ϵС,(t1,...,tn)Ϊs.
8. t(S,,)AAиֵvָԪA(t)(v):
(1) tǱԪx,A(t)(v)=v(x);
(2) tǦ(t1,...,tn),s1...snǦҵso(t1)...so(tn)ϵС,

ֱԪΪ.t븳ֵ޹,,ɽA(t)(v)ΪA(t).
9. t1t2(S,,),sS,so(t1)s,so(t2)s,t1=s t2(S,,)ʽ.һ(S,,)ʽɵļ,((S,,),)Ϊʽ.
10. t1=s t2(S,,)ʽ,(S,,)Aÿֵv,A(t1)(v)=AsA(t2)(v),t1=s t2AЧ,ΪAt1=s t2.
11. еÿʽ(S,,)AЧ,Aǵʽ((S,,),)ģ.((S,,),)ģAÿģΨһ̬ͬӳ,AΪ((S,,),)ĳʼģ.
12. SSСӼ:
(1) ,sǷǿռ,sS;
(2) s1Ss1s2,s2S;
(3) s1,...,snSҦs1...sn,sǷǿռ,sS.
S=S,ɭ͹(S,,)Ϊɾ.
(S,,)ǿɾɭ͹,ÿsS,ڻtʹso(t)s.,ÿͶָԪصĻ,Ᵽ֤涨ĵ䷶еÿͶǷǿյ.Լ,ۿɾɭ͹.
((S,,),)ǵʽ.ÿsS,Ƕ弯{t|tǻ,so(t)s}ϵĵȼ۹ϵs:
t1s t2ҽ((S,,),)ÿģA,A(t1)=AsA(t2).
sĻt,ãtsʾtڵĹڡsĵȼ.
13. ʽ((S,,),)ĵ䷶C£
(1) ÿsS,Cs={tstǻ,so(t)s};
(2) s1s2,Cs1s2(ts1)=ts2;
(3) ҡʦs1...sn,s,.
1. C((S,,),)ģ,CΪ((S,,),)ĵ䷶ģ.
֤:ȡеʽt=s uCиֵv,Cso(t)s(C(t)(v))=Cso(u)s(C(u)(v)).
2. ʽ((S,,),)ĵ䷶ģCĳʼģ.
֤:C((S,,),)ģAΨһ̬ͬӳhΪhs(ts)=Aso(t)s(A(t)).
1:ϡؼջǿջĴ淶ɱʾΪĵʽ.
һɭ͹(S,,).S={j,d,z,f,s},j,d,z,f,sֱǼϡؼջǿջĺƴĵ1ĸ.S϶Ԫϵ{s,f,f,z,z,d,d,j}Էݱհ.е:
:jjj,:ddd,0:s,succ:ss,
push:szf,pop:fz,top:fs,empty:z.
ü±x,y,zʾԪ,±ǱԪ.еĵʽ£
top(push(xs,yz))=s xs,pop(push(xs,yz))=z yz,push(xs,empty)=f xs,
push(xs,push(ys,zz))=d push(ys,push(xs,zz)),ؼԪسֵĴ
push(xs,push(xs,yz))=j push(xs,yz),ϲԪصĳִ
push(xs,yz)=d xsyz,ؼһԪʹԪص1
ȡʽ((S,,),)ģA:
As=N(Ȼ);Af=N+;Az=N*;
Ad={gg:NN,{n|g(n)0}},g(n)nڶؼgе;
Aj=NӼɵļ.
Asf(n)=n(Ϊ1Ĵ),ÿnN;
Afz(w)=w,ÿwN+;
ÿwN*,Azd(w)=gw,gw(n)=nwеĳִ,ÿnN;
Adj(g)={nnN,g(n)0},ÿgAd.

ÿnN,wN*,
g1,g2Ad,,g(n)=g1(n)+g2(n),ÿnN;
,NӼBC.
A((S,,),)ĵ䷶ģͬ,Ǹô淶һȷʵ.
ͨѶϵˣǿ, 100083,պѧѧ빤ϵ
߼顡ǿ,1943,,ҪоΪ߼,Եʽ.
ߵλպѧѧ빤ϵ100083
ο
1Goguen J A, Meseguer J. Order-sorted algebra : equational deduction for multiple inheritance, overloading, exceptions and partial operations. Theoretical Computer Science, 1992,105(2):217273
2Cardelli L, Mitchell J C. Operations on records. Mathematical Structures in Computer Science, 1991,1(1):348
3Cardelli L. Extensible records in a pure calculus of subtyping. In: Gunter C A, Mitchell J C eds. Theoretical Aspects of Object-oriented Programming. Cambridge: MIT Press, 1994. 373425
4Bruce K B, Longo G. A modest model of records, inheritance, and bounded quantification. Information and Com-putation, 1990,87(1,2):196240
1997-04-10յԭ,1998-05-12յ޸ĸ
