2.4 Multiple Representations for Abstract Data - CloneableX/SICP-learning GitHub Wiki

本书之前的内容已经介绍了数据抽象，它能够通过分离数据实现及数据维护程序达到结构化程序的目的。例如，在设计有理数系统时已经展示过如何将有理数的数据实现与有理数运算规则之间进行分离。数据抽象的关键是建立抽象屏障，有理数的示例中是它的构造器和选择器，通过此方式隔离有理数的运算和表示方式。类似的抽象屏障还有有理数的基础运算（有理数的加、减、乘、除），这些基础运算将被更高级别的程序使用。

数据抽象屏障可以有效控制系统的复杂性。通过将数据对象的具体表现方式隔离，在设计庞大系统时便可以从相对独立的小任务开始。但这种数据抽象方法还不够强大，因为它还不能处理所有数据对象的潜在表现方式。

因为数据对象的多重表现方式也是一种常见情况。举个简单的例子，复数可以用两种几乎等同的方式表示：矩形形式（实部和虚部）和极坐标形式（大小和角度）。有时矩形形式更适合表达，有时极坐标形式更适合。于是，我们可以想象存在一个复数系统，它能够通过两种形式表示，而且对复数进行运算时无论哪种表现形式都可以得到正确结果。

更重要的是，程序系统通常是由许多人在长期工作中设计出来的，其要求会随着时间的推移而改变。在这样的环境下，数据对象表现的设计肯定无法在一开始时完全确定。所以需要通过数据抽象屏障隔离数据对象表现方式对使用的影响，同时也需要抽象屏障能够保证多种表现形式同时存在。而且，许多大型系统都是基于已经被独立完成的模块继续创建，所以需要赋予程序员在尚未设计和实现这些模块的情况下向大型系统增量添加对应模块的能力。

在本节中，我们将学习如何处理在不同情况下采用不同表现的数据对象。解决方案是使用通用程式，这种程式可以操作存在多种表现方式的数据。构建通用程式的主要技术是类型标识，也就是说数据对象中会包含能够直接表示自身类型的标识。接着会讨论数据导向编程，它是一种利用通过操作进行增量组合式系统的实现策略，它不仅实用而且十分方便。

本节内容从一个简单的复数示例开始，接着将展示如何通过类型标识和数据导向的方式设计兼容矩形形式和极坐标形式的复数对象。然后基于复数对象的构造器和选择器开发运算程式。最终复数系统将包含两种抽象屏障，如下图。其中竖直的部分是对更高级别操作的隔离，水平的屏障用于隔离不同表现方式的设计。

Data-abstraction barriers in the complex number system

在下一节会沿用本节的类型标识和数据导向方式开发一个通用算法包。此算法包将提供加减等程式，这些程式能够对所有类型的数据进行运算，并且当出现新的数据类型时也可以轻易扩展适应新的数据类型，然后展示如何使用通用算法包执行代数式。

复数的表现形式

现在我们打算开发一个能够执行复数算术运算的系统，看上去虽然简单但它需要使用通用操作才能实现。当复数作为有序序对时存在两种有效的表现方式，分别是矩形形式（分为实数和虚数部分）和极坐标形式（大小和角度）。在上一节内容中已经展示过如果通过类型标识和通用操作使不同的表现方式共存。

与有理数类似，复数也是通过有序序对表示。可以认为在平面直角坐标系中存在两个轴，分别代表实轴和虚轴，如下图。复数为此坐标系中的一个点，表示为 z=x+iy（其中 i^2=-1），其中实轴坐标值为 x，虚轴坐标为 y。

Complex numbers as points in the plane

于是复数的加法被转化为坐标的加法，具体公式如下：

Real-part(z1+z2) = Real-part(z1) + Real-part(z2)
Imaginary-part(z1+z2) = Imaginary-part(z1) + Imaginary-part(z2)

不过在计算复数的乘法时通过极坐标的转化方式更加容易。所以复数的乘积是通过将一个复数的长度拉伸到另一个的长度，然后将一个的角度旋转至另一个的角度产生，具体公式如下：

Magnitude(z1 * z2) = Magnitude(z1) * Magnitude(z2)
Angle(z1 * z2) = Angle(z1) + Angle(z2)

此时复数存在了两种适合不同情况的表现方式。不过从编写程序的角度出发，数据抽象指导我们在处理复数的运算时应该忽略它在表达方式上的不同。例如，在矩形形式中也能够得出复数的大小，在极坐标中也能够获取复数的实数部分。

