о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999Vol.36No.6P.695-704



ND-Polyaʵּ
ժҪʶۺͷ۵ĽǶ಻ʶΨһͬʮҪ.Ȼͳļַֻ̳ķ.ƵND-Polyaͨµļ̳лơԼ̳֧ȷ.ʹԼ̳лƣԱԵķʽ.мҪND-PolyaԼ̳ʩڴ˻Ͼ˸ûƵʵּ.
ؼʣԼ̳УND-Polyaȣʵ
ţTP311
THE IMPLEMENTATION TECHNIQUES OF 
THE ANALOGY IN ND\|POLYA
MA Xiao-XingTANG BaoTAO Xian-PingYI BoL Jian
(State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093)
(Institute of Computer Software,Nanjing University,Nanjing 210093)
AbstractAnalogy is a very important method for cognition and solving problems besides classification in the view of epistemology and methodology. However, the traditional inheritance only reflects the idea of classification. The ND-Polya language supports the analogy in object-oriented programming by providing a new inheritance mechanismsoft-inheritance, with which one can develop a new software system by describing its similarity to an existing system. After giving a brief introduction to the soft-inheritance facilities in the self-designed language ND-Polya, the implementation techniques of the soft-inheritance are discussed in detail.
Key wordssoft-inheritance, ND-Polya,analogy,implementation
1
νָ˼ߴĳͼȥϵͳ.ͼϣƴΪȷĶӦϵϣֶӦϵܰĵ1.ʶҪҲǽЧֶΣ෽һ𹹳ʶвɷָ2.
̳֧緶ĺĻ֮һ˶̬ĻΪ븴ṩЧ;.ȻԵļ̳лǻеġӲԵļ̳УڸֵǷ֧ʶͬҲҪȷ.ʹʱ͸˾ĸ;Ľָøõизĳֳ󣬶䱾Ҳ˵߽.еļ̳лƶԴΪ.
ΪˣۺͷΪһ͵ļ̳лơԼ̳л.͵Լ̳лƣͨǰһʵֵ֮ԺԵķʽ࣬ɻͨȷƵֵأԶʵ֣ӶõԴʼĸ.ͽȳƵ˼ӦƷӶ˸õĲκ.
ND-PolyaƵһԣṩһ֧ȵԼ̳ʩûʹĿԴԣȻϵͳȷƵԶɸʵ.Լ̳еĸND-PolyaԵƽϸֻۣҪ.Լ̳лһµԻƣʵּоһʮѵ.ĹصҪǻڶۺͷоɹ25ݣһֻġ̽ṹͨǲֲ֧ͬӦȣͨԭӵ⣬ϺõʵND-PolyaṩԼ̳л.
2ND-Polyaеʩ
ƵһֻĳЩԣڶһԪɻΪһԪνʣ.ͬƣҪԺͳʽ.ʽжԵƳ򵥵ͬνԲͬĲͬ⣬ܲͬƵķʽҲֶ.磬볤οȣεĶǶάĶά㣻ԭӽṹϵͳϵϵͳȣԭеĵϵеƣƵķʽǵɶܵã.ṩؼaswhereƷʽ.ڶӿɱΪ
class ԭӽṹϵͳ  ϵϵͳ {
  as   where{ . .};

}
ʵѷſ˴ͳ̳вضԵ.
GentnerΪ6ݣУϵͳеĹϵҪö.ΪǹġʣϵϵͳеĽṹҪڹϵ.̻ϵϵĸ߽׹ϵܽʾϵͳڱʣӳϵͳĶ̬ΪҪ.ԣģ֣֮ǲģӦ߼ṹ֮佨ȷĶӦϵ.ƽϵĵ(2DP)Ϳռϵĵ(3DP)ƣԽ2DP3DP֮ȶӦȣ2DPеx,yƣӦΪһ飬ͬ3DPеx,y,zƣҲΪһ飬֮佨Ӧ.ӦأmoveĲҲҪΪһ飬.Ǿͼ1ĶӦ.ӿԿڽӦǰƵԻֳ飬ӶƽġĽṹתΪһֳġ̡ṹ̽ṹĳ̶ֳи߽߼ϵ.̽ṹ֮佨ͬϵǾΪ֮ͽõȶӦ.Gentnerṹӳ(structure mapping)ϵͳԭ(systematicity principle)ָڸ߽׹ϵϵµĹϵֲϵͳонϸߵĿŶ.ͬ̽ṹƵķҲӦнϸߵȷ.


