SICP Chapter2 读书笔记

Chapter 2: Building Abstractions with Data 构造数据抽象

这一章讨论将数据对象组合起来,形成复合数据的方式。

  • 复合数据:能够提升我们在设计程序时所位于的概念层次,提高设计的模块性,增强语言的表达能力。
  • 数据抽象:将程序中处理数据对象的表示的部分与处理数据对象的使用部分相互隔离的技术。
  • 复合数据中的闭包概念:用于组合数据对象的粘合剂不但能用于组合基本的数据对象,也能组合复合数据对象。
  • 复合数据对象:能够成为以混合与匹配的方式组合程序模块的方便接口。

2.1 Introduction to Data Abstraction 数据抽象导引

  • 数据抽象的基本思想:在构造复杂的过程时可以将一个过程用作其中的元素,这样有关过程的实现细节可以被隐蔽起来,即“使用和实现相分离”。
2.1.1 Example: Arithmetic Operations for Rational Numbers 实例:有理数的算术运算
  • Scheme的基本复合结构称为“序对”,序对本身也是数据对象,可以用于构造更复杂的数据对象。

例子:使用cons,car和cdr来表示一个有理数:

(define (make-rat n d)
  (cons n d))
(define (numer x)
  (car x))
(define (denom x)
  (cdr x))
2.1.2 Abstraction Barriers 抽象屏障

上图表示有理数系统的结构,水平线表示抽象屏障,表示系统的不同层次,每一层中的过程构成了所定义的抽象屏障的界面,联系起系统中的不同层次,使得程序容易维护和修改。

2.1.3 What Is Meant by Data? 数据意味着什么?
  • 一般而言,我们总可以将数据定义为一组适当的选择函数和构造函数,使这些过程成为一套合法的表示。

我们可以不使用数据结构,只使用过程来实现序对:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= n 1) y)
          (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))

过程和数据的界限被模糊化了;尽管实际语言的实现不是上面的形式,但是这确实是表示序对的合法方式。

习题2.06:
介绍Church数的表示形式,完全用过程实现整数算术系统:

(print "Church numerals")
 
(define zero
  (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda(x) (f ((n f) x)))))
 
(define (church-to-int ch)
  ((ch (lambda (x) (+ x 1))) 0))
(define one
  (lambda (f) (lambda (x) (f x))))
(define two
  (lambda (f) (lambda (x) (f (f x)))))
(church-to-int one)
(church-to-int two)
 
(define (add a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))
(church-to-int (add one two))

2.2 Hierarchical Data and the Closure Property 层次性数据与闭包性质

  • 建立元素本身也是序对的序对的能力成为cons的闭包性质。
  • 一般来说,某种组合数据对象的操作满足闭包性质,即通过它组合起数据得到的结果本身还可以通过同样的操作再进行组合。
2.2.1 Representing Sequences 序列的表示
(list <a1> <a2> ... <an>)

等价于:

(cons <a1>
      (cons <a2>
            (cons ...
                  (cons <an>
                        nil)...)))
  • 表操作
  • 对表的映射

map构建一层抽象屏障,将实现表变换的过程的实现,与如何提取表中元素以及组合结果的细节隔离开。

2.2.2 Hierarchical Structures 层次性结构
  • 树,表示元素本身也是序列的序列,元素即树的子树。

统计树的叶子数的过程实现:

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

对树的映射:

  • map与递归相结合是处理树的一种强大的抽象:
(define (sacle-tree tree factor)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (* tree factor))
        (else (cons (sacle-tree (car tree) factor)
                    (sacle-tree (cdr tree) factor)))))
  • 另一种方法:将树看成子树的序列,并对它使用map:
(define (scale-tree tree factor)
  (map  (lambda (sub-tree)
          (if (pair? sub-tree)
              (scale-tree sub-tree factor)
              (* sub-tree factor)))
        tree))
2.2.3 Sequences as Conventional Interfaces 序列作为约定的界面
  • 使用约定的界面是一种强有力的设计方式。
  • 为了展现信号流的结构,组织程序的关键点是处理从一个阶段流向下一个阶段的“信号”。

例子:计算值为奇数的叶子的平方和:

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

*注意它以一棵树为参数。

例子:生成只保留偶数的斐波拉契数表:

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k l)))
              (next (+ k 1))))))
  (next 0))

上面两个过程看起来结构相差很大,但是计算的抽象描述是非常相似的:

  1. 从枚举器开始,产生给定的树的树叶组成的信号。
  2. 信号流过过滤器,过滤掉不符合规则的信号。
  3. 通过一个映射,转换每一个元素。
  4. 积累器把所有的元素组合起来。

通过提供一个标准不见的库,并使这些不见都有着一些能以灵活方式互相连接的约定接口,将能够进一步推动模块化设计。
在实际工程设计中,模块化结构是控制复杂性的一种强大的策略。