所以在设计此系统时需要沿用处理有理数的策略，先假设复数存在 real-part imag-part magnitude angle 几个选择器和 make-from-real-imag make-from-mag-ang 两个构造器，其他的复数运算都在此基础上设计。所以对于任意复数 z 都可以按如下方式使用：

(make-from-real-imag (real-part z) (imag-part z))
(make-from-mag-ang (magnitude z) (angle z))

按照之前的复数计算公式，通过预设的复数构造器和选择器便可以实现复数的基础运算：

(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) (mangitude z2))
                     (- (angle z1) (angle z2))))

为了实现复数包，现在需要实现复数的构造器和选择器。按照上述讲解的内容无论是矩形形式还是极坐标形式都可以通过序对表示，不过要选择哪种形式表现复数呢？

为了使不同的表现选择更加具体，先想象此时存在两位程序员，分别是 Ben 和 Alyssa，他们分别实现了复数系统。其中 Ben 选择通过矩形形式表示复数，所以实数和虚数选择器直接返回通过构造器传入的实数和虚数即可，但是极坐标中的大小和角度便需要进行计算，具体公式如下：


按照上述公式将实数与虚数 (x,y) 转换为了大小和角度 (r,A)。所以 Ben 的构造器和选择器实现如下：

(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))))

而 Alyssa 恰恰相反，她通过极坐标方式表示复数，所以她的构造器和选择器实现如下：

(define (real-part z) (* (magnitude z) (cos (angle z))))
(define (imag-part z) (* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))
(define (make-from-mag-ang r a) (cons r a))

数据抽象的规则确保了无论构造器和选择器按照 Ben 的还是 Alyssa 的方式实现，复数的基础运算程式 add-complex sub-complex mul-complex div-complex 都可以正常运转。

标识数据

换一个角度，其实还可以将数据抽象视为按最小承诺原则建立的应用。在实现复数系统时，既可以使用 Ben 的矩形形式也可以使用 Alyssa 的极坐标形式，主要是因为由构造器和选择器组成的抽象屏障保证了数据对象不同表现方式的兼容可能性，为系统提供了充足的灵活性。

最少承诺原则还能做到更加极限。只要你愿意，甚至可以在完成构造器和选择器的设计后再维护拥有多义的表现形式，就像复数系统中既可以使用 Ben 的方案也可以使用 Alyssa 的方案一样。即使两种表现形式同时出现在一个系统中，也只需要区分当前的数据对象属于哪种表现形式即可。例如，当需要获取序对 (3, 4) 中的 magnitude 时无法明确结果应该是 5（使用矩形形式时）还是 3（使用极坐标时）。区分不同数据对象表现形式的最直接方式是使用 类型标识（type tag），通过将标识 rectangular 和 polar 作为复数的组成部分实现。当维护复数时，便可以通过类型标识识别它属于哪种表现形式。

为了维护标识数据，先假设已经存在 type-tag 和 contents 程式可以从数据对象中提取标识和实际内容（也就是极坐标或矩形形式坐标）。同时需要假设 attach-tag 程式能够将标识和实际内容结合并产生被标识的数据对象。实现这些程式最直接的方式是使用列表结构：

(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)))

在上述程式的基础上便能够建立谓词 rectangular? 和 polar?，分别用于判断数据对象是矩形形式还是极坐标形式，具体实现如下：

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar z) (eq? (type-tag z) 'polar))

当有了类型标识，Ben 和 Alyssa 的代码便可以同时存在于同一系统中。Ben 的程式构造复数时都标识为 rectangular，Alyssa 的程式构造的复数都标识为 polar，另外还需要保证他们的程式名称不冲突。一种解决方式是对 Ben 关于数据对象表现形式的程式后都加上 rectangular 后缀，Alyssa 关于数据对象表现形式的程式后都加上 polar 后缀。下面是 Ben 的程式的修改：

(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))
(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a)
  (attach-tag 'rectangular
              (cons (* r (cos a)) (* r (sin a)))))

接下来修改 Alyssa 的程式：

(define (real-part-polar z)
  (* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z)
  (* (magnitude-polar z) (sin (angle-polar z))))
(define (magnitude-polar z) (sin (angle-polar z)))
(define (angle-polar z) (cdr z))
(define (make-from-real-imag-polar x y)
  (attach-tag 'polar
              (cons (sqrt (+ (square x) (square y)))
                    (atan y x))))