ͼ1
ôõ̽ṹ˵ûϵͳṩԷϢأPolyaṩ3ֶϢ.1ַһֳϵİʾ2DPеxyڱ˵ʱд
int x, y;
д
int x;
int y;
һ,ͬͬͱӦͬһ˵˵.ʵһõĳд.2ַڷʽвķ飬öָ÷ָֺͬ.3ַ˵Եԣ磬3DPжz˵Ӧд
int z like x,y;
һ±zͬʱָzxyƣӦΪһ.
ڽȵδз涼ƣʱֻҪвȣʱӦڣԣ̳ʱԴĳЩʹĳЩԺͷɼ
discards SomethingNotNeeded;
ûֶͨԴĿ֮ԣϵͳЩϢ֮佨ȶӦϵͨԶȷʵ.3DPеmoveֻɣ
3DP move(int dx,int dy,int dz) from 2DP move(int dx,int dy);
moveľʵּϵͳƵó.Ӿμ¼.
ûʵԵʶԴĿ֮ԣԭԼȵĺԸ.Լ̳лƽûṩϢǷìܣĳЩȶӦ޷ƵĴʹԼϢǷ֣ԽƵ.ϢֻìʱϵͳʾûһǷȵǷǡ.
3ϵͳʵ
ǵϵͳND-Polya༭PolyaJavaķϵͳJavaı롢ϵͳ.зϵͳǹؼĹʵֵ.֮ȰĹȣҪȷ֮ƹϵҲǴӣ֣ṹȶӦóṹȶӦȷȻԴࣨϵͳͨȶӦֲĿࣨϵͳУӶõĿʵ֣ҲƵ.ûύPolyaԴͬõJavaԴϳΪPolyaԴύ﷨ȷһøϢ﷨תչµ﷨Java.ϵͳṹͼ2ʾ.


ͼ2
3.1﷨ȷ
ڽƵ֮ǰҪND-PolyaԴ﷨ȷ.һУй
(1) Ƶԣóı뼼LexYACCȹߵĸ±ƴʷ﷨򣬶ԴɨʶųʷһЩ򵥵﷨ͬʱԵϵؽһ﷨.
(2) ű.﷨еĸʶԽ͡ϵڷűӦӶһϵ﷨еĶ㣻һųʶ޶֮Ĵ.һĹ﷨Զµݹ½ؽ.
(3) ڶԱʶн͵ͬʱϢռͷԴĿ֮ƶӦϵԵķϢ֮ƶӦϵ.ʱųϢìܴ.ֵעǣϢҲģǵĴҲӦ﷨Ƕײνṹ.
(4) ̬ͼ.Ҫһľ̬ͼ⣬ǻҪԼ飬ҪǼasӾ.ǰΪBtԴΪAĳsҪBAȣݣͨsõAԻ򷽷BоȷĶӦ֤㹻ȶӦϢ.¼ĳЩ;ͬķʵ͵ļӷ͵ļӷм̳йϵеͬһԻ򷽷ض壩ʹwhereӾʽ˵˵ĶӦԻ򷽷. 
ڣǵõһѳֽ͵﷨ԼϵϢͿԽԵõĿʵ.
3.2ʵֵ
Ϊ˵õĿʵ֣ȸһԴ﷨ȻϢתΪĿ﷨.ΪУת.
3.2.1ת
ȵԴĿڲͬ.һϵͳôԴĿ;вͬġ.﷨Դġ򡱣Ϊ򣩱任Ŀġ򡱣Ϊ򣩵Ĺǳ֮Ϊת.
תҪǻ﷨ݹ½ؽ.ÿһ﷨ΣȽϵڱ﷨ڵϢеĻһ﷨μ̳ЧϢϲγɵǰЧϢȻԱڵĸ﷨ɷֵݹؽлֱɸݵǰЧϢֱӾδĵʶ.
﷨ͬʱҲƻԭеϵ.뱣֤﷨ʹ.ʱʹ˵ȲԭûʹwhereӾָȶӦìܣӦû.
һһֵ⣺δʱͣһְ취ڱдԴEiffelеġlikeƣͬlikeҪʱϵڷʱҲһõĳ.JavaвֻƣǾһַĳЩʽԸʱͽв²⣬ʹЩʽƥ.²ĽʹñγʹǾΪ²ɹ.Ȼ²ⲻһܳɹɹҲܱ֤ȷڴܲ³ȷ͵.
һΪֹǵϵͳѾ߱൱ܴԴƵֱӣͬĿ࣬ЧЩһеģ/ƣȻ֮ȣȻŵ㣺
(1) ȻƲҪȳ.ģҪʹ֮ǰѾƵ򷽷󣬲дģĸʽ.ʵʵıʵУǳڽʱŷ֪ƣԸд룬ȻʱֲԸصرдһģ.
(2) ģȣȻƸ̣ܸǿ.磬ȻƲԻһĳԵͣһܻԣΪһ󣩵ԺͷͨwhereӾ䣩ģ.
(3) ȻƲƵԴֱͬĿ࣬ҪͨƵԴ̽ṹͬĿ࣬Ӷӵ.Ǿ.
3.2.2
ڽʱǰٵ֪Ҫø.ǰָǵǽ̽ṹͬĻϵģĸԾͱΪĿԵƶӦ.2пռĵƽĵȵУ3DP顴x,y,zͱ2DPӦ顴x,y.£ҪõĿʵ־ͱشӦı任.ж໥ʱñȽϸ.ǽϸ۶Դŵ㷨.
﷨Ͻ.Ϊ˷һЩ
(1) Ե
﷨ͬ ҶڵҶڵͬ.﷨T(T1,T2,,Tn) S(S1,S2,Sn)ͬҽTS Ϊͬ﷨ṹTiSiͬ(i=1,2,,n);
Աʾ һ﷨SɿʩҶڵϵĳֲ.OPsʾò(ͬ﷨ͬĲ)SɱʾΪ
OPs(n1,n2,,nk)
n1,n2,,nkΪȸSҶڵ.֪ñʾΨһڵ.
۶ԵȣͬOP(n1,n2,,nk)OP(m1,m2,,mk)Եȵҽnimi(i=1,2,,k) ֮һ
1) ͬ.
2) Ϊ.
3) Ϊֲͬ.
4) Ϊͬһ֮.
5) Ϊ޹صķǾֲ.
ȻĶԵȹϵһֵȼ۹ϵ.ʵֵǴһֻڱƹϵġԳơĹϵ.
(2) ŵĻ
 ŵĻĳǡΪ(ظ©)ĳһGȫΪŵĻ.
 ŵĻ
