2020-02-06a2d431cb675e80ef3ca693ebaaeb5f77

99+ sicp27 分钟读完 (大约 4032 个字) 0次访问

抽象系统的多重表示

主要是对SICP(Structure and Interpretation of Computer Programs)，第二章四节的读书笔记。

文中由复数的两种表达形式引出了，基于类型分派(Tagged Data)，消息传递(Message Passing), 数据导向(Data Directed)。

复数的表示

复数存在两种表达方式：直角坐标形式（实部和虚部），极坐标形式（模和幅角）。如何使两种表达形式共存于同一个系统中。

复数的两种表达形式分别适用不同的运算。

复数的加法倾向于用直角坐标系：

实部(Z₁ + Z₂) = 实部(Z₁) + 实部(Z₂)

虚部(Z₁ + Z₂) = 虚部(Z₁) + 虚部(Z₂)
复数的乘法自然的考虑是复数的极坐标：

模(Z₁ * Z₂) = 模(Z₁) * 模(Z₂)

幅角(Z₁ * Z₂) = 幅角(Z₁) + 模(Z₂)

从编写程序角度来说，我们需要所有的复数操作都可以使用，不论所用的具体表示形式是什么。

复数的运算

假定所有复数运算的实现都基于如下四个选择函数：real-part, imag-part, magnitude和angle; 两个构造的过程：make-from-real-imag返回一个采用实部和虚部描述的复数，make-from-mag-ang返回一个采用模和幅角描述的复数。

1 2	(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) (magnitude z2))
                     (- (angle z1) (angle z2))))

在这里，实部、虚部、模和幅角有以下关系：

\(x = r cos A\)
\(y = r sin A\)
\(r = \sqrt{x ^ 2 + y ^ 2}\)
\(A = arctan(y, x)\)

复数的直角坐标表示

采用直角坐标表示形式，选取复数与虚部是直截了当的。选取极坐标表示形式则可以利用上面的公式，提供新的选择函数和构造函数：

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

带标志数据

如果要在同一个系统里包含复数的两种不同表示形式，需要一种方式，将极坐标形式的数据和直角坐标形式的数据分开。

假想一下，现在需要找到对偶(3,4)的magnitude，我们无法知道答案是5（将数据解释直角坐标表示形式）还是3（将数据解释为极坐标表示）。

为了完成这种区分，我们在每个复数包含一个类型标志部分，用符号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)))

;; 添加判断函数
(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))
(define (polar? z)
  (eq? (type-tag z) 'polar))

添加类型tag的直角坐标表示

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

添加类型tag的极坐标表示

(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) (car 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过程保持不变，因为它们调用的选择函数现在都是通用型，对任何表示都能工作。

现在我们还需要选择合理的构造函数，合理的选择是手头有实部和虚部时采用直角坐标表示，有模和幅角就采用极坐标表示。

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

;; 调用合理的构造函数

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

在给定的一种表示实现中，复数是一种无类型的对偶（模，幅角）。当一个通用型选择函数对一个polar类型的复数进行操作的时，它会剥去标志并将相应内容传递给处理极坐标的代码。与此对应，当极坐标表示构造一个供一般性使用的复数时，也需要为其加上类型标志，使这个对象可以为高层过程所识别。在将数据对象从一个层次传到另一个层次的过程中，这种剥去和加上标志的规范方式可以成为一种重要的组织策略。

类型分派，数据导向，消息传递

在需要处理针对不同类型的一集公共通用型操作时，事实上，我们所在处理的是一个二维表格，其中一维包含着所有的可能操作，另一维就是所有的可能类型。表格中的项目是一些过程，它们针对作为参数的每个类型实现每一个操作。在前一节中开发的复数系统里，操作名字、数据类型和实际过程之间的对应关系散布在各个通用界面过程的各个条件子句。

操作	Polar	Rectangular
real-part	real-part-polar	real-part-rectangular
imag-part	imag-part-polar	imag-part-rectangular
magnitude	magnitude-polar	magnitude--rectangular
angle	angle-polar	angle-rectangular

基于类型的分派

检查一个数据项的类型，并据此去调用某个适当过程称为 基于类型的分派

类型分派有两个显著的弱点：

对于处理不同函数类型的通用型选择函数，必须知道所有类型的不同表示。
独立的类型标识形式需要避免命名冲突。

上述两个弱点之下的基础问题是，基于类型的分派实现的系统不具有可加性。每次新增一种表达形式时，实现通用选择函数的人，必须去修改他们的过程，做单独的类型函数的人也必须修改他们的代码，避免命名冲突。所有的修改直接对代码去做，极易产生错误。再假设，如果我们的系统有上百种不同的复数表示形式？将再难以维护。

数据导向的程序设计

数据导向的程序设计是一种使程序能直接利用上图表格工作的程序设计技术。

我们需要实现一个过程，由它用操作名和参数类型的组合到表格中查找，来找出应该调用的适当过程，并将这一过程应用与参数的内容。

添加新的表示包到系统中，就不需要修改任何现存的代码。

处理操作/类型表格需要两种方法：(op => 操作；type => 类型；item => 函数)

将函数放入表格中：(put <op> <type> <item>)
查找与操作和类型对应的项，获取函数： (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 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)

这笔，直角坐标表示形式的real-part过程安装在操作名字real-part和类型(rectangular)表之下，其余选择函数与之类似。这个过程还提供给外部系统的构造函数。

极坐标表示的实现

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

复数运算 虽然极坐标和直角坐标有些过程有相同的名字（如real-part），但对其他部分而言，这是内部的，不会有名字冲突问题。

复数系统的选择函数需要通过一个中间函数来访问有关类型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))))))

