[软件构造] ADT 抽象数据类型：软件构造课程的灵魂

软件构造] ADT 抽象数据类型：软件构造课程的灵魂"/>

[软件构造] ADT 抽象数据类型：软件构造课程的灵魂

Intro

• enable us to sepestructure itself
• rate how we use a data strustire in a program from the particular form of the data
• 能够分离数据结构本身和我们如何使用数据结构
• address a dangrous problem :cilents making asssumptions about the type’s internal representation解决了这个危险的问题： 甲方需要假设数据结构内部的表示

What abstraction means?

• goes by 遵循
• slightly diffferent shades of meaning 细微差别
• Abstraction: Omitting or hiding 用简单的 高级的想法 省略 低层的想法
• Modularity :Dividing a system into components or modules,each of which can be designed ,implemented ,test, resoned about ,and reused separately from the rest of the system 模块（独立设计 实现 测试 复用）
• encapsulation:Building a wall around a module(a hard shell or capsule)sp that the module is …设计一个壳（一大堆接口的集合）来全权代表其内部

move beyond 超越
abstractions for method =spec（规约 对方法的抽象 对动词的抽象）
abstraction for data=ADT

User-defined types

seminal work 开创性的工作
The key idea of data abstraction is that a type is charactersized by the operations youcan perform on it
Somthing literal :对数据的抽象（ADT）=一堆数（数据）+数据结构（静态的）+对数据的操作（动态的） （相当于对名词的抽象 不过是一个聚合的数据类型（数据的容器））

• 数据容器（或者类型）的区别主要在于能进行的操作的不同
• ADT 是从 操作 角度对data进行的抽象

Classifying types and operations

• Types= mutable / immutable type
• Ops of ADT=Creators + Producers +Observers+ Mutators
• Mutators=Functions
• schematically 图式的
• +号表示 * 号意义同形式语言
• 以笛卡尔乘积形式给出

ADT examples

An abstract type is defined by operatios

Designing an abstract type

• a few,simple operations
• coherent behaior ,no corner case
• nested list 内嵌列表
• it should not mix generic and domain-specific features

Repesentation independence

• 实现的独立性
• spec

Realizing ADT concepts in Java

Test ADT

Reading 11 Abstraction function and Rep invariants 抽象功能与代表不变量

• designed to accomodate changs withour rewriting 适应变化
• repreesntation exposure 代表暴露
• what it means for a class implement an ADT 我们用class来实现ADT意味着什么
• notions of abtraction funcs and rep invariants (make it easier to catch bugs by D S error)

invariants

• this is done by hiding or protecting the variables involved in the invariants (e.g. using langguages like private ),and allowing accesss only through opts withs well_defi…ed
• contracts.实现（is done ）通过语言特性(private 修饰符) contracts(可以翻译为协议 就舒服多了)

immutability

• a trival example一个简简单单的例子
• mechanisms = method
• public / private / readonly keyworrds
• That’s not the end of the story. 故事余音。（这句话好美呀）
• aliases = another name
• defensive copying 防御性拷贝：making a copy of a mutable object to avoid leaking out references to the rep.(That is :defense by copying)
• defects: too large to copy efficiently
• （好像有点明白 copy 和 赋值的区别 copy 是从变量到变量 赋值是从常量到变量）

Rep invariants and abstraction func 代表不变量 抽象函数

两个space ADT_value_space / Rep_value_space

• this part is to answer Qs.

• ADT_value_space={values| supported from the client’s point of view}

• Rep_value_space={objects| we need to implemented }

• {Bigint} / {Array1,Array2}

• 所以代表制空间是实现层的数据对象的集合

• ADT 是抽象层的数据对象的集合

• (这里的space 指集合 不指物理上的空间)

• teak a deeper look at the theory underlying abatract data types

• subtle traps 细微的陷阱