OP1(n11,n12,,n1k);
OP2(n21,n22,,n2k);

OPs(ns1,ns2,nsk);
ͬʱ򹹳һŵĻ 
1) Ե.
2) nit(1is,1tk) ΪĳһG֮еj (j=1,2,,s)njtͬǡùGŵĻ.
3) ٴһt(1tk), njt(j=1,2,,s)ǾֲǡùĳGŵĻ.
4) r(1rk), njr(j=1,2,,s)ΪֲҪôȫͬҪôͬںһһ,ЩֲɸŵĻŵ±ҲµľֲڷǾֲŵı.
5) r,t(1r<tk), njrΪG1ŵĻ, njtΪG2ŵĻG1G2ŵıӦͬ.
6) r,t(1r<tk), njr(j=1,2,,s), njt(j=1,2,,s)ΪͬһGŵĻ
njr=njt, (j=1,2,,s).
νŵĻʵǴдŵĺʵĶԳƽṹ16֤һ˵С.
.ǴĲڲͬĶӦҶڵУ﷨ĽṹܲʺĲҪ任ΪԱʾԻʵһָָҶڵ.ǵ㷨ϻ﷨ݹؽУֻҪȵ˳򣬼С﷨ԪŴ﷨Ԫ.ÿһŵ﷨Σڵ㣩Ƚͬ﷨ֱԻһȻ鿴ǷдŵĻ.ÿҵһŻ
OP1(n11,n12,,n1k);
OP2(n21,n22,,n2k);

OPs(ns1,ns2,nsk);
һų
OPs+1(ns+11,ns+12,ns+1k);

OPr(nr1,nr2,nrk);
ŵĹǣ
 ÿųԵԭ.
 njt(j=1,2,,s)ͬnjt(j=1,2,,r)ͬ
 njt(j=1,2,,s)ǡùĳGŵĻnjt(j=s+1,s+2,,r)ǡΪGŵı
 njt(j=1,2,,s) Ϊֲnjt(j=s+1,s+2,,r)Ϊµľֲ
 njt(j=1,2,,s)Ϊ޹֮ȫֱnjt(j=s+1,s+2,,r)Ϊȫֱ
 njt(j=1,2,,s) Ϊnjt(j=s+1,s+2,,r)ΪֵҪʾû.