(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

每个通用选择器都是通过按照数据对象的标识调用相应的程式处理实现。例如，需要获取复数的 real-part 时，可以通过其中的类型标识确定使用 real-part-rectangular 处理还是使用 real-part-polar 处理。然后，再通过 contents 提取无标识的原始数据给矩形程式或极坐标程式。

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type: REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
    (imag-part-rectangular (contents z)))
  ((polar? z)
    (imag-part-polar (contents z)))
  (else (error "Unknown type: IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
    (magnitude-rectangular (contents z)))
  ((polar? z)
    (magnitude-polar (contents z)))
  (else (error "Unknown type: MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
    (angle-rectangular (contents z)))
  ((polar? z)
    (angle-polar (contents z)))
  (else (error "Unknown type: ANGLE" z))))

为了实现复数算术运算，需要使用 add-complex、sub-complex、mul-complex 和 div-complex，因为现在的选择器已经被改造为通用程式了，所以无论使用哪种表现形式都可以。例如，add-complex 具体实现如下：

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))

最后，还需要选择通过 Ben 的表现方式还是 Alyssa 的表现方式表示复数。最合理的选择是，当使用实数和虚数构建时产生矩形形式复数，使用大小和角度时产生极坐标复数。

(define (make-from-real-imag x y)
  (make-from-real-imag-rectangular x y))

(define (make-from-mag-ang r a)
  (make-from-mag-ang-polar r a))

目前复数系统的结构如下图所示。整个系统被分解为了三个互不依赖的部分，分别是复数算术运算、Alyssa 的极坐标实现和 Ben 的矩形实现。极坐标和矩形的实现由 Alyssa 和 Ben 分别完成，并且这两种实现方式由第三位程序员为其提供统一的构造器和选择器接口。

Structure of the generic complex-arithmetic system

当每个数据对象都被标识了类型时，选择器便可以通过通用行为操作数据。所以每个选择器要根据不同的类型标识将数据应用于不同的运算程式。

要注意的是，通用算法是不同表现形式的接口，在给定的表现方式实现中复数是一个没有标识类型的序对。当通用选择器处理 polar 类型的复数时，它将剥离类型标识并通过 Alyssa 的程式返回复数内容。当流程反转时也一样，Alyssa 使用通用构造器构建复数时，产生的复数会携带相应的类型标识，以便更高级的程式能够判断。剥离和组装类型标识数据对象的规则是依靠程式间的层层传递实现，这是一种重要的系统组织策略。

数据导向编程和可加性

通过检测数据对象的类型再调用相应程式的通用策略称为 按类型分发（dispatching on type）。这是一种在系统设计中有效保障模块化的策略，不过上一节的分发策略实现中还有两个重大的缺点。一个是通用接口程式必须了解所有表现形式。例如，现在打算将一种新的复数表现形式加入系统中，系统中的每个通用接口程式都需要知晓新的表现形式的数据类型，以及它相应的选择器等。

另一个缺点是，即使个别表现方式可以分别设计，但系统中同名的程式无法共存。这也是 Ben 和 Alyssa 必须修改原先程式名字的原因。

这项技术的两个缺点引出的问题是在实现通用接口时难以进行增量开发。因为当每次加入新的表现形式时就需要修改所有通用选择器，如果这些程式是单独设计还需要注意避免与系统程式重名的情况。虽然需要修改的代码都比较简单，但还是需要修改，这也是造成源码不方便和大量错误的根本原因。目前复数系统的表现方式比较少，所以没有表现出太大的问题，但如果复数系统需要实现几百个不同的表现形式呢？这种情况下，大量的通用选择器需要被维护，并且实际上也不会有任何一位程序员了解所有的接口程式和所有的表现形式。这个问题不仅真实存在，还大量存在于大型数据库管理系统中。

我们需要一个更深入模块化系统设计的方法。这种编程技术叫做 数据导向编程（data-directed programming）。为了了解数据导向编程如何运作，需要通过一组运算不同类型的通用程式为实例讲解，更确切地说，是在二维表格中不同类型列对应相应类型的运算的方式。在表格中的条目是对表格中不同类型参数实现运算的程式。在上一节复数系统的开发过程中，不同运算、数据类型和实际程式联系是通过通用程式中的条件表达式实现，这些信息可以组织为表格形式，如下图。

Table of operations for the complex-number system

数据导向编程是通过直接通过表格进行程序设计。在此之前，我们设计的复数系统使用了两个表现形式的包，每一种表现形式都对应着一类数据类型。接口程式会根据参数类型查找相似的程式名称，并调用此程式。如果按照这种方式实现，当添加一种新的表现形式时，便不再需要修改已经编写好的代码，只需要为表格增加一个条目即可。