2.2.4 Example: A Picture Language 实例:一个图形语言
  • 这一节通过介绍一种用于画图的简单语言来展现数据抽象和闭包的强大能力。
  • 基本数据抽象和“画家”都用过程来实现,这使得语言能够以一种统一方式去处理各种本质上完全不同的画图能力。
  • 实现组合的方法满足闭包性质,这使得我们方便构造各种复杂的设计。

分层设计:

  1. 一个复杂的系统应该通过一系列的层次构造出来,为了描述这些层次,需要用到一系列的语言。
  2. 构造各个层次的方法:设法组合起作为这一层次中部件的各个基本元素,这样构造出来的部件又能成为下一个层次的基本元素。
  3. 在分层设计中,每个层次上所用的语言都提供了一些基本元素和组合手段,以及对层次中细节做抽象的方法。

2.3 Symbolic Data 符号数据

  • 之前使用的所有复合数据,都是从数值出发构造起来的;
  • 这一章引入将任意符号作为数据的功能,来扩充我们所用语言的表达能力。
2.3.1 Quotation 引号
  • 一个单引号’的意义是引用下一个对象。
  • 但引号的这种使用方式,违背了“语言中所有的复合表达式都应该由括号限定,都具有表的形式”的普遍性原则。
  • 通过引进特殊形式quote可以避免违背原则,即把‘a改写成(quote a)。
  • 我们可以通过求值'()来得到空表,就不需要变量nil了。
2.3.2 Example: Symbolic Differentiation 实例:符号求导

对抽象数据的求导:

;e是变量吗
(define (variable? x)
  (symbol? x));symbol?判断变量是不是符号
;v1和v2是同一个变量吗
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
;e是和式吗
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
;e的被加数
(define (addend s) (cadr s))
;e的加数
(define (augend s) (caddr s))
;构造起a1和a2的和式
(define (make-sum a1 a2) (list '+ a1 a2))
;e是乘式吗
(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
;e的被乘数
(define (multiplier p) (cadr p))
;e的乘数
(define (multiplicand p) (caddr p))
;构造起来m1与m2的乘式
(define (make-product m1 m2)
       (list '* m1 m2))
;求导
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))
(deriv '(+ x 3) 'x)
(deriv '(* x y) 'x)
(deriv '(* (* x y) (+ x 3)) 'x)
'(+ 1 0)
'(+ (* x 0) (* 1 y))
'(+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3)))
2.3.3 Example: Representing Sets 实例:集合的表示

集合作为未排序的表:

;判断是不是表成员
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))
;向表增加一项
(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))
;合并
(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

集合作为排序的表:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))
    
(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
       '()
       (let ((x1 (car set1)) (x2 (car set2)))
         (cond ((= x1 x2)
                (cons x1
                      (intersection-set (cdr set1)
                                        (cdr set2))))
               ((< x1 x2)
                (intersection-set (cdr set1) set2))
               ((< x2 x1)
                (intersection-set set (cdr set2)))))))

集合作为二叉树:

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))
  
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))
;插入要找到正确位置
(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))
2.3.4 Example: Huffman Encoding Tree 实例L哈夫曼编码树

哈夫曼树的表示:

;树的表示
;leaf 符号 权重
(define (make-leaf symbol weight)
  (list 'leaf symbol weight))
  
(define (leaf? object)
  (eq? (car object) 'leaf))
  
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))
(define (make-code-tree left right)
  (list left
        right
        (append (symbols left) (symbols right))
        (+ (weight left) (weight right))))
        
(define (left-branch tree) (car tree))
(define (right-branch tree) (cadr tree))
(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))
(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (caddr tree)))

哈夫曼树解码过程:(以一个0/1表和一棵哈夫曼树作为参数)

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))

带权重元素的集合:

将树叶和树的集合表示为一批元素的表,按照权重的升序排列表中的元素。

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))
(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)
                               (cadr pair))
                    (make-leaf-set (cdr pairs))))))

2.4 Multiple Representations for Abstract Data 抽象数据的多重表示

  • 2.1-2.3构造了抽象数据的系统,但是系统的缺陷是没办法让多种数据并存,这节以复数为例解决这个缺陷:
  • 一个数据对象可能有多种表示方式,我们希望能处理多种表示形式。如复数有直角坐标表示法(实部与虚部)和极坐标表示法(模和幅角)
  • 构造通用过程,使数据对象带有“标志”。
2.4.1 Representations for Complex Numbers 复数的表示

直角坐标表示法与极坐标表示法:

(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))
(define (angle z)
  (atan (imag-part z) (real-part z)))
