Abstract Data Types 抽象数据类型 Institute of Computer Software 2019/2/24

Presentation on theme: "Abstract Data Types 抽象数据类型 Institute of Computer Software 2019/2/24"— Presentation transcript:

1 Abstract Data Types 抽象数据类型 Institute of Computer Software 2019/2/24
Nanjing University 2019/2/24

2 摘要 从面向过程到面向对象 如何规约对象？——抽象！ Abstract data type ADT与软件开发
Institute of Computer Software Nanjing University 2019/2/24

3 回顾：结构化软件开发 何谓“结构化（structured）”开发方法？ 开发过程侧面 程序设计侧面
The Big Name “E.W. Dijkstra” 开发过程侧面 自顶向下，逐步求精 程序设计侧面 小结构：顺序，选择，循环 大结构：过程抽象，避免全局变量 Institute of Computer Software Nanjing University 2019/2/24

4 回顾：结构化软件开发 “结构化（structured）”的合理性 Correctness
管理复杂性的有效手段 分解, 抽象, 层次 Correctness 规约与实现 Extendibility? Reusability? Institute of Computer Software Nanjing University 2019/2/24

5 从面向过程到面向对象 “结构化”的基本思想已经深入人心 但对于复杂、易变、交互性软件系统，以“功能” 为中心的分解方式有局限 应变？
完全自顶向下的功能分解？ 线性过程式的程序组织？ 应变？ Institute of Computer Software Nanjing University 2019/2/24

6 The first step 程序运行：在某个数据体上施以某些操作。 两个要素
操作（功能）Functions [or: Operations, Actions] 客体（对象）Objects [or: Data] Action Object Processor Institute of Computer Software Nanjing University 2019/2/24

7 如何导出软件系统的结构？ 两条途径： 形成两种抽象方法： 从操作/功能入手 从客体/对象入手 基于过程的抽象 基于数据的抽象
Institute of Computer Software Nanjing University 2019/2/24

8 过程抽象 vs. 数据抽象 过程抽象：指任何一个明确定义功能的操作都 可以被使用者看作单个的实体，尽管这个操作 实际上可能由一系列更低级的操作完成 数据抽象：定义了数据类型和施加于该类型对 象上的操作，并限定了对象的值只能通过使用 这些操作修改和观察。包含了2个概念： 模块封装 信息隐蔽 Institute of Computer Software Nanjing University 2019/2/24

9 数据抽象的意义 数据抽象提供了面向对象计算的起点：系统应 该被分解为概念上的实体，实体的内部细节应 该被隐藏！
Institute of Computer Software Nanjing University 2019/2/24

10 数据抽象发展 第一阶段：从无类型的二进制到基本数据类型 第二阶段：从基本类型到用户自定义类型
Fortran, Algol: 整型、实数、布尔数 第二阶段：从基本类型到用户自定义类型 Algol68, Pascal 第三阶段：从用户自定义类型到抽象数据类型 （Abstract Data Types）-- 面向对象 模块化程序设计和模块 Institute of Computer Software Nanjing University 2019/2/24

11 面向对象的分解好在何处？ Reusability: 数据（结构）及其上之操作的整 体复用，而非仅仅复用操作功能；
Extendibility, Continuity: 对象更直接对应问题空 间的概念，因而较“功能”更稳定. Institute of Computer Software Nanjing University 2019/2/24

12 Reality 现实世界 抽象 问题世界 软件世界 Institute of Computer Software 2019/2/24
Nanjing University 2019/2/24

13 例：考虑一个工资系统 一开始，客户说他的需求很“简单明确”： Produce Paychecks Employee information
Hours worked Institute of Computer Software Nanjing University 2019/2/24

14 例：考虑一个工资系统 这种功能明确的系统确实适合结构化的开发方法：自顶向 下，逐步求精。 你完美地完成了任务。
而后，极有可能，客户会跑过来跟你说： 给我加个统计报表撒 下个月我想一些人发记时工资，一些人发计件工资啊行啊，有人 每月一发，有人每周一发哦 加个个人所得税系统接口 再加个图像用户界面，用来交互查询吧 …… Institute of Computer Software Nanjing University 2019/2/24

15 “面向对象的软件构造”含义（1） 面向对象的软件构造（OOSC）乃是基于系统所 操作之对象类型（而非系统需实现之功能）来 架构系统的途径。
Meyer: “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.” Institute of Computer Software Nanjing University 2019/2/24

16 面向对象设计的相关问题 如何找到对象类型？ 如何描述对象类型？ 如何描述对象类型之间的关系和共性？ 如何使用对象类型来构造程序？
Institute of Computer Software Nanjing University 2019/2/24

17 对象刻画 考虑一类具有相似属性的对象而不是单个对象
定义对象的类型不是通过定义对象的物理表述， 而是通过定义它们的行为：即它们提供给外部 的服务 External, not internal view: ABSTRACT DATA TYPES Institute of Computer Software Nanjing University 2019/2/24