通用型选择函数定义

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

实际算数运算中，过程add-complex等保持不变，调用相同的选择函数。

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

消息传递

消息传递风格的程序设计来源于，将数据对象设想为一个实体，它以“消息”的方式接受所需操作的名字。

数据传递的程序设计中，最关键的想法就是显式处理操作-类型表格的方式，管理程序中的各种通用型操作。基于类型的分派的组织方式中，让每个操作管理自己的分派。从效果上来看，这种方式就是将操作-类型表格分解成一行一行，每个通用型过程表示为表格的一行。

消息传递的实现策略是：将表格按列进行分解，不是采用一批“智能操作”去基于数据类型分类，而是采用“智能数据对象”，基于操作名完成分派。我们将数据对象（如一个采用直角坐标表示的复数）表示为一个过程，以操作的名字作为输入，能够去执行指定的操作。

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

调用make-from-real-imag返回的是一个过程---内部的dispatch过程。相当于一个整体数据对象。

对应的apply-generic过程对参数应用一个通用型操作，将操作名传递给数据对象，并让那个对象完成剩下工作。

消息传递不是一种数学技巧，而是一种有价值的技术，可以用于组织带有通用型操作的系统。

思考

一个带有通用型操作的大型系统可能不断演化，在演化过程中常需要添加新的数据类型或者新的操作。对于上面讨论的三种策略：带有显示分派的通用型操作，数据导向的风格，以及消息传递的风格。请描述在加入一个新类型或者新操作时，系统所必须做的修改。哪种组织方式最适合那些经常需要加入新类型的系统？哪种组织方式最适合那些需要加入新操作的系统。

显示分派：这种策略在增加新操作时需要使用者避免命名冲突，而且每当增加新类型时，所有通用操作都需要做相应的改动，这种策略不具有可加性，因此无论是增加新操作还是增加新类型，这种策略都不适合。
数据导向：数据导向可以很方便地通过包机制增加新类型和新的通用操作，因此无论是增加新类型还是增加新操作，这种策略都很适合。
消息传递：消息传递将数据对象和数据对象所需的操作整合在一起，因此它可以很方便地增加新类型，但是这种策略不适合增加新操作，因为每次为某个数据对象增加新操作之后，这个数据对象已有的实例全部都要重新实例化才能使用新操作。

本文最后修改于: 2020-03-27.

本文标题：抽象系统的多重表示
本文作者：hddhyq
本文链接：https://hddhyq.github.io/2020/02/06/抽象系统的多重表示/
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！