为了上述计划的顺利实现，需要先假设此时已经存在两个程式 put 和 get，它们负责维护运算-类型对应表。

  • (put <op> <type> <item>) 将 <item> 加入表格，并且可以通过 <op> 和 <type> 查找它
  • (get <op> <type>) 查找表格中的 <op> 和 <type>，并返回符合条件条目，如果没有对应的条目将返回 false

现在先假设 Scheme 中已经存在 put 和 get 程式，在第 3 章再讨论实现这两个程式的细节。

将数据导向编程应用于复数系统可以如下操作。Ben 依然独立开发矩形形式的代码，他需要定义一组程式以及能够告知系统如何向表格添加矩形类型操作的接口。这些都是通过调用下列程式实现：

(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 to 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)

其中的内部程式与本章一开始 Ben 实现的一样，不同的是声明了系统可调用的接口。而且将各个程式定义为内部程式后，Ben 不再需要为名称冲突担心。Ben 通过 real-part 作为操作名，rectangular 作为类型名向系统声明 real-part 程式，其他的选择器声明也是类似操作，并且接口声明还可以声明构造器接口。这些定义与 Ben 的内部构造器定义相同，只是它们使用 tag。

Alyssa 的极坐标表示也是类似：

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  (define (angle z) (cdr z))
  (define (make-from-mag-ang r a) (cons r a))
  (define (real-part z) (* (magnitude z) (cos (angle z))))
  (define (imag-part z) (* (magnitude z) (sin (angle z))))
  (define (make-from-real-imag x y)
    (cons (sqrt (+ (square x) (square y)))
          (atan y x)))

  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'polar x))
  (put 'real-part '(polar) real-part)
  (put 'imag-part '(polar) imag-part)
  (put 'magnitude '(polar) magnitude)
  (put 'angle '(polar) angle)
  (put 'make-from-real-imag 'polar
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'polar
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

按照上述实现方式，即使 Ben 和 Alyssa 的程式名字相同，但由于只是内部程式的缘故所以对使用毫无影响。

复数选择器通过通用操作程式 apply-generic 访问表格，并将参数应用通用程式。apply-generic 根据操作名称和参数类型调用指定程式。

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error
            "No method for these types: APPLY-GENERIC"
            (list op type-tags))))))

通过 apply-generic 可以定义下列通用选择器：

(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))

当系统中加入一个新的表现方式时这些程式并不需要修改。

同样也可以从表格中提取构造器，使其在代码包之外应用。与之前的实现一样，如果提供的数据为实数和虚数便构建矩形形式的数据，如果提供的数据为大小和角度则构建极坐标形式的数据。

(define (make-from-real-imag x y)
  ((get 'make-from-real-imag 'rectangular) x y))

(define (make-from-mag-ang r a)
  ((get 'make-from-mag-ang 'polar) r a))

消息传递

数据导向编程的关键在于将通用程式的处理对象转变为了操作与类型对应表。这种编程风格主要用于处理需要按类型分发调用对应程式的情况，实际上是通过将操作类型对应表中的数据分成一行一行地处理，因为表格的每行都表示通用操作程式。

另一种策略是通过将表格按列分解的方式处理，按类型分发替换为集成操作，按操作名称分发替换为集成数据对象。按照这种方式能够将相关的事情集中到同一数据对象中，对于矩形数据，就通过接收操作名称的程式和操作对应的程式实现。在这种情况下，make-from-real-imag 可以改写为：

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

相应地，apply-generic 程式只需要提供操作名称给数据对象，数据对象便可以正常运作。

(define (apply-generic op arg) (arg op))

要注意的是 make-from-real-imag 返回的结果是一个内部程式 dispatch，这个程式在 apply-generic 需要调用具体程式时使用。

这种编程风格称为 消息传递（message passing）。当一个数据对象被视作接收请求的实体，请求本身是操作名称时，此时整个系统就如同消息传递一般。在第 2 章时我们已经展示了一个关于消息传递的例子，当时通过非数据对象的方式实现了 cons car cdr 三个程式。刚才提及的消息传递并不是一个数学技巧，但它是一项在通过通用操作组织系统上十分有用的技术。在后面章节，讨论通用算术运算时依然会基于数据导向编程，而不是消息传递。在第 3 章，我们会回到消息传递上，并展示它在构建模拟程序上的强大。

⚠️ **GitHub.com Fallback** ⚠️