用变换型方法模拟开发电话交换系统 屈婉玲 张乃孝 (北京大学计算机科学技术系) 摘要：本文给出了用变换型软件开发方法(Specification+Transformation= Software)模拟开发电话交换系统的描述,由抽象的软件规范出发,通过一系列变 换实现了数据的精化和运算的分解,最终得到可在机器上运行的程序.整个开发 过程是用变换型语言Polya写的.最后提出了对Polya的改进建议.　 关键词: 程序变换,语言,软件开发方法 　　　　　　　　 一. 电话交换系统的简单描述 电话交换系统Exchange由用户号码集Subs,呼叫线集callset组成[1]. 一条 呼叫线call的状态转换由图1所示.其中的Lift,Dial为呼叫方的操作,Relift为 接收方的操作,Clear为呼叫方或接收方的操作,Sy1,Sy2,Sy3,Sy4为系统操作. ┌───────────────────────────────┐ │ Clear ↑ ↑Clear ↑ 放听筒Clear ↑放听筒Clear ↑ │ 放│ 放│ ┏━━┷━━━┓ ┏━┷━━┓ │ │ 听│ 听│ ┃unobtainable┃ ┃ engaged┃ │ │ 筒│ 筒│ ┗━━━━━━┛ ┗━━━━┛ │ │ │ │ Sy1↑不正确 Sy3↑对方占线 │ │ │ └───┐│ │ │ ↓ Lift ┏━┷━┓Dial┏━┷━━┷━┓Sy2 ┏━━┷━━┓ Clear│ ─────→┃seize ┠─→┃ dialing ┠─→┃connecting┠──→  ↑拿听筒┗━━━┛拨号┗━━━━━┯┛正确┗━━┯━━┛放听筒↑ │ ↑ 未拨完 │ Sy4│对方不 │ │ └────┘ │占线 │ │ ↓ │ │ Clear ┏━━━━┓ Relift ┏━━━━┓ Clear│ └──────────┨ speech ┃←────┨ ringing┠──→┘ 放听筒 ┗━━━━┛对方拿听筒┗━━━━┛放听筒 图1. 呼叫线的状态转换图 1. 电话交换系统的状态定义 用户号码集 Subs 有效拨号集 Valid={n:十进制数字序列 s(s Subs n是s的前缀)} 电话呼叫线状态集 State={seize,dialling,connecting,ringing, speech,engaged,unobtainable} 一条呼叫线 call=u1→(s,u2),其中u1是呼叫方的号码,s是呼叫线的状态,u2为 该状态下呼叫方已拨完的数字序列(可能是接收方号码的前缀,也可能是一个错误的 号码).call callset. 用户号码集Subs被划分成三类:Free,Unavail,Busy.Free是闲置待用的号码集, Unavail是系统中已不能使用的号码集, Busy是呼叫方和在speech或ringing状态下 的接收方的号码集. ──────────────────────────── * 本项研究得到国家自然科学基金和 863 项目的资助 2. 系统初始化状态 Free=Subs,Busy={ },Unavail={ },callset={ }. 3. 系统的外部操作 操 作 输 入 输 出 前 置 条 件 Lift e:Exchange,u1:Subs e':Exchange u1 Free Dial e:Exchange e':Exchange u1的呼叫线状态是 u1:Subs,d:Digit seize或dialling Clear e:Exchange,u:Subs e':Exchange u是呼叫方或u是Speech 状态下的接收方 Relift e:Exchange,u2:Subs e':Exchange 呼叫线状态是ringing 呼叫号码是u2 Repair e:Exchange,u:Subs e':Exchange u Unavail '埰渲蠨ight是十进制数字,Repair是根据用户的要求将失效的电话修好的操作. 二. 用变换型方法开发电话交换系统 Polya语言是一种变换型的语言,它具有一个强有力的类型定义子语言和一种定 义和控制程序变换的机制——变换模块和变换命令[2],[3],[4].一个变换模块给出 一组相关的规则, 这些规则定义了一个抽象数据类型的一种具体表示形式和这个抽 象数据类型部分操作的实现细节.变换的控制是通过将"变换实例"作用于要变换的 变量来完成. 变换实例可以是一个简单的模块名(无参的情况), 或者(在有参的情 况)是一个变换模块名后缀以适当的实参,这时变换所使用的是用实参进行实例化以 后的变换模块. 变换模块的一般形式是: TRANSFORM 变换模块名[(参数表)] /*首部*/ DECLARATION /*说明部分*/ REPR 抽象变量说明 USING 表示变量说明 RULES /*规则部分*/ REPR 抽象表达式 USING 表示表达式 REWRITE 抽象表达式 USING 重写表达式 REPLACE 抽象语句 using 置换语句 WITH /*规则右部用到的局部过程或函数的说明*/ END; '埰渲衃 ]为元语言符号,表示可省缺.说明部分定义了本变换模块中使用的抽象变量, 抽象类型,表示变量,表示类型以及抽象变量和表示变量之间的关系.变换的规则分 为三类,分别称为表示规则(REPR),重写规则(REWEITE)和置换规则(REPLACE),前两 类用于表达式的变换,而后一类用于语句的变换.在表示规则中,抽象表达式的类型 必须是本模块定义的抽象类型,而表示表达式的类型必须是本模块定义的表示类型. 每个表示规则定义了一类抽象类型的表达式在该变换下的具体表示形式.重写表达 式的语法与表示表达式相同,但在重写规则中,抽象表达式与重写表达式必须具有相 同的类型.每个重写规则定义了一类表达式的等价重写.置换规则中的抽象语句的构 成类似于抽象表达式,置换语句的构成类似于重写表达式, 其差别仅在于前者是一 个语句模式,而后者是一个表达式模式. 使用Polya语言,用户可以从抽象的软件规则出发,通过一系列的程序变换,最终 得到一个可在机器上运行的程序.这种变换形的开发方法可以总结为: Specification+Transformation=Software. 根据这种思想我们使用改进的Polya语言模拟开发了电话交换系统.该系统由状态和 操作构成,通过操作使系统初始化或改变其状态.把系统的状态作为抽象数据,并与 它的操作封装在一起,就得到抽象数据类型exchange.外部操作命令是另一种抽象数 据类型comop. 通过变换模块的作用,将这两种抽象数据类型逐步变换成一般程序设 计语言所具有的基本数据类型.每一步的变换同时完成数据的精化和运算的分解.变 换模块的定义则给出了抽象数据类型的语义解释 它的表示类型和类型上的运算. 通过变换模块定义和使用的正确性来保证程序变换的正确性.这种基于模型的变换 型软件开发方法使得所开发的软件结构清晰,正确性证明也比较容易. 1. 电话交换系统的初始数据类型和源程序 初始数据类型: TYPE exchange /*电话交换系统状态的类型*/ OPERATIONS make-ex(s:set(seqdigit)) exchange /*根据用户号码集使系统初始化,seqdigit是十进制数字的类型*/ manulift(e:exchange,u:seqdigit) exchange /*拿听筒操作*/ manuclear(e:exchange,u:seqdigit) exchange /*放听筒操作*/ manudial(e:exchange,u:seqdigit) exchange /*拨号操作*/ manurelift(e:exchange,u:seqdigit) exchange /*接电话操作*/ manurepair(e:exchange,u:seqdigit) exchange/*管理操作 修电话*/ END TYPE comop /*外部操作命令的类型*/ OPERATIONS getcommand() comop /*得到一条命令*/ manu-opera(c:comop,e:exchange) exchange /*根据外部命令操作*/ END 源程序: program p1= block var e:exchange; c:comop; s:set(seqdigit); input(s); /* 得到所有用户号码*/ e:=make-ex(s); /* 系统初始化*/ do true -> c:=getcommand(); /* 系统运行*/ e:=maanu-opera(c,e) od end. 2. 变换过程和变换模块 t1: comop comrecord=record o:operat; u:seqdigit end t2: exchange exrecord=record Subs,Valid,Free,Unavail:set(seqdigit); callset:callstate; end t3: operat record s:cstate; d:digit end t4: callset set(call) t5: call record u1,u2:seqdigit; s:state end t6: seqdigit int 上式箭头的左边是抽象数据类型,右边是它的表示类型,t1--t6是变换模块的名 称.t1用记录comrecord实现抽象类型comop(操作命令),其中operat是操作命令的内 容,u是操作者. t2用记录exrecord实现抽象类型exchange(交换系统),其中Subs, Valid,Free,Unavail定义同前,callstate是呼叫线集的类型.t3用记录实现抽象类 型operat(一条操作命令的内容),其中cstate是操作要求,为枚举类型,即cstate= {"lift","clear","dial","relift","repair"},digit是十进制数字的类型.t4用集 合实现呼叫线集类型callstate,其中的呼叫线类型call通过t5变换成用户号码u1, 拨号序列u2,呼叫线状态state构成的记录. 变换模块t1引入的operat类型(操作命令内容的类型)定义为: TYPE operat OPERATIONS str(o;operat) cstate /*取命令的操作要求*/ dig(o:operat) digit /*取于拨号命令相关的数字*/ END 变换模块t1的定义: TRANSFORM t1 /*comop类型变到comrecord类型*/ DECLARATION REPR c:comop USING b:comrecord REPR c1:comop USING b1:comrecord RULES REPR getcommand() USING getcommandre() REPLACE c:=c1 USING b:=b1 REPLACE e:=manu-opera(e,c) USING manu-operare(b.o,b.u,e) WITH /*comrecord类型上的局部过程*/ procedure manu-operare(in op:operat, in uu:seqdigit, inout ee:exchange)= /*inout表示输入和输出,in表示输入*/ block var d:digit if (str(op)="lift") -> ee:=manulift(ee,uu) /*拿听筒*/ [] (str(op)="clear") -> ee:=manuclear(ee,uu) /*放听筒*/ [] (str(op)="dial") -> ee:=manudial(ee,uu,d) /*拨号*/ [] (str(op)="relift") -> ee:=manurelift(ee,uu) /*接电话*/ [] (str(op)="repair") -> ee:=manurepair(ee,uu) /*修电话*/ fi end END: 变换模块t2的定义: TRANSFORM t2 DECLARATION REPR e:exchange USING er: exrecord REPR e1:exchange USING er1:exrecord RULES REPR make-ex(s) USING make-exre(s) REPR manulift(e,u) USING lift(er,u) REPR manuclear(e,u) USING clear(er,u) REPR manudial(e,u,d) USING dial(er,u,d) REPR manurelift(e,u) USING relift(er,u) REPR manurepair(e,u) USING repair(er,u) REPLACE e:=e1 USING er:=er1 WITH ... END; 在变换模块t2的REPR规则中,左部是抽象类型exchange中的一个操作,右部是该 操作分解后得到的局部函数施用,限于篇幅,WITH后面省去这些函数的说明. 3. 一次变换的结果 下面给出施用变换模块t1到程序p1后得到的结果程序p2. program p2= block var e:exchange; b:record o:operat; u:seqdigit end; s:set(seqdigit) ; procedure manu-operare(in op:operat,in uu:seqdigit, inoutee:exchange)= block var d:digit; if (str(op)="lift" -> ee:=manulift(ee,uu) [] (str(op)="clear" -> ee:=manuclear(ee,uu) [] (str(op)="dial" -> ee:=manudial(ee,uu) [] (str(op)="relift -> ee:=manurelift(ee,uu) [] (str(op)="repair" -> ee:=manurepair(ee,uu) fi end; input(s); e:=make-ex(s); do true -> b:=getcommandre(); manu-operare(b.o,b.u,e) od end. 三. 讨 论 通过开发电话交换系统和程序变换系统[6],进一部改进了Polya语言. 1. Polya的类型系统应该分层构成,高层是比较抽象的类型,低层是比较具体的 类型.变换必须从高到低进行,同一层的类型之间不允许进行变换.这样才能保证不 会形成一个变换的死循环,使得任何正确的程序经过有限步的变换后都可以达到只 由基本数据类型构成的最低层.根据"语言是类型的集合"这一基本观点,类型的分层 将导致语言的分层,形成一个分层的语言族. 通常说"用类型T1实现类型T2",是指用 类型为T1的变量来表示类型为T2的变量,并用T1中的操作来解释T2中的操作,这时称 T1是T2的"实现类型",也称T2是T1的"抽象类型". 类似地我们称"语言L1是语言L2的 实现语言",如果L2中的所有类型都可以用L1中的类型来实现,反过来,也称L2是L1的 "抽象语言".一个变换模块是一种机制,它把一个抽象数据类型及其实现的细节封装 起来.也可以采用一种类似于变换模块的封装机制GARMENT把一个抽象语言和它的实 现细节封装在一起.如果限制每种语言只考虑一种实现,把实现语言看作抽象语言的 前驱,那么各层语言就构成一棵语言族树,它的根结点就是由最基本的数据类型构成 的最低层语言. 从一个结点到根的路径则刻划了该结点所代表的抽象语言的实现过 程.这棵树的每个结点(除根结点外)都可以通过GARMENT来生成. 用户可以根据需要 从树中选择一个合适的结点(即一个语言)来编程, 该程序将自动变换到由最低层语 言书写的程序,并自动运行. 根据各种不同要求,在这棵树上可以开发出面向一个专 门领域的专用语言,这将大大提高编程效率.关于GARMENT的定义和形式描述将另文 给出. 2. 从部分实现的思想出发,Polya中允许同一类型的变量采用不同的表示类型. 如果两个不同表示类型的变量运算时,必须进行类型的强制转换.而这种转换将给变 换系统带来许多问题.此外,Polya的变换命令不能控制对包含在某种抽象数据类型 中的分量的类型(如exrecord记录的callstate类型)进行变换. 我们对Polya的变换 命令进行了修改和扩充,把Polya的变换命令分成三类: 作用在一个变量上的命令 作用在某个类型的所有变量上的命令 作用在某个组合类型的分量上的命令 为了方便用户,如果不加说明,变换系统将自动按照第二种变换命令运行. 3. 变换模块允许带有参数,使用带参数的变换模块要先给出实参,将模块实例 化,然后再用于对变量的变换. 变换模块的参数可以是类型参数,这种变换模块实际 上是一类变换模块的模式. 研究生肖灵在电话交换系统的开发中做了大量的程序工作,在此表示衷心的感谢. 参 考 文 献 [1]. Jim Woodcock & Martin Loomes,SoftwareEngineering Mathematics,Pitman Publishing, 1988. [2]. P.Volpano & D.Gries, Type Definitions in Polya, Tech. Rpt. Computer Science Dept. Cornell Univ. 1990. [3]. D.Gries & P. Volpano, The Transform - A New Language Construct,Tech. Rpt. Computer Science Dept. Cornell Univ. 1990. [4]. 张乃孝, 程序变换在程序语言中的一种表示──兼论变换型语言, 软件学报, 第4卷, 第5期, 1993年10月. [5]. 张乃孝,许卓群,屈婉玲, 面向模型的变换型软件开发方法研究, 理论计算机科学, No.2,1994. [6]. 陈光,用变换型方法开发程序变换系统,硕士论文,北京大学计算机系,1993. Simulation of Developing A Telephone Exchange System by Transformational Method Qu Wanling zhang Naixiao (Dept. of Computer Science & Technology, Peking Univ.) Abstract: This paper presents simulation of developing a telephone exchange system by transformational method (Specification+Transformation=Software). Refinement of data and decomposition of operations are done by a series of transformatuions from specification to program that can run. The whole procedure of developing is described in the transformational language Polya. At last the suggestions of improving Polya is made. Keywords:transformation of program,language,method of developing software