ѧ
Journal of Software
2000 Vol.11 No.1 P.67-72



ݷֽĲ򿪷

ժҪһִVDM-SL(Vienna development method-specification language)ԼĿ,ַDD-VDM(data decomposition-Vienna development method).ڴ˻ԭӡкڲеȸ,̶һǶṹЩ.ֱӹϵͳͷֲϵͳĽǶǶṹʵּ.
ؼʡʽ,ݷֽ,Ƕṹ,.
ͼšTP311
A Data-Decomposition-Based Development Method of Concurrent Object-Oriented Programs
YANG Da-junL Jian
(State Key Laboratory for Novel Software TechnologyNanjing UniversityNanjing210093)
YANG Da-junL Jian
(Institute of Computer SoftwareNanjing UniversityNanjing210093)
AbstractIn this paper, a method is proposed to develop a concurrent program from a VDMSL (Vienna development method-specification language) specification. On the basis of DD-VDM (data decomposition-Vienna development method), service parallelism, internal parallelism and virtual atomicity can be observed in the development process. Then a nested object-oriented structure is presented to specify these parallelisms. This nested structure can be implemented with several language structures for two different kinds of applications including share-variables parallel system and distributed parallel system.
Key wordsFormal method, data decomposition, nested object-oriented structure, concurrent object-oriented programming language.
ĽǵǰԵҪص֮һ1.Ȼ,߿ɿȵĲҪһ׺õʽ.VDM(Vienna development method)2ǵǰΪʽ֮һ,˳ĿкܶɹӦã3.νVDMӦڲгĿһֵֵ̽.ΪʹVDMпг,ף46rely/guarantee,˸Ľ.,ⷽ湤ص㿪ʼתƵ˼VDMл7,8.,VDMĲг򿪷һЩ,,˱VDMһʽDD-VDM(data-decomposition-Vienna development method)9,10.Ŀǰ,ַѵõͬеעϿ.ף11ýϴƪݷֽVDM++11,12еڿ˻֮Ĺϵ,һ˵ݷֽڲ򿪷еǱ.
ĲһVDM++ȫͬ;оĿ,һֻDD-VDMĲ򿪷,˵ĳϿݷֽתϵ˼VDM++е˻,ͬʱ˺Ϊ֤ȷԶӵĸ.˼,VDM-SL(Vienna development method-specification language)13ݱʾԼʼ,DD-VDMṩݾֽݷֽԾͷֽ,Ӷõӳ̵νṹ.Ȼ󽫴νṹֱӶӦһǶ׵Ĳƽṹ.,ɸֱӹϵͳͷֲϵͳĽǶȽǶ׵ƽṹһԻƼԱʾʵ,ӶɴVDM-SLԼĿ.ڴ˹,ûģ͵VDM-SLԼԼ,ȻؽDD-VDM˼л,ȻDD-VDMݷֽõĶֽصȻСڲкԭӵĸ.
1DD-VDMڶĲ
1.1DD-VDM
DD-VDMΪһ,VDMһʽԼͿ֤Ʋ.ĹԼʹVDMĹԼVDM-SL.DD-VDMVDMҪͬΪݷֽƲ,VDMеݾͲֽ⽻.DD-VDMҪ˼ݷֽ.ӸϽ,ݷֽģͷֽ⡢ӹԼγɡԼعͲ4.Ҫصͬģ͵.ϸݺӼף9.DD-VDMĻ,һʺϲĿ.
1.2Ҫ˼
ģ͹ԼԼ伫ΪǿṩȾݷֽӹԼĲཻΪǿṩ˻,ǵҪ˼ǻڴ..
(1) DD-VDMӦĿ.DD-VDMǽڻģ͹ԼĻϵ.ģ͵ĹԼҪһ״̬ĶͽڴģͻϵĲ.ף7,8,Խģ͵ĹԼԼ,ģ͵ķֽ⿴ķֽ,ģе״̬ԿǶ,ԿǷ.,DD-VDMƷѧ.
(2) ڲкͷ.ݷֽĹؼصͬӹԼĶ.,ԭԼе¹Լбֱֵӻӷֽϵķֽ,ôͿԱûе,ṩ˷.һ,ڲѹ,һԱʵΪڷֽз˳.ΪֽͬǱ˴˶,ǵķ䲻ڸ,,˳صÿתΪеĵ.ڲ.
(3) ԭ.ĬϵĹ,һһʱ̽һ,ִԭԵ.ڲ,һԭӶAֽܱΪηֽеĸСԭӶĲִ.ڴ˽׶,AѲԭӶ,ܹﵽԭӶЧ.ṩһԭ.ԭܹ˳ȷִ֤Ч.
(4) ݷֽǶṹ.,ͨṹַ֧кԭ,,Ƕ׵ṹֱӶӦʹDD-VDMõĿ,Ӷ֧.
(5) Ӳжȵת.Ϊķڲ,ϣͷķӲж.ף7,8еתԶһṩЧ֧.
1.3
ʹף9World˵ǵĿ.ͼ1ʾĿǾݷֽõ.ǿɽĿ.