ųظزͱ﷨ڵ.ϲ裬ֱдŵĻ.
3.3
󣬽Ƶ﷨ԭΪJavaԴ.һ﷨ƵĹӦ﷨ɷֵĻʹĳֳһ־״ķĶҪ.
4ᡡ
ļҪģND-Polya֧Լ̳еʩϸظʵּ.ѾC++SUN SolarisʵND-PolyaͨһЩʵаһƽͼת任ϵͳȵõͼת任ϵͳɲμ¼.
ͨʵΪͨƵʵֵԼ̳һĴ븴ûƣͬʱȳµĳƵ˼ͷ൱Ӧǰ.
ʹND-PolyaԽȳƣ˿ֱӸһЩԭԸõĸʹ⣬һǱڵĺôĳЩαΪԴĻͿԽܽΪģ塢ܻģʽпγһԶģʽ;.һֵüо.
 ¼
Уһɽƽģ͵ƽơתȱ任ϵͳ(ͼ3)Ҫһģ͵ı任ϵͳ(ͼ4).ǵļ֪ʶάռάռƵ.ȥϵͳ˼ʹ.һӳƺͼͼѧĽǶȷϵͳӦƵĽṹƵĹؼ㷨ξĳ˷иϱ任.Ȼϵͳӽṹ㷨˼붼ƣͳĻеĴ븴÷̳СȣȴΪ.ʹȵ˼룬Լ̳еֶΣǿظеĳ򣬷ؿάģת任ϵͳ.ʹǵԿĲֽ¼.ԭеĶάϵͳȿάϵͳƵĲJava.
//ƽ㼰ƽת仯
class Point {
float x, y;
void move(float dx, float dy) {
x += dx;
y += dy; }
float distance(Point p) {
return (float)Math.sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y)); }
//ԭת
void rot(double theta) { 
theta *= (3.14159 / 180);
double ct = Math.cos(theta);
double st = Math.sin(theta);
float Ny =(float)(y*ct+x*st);
float Nx =(float)(x*ct-y*st);
x = Nx;
y = Ny; }
//ȥһЩ

}
//ƽģͱ任ξ˷ȣ
class Matrix {
Point po, px, py;
//ת
void rot(double theta) {
po.rot(theta);
px.rot(theta);
py.rot(theta); }
//ƽ渴ϱ任ξ˷:
void mult(Matrix2D rhs) {
Point lx=new Point(),ly=new Point(); 
Point lo=new Point;
lx.x = px.x * rhs.px.x + px.y * rhs.px.y ; 
ly.x = py.x * rhs.px.x + py.y * rhs.px.y ;
lo.x = po.x * rhs.px.x + po.y * rhs.px.y ;
lo.x += rhs.po.x;
lx.y = px.x * rhs.py.x + px.y * rhs.py.y ;
ly.y = py.x * rhs.py.x + py.y * rhs.py.y ;
lo.y = po.x * rhs.py.x + po.y * rhs.py.y ;
lo.y += rhs.po.y;
px.x = lx.x;
py.x = ly.x;
po.x = lo.x;
px.y = lx.y;
py.y = ly.y;
po.y = lo.y; }
//ȥһЩ
 }
class Model{
//ʹPointMatrixʵƽģͼתȹ.
 }
class TwoD extends Applet {
//ʾƽģͱ任Ч.
 }

//****************************

//Ӷάȳά㣺
class Point3D  Point {
float z like x,y;

void move(float dx, float dy, float dz) as move(float dx, float dy);
void distance(Point3D p) as distance(Point p);
//άռתάȣԲͬȷʽӶάռתȵõ
void roty(double theta) from rot(double theta) where{ x, z  Point.x, Point.y };
void rotx(double theta) from rot(double theta) where{ y, z  Point.x, Point.y }; 
void rotz(double theta) from rot(double theta) where{ x, y  Point.x, Point.y }; 
 }
//Ӷάξȳάؼ㷨 
class Matrix3D  Matix {
Point3D po,px,py as Point po,px,py where { x, y, z  x, y };
void rotx(double theta) from rot(double theta) where { Point3D.rotx()  Point.rot() };
void roty(double theta) from rot(double theta) where { Point3D.roty()  Point.rot() };
void rotz(double theta) from rot(double theta) where { Point3D.rotz()  Point.rot() } ;
//˴ͬһͿ άξ˷ 
void mult(Matrix3D rhs) from mult(Matrix2D rhs) 
where { Point3D.x,Point3D.y,Point3D.z  Point.x,Point.y };
 }