• a ATD type is implemented as a networks of bojects. (class 's network)

• Now, of course, the implementer of the abstract type must be interested in the representation values, since it is the implementer’s job to achieve the illusion of the abstract value space using the rep value space.

• But we (the implementee of ADT type) should focus on Rep values ,(Since implementaion means achieveing the uillusion of the ADT value using Rep value space 因为”实现“这个工作本身就意味着 让 用 实现层的数据对象 完成对 抽象层的数据对象 的支持)

• A 是字符char的数学集合

• R 是string的集合

• 这里 A string represent a set of characters

• 已经发现了本节的key 在于如何理解represent这个动词

• 显然，需要理解一些名词，不然为啥叫“学习新名词”呢。

• map : . verb 映射

abstraction function(AF)

• AF:R -> A
• AF means maps (.verb) rep_values to the_abstarct_value
• and this map need to be surjective(onto ) no necessarily injective(one-to to )需要满射，不必单射

Rep invariant(RI)

*RI:R ->boolean
For a rep value r, RI® is true if and only if r is mapped by AF.

• a value to describe whether or not a element in R set have a corresponding value in A set.
• 
  RI(“a”) = true, RI(“ac”) = true, and RI(“acb”) = true

Tips to ADT implement

• not only choosing the two spaces (ADT value space for spec / Rep value space for implement )
• but also deciding which rep valuesare legal ,and how to interpret them as abstract values
• 所以到这里 What Rep_value means ?
• What Rep means ?
• What Rep_value_space means ?
• 有点乱 过一段时间再重新理一下

Checking the rep invariants 使用断言语句检查内部不变量

• Somrthing litral:
• 其实就是把 ADT / class 的实现过程中涉及的值分了两类 内部的 外部的 ,因为集合吗 ，所以两个“空间”这个词 也应该就是private修饰的不要变
• 使用断言 assert()检查

No null values in the rep

Benefiicent mutation

Documenting the AF ,RI,and safety frome rep exposure

What an ADT spec may talk about?

• 一个很好的办法去理解图 就是C语言中的函数
• 作为调用者 我们关心 函数功能 输入参数 返回参数
• 作为函数的实现者 我们关系 函数的常量 变量 以及 他们与外部量的映射
• 当我们把 函数 这个过程调用的概念 从ADT角度看的时候
• 一切是水到渠成的。

ADT invariants replace preconditions

• 把变量名写具体点，实际上就是把 数据 好好封装
• 规约文本 （Spec 是contract 那就是doc 对的）的precondions就能少写一点

How to establish invariants

Recipes for programming

• ADTs are at the heart of software constuction for correctness ,clarity ans changeability.
• ADT是本课程的heart
• "Test-first"理念
  Writing an abstract data type
  Spec. Write specs for the operations of the data type, including method signatures, preconditions, and postconditions.
  Test. Write test cases for the ADT’s operations.
  Again, this puts pressure on the spec. You may discover that you need operations you hadn’t anticipated, so you’ll have to add them to the spec.
  Implement. For an ADT, this part expands to:
  Choose rep. Write down the private fields of a class (or, as we’ll see in future readings, choose and define a different kind of rep). Write down the rep invariant and abstraction function as a comment.
  Assert rep invariant. Implement a checkRep() method that enforces the rep invariant. This is critically important if the rep invariant is nontrivial, because it will catch bugs much earlier.
  Implement operations. Write the method bodies of the operations, making sure to call checkRep() in them. You’re done when the tests are all passing.
  And let’s broaden it further to a recipe for:

Writing a program
(consisting of ADTs and functions)

Choose data types. Decide which ones will be mutable and which immutable.
Choose functions. Write your top-level main function and break it down into smaller steps.
Spec. Spec out the ADTs and functions. Keep the ADT operations simple and few at first. Only add complex operations as you need them.
Test. Write test cases for each unit (ADT or function).
Implement simply first. Choose simple, brute-force representations. The point here is to put pressure on the specs and the tests, and try to pull your whole program together as soon as possible. Make the whole program work correctly first. Skip the advanced features for now. Skip performance optimization. Skip corner cases. Keep a to-do list of what you have to revisit.
Iterate. Now that it’s all working, make it work better. Reimplement, optimize, redesign if necessary.

• 不复述了 基本就是

1. 写规约的文本
2. 写一些测试的文本和代码
3. 写代码（method / ADT / proc）
   • 把内部量定好
   • 断言检查内部不变量

• (这些其实再python的那个项目里我们都见到过了 只是组织了一下 加了一些新的名词而已)

用 概念公式 学习OOP