18 对象刻画问题 主要问题：如何描述程序对象（数据结构）？ Completely Unambiguously
Without overspecifying? (Remember information hiding) Institute of Computer Software Nanjing University 2019/2/24

19 A stack, concrete object
capacity count “Push” operation: (array_up) count := count + 1 representation [count] := x representation “Push” operation: representation [free] := x (array_down) free := free - 1 free 1 “Push” operation: representation new (n) new item previous n.item := x n n.previous := last item previous (linked) head := n previous item 19

20 Abstract Data Type 数据类型由一个对象集合(值集合)以及在该集合 上定义的若干合法运算所组成的运算集合组成。
抽象数据类型(ADT)：用数学方法定义对象集合 和运算集合，仅通过运算的性质刻画数据对象， 而独立于计算机中可能的表示方法 Institute of Computer Software Nanjing University 2019/2/24

21 ADT规约方法 代数方法 模型方法 C.A.R. Hoare的前后断言方法：通过已定义的(抽象) 数据类型来给出要定义的新类型的抽象模型
Institute of Computer Software Nanjing University 2019/2/24

22 代数规范 语法部分 公理部分 ADT名 运算(函数)的定义域和值域 给出一组刻画各运算之间相互关系的方程来定义各 运算的含义
语义正确性：相应代数满足规约中公理部分的所有 公理。 Institute of Computer Software Nanjing University 2019/2/24

23 Stack: An abstract data type
Types: STACK [G] G: Formal generic parameter Functions (Operations): put: STACK [G]  G  STACK [G] remove: STACK [G]  STACK [G] item: STACK [G]  G empty: STACK [G]  BOOLEAN new: STACK [G] Institute of Computer Software Nanjing University 2019/2/24

24 Using functions to model operations
( ) put , = s x s’ Institute of Computer Software Nanjing University 2019/2/24

25 ADT函数分类 一个 ADT T 中可有三种函数（算子）: Creators（构造算子）: OTHER  T e.g. new
Queries（观察算子）: T ...  OTHER e.g. item, empty Commands（运算算子）: T ...  T e.g. put, remove 构造算子产生该数据类型的一个新元素 观察算子作用于该数据类型的元素，但返回其它类型的元素，如自然数或布尔值 运算算子是该数据类型上的函数，但它不产生新元素 Institute of Computer Software Nanjing University 2019/2/24

26 Reminder: Partial functions
A partial function, identified here by , is a function that may not be defined for all possible arguments. Example from elementary mathematics: inverse:   , such that inverse (x) = 1 / x Institute of Computer Software Nanjing University 2019/2/24

27 The STACK ADT (cont’d) 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)) = s empty (new) (or: empty (new) = True) not empty (put (s, x)) (or: empty (put (s, x)) = False) put ( , ) = s x s’ Institute of Computer Software Nanjing University 2019/2/24

28 The STACK ADT Institute of Computer Software 2019/2/24
Nanjing University 2019/2/24

29 Formal stack expressions
value = item (remove (put (remove (put (put (remove (put (put (put (new, x8), x7), x6)), item (remove (put (put (new, x5), x4)))), x2)), x1))) Institute of Computer Software Nanjing University 2019/2/24

30 Expression reduction (1/10)
Institute of Computer Software Nanjing University 2019/2/24

31 Expression reduction (2/10)
Institute of Computer Software Nanjing University 2019/2/24

32 Expression reduction (3/10)
Institute of Computer Software Nanjing University 2019/2/24

33 Expression reduction (4/10)
Institute of Computer Software Nanjing University 2019/2/24

34 Expression reduction (5/10)
Institute of Computer Software Nanjing University 2019/2/24

35 Expression reduction (6/10)
Institute of Computer Software Nanjing University 2019/2/24

36 Expression reduction (7/10)
Institute of Computer Software Nanjing University 2019/2/24

37 Expression reduction (8/10)
Institute of Computer Software Nanjing University 2019/2/24

38 Expression reduction (9/10)
Institute of Computer Software Nanjing University 2019/2/24

39 Expression reduction (10/10)
Institute of Computer Software Nanjing University 2019/2/24

40 Expressed differently
value = item (remove (put (remove (put (put (remove (put (put (put (new, x8), x7), x6)), item (remove (put (put (new, x5), x4)))), x2)), x1))) s1 = new s2 = put (put (put (s1, x8), x7), x6) s3 = remove (s2) s4 = new s5 = 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) Institute of Computer Software Nanjing University 2019/2/24

41 An operational view of the expression
y1 x8 x8 x5 x5 s1 s2 s3 s4 s5 s6 (empty) (empty) x2 x1 x5 x5 x5 x5 x7 x7 x7 x7 x8 x8 x8 x8 s7 (s9, s11) s8 s10 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))) Institute of Computer Software Nanjing University 2019/2/24