Fig.1The development structure of World
ͼ1WorldĿṹ
(1) ڶMarriageвѺ.MarriageΪԷֱڲеMarriageMaleMarriageFemaleĵãݷֽص,MarriageֱӷֽΪе,
Marriage(m:Name,f:Name)
male.MarriageMale(m)female.MarriageMale(f);
end.
ֲо˵ڲ.֮ڸ,Ҫʹrely/guarantee.
(2) Ϊ{MarMal,SingMal,NewMal}{MarFem,SingFem,NewFem}ֱڲֽཻFemaleMale,,һеһһеһͬʱ.ֲоνķ.
(3) ΪֽFemaleMaleܹһֽΪСķֽ,,ԭԼеԭӶMarriageMaleMarriageFemaleֽܱΪεĸСԭӶCHGSM,CHGMM,CHGSF,CHGMFĲִ.ԭԾνԭ.
(4) Ϊ濪Ľ,ͼ2ʾǶṹʾ,World-o,Male-o,Female-o,SingMale-o,MarMale-o,SingFem-o,MarFem-oΪǲͬĶ.

Fig.2The nested object-oriented structure of World
ͼ2WorldǶ׵ṹ
ʽ˵,Ƕ׵ṹº壺
. Ƕ׵ṹṹ̵ֱӱʾ.
. ΪȷԼвʽЧ,ֻԭԼеķܹû.ⲿַPubʶеķҽܵڷֽе˽з.
. ǶṹִеԷʽ.һܴڻסƺͿ4״̬.һִһʱ,ڻ״̬.ڻ״̬ܱ.һڲڻ״̬ʱ,ס,סзܱ.һڻ״̬ʱ,,ƶйܱû,˽зܱ.һ󲻴κһ״̬ʱ,ڿ״̬.,֧ڲСкԭ.
. ڷ,һҪα֤ʽ,Ϊͬ״̬ռͬʱ.Ƕṹ屣֤ܹеķֱڲͬĶ,Ҳ˵,޸ŵ,,ǿԽп˳ִ,յĽһģ14.,÷˳ִеķʽʽ,ͱ֤˲ʽȷ.
(5) Ӳжȵת.ϸǶṹ,ͻᷢƲеĳЩ.һеķʱ,ڲͻܵ.ĳЩ,ǲҪ.ף7,8еת.,MarriageԽת

2Ƕ׽ṹʵת
ݷֽ,ǿԵõһǶ׵ṹ.Ƕ׽ṹǸƼ,ڿͨԸݲͬвͬʵ.
2.1Ƕṹֱʵ
Ƕ׽ṹԶΪԪ,ṹһ,,ֱʵͨغ.һ,ֱʵֳɵԪӦǶ.лԭͣ󣩵ԿһҪ.һ,ֱʵִָеӦڶṹ,Ҫͬƽ.ʵԿԺܺõƥǶṹ.α뽫.
object World
objects:
object Male
objects:
object SingMale
instance variables:...
methods:...
end SingMale
object MarMale
...
end MarMale
method:...
end Male
object Female
...
end Female
methods:
Pub Marriage(...)...
end World
ӿڿֿ.һǷļ,Ƕ׶бʶΪPubķ.һǶͷɵĶԪ,жǶ׶бʶΪPubĶ,ڴ˶жбʶΪPubķ,,Ƕ׶ûͿͨڲֱӵӦķ.ѡֽӿڷʽȡõʵԺͿ.ԭʽʵʿкʹ,ļʵ.
2.2ʵǶ׽ṹ
ʵֿֿܳǣһǶǶͨǶ׽,Ƕ׽ṹӳǶṹִ壻һǶǶ׽ṹͨĶṹʵ,Ƕ׽ṹƼʵ.
(1) Ƕ׻.Ƶ˼ǣ,ǶױΪǶ,Ϊʵ,ΪǶʵ,ڲûṩķ֮ӦĽӿ,Ӷڲ֮佨˿ͻϵ,ǶĽṹǰǶ׽ṹ,Ǽӵͨͬʵֵ,ڲҪǿڲⲿ˽ԺͶⲻɼ.ģͽĲ.
(2) ԭ.ݷֽΪṩһֿɲִеǶ׽ṹ.,ڶԴǶ׽ṹֱʵʱҪִ乤.˿ԽݷֽΪһ벢еĹ,һ˼ļ¼,˼¼ĳַʽӳڷǶ׽ṹ.ΪԭΪģͻָԭĵģ.ֵע,ݷֽõ˽з,Ϊ˱ԭģ͵,Ҫ߱(ͬ)ͶͬʱõĿԣУ.
ᵽĸʵַȱ,ʵʵĿ,ӦøӦĲ֧ͬŹߵĲͬԼʱƺϵͳѡ.
2.3Ƕ׽ṹתʵ
һǶ׽ṹ,ڲΪⲿһִڵ.,Ƕ׽ṹԣ,˶ڲĸã,Ƕ׵ĽṹӸֻڴڹĲϵͳ,ʺڷֲʽ.Ŀ,ĳЩ,Ƕ׵ĽṹתΪƽнṹǱҪ.תͼ3ʾ.