(define (make-from-real-imag x y) (cons x y))
(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))
(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
  (make-from-real-imag (- (real-part z1) (real-part z2))
                       (- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                     (+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                     (- (angle z1) (angle z2))))
2.4.2 Tagged data 带标志数据
  • “最小权限原则”:在实现上面的复数系统的时候,采用两种形式,由选择函数和构造函数形成的抽象屏障,使我们可以把为自己所用的数据对象选择具体表现形式的事情尽量往后推,而且还能够保持系统设计的最大灵活性。
  • 不到迫不得已不做决策
  • 利用类型标志,来确定类型,选择函数。

增加类型标志“rectangular”和“polar”:

(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))
(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))
(define (polar? z)
  (eq? (type-tag z) 'polar))
2.4.3 Data-Directed Programming and Additivity 数据导向的程序设计与可加性

基于数据的分派:检查一个数据项的类型,并据此去调用某个过程。

像2.4.2实现的分派有两个弱点:

  1. 通用过程必须知道所有不同的表示,若我们想为复数系统增加一种表示方式,我们就必须为这种表示方式标志为一种新类型,而且要在每个通用过程里增加一个检查新类型并选择函数的子句。
  2. 由于1,我们必须增加很多过程,同时,我们必须保证整个系统里不存在两个相同名字的过程,在增加新过程时会有命名冲突,可能出现需要去修改以前设计的过程名字的情况。

总的来说:2.4.2的分派技术不具有可加性。在每一次增加一种新类型的时候,需要去修改原过程,修改类型判断,增加代码,修改过程名字。

我们需要能将系统设计进一步模块化的方法:数据导向的程序设计。

设计一个二维表格,其中一个维上包含着所有可能操作,另一个维包含所有可能类型。

复数系统的操作表:

 

定义两个过程put和get来实现操作-类型表格:

put <op> <type> <item>

put:将表项<item>加入表格中,以<op>和<type>作为这个表项的索引。

get <op> <type>

get:从表中查找与<op>和<type>对应的项,如果找到就返回找到的项,否则就返回假。

实现复数操作-类型表格:

(define (install-rectangular-package)
  ;internal procedures
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))
  (define (make-from-real-imag x y) (cons x y))
  (define (magnitude z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))
  (define (angle z)
  (atan (imag-part z) (real-part z)))
  (define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))
  ;interface the rest of the system
  (define (tag x) (attach-tag 'rectangular x))
  (put 'real-part '('rectangular) real-part)
  (put 'imag-part '('rectangular) imag-part)
  (put 'magnitude '('rectangular) magnitude)
  (put 'angle '('rectangular) angle)
  (put 'make-from-real-imag '('rectangular)
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang '('rectangular)
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)
  • 数据导向的程序设计,最关键的思想是通过显式的操作-类型表格的方式,管理程序中的各种通用性操作。
  • 上面使用的程序设计风格是一种基于类型进行分派的组织方式,其中让每个操作管理自己的分派。
  • 从效果上看,这种方式就是将操作-类型表格分解位一行一行,每个通用型过程表示表格中的一行。
  • 另一种实现策略是将这一表格按列进行分解,不是采用一批“只能”操作区基于数据类型进行分派,而是采用“只能数据对象”,让它们基于操作名完成所需要的分派工作。

为了这种实现策略,我们需要将每一个数据对象表示为一个过程。

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'iamg-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (square x) (square y))))
          ((eq? op 'angle) (atan y x))
          (else
           (error "Unkonown op -- MAKE-FROM-REAL-IMAG" op))))
dispatch)
(define (apply-generic op arg)
  (arg op))

这种风格的程序设计称为消息传递,将数据对象设想为一个实体,它以消息的方式接受所需要操作的名字。

2.5  Systems with Generic Operations 带有通用型操作的系统

  • 我们需要:不但能定义出能够在不同表示上的通用操作,还能定义针对不同参数种类的通用型操作。
2.5.1 Generic Arithmetic Operations 通用型算术运算

设计通用型的算术运算:

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))
(define (install-scheme-number-package)
  (define (tag x)
    (attach-tag 'scheme-number x))
  (put 'add '(scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'sub '(scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'mul '(scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div '(scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'make '(scheme-number scheme-number)
       (lambda (x) (tag x)))
  'done)
  
  (define (make-scheme-number n)
  ((get 'make 'scheme-number) n))

类似地可设计出有理数和复数算术运算系统

2.5.2  Combining Data of Different Types 不同类型数据的组合
  • 2.5.1我们定义了算术系统,可以进行整数,有理数,复数,或者定义的其他数据类型的运算。
  • 但这是相互独立分离的,即只能进行两个整数运算,或者两个有理数运算,不能实现一个整数与有理数的运算。

所以我们要引进跨类型的操作:

方法一:为每一种跨类型操作提供专门的过程处理。

  • 这样做是可以实现并完成跨类型运算,但是太麻烦。每添加一种类型,要增加太多过程。

方法二:强制类型转换

  • 转换基础:类型之间的适当转换只依赖于类型本身,而不依赖于所实际应用的操作。

类型的层次结构:就是“继承”。

优点:

  1. 将一个新类型加入层次结构的难度大大降低。
  2. 类型去“继承”它的超类型的所有操作变得容易实现。

不足:

  1. 一个类型可能同时有多个子类型和多个超类型,就会出现“菱形结构”导致不止一种方法去“提升”一个类型。如等腰直角三角形既是等腰三角形也是直角三角形。

1 thought on “SICP Chapter2 读书笔记

发表评论

电子邮件地址不会被公开。 必填项已用*标注