软件构造从面向过程到面向对象

1、Institute of Computer SoftwareNanjing University1Abstract Data TypesInstitute of Computer SoftwareNanjing University2摘要摘要l软件构造：从面向过程到面向对象l如何规约对象？抽象！lAbstract Data Type Specificationl形式？l质量？lADT与软件开发Institute of Computer SoftwareNanjing University3回顾：结构化软件开发回顾：结构化软件开发l何谓“结构化（structured）”开发方法？lThe Big

2、 Name “E.W. Dijkstra”l开发过程侧面l自顶向下，逐步求精l程序设计侧面l小结构：concatenation, selection, and repetition. l大结构：过程抽象，避免全局变量Institute of Computer SoftwareNanjing University4回顾：结构化软件开发回顾：结构化软件开发l“结构化（structured）”的合理性l管理复杂性的有效手段l分解, 抽象, 层次lCorrectnesslAdaptability, ManageabilityInstitute of Computer SoftwareNanjing U

3、niversity5有关程序正确性有关程序正确性l规约与实现l对程序的理解：l具体操作l状态变化l逻辑公式lInstitute of Computer SoftwareNanjing University6从面向过程到面向对象从面向过程到面向对象l“结构化”的基本思想已经深入人心l但对于复杂、易变、交互性软件系统，以“功能”为中心的分解方式有局限l完全自顶向下的功能分解？l线性过程式的程序组织？l应变Chair of Software Engineering7The first step A system performs certain actions on certain data. Ba

4、sic duality: Functions or: Operations, Actions Objects or: DataActionObjectProcessorChair of Software Engineering8Finding the structure The structure of the system may be deduced from an analysis of the functions (1) or the objects (2). Resulting analysis and design method: Process-based decompositi

5、on: classical (routines) Object-oriented decomposition Chair of Software Engineering9Arguments for using objects Reusability: Need to reuse whole data structures, not just operations Extendibility, Continuity: Objects remain more stable over time.Employee informationHours workedProduce PaychecksPayc

6、hecksChair of Software Engineering10Object technology: A first definition Object-oriented software construction is the approach to system structuring that bases the architecture of software systems on the types of objects they manipulate not on “the” function they achieve.Chair of Software Engineeri

7、ng11The O-O designers motto Ask NOT first WHAT the system does:Ask WHAT it does it TO!Chair of Software Engineering12Issues of object-oriented design How to find the object types. How to describe the object types. How to describe the relations and commonalities between object types. How to use objec

8、t types to structure programs.Chair of Software Engineering13Description of objects Consider not a single object but a type of objects with similar properties. Define each type of objects not by the objects physical representation but by their behavior: the services (FEATURES) they offer to the rest

9、 of the world. External, not internal view: ABSTRACT DATA TYPESInstitute of Computer SoftwareNanjing University14对象刻画问题对象刻画问题lThe main issue: How to describe program objects (data structures):lCompletely lUnambiguously lWithout overspecifying?l(Remember information hiding)Chair of Software Engineeri

10、ng15A stack, concrete objectcountrepresentation(array_up)capacityrepresentation count := xfree(array_down)1representationnnew(linked)itemitempreviousitempreviousprevious“Push” operation:count := count + 1representation free := x“Push” operation:free := free - 1new (n)n.item := x“Push” operation:n.pr

11、evious := lasthead := nChair of Software Engineering16A stack, concrete objectcountrepresentation(array_up)capacityrepresentation count := xfree(array_down)1representationnnew(linked)itemitempreviousitempreviousprevious“Push” operation:count := count + 1representation free := x“Push” operation:free

12、:= free - 1new (n)n.item := x“Push” operation:n.previous := lasthead := nInstitute of Computer SoftwareNanjing University17抽象数据类型抽象数据类型l一种数学的刻画方式l“类型”？ - (Data type, 简称Type)l值l操作函数l规律公理Chair of Software Engineering18Stack: An abstract data type Types: STACK G - G: Formal generic parameter Functions

13、(Operations): put: STACK G G STACK G remove: STACK G STACK G item: STACK G G empty: STACK G BOOLEAN new: STACK GChair of Software Engineering19Using functions to model operationsput,=()sxsChair of Software Engineering20Reminder: Partial functions A partial function, identified here by , is a functio

14、n that may not be defined for all possible arguments. Example from elementary mathematics: inverse: , such that inverse (x) = 1 / xChair of Software Engineering21The STACK ADT (contd) Preconditions: remove (s: STACK G) require not empty (s) item (s: STACK G) require not empty (s) Axioms: For all x:

15、G, s: STACK G item (put (s, x) = x remove (put (s, x) = s empty (new) (or: empty (new) = True) not empty (put (s, x) (or: empty (put (s, x) = False)put (,) =sxsChair of Software Engineering22Formal stack expressionsvalue = item (remove (put (remove (put (put (remove (put (put (put (new, x8), x7), x6

16、), item (remove (put (put (new, x5), x4), x2), x1)Chair of Software Engineering23Expressed differentlys1 = 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

17、= remove (s10)value = item (s11)value = item (remove (put (remove (put (put (remove (put (put (put (new, x8), x7), x6), item (remove (put (put (new, x5), x4), x2), x1)Chair of Software Engineering24An operational view of the expressionvalue = item (remove (put (remove (put (put (remove (put (put (pu

18、t (new, x8), x7), x6), item (remove (put (put (new, x5), x4), x2), x1)x8x7x6x8x7s2s3(empty)s1x5x4s5(empty)s4x5s6y1x8x7x5s7 (s9, s11)x8x7x5s8x2x8x7x5s10 x1Chair of Software Engineering25Expression reduction (1/10)value = item ( remove ( put ( remove ( put ( put ( remove ( put (put (put (new, x8), x7)

19、, x6) ) , item ( remove ( put (put (new, x5), x4) ) ) ) , x2) ) , x1) ) )x7x8x6x5x4Stack 1Stack 2Chair of Software Engineering26Expression reduction (2/10)x7putremovex8x7x8x7x8x6value = item ( remove ( put ( remove ( put ( put ( remove ( put (put (put (new, x8), x7), x6) ) , item ( remove ( put (put

20、 (new, x5), x4) ) ) ) , x2) ) , x1) ) )x5x4Stack 1Stack 2Chair of Software Engineering27Expression reduction (3/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) ) )x7putremovex8x7x8x7x8x2x

21、7putremovex8x7x8x7x8x2Stack 1x5x4Stack 2Chair of Software Engineering28Expression reduction (4/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) ) )x5putremovex5x5x4x7x8x7x8Stack 1Stack 2Ch

22、air of Software Engineering29Expression reduction (5/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) ) )itemx5Stack 2x7x8x7x8Stack 1Chair of Software Engineering30value = item ( remove (

23、put ( remove ( put ( put ( remove ( put (put (put (new, x8), x7), x6) ) , item ( remove ( put (put (new, x5), x4) ) ) ) , x2) ) , x1) ) )Expression reduction (6/10)x5Stack 2x7x8x7x8Stack 1Chair of Software Engineering31value = item ( remove ( put ( remove ( put ( put ( remove ( put (put (put (new, x

24、8), x7), x6) ) , item ( remove ( put (put (new, x5), x4) ) ) ) , x2) ) , x1) ) )Expression reduction (7/10)x5x7x8x7x8Stack 3Chair of Software Engineering32Expression reduction (8/10)value = item ( remove ( put ( remove ( put ( put ( remove ( put (put (put (new, x8), x7), x6) ) , item ( remove ( put

25、(put (new, x5), x4) ) ) ) , x2) ) , x1) ) )x5x7x8x7x8Stack 3putremovex1x5x7x8x7x8x5x7x8x7x8Chair of Software Engineering33Expression reduction (9/10)itemx5x7x8x7x8Stack 3value = item ( remove ( put ( remove ( put ( put ( remove ( put (put (put (new, x8), x7), x6) ) , item ( remove ( put (put (new, x

26、5), x4) ) ) ) , x2) ) , x1) ) )Chair of Software Engineering34Expression reduction (10/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) ) ) value = x5x5x7x8x7x8Stack 3Institute of Computer

27、 SoftwareNanjing University35ADT 函数分类函数分类l一个 ADT T 中可有三种函数: lCreators:OTHER T e.g. new lQueries:T . OTHERe.g. item, empty lCommands: T . T e.g. put, removeNote：Mutable vs. ImmutableInstitute of Computer SoftwareNanjing University36ADT规约质量？规约质量？l到底要描述多少特性才足够？l相对什么而言 完全？l数学的完全？l会不会描述的太多 “言多必失”？l一致性？In

28、stitute of Computer SoftwareNanjing University37Sufficient Completenessl一个类型 T 的ADT规约是sufficiently complete 当且仅当 对于任何well-formed的表达式 e 均可依据该ADT的公理lS1 判定 e 是否 correct.lS2 若 e 为查询表达式且 correct, 则 e 的值可不用任何T类型的值就可表达。l（一般而言不可判定）Institute of Computer SoftwareNanjing University38ConsistencylAn ADT specific

29、ation is consistent if and only if, for any well-formed query expression e, the axioms make it possible to infer at most one value for e.l（一般而言不可判定）Chair of Software Engineering39Stack: An abstract data type Types: STACK G - G: Formal generic parameter Functions (Operations): put: STACK G G STACK G

30、remove: STACK G STACK G item: STACK G G empty: STACK G BOOLEAN new: STACK GChair of Software Engineering40The STACK ADT (contd) Preconditions: remove (s: STACK G) require not empty (s) item (s: STACK G) require not empty (s) Axioms: For all x: G, s: STACK G item (put (s, x) = x remove (put (s, x) =

31、s empty (new) (or: empty (new) = True) not empty (put (s, x) (or: empty (put (s, x) = False)put (,) =sxsInstitute of Computer SoftwareNanjing University41证明证明l证明上述ADT的sufficient completenessl判定任何一个well-formed的栈表达式 e 的correct与否l若 e 的确correct, 求empty(e)和item(e)的值（以不包含栈值的表达式表示）Institute of Computer Sof

32、twareNanjing University42基本思路基本思路l对表达式长度（嵌套层数即括号对数）进行归纳l操作性解释：l影响correctness的关键是栈中元素多少l查询操作不改变栈状态 仅new put remove改变lEmpty(put.) item(put.) 均可求值 故消解remove即可Institute of Computer SoftwareNanjing University43WeightThe weight of a well-formed stack expression not involving item or empty is defined induc

33、tively as follows:lW(new) = 0.lW(put (s, x) = W(s) + 1lW(remove (s) = W(s) - 1Institute of Computer SoftwareNanjing University44lWeight Consistency rule : lA well-formed stack expression e, involving neither item nor empty, is correct if and only if its weight is non-negative, and any subexpression

34、of e is (recursively) correct.lZero Weight rule:lLet e be a well-formed and correct stack expression not involving item or empty. Then empty (e) is true if and only if e has weight 0.Institute of Computer SoftwareNanjing University45以归纳法证明上述两规则： e 是 well-formed 的 不包含empty和item 1. e是correct的 W(e) 0 e

35、中的子表达式correct 2. 若e是correct的，empty(e) W(e)=0 嵌套层数为0：必为new，上述两规则显然成立（当然我们也可以验证为1的情况）假设对于嵌套层数不超过n的表达式上述两规则均成立，现证明对于嵌套层数为n+1时它们成立 考虑e的最外层函数 必为 put 或 remove若e = put(s, x), . Institute of Computer SoftwareNanjing University46.若e = remove(s), 1= e is correct, s is correct and not empty(s), W(s)0 W(e)=W(s)

36、-1 0 10, s至少有一个put，设其最外的put为put(s, xexp), 在e中它的外面必为remove. remove( put ( s, xexp ) ) .e 变成 e 层数减2 empty值不变 规则2成立Correct的无empty和item的表达式可消去removeInstitute of Computer SoftwareNanjing University47利用这两个规则证明sufficient Completeness.再对嵌套层数进行归纳 e = f(s) S嵌套层数为0 必为 new, empty(s)= TRUE, item(s)不correct假设s层数不

37、超过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)正确且等于xInstitute of Computer Softw

38、areNanjing University48ADT与软件开发与软件开发lADT为软件模块分解提供了理论基础：Chair of Software Engineering49ADT and software architecture Identify every module with an implementation of an abstract data type, i.e. the description of a set of objects with a common interface. The interface is defined by a set of operations

39、 (implementing the functions of the ADT) constrained by abstract properties (the axioms and preconditions). The module consists of a representation for the abstract data type and an implementation for each of the operations. Auxiliary operations may also be included. Chair of Software Engineering50I

40、mplementing an ADT Three components: (E1)The ADTs specification: functions,axioms, preconditions. (Example: stacks.) (E2)Some representation choice.(Example: .) (E3)A set of subprograms (routines) and attributes, each implementing one of the functions of the ADT specification (E1) in terms of the ch

41、osen representation (E2).(Example: routines put, remove, item, empty, new.) Chair of Software Engineering51A choice of stack representationcountrepresentation(array_up)capacity“Push” operation:count := count + 1representation count := xChair of Software Engineering52Application to information hiding

42、Secret part:Choice of representation (E2)Implementation of functions by features (E3)ADT specification (E1)Public part:Chair of Software Engineering53Object technology: A first definition Object-oriented software construction is the approach to system structuring that bases the architecture of software systems on the types of objects they manipulate not on “the” function they achieve.Chair of Software Engineering54Object technology: More precise definition Object-oriented software construction is the co