Fig.3Transformation from nested structure to flattened structure
ͼ3Ƕ׽ṹƽнṹת
תʵϾǽİϵתΪָϵ.VDM++˻ҪﵽĿ,Ϊ˱VDM++еĸ,תӦʵֽ׶.
ڽǶṹתΪƽṹʱ,Ϊ˱֤Ƕ׽ṹ,ת3.(1) ƽнṹ,Կͻ˽е,ͻӵз˽ָǶ׽ṹģ.˽ָͨ﷨Բݽʵ.(2) ûɼǿͻ,ܶԭڲֱӽдȡ,ΪԭԼһ.ҪڿͻṩûɼĽӿ.(3) Ƕ׽ṹĲӦƽнṹʹͬʵ.
Ƕ׽ṹ¼ÿһ,ЩǲҪġ.,ڽǶ׽ṹתƽнṹʱ,ԲһһӦ.WorldΪ,ͼ4ʾ3ɹѡƽнṹ.ƽнṹִԽṹʵ.ֵע,ӦѡԵĻʵԭǶ׽ṹ.

Fig.4Three kinds of transformations for the nested structure World
ͼ4Ƕ׶World3ת
3ᡡ
DD-VDMĻһʽĲĿ.ͼ5ʾ.VDMȻ,,ʹ.ֵָ,ʹDD-VDMݷֽõĲ,ṹ״,DD-VDMVDMеƲ,ʹܹӵĲк״Ľṹ.ݷֽһƲʹõrely/guaranteeĸӹ֤,Ϊṩ˿ѡ.ǽһĹҪVDM-SLĲԼƺͽлںϽµĿ֮.Ŀǰⷽоȡý׶Գɹ,ݽĽ.

Fig.5The concurrent object-oriented software process using DD-VDM
ͼ5DD-VDMĲĿ
оõȻѧNo.69873021863߿ƼĿNo.863-306-ZT02-02-03ʵǼƻ͹ҽܳѧNo.61525204
Ͼѧ¼صʵҡϾ210093ϾѧоϾ210093
Ͼѧ¼صʵҡϾ210093ϾѧоϾ210093
ο
1Yang Da-jun, Zhang Ming, L Jian. The study of concurrent object-oriented programming languages. Computer Research and Development, 1998,35(9):769775
(,,.о.о뷢չ,1998,36(9):769775)
2Jones C B. Systematic Software Development Using VDM. 2nd ed., Englewood Cliffs: Prentice-Hall, Inc., 1990
3Jones C B, Shaw R C F. Case Studies in Systematic Software Development. Englewood Cliffs: Prentice-Hall, Inc., 1990
4Jones C B. Development methods for computer programs including a notion of interface Ph.D. Thesis. Oxford University, 1981
5Jones C B. Specification and design of (parallel) programs. In: Proceedings of IFIP'83. North-Holland, 1983. 321332
6Stolen K. Development of parallel programs on shared data-structures Ph.D. Thesis. Manchester University, 1990
7Jones C B. Constraining interference in an object-oriented design method. In: Gaudel M C, Jouannaud J P eds. TAPSOFT'93: Theory and Practice of Software Development. Lecture Notes in Computer Science, London: Springer-Verlag, 1993. 136150
8Jones C B. A pi-calculus semantics for an object-based design notation. In: Best E ed. CONCUR'93: the 4th International Conference on Concurrent Theory. Lecture Notes in Computer Science, Berlin: Springer-Verlag, 1993. 158172
9L Jian, Zhang Jian-ying. A formal software development method DD-VDM. Journal of Software, 1996,7(supplement):385393
(,ŽӨ.ʽDD-VDM.ѧ,1996,7():385393)
10L Jian. Introducing data decomposition into VDM for tractable development of programs. ACM SIGPLAN Notices, 1995,30(9):4150
11Goldsack S, Lano K, Drr E H. Annealing and data decomposition in VDM++. ACM SIGPLAN Notices, 1996,31(4):3238
12Goldsack S J, Kent S J H. Formal Methods and Object Technology. London: Springer-Verlag, 1996. 86112
13Dawes J. The VDMSL Reference Guide. London: Pitman, 1991
14Apt K R, Olderog E R. Verification of Sequential and Concurrent Programs. 2nd ed., New York: Springer-Verlag, 1997
1998-11-13ո
1999-09-03޸