42 Sufficient completeness
Three forms of functions in the specification of an ADT T: Creators: OTHER  T e.g. new Queries: T ...  OTHER e.g. item, empty Commands: T ...  T e.g. put, remove Sufficiently complete specification: a “Query Expression” of the form: f (...) where f is a query, may be reduced through application of the axioms to a form not involving T Institute of Computer Software Nanjing University 2019/2/24

43 ADT Consistency An ADT specification 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. Institute of Computer Software Nanjing University 2019/2/24

44 ADT 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 (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. Institute of Computer Software Nanjing University 2019/2/24

45 Implementing an ADT Three Elements
(E1) The ADT’s specification: functions, axioms, preconditions. (Example: stacks.) (E2) Some representation choice. (Example: <representation, count>.) (E3) A set of subprograms (routines) and attributes, each implementing one of the functions of the ADT specification (E1) in terms of the chosen representation (E2). (Example: routines put, remove, item, empty, new.) Institute of Computer Software Nanjing University 2019/2/24

46 A choice of stack representation
capacity put(x:G) is --Push x onto stack --no check for possible stack overflow do count := count + 1 representation [count] := x end count (array_up) representation Institute of Computer Software Nanjing University 2019/2/24

47 使用ADT的程序应该只依赖于它的规约保证的性质，而不依赖于它的任何特定实现
信息隐蔽原则 Public part: ADT specification (E1) Secret part: Choice of representation (E2) Implementation of functions by features (E3) 使用ADT的程序应该只依赖于它的规约保证的性质，而不依赖于它的任何特定实现 Institute of Computer Software Nanjing University 2019/2/24

48 “面向对象的软件构造”含义（1） 面向对象的软件构造（OOSC）乃是基于系统所 操作之对象类型（而非系统需实现之功能）来 架构系统的途径。
Meyer: “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.” Institute of Computer Software Nanjing University 2019/2/24

49 “面向对象的软件构造”含义（2） 面向对象的软件构造乃是将系统构造为抽象数 据类型实现（可能是部分实现）的结构化组合。
Meyer:“Object-oriented software construction is the construction of software systems as structured collections of possibly partial abstract data type implementations.” 这个“抽象数据类型的实现”就是类（class） Institute of Computer Software Nanjing University 2019/2/24

50 从ADT到类 一般说类是抽象数据类型的实现 类可能只是部分实现 抽象数据类型乃是一种规约； 类是OOPL实现这种类型的设施；
但是Meyer说：“A class is an abstract data type equipped with a possibly partial implementation.” Meyer在Eiffel中强调将ADT规约作为类的一部分 强调从规约到实现的一致表达和平滑过度 类可能只是部分实现 Deferred and effective class Institute of Computer Software, Nanjing University 2019/2/24

51 类：对象程序的基本结构 模块module与类型type的统一： 二者联系:
Module = Unit of decomposition: set of services Type = Description of a set of run-time objects (“instances” of the type) 二者联系: The services offered by the class, viewed as a module, are the operations available on the instances of the class, viewed as a type. Institute of Computer Software Nanjing University 2019/2/24

52 基于类的面向对象的语言机制的强有力之处在于“类”统一了类型和模块
模块与类型的统一 模块是软件分解的单元，是语法概念 类型是某些动态对象的静态描述，是语义概念 传统语言 模块与类型分离 对象语言 模块与类型统一 类型：类是抽象数据类型的实现 模块：类是对象式程序的基本组成单元 基于类的面向对象的语言机制的强有力之处在于“类”统一了类型和模块 Institute of Computer Software Nanjing University 2019/2/24

53 类之间的关系 允引 继承 Client Heir Institute of Computer Software 2019/2/24
Nanjing University 2019/2/24

54 层次性 封装性帮助隐藏细节；模块化使结构更加有序， 但仍然不够！ 层次性是对抽象的排序和定位 实现方式 类结构关系（”is a”）
对象结构关系（”part of”） 实现方式 继承：子类，父类 单继承，多继承 聚合：拥有关系/组合关系 Institute of Computer Software Nanjing University 2019/2/24

55 Overall system structure
space_before space_after add_space_before add_space_after CHUNK FEATURES QUERIES COMMANDS length set_font add_word font hyphenate_on FIGURE remove_word hyphenate_off PARAGRAPH WORD justify word_count unjustify justified? Inheritance Client Institute of Computer Software Nanjing University 2019/2/24

56 小结 ADT Why What How Institute of Computer Software 2019/2/24
Nanjing University 2019/2/24

57 作业 1.给出队列（先进先出）的抽象数据类型 2.给出容量受限的堆栈（后进先出）的抽象数 据类型（假设最大容量为max）
Institute of Computer Software Nanjing University 2019/2/24