威廉勃特勒叶芝(Willia.ppt

AbstractDataTypes,抽象数据类型,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,1,育儿知识http:/www.pangbaba.cc,摘要,软件构造：从面向过程到面向对象如何规约对象？抽象！AbstractDataTypeSpecification形式？质量？ADT与软件开发,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,2,回顾：结构化软件开发,何谓“结构化（structured）”开发方法？TheBigName“E.W.Dijkstra”开发过程侧面自顶向下，逐步求精程序设计侧面小结构：concatenation,selection,andrepetition.大结构：过程抽象，避免全局变量,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,3,回顾：结构化软件开发,“结构化（structured）”的合理性管理复杂性的有效手段分解,抽象,层次CorrectnessExtendibility?Reusability?,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,4,注：有关程序正确性,规约与实现对程序的理解：具体操作状态变化逻辑公式,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,5,从面向过程到面向对象,“结构化”的基本思想已经深入人心但对于复杂、易变、交互性软件系统，以“功能”为中心的分解方式有局限完全自顶向下的功能分解？线性过程式的程序组织？应变,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,6,Thefirststep,程序运行：在某个数据体上施以某些操作。两个要素操作（功能）Functionsor:Operations,Actions客体（对象）Objectsor:Data,7,Action,Object,Processor,如何导出软件系统的结构？,两条途径：从操作/功能入手从客体/对象入手形成两种分析设计方法：基于过程的分解面向对象的分解,8,面向对象的分解好在何处？,Reusability:数据（结构）及其上之操作的整体复用，而非仅仅复用操作功能；Extendibility,Continuity:对象更直接对应问题空间的概念，因而较“功能”更稳定.,9,例：考虑一个工资系统,一开始，客户说他的需求很“简单明确”：,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,10,Employeeinformation,Hoursworked,ProducePaychecks,Paychecks,例：考虑一个工资系统,这种功能明确的系统确实适合结构化的开发方法：自顶向下，逐步求精。你完美地完成了任务。而后，极有可能，客户会跑过来跟你说：给我加个统计报表撒下个月我想一些人发记时工资，一些人发计件工资啊行啊，有人每月一发，有人每周一发哦加个个人所得税系统接口加个图像用户界面，用交互查询,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,11,“面向对象”的含义（之一）,面向对象的软件构造乃是基于系统所操作之对象类型（而非系统需实现之功能）来架构系统的途径。“Object-orientedsoftwareconstructionistheapproachtosystemstructuringthatbasesthearchitectureofsoftwaresystemsonthetypesofobjectstheymanipulatenoton“the”functiontheyachieve.”,12,TheO-Odesignersmotto,AskNOTfirstWHATthesystemdoes:AskWHATitdoesitTO!,13,对象设计相关问题,Howtofindtheobjecttypes.Howtodescribetheobjecttypes.Howtodescribetherelationsandcommonalitiesbetweenobjecttypes.Howtouseobjecttypestostructureprograms.,14,对象刻画,Considernotasingleobjectbutatypeofobjectswithsimilarproperties.Defineeachtypeofobjectsnotbytheobjectsphysicalrepresentationbutbytheirbehavior:theservices(FEATURES)theyoffertotherestoftheworld.External,notinternalview:ABSTRACTDATATYPES,15,对象刻画问题,Themainissue:Howtodescribeprogramobjects(datastructures):CompletelyUnambiguouslyWithoutoverspecifying?(Rememberinformationhiding),2020/6/11,InstituteofComputerSoftwareNanjingUniversity,16,Astack,concreteobject,17,count,representation,(array_up),capacity,representationcount:=x,free,(array_down),1,representation,n,new,(linked),item,item,previous,item,previous,previous,“Push”operation:,count:=count+1,representationfree:=x,“Push”operation:,free:=free-1,new(n),n.item:=x,“Push”operation:,n.previous:=last,head:=n,Astack,concreteobject,18,count,representation,(array_up),capacity,representationcount:=x,free,(array_down),1,representation,n,new,(linked),item,item,previous,item,previous,previous,“Push”operation:,count:=count+1,representationfree:=x,“Push”operation:,free:=free-1,new(n),n.item:=x,“Push”operation:,n.previous:=last,head:=n,抽象数据类型,一种数学的刻画方式“类型”？-(Datatype,简称Type)值操作函数规律公理,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,19,Stack:Anabstractdatatype,Types:STACKG-G:FormalgenericparameterFunctions(Operations):put:STACKGGSTACKGremove:STACKGSTACKGitem:STACKGGempty:STACKGBOOLEANnew:STACKG,20,Usingfunctionstomodeloperations,21,put,=,(,),s,x,s,Reminder:Partialfunctions,Apartialfunction,identifiedhereby,isafunctionthatmaynotbedefinedforallpossiblearguments.Examplefromelementarymathematics:inverse:,suchthatinverse(x)=1/x,22,TheSTACKADT(contd),Preconditions:remove(s:STACKG)requirenotempty(s)item(s:STACKG)requirenotempty(s)Axioms:Forallx:G,s:STACKGitem(put(s,x)=xremove(put(s,x)=sempty(new)(or:empty(new)=True)notempty(put(s,x)(or:empty(put(s,x)=False),23,put(,)=,s,x,s,Formalstackexpressions,value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1),24,Expresseddifferently,s1=news2=put(put(put(s1,x8),x7),x6)s3=remove(s2)s4=news5=put(put(s4,x5),x4)s6=remove(s5)y1=item(s6)s7=put(s3,y1)s8=put(s7,x2)s9=remove(s8)s10=put(s9,x1)s11=remove(s10)value=item(s11),25,value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1),Anoperationalviewoftheexpression,value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1),26,x8,x7,x6,x8,x7,s2,s3,(empty),s1,x5,x4,s5,(empty),s4,x5,s6,y1,x8,x7,x5,s7(s9,s11),x8,x7,x5,s8,x2,x8,x7,x5,s10,x1,Expressionreduction(1/10),value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1),27,x7,x8,x6,x5,x4,Stack1,Stack2,Expressionreduction(2/10),value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1),28,x7,put,remove,x8,x7,x8,x7,x8,x6,x5,x4,Stack1,Stack2,ADT函数分类,一个ADTT中可有三种函数:Creators:OTHERTe.g.newQueries:T.OTHERe.g.item,emptyCommands:T.Te.g.put,removeNote：Mutablevs.Immutable,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,29,ADT规约质量？,到底要描述多少特性才足够？相对什么而言完全？数学的完全？会不会描述的太多“言多必失”？一致性？,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,30,SufficientCompleteness,一个类型T的ADT规约是sufficientlycomplete当且仅当对于任何well-formed的表达式e均可依据该ADT的公理S1判定e是否correct.S2若e为查询表达式且correct,则e的值可不用任何T类型的值就可表达。（一般而言不可判定）,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,31,Consistency,AnADTspecificationisconsistentifandonlyif,foranywell-formedqueryexpressione,theaxiomsmakeitpossibletoinferatmostonevaluefore.（一般而言不可判定）,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,32,Stack:Anabstractdatatype,Types:STACKG-G:FormalgenericparameterFunctions(Operations):put:STACKGGSTACKGremove:STACKGSTACKGitem:STACKGGempty:STACKGBOOLEANnew:STACKG,33,TheSTACKADT(contd),Preconditions:remove(s:STACKG)requirenotempty(s)item(s:STACKG)requirenotempty(s)Axioms:Forallx:G,s:STACKGitem(put(s,x)=xremove(put(s,x)=sempty(new)(or:empty(new)=True)notempty(put(s,x)(or:empty(put(s,x)=False),34,put(,)=,s,x,s,证明,证明上述ADT的sufficientcompleteness判定任何一个well-formed的栈表达式e的correct与否若e的确correct,求empty(e)和item(e)的值（以不包含栈值的表达式表示）,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,35,基本思路,对表达式长度（嵌套层数即括号对数）进行归纳操作性解释：影响correctness的关键是栈中元素多少查询操作不改变栈状态仅newputremove改变Empty(put.)item(put.)均可求值故消解remove即可,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,36,Weight,Theweightofawell-formedstackexpressionnotinvolvingitemoremptyisdefinedinductivelyasfollows:W(new)=0.W(put(s,x)=W(s)+1W(remove(s)=W(s)-1,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,37,WeightConsistencyrule:Awell-formedstackexpressione,involvingneitheritemnorempty,iscorrectifandonlyifitsweightisnon-negative,andanysubexpressionofeis(recursively)correct.ZeroWeightrule:Letebeawell-formedandcorrectstackexpressionnotinvolvingitemorempty.Thenempty(e)istrueifandonlyifehasweight0.,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,38,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,39,以归纳法证明上述两规则：e是well-formed的不包含empty和item1.e是correct的W(e)0e中的子表达式correct2.若e是correct的，empty(e)W(e)=0嵌套层数为0：必为new，上述两规则显然成立（当然我们也可以验证为1的情况）假设对于嵌套层数不超过n的表达式上述两规则均成立，现证明对于嵌套层数为n+1时它们成立考虑e的最外层函数必为put或remove若e=put(s,x),.,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,40,.若e=remove(s),1=eiscorrect,siscorrectandnotempty(s),W(s)0W(e)=W(s)-1010,s至少有一个put，设其最外的put为put(s,xexp),在e中它的外面必为remove.remove(put(s,xexp).e变成e层数减2empty值不变规则2成立Correct的无empty和item的表达式可消去remove,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,41,利用这两个规则证明sufficientCompleteness.再对嵌套层数进行归纳e=f(s)S嵌套层数为0必为new,empty(s)=TRUE,item(s)不correct假设s层数不超过n时f(s)的correctness可判定，若correct则empty(s)和item(s)的值可求现证明层数为n+1亦如是考虑s的子表达式u,若u最外层为empty或item，因u嵌套层数不超过n，它的correctness可判定，若不correct,则s不corrct,若u是correct的，则可求值；不断对这样的u求值最终消解empty和item,消解remove,仅剩put和new，若外层为new上面已讨论，若s=put(s,x),则empty(s)正确且等于FALSE，item(s)正确且等于x,ADT与软件开发,ADT为软件模块分解提供了理论基础：,2020/6/11,InstituteofComputerSoftwareNanjingUniversity,42,ADTandsoftwarearchitecture,Identifyeverymodulewithanimplementationofanabstractdatatype,i.e.thedescriptionofasetofobjectswithacommoninterface.Theinterfaceisdefinedbyasetofoperations(implementingthefunctionsoftheADT)constrainedbyabstractproperties(theaxiomsandpreconditions).Themoduleconsistsofarepresentationfortheabstractdatatypeandanimplementationforeachoftheoperations.Auxiliaryoperationsmayalsobeincluded.,43,ImplementinganADT,Threecomponents:(E1)TheADTsspecification:functions,axioms,preconditions.(Example:stacks.)(E2)Somerepresentationchoice.(Example:.)(E3)Asetofsubprograms(routines)andattributes,eachimplementingoneofthefunctionsoftheADTspecification(E1)intermsofthechosenrepresentation(E2).(Example:routinesput,remove,item,empty,new.),44,Achoiceofstackrepresentation,45,count,representation,(array_up),capacity,“Push”operation:count:=count+1representationcount:=x,信息隐蔽原则,46,Secretpart:Choiceofrepresentation(E2)Implementationoffunctionsbyfeatures(E3),ADTspecification(E1),Publicpart:,“面向对象”的含义（初步）,面向对象的软件构造乃是基于系统所操作之对象类型（而非系统需实现之功能）来架构系统的途径。“Object-orientedsoftwareconstructionistheapproachtosystemstructuringthatbasesthearchitectureofsoftwaresystemsonthetypesofobjectstheymanipulatenoton“the”functiontheyachieve.”,47,“面向对象”的含义（进一步）,面向对象的软件构造乃是将系统构造为抽象数据类型实现（可能是部分实现）的结构化组合。“Object-orientedsoftwareconstructionistheconstructionofsoftwaresystemsasstructuredcollectionsof(possiblypartial)abstractdatatypeimplementations.”这个“抽象数据类型的实现”就是类（class）,48,类：对象程序的基本结构,模块module与类型type的统一：Module=Unitofdecomposition:setofservicesType=De