class Model3D  Model { //...  }
class ThreeD  TwoD {  //...  }
ƵPoint3DMatrix3DĲֽ
class Point3D extends java.lang.Object
{
float x, y, z;
... ...
void move(float dx,float dy,float dz)
{
x+=dx;
y+=dy;
z+=dz;
}
float distance(Point3D p)
{
return (float)Math.sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)+(z-p.z)*(z-p.z)) ;
};
void roty(double theta)
{
theta*=(pi/180);
double ct=Math.cos(theta);
double st=Math.sin(theta);
float Ny=(float)(z*ct+x*st);
float Nx=(float)(x*ct-z*st);
x=Nx;
z=Ny;
}
//rotx  rotz  roty ơΪʡƪ˴. 
}
class Matrix3D extends java.lang.Object
{
Point3D po=new Point3D(), px=new Point3D(), py=new Point3D();
void roty(double theta)
{
po.roty(theta);
px.roty(theta);
py.roty(theta);
pz.roty(theta);
}
//rotx  rotz  roty ƣΪʡƪ˴.
//Ƶάξ˷
void mult(Matrix3D rhs)
{
Point3D lx=new Point3D(), ly=new Point3D(), lxnew0=new Point3D();
Point3D lo=new Point3D();
lx.x=px.x*rhs.px.x+px.y*rhs.px.y+px.z*rhs.px.z;
ly.x=py.x*rhs.px.x+py.y*rhs.px.y+py.z*rhs.px.z;
lo.x=po.x*rhs.px.x+po.y*rhs.px.y+po.z*rhs.px.z;
lo.x+=rhs.po.x;
lx.y=px.x*rhs.py.x+px.y*rhs.py.y+px.z*rhs.py.z;
ly.y=py.x*rhs.py.x+py.y*rhs.py.y+py.z*rhs.py.z;
lx_new0.x=pz.x*rhs.px.x+pz.y*rhs.px.y+pz.z*rhs.px.z;
lx.z=px.x*rhs.pz.x+px.y*rhs.pz.y+px.z*rhs.pz.z;
lx_new0.z=pz.x*rhs.pz.x+pz.y*rhs.pz.y+pz.z*rhs.pz.z;
ly.z=py.x*rhs.pz.x+py.y*rhs.pz.y+py.z*rhs.pz.z;
lx_new0.y=pz.x*rhs.py.x+pz.y*rhs.py.y+pz.z*rhs.py.z;
lo.y=po.x*rhs.py.x+po.y*rhs.py.y+po.z*rhs.py.z;
lo.z=po.x*rhs.pz.x+po.y*rhs.pz.y+po.z*rhs.pz.z;
lo.y+=rhs.po.y;
lo.z+=rhs.po.z;
px.x=lx.x;
py.x=ly.x;
po.x=lo.x;
px.y=lx.y;
py.y=ly.y;
pz.x=lx_new0.x;
px.z=lx.z;
pz.z=lx_new0.z;
py.z=ly.z;
pz.y=lx_new0.y;
po.y=lo.y;
po.z=lo.z;
}
... ...
Point3D pz=new Point3D();
}
... ...

ͼ3ƽģ͵ת

ͼ4ģ͵ת
ллND_PolyaͬѧľϺ.ǣ誡·.
ĿõȻѧ(Ŀ69473038)ҽܳѧ(Ŀ61525204)ͽʡ(ĿBQ96005).
߼飺ǣУ19758˶ʿоҪоӦÿܺ衡ģʽ.
ƱУ19745˶ʿоҪо򣺲.
ƽУ19703ʿоʦҪоԶAgent.
У195811ڣҪоۡԶ.
У196010ڣʿʦϾѧ¼صʵ顡Σйѧ£оԶʽԼ
.
ߵλǣϾѧ¼صʵҡϾ210093
ƱϾѧ¼صʵҡϾ210093
ƽϾѧ¼صʵҡϾ210093
Ͼѧ¼صʵҡϾ210093
Ͼѧ¼صʵҡϾ210093
ǣϾѧоϾ210093
ƱϾѧоϾ210093
ƽϾѧоϾ210093
ϾѧоϾ210093
ϾѧоϾ210093
οף
1Ҹ..ѧ198916(4)18
(Yi Bo,Xu Jiafu.A survey on analogy reasoning.Computer Science (in Chinese),1989,16(4):18)
2Ҹ.ģͺȶӦ.йѧ(A)199222(1):8793
(Yi Bo,Xu Jiafu.Analogy mode and analogy correspondence.Science in China (A) (in Chinese),1992,35(3),374384)
3Yi Bo,Xu Jiafa.Analogical type theory.Symbolic Computation,1995,19(1):3244Yi Bo,Xu Jiafu.Analogy calculus.Theoretical Computer Science,1993,113(2):211230
5L Jianguo, Xu Jiafu.Analogical program derivation based on type theory.Theoretical Computer Science,1993,113(2):259272
6entner D.Structure mapping:A theoretical framework for analogy.Cognitive Science,1983,7:155170
ոڣ1998-08-19
޸ڣ1998-11-23
