2.2 Hierarchical Data and the Closure Property - CloneableX/SICP-learning GitHub Wiki

上一节内容向我们展示了通过序对构建数据对象的能力。下图展示了可视化序对的方式，它展示的例子是 (cons 1 2)。这种形式称为 盒子与指针表示法（box-and-pointer notation），每个对象都是作为盒子的指针展示，而一个基础对象便包含了此对象的表现形式。例如，一个数字的盒子就包含着数字本身。序对的盒子实际上是一对盒子，左侧包含了序对 car 部分，右侧包含了序对的 cdr 部分。

我们已经知道序对不止能用于数字的组合，对于其他序对也同样适用。所以，序对提供了一种通用的构建方式，便于构建所有的有序数据结构。下图展示了两种通过序对构建数字 1，2，3，4 的方式。

能够将序对作为另一序对的元素构建的能力，是其能作为列表结构的重要表达工具的实质。通常我们称这种能力为 cons 的 闭包属性（closure property）。如果一个被构建的数据对象能够对自身再次使用相同的构建操作，便可以认为这种构建数据对象的操作符合闭包属性。闭包是所有构建方法的关键能力，因为它能够提供创建分层结构的能力，分层结构使数据对象可以由其他数据对象构成，而它又将构成另一个数据对象。

从第一章的开始已经在使用闭包特性，除了极简单的个别例子外，其他程序都基于这样一个事实，程序中的元素也可以是由其他元素组成。本节内容将介绍闭包特性在组合数据上的使用，首先会抽象序列和树型数据结构，其次还会通过图形化语言这种生动的方式讲解闭包。

序对能够构建的重要数据结构中有一种叫做 序列（sequence），它是一组有序数据对象。序列可以通过许多方式被序对构建。上图展示了一种比较简单明了的方式，1、2、3、4 按照序对链的方式展示。每个序对的 car 指向当前项的数字，而 cdr 指向链上的下一个序对。链上的末尾序对的 cdr 值指向一个非序对的特殊值，以此标志序对链的结束，在图示中通过对角线表示，在程序中通过 nil 值表示。整个序列通过 cons 的内嵌实现，如下：

(cons 1
      (cons 2
            (cons 3
                  cons 4 nil)))

像上述这种通过内嵌 cons 的方式构建的序列称为 列表（list），并且 Scheme 提供了基础程式 list 帮助构建列表。所以，上述的序列也可以通过 (list 1 2 3 4) 构建。也就是说，下列两个表达式完全相等：

(list <a1> <a2> ... <an>)

(cons <a1>
      (cons <a2>
            (cons ...
                  (cons <an>
                        nil)...)))

Lisp 系统按照常规打印列表时会将列表中的每个元素都打印，并且将其包裹在小括号中。所以前面的列表对象打印结果为 (1 2 3 4)。

按照上述列表的构建方式，我们能够推导 car 是获取列表的第一个元素，cdr 将获取除第一个元素外的子列表。通过 car 和 cdr 不断内嵌调用，便可以获得列表更后面的元素和子列表。cons 也可以把原有列表构建为新列表，不过需要提供列表的第一个元素值。

(define one-through-four (list 1 2 3 4))
one-through-four
(1 2 3 4)

(car one-through-four)
1
(cdr one-through-four)
(2 3 4)
(car (cdr one-through-four))
2
(cons 10 one-through-four)
(10 1 2 3 4)
(cons 5 one-through-four)
(5 1 2 3 4)

nil 值用于结束序对链，也可以认为表示此序列没有元素了，也就是空列表。单词 nil 来自拉丁语 nihil，表示「无」。

目前通过序对实现了列表，不过当前程序只能通过内嵌调用 cdr 方式才能维护列表，但是我们需要一种更加方便的方式对列表进行维护。例如，向程式 list-ref 传递参数 n 时表示获取列表中第 n 个元素，不过列表的元素通常是以 0 开始计数。list-ref 的运算方法如下：

• 当 n=0 时，list-ref 返回列表的 car 程式结果
• 否则，list-ref 应当返回通过 cdr 获取的子列表中的第 n-1 个元素。

程式实现如下：

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))

(define squares (list 1 4 9 16 25))
(list-ref squares 3)
16

为了避免无尽地通过 cdr 获取子列表，Scheme 提供了 null? 判断，以此检测列表是否已经结束。通过程式 length 可以获取列表的元素个数，我们用下列的程式实现说明：

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7))
(length odds)
4

上述的 length 程式为递归过程，也可以将其修改为迭代过程，如下：

(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) (+ count 1))))
  (length-iter items 0))

还有一种编程技术能够将列表拼接，也就是 append 程式，它可以将两个列表的元素拼接生成新列表。

(append squares odds)
(1 4 9 16 25 1 3 5 7)
(append odds squares)
(1 3 5 7 1 4 9 25)

append 也可以通过递归过程实现，拼接 list1 和 list2 的过程如下：

• 如果 list1 是空列表，则返回 list2
• 否则，list1 通过 cdr 获取的子列表与 list2 拼接，并且通过 cons 将 list1 当前的第一项元素合并至结果中

具体实现如下：

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

将列表的每一个元素进行转换并生成新列表，这种操作十分有用。例如，下列程式需要将列表的每个元素都扩大相同倍数：

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))

(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)

我们可以通过一个高阶程式对此通用概念进行抽象，产生的高阶程式命名为 map，map 接收两个参数，一个为程式，另一个为列表，并对列表的每个元素都应用程式，然后返回新元素构成的列表。具体实现如下：

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)
(map (lambda (x) (* x x)) (list 1 2 3 4))
(1 4 9 16)

通过 map 重写的 scale-list 如下：

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

map 是一种极为重要的结构，不止因为它提取了一种通用模式，还因为它为操作列表提供了一个更高阶的抽象。在原先实现的 scale-list 中需要关注遍历列表元素的过程，后面改写的 scale-list 由 map 承担了遍历列表元素的工作，程式本身只需要关注元素转换的过程即可。两个程式的区别并不在于内部调用了不同的程式实现，而在于我们思考的过程发生了转变。实际上，map 建立了一个抽象屏障，将程式转换列表元素的过程与遍历列表、组合列表的实现隔离。这个抽象提供了对序列底层实现进行修改，而不改变上层程式功能的灵活性。

列表中序列作为元素的表现形式与序列中的其他元素并无不同。例如，我们可以将 ((1 2) 3 4) 结构视为 (cons (list 1 2) (list 3 4))，就像一个拥有三个元素的列表，不同的是列表的第一个元素也是个列表。下图展示了这种结构如何通过序对表达。

我们不妨换个角度思考，如果把上述序列看作树形结构，序列的元素就是树形的分支，如果元素是序列则为子树，下图将上述序列转换了树形结构。

递归是处理树形结构的天然工具，当操作树形的分支时将转换为对分支的分支进行操作，直到不再出现分支为止。我们可以对比 length 程式和 count-leaves 程式：

(define x (cons (list 1 2) (list 3 4)))
(length x)
3

(count-leaves x)
4

(list x x)
(((1 2) 3 4) ((1 2) 3 4))
(length (list x x))
2
(count-leaves (list x x))
8

我们可以参考 length 的实现通过递归过程实现 count-leaves 程式，具体规则如下：

• 空列表的 count-leaves 结果为 0
• count-leaves 统计树形 x 的叶子数量可以等价为将 x 的 car 叶子数量与 x 的 cdr 叶子数量相加
• 叶子的 count-leaves 结果为 1

为了防止对树形的无尽递归，Scheme 提供了基础程式 pair?，它可以检测提供的参数是否为序对。下面是完整的程式实现：

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

map 不仅对于序列是一种重要的抽象，对于树形数据也一种重要的抽象。例如，scale-tree 程式与 scale-list 功能类似，它能够将树的叶子节点数据都扩大相同倍数，并返回一个相同结构的树形数据。scale-tree 的具体实现如下：

(define (scale-tree tree factor)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (* tree factor))
        (else (cons (scale-tree (car tree) factor)
                    (scale-tree (cdr tree) factor)))))

(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10)
(10 (20 (30 40) 50) (60 70))

scale-tree 的另一个实现方法是将子树看作序列通过 map 处理，将子树序列元素转换后再组装回子树。具体实现如下：

(define (scale-subtree tree factor)
  (map (lambda (subtree)
         (if (pair? subtree)
             (scale-subtree subtree factor)
             (* subtree factor)))
       tree))

关于树形的许多操作都可以通过这种将序列操作与递归结合的方式实现。

关于复合数据，我们已经讨论过它是如何避免程序设计阶段就陷入数据结构的细节中，以及如何保证修改具体数据形式的灵活性的。本节内容将介绍另一种设计思想，叫做 接口约定。

在之前的章节，我们已经了解过高阶程式作为程式抽象提取通用模式的能力。不过目前编写复合数据的操作程式时依然要根据数据结构的风格定制。例如，如果编写一个与 count-leaves 类似的程式，不过这个程式计算的是叶子节点值为奇数的平方和，具体程式如下：

(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 1)))
              (next (+ k 1))))))
  (next 0))

尽管上述两个程式的结构并无相似之处，但它们隐含了一个相似的概念。第一个程式过程为：

• 枚举树的叶子节点
• 筛选叶子节点，保留数值为奇数的叶子节点
• 对符合条件叶子节点值进行平方运算
• 通过加法累计结果，初始值为 0

第二个程式过程为：

• 枚举 0 至 n 的整数
• 计算每个整数对应的斐波那契数值
• 将斐波那契数值过滤，获取偶数数值
• 并通过 cons 累计结果，初始值为空列表

这在信号工程领域就是信号流经层叠阶段的计算过程，上述两个程序的过程如下图。在 sum-odd-squares 中，初始输入为一个枚举器，它是由参数中树形数据的叶子构成的一个信号。这个信号将穿过过滤器，非奇数的元素将被剔除，然后信号将通过转换器转换，也就是对符合条件的元素进行平方运算。最后转换器生成的结果再由累计器通过加法累计。even-fibs 的过程与之类似。

不幸的是上述两个程式的实现并未展示这种信号流结构。例如，如果继续研究 sum-odd-squares 程式，会发现它的枚举实现一部分靠 null? 和 pair? 检测，另一部分靠树形递归的结构。关于累计的部分也一样，其中一部实现通过判断条件实现，一部分依靠递归完成。也就是说，这两个程式没有与信号流计算过程对应的部分，它们使用不同的方式分解计算过程，不仅通过不同程序实现遍历，而且还将转换、过滤和累计过程混为一谈。如果我们将程序重新组织，并使其与信号过程对应，这将有利于程序对思想的清晰表达。

整理程序的关键是更加清晰地反映信号在信号流中每一步衔接的过程。如果将列表作为信号，接着便是在每一步通过列表操作实现对应步骤。例如，可以通过 map 实现信号转换的步骤，如下：

(map square (list 1 2 3 4 5))
(1 4 9 16 25)

根据提供的谓词过滤序列的实现如下：

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

(filter odd? (list 1 2 3 4 5))
(1 3 5)

列表累计也能按如下方式实现：

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))
15
(accumulate * 1 (list 1 2 3 4 5))
120
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)

这些程式都是为完成序列元素的转换与信号流过程的对应。对于 even-fibs 还需要一个程式生成给定范围内的序列，实现如下：

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

(enumerate-interval 2 7)
(2 3 4 5 6 7)

枚举树的叶子节点，可以按如下实现：

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
(1 2 3 4 5)

现在已经具备了按照信号流过程修改 sum-odd-squares 和 even-fibs 的条件。sum-odd-squares 需要枚举树的叶子节点序列，然后进行过滤，保证序列中只有奇数值，接着对每个元素进行平方运算，最后将其累加，具体实现如下：

(define (sum-odd-squares tree)
  (accumulate
    + 0 (map square (filter odd? (enumerate-tree tree)))))

even-fibs 将枚举 0 到 n 之前的整数，并将这些整数生成对应的斐波那契数列，然后序列中只保留偶数，最后将结果生成列表返回，具体实现如下：

(define (even-fibs n)
  (accumulate
    cons
    nil
    (filter even? (map fib (enumerate-interval 0 n)))))

这样改写程式的价值在于有效提高了程序设计的模块化，程序的实现只需要将几个相互独立的程式组合即可。如果提供一个符合接口约定的标准组件包，并且组件之间可以通过灵活的方式协作，这将极大鼓励程序员的模块化设计能力。

模块化这种策略能够在工程设计中有效控制复杂度。在实际信号工程应用中，工程师们通常会利用标准库中的过滤器和转换器对元素叠加的方式构建系统。与之类似，我们也可以将序列的标准操作进行不同组合使用。例如，可以将 sum-odd-squares 和 even-fibs 程式中使用的序列标准程式用于构建 n 个斐波那契数的平方列表程式的构建：

(define (list-fib-sequares n)
  (accumulate
    cons
    nil
    (map square (map fib (enumerate-interval 0 n)))))

(list-fib-sequares 10)
(0 1 1 4 9 25 64 169 441 1156 3025)

同样也可以实现计算序列中奇数值的平方之积：

(define (product-of-squares-of-odd-elements sequence)
  (accumulate * 1 (map square (filter odd? sequence))))

(product-of-squares-of-odd-elements (list 1 2 3 4 5))
225

当然还可以定制更多关于序列操作的数据流程式。假设现在有一组员工记录，希望能从中查到薪水最高的程序员。实现这个功能需要一个 salary 选择器，它将返回一条记录的薪水数据，还需要一个 programmer? 程式判断员工是否为程序员，接着就可以按如下方式实现：

(define (salary-of-highest-paid-programmer records)
  (accumulate max 0 (map salary (filter programmer? records))))

这些例子提醒我们，只要能够将数据转换为序列形式，它们将拥有大量的操作组合。

列表序列按照接口约定提供服务，这种方式保证了程式模块化的能力。另外，在序列的结构统一后，数据结构的信赖关系被限制在少数几个序列操作程序中。通过这个改变，可以在不影响系统整体设计的基础上修改程式的实现。当我们在 3.5 节将序列过程泛化为无限序列时会用到此功能。

在序列的范例中有许多运算都有嵌套循环的参与。一起来解决这样一个问题，给定一个正整数 n，查找满足 的有序序对 i 和 j，并且 i+j 是素数。例如 n 是 6，符合条件的序对如下：

常规的计算方式为先生成所有小于或等于 n 的正整数序对序列，然后排除序对数值之和为非素数的序对，并在最后将每个元素转换为 (i,j,i+j) 的三元数组。

要生成序对序列，需要对 的每个整数 i 都枚举符合 j < i 的整数，每个整数 i 和 j 都组成一组序对 (i,j)。生成序列区间可以通过 (enumerate-interval 1 n) 操作，对于每个 i 都需要生成序列 (enumerate-interval 1 (- i 1))，也就是 j 的序列，此时的 i 与 j 的序列组合生成序对 (list i j)，最终将得到所有的 i 与 j 组合。具体实现如下：

(accumulate 
 append nil (map (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))

类似将转换、累计和 append 的组合方式是排序程序的常用方法，现在将其单独提取为一个程式：

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

现在将序对序列过滤，剔除两数之和为非素数的组合。因为过滤时需要提取序对中的整数相加再判断，所以判断程式的实现如下：

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

最后再使用下列程式将过滤的序列转换为新序列即可，具体实现如下：

(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

现在将这些程式组合起来：

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum? (flatmap
                           (lambda (i)
                             (map (lambda (j) (list i j))
                                  (enumerate-interval 1 (- i 1))))
                           (enumerate-interval 1 n)))))

嵌套映射对于枚举区间之外的序列也很有用。假设我们想生成数组 S 中的所有排列组合，也就是 S 中元素排序后的所有组合方式。例如，{1,2,3} 的排列组合为 {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}。目前的实现方式如下，首先遍历 S 中的每个元素 x，并且递归地生成 S-x 排列组合与 x 形成的组合。具体实现如下：

(define (permutations s)
  (if (null? s)
      (list null)
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))

上述解决方案通过将 S 元素的排列组合问题缩小至更小数组的排列组合实现。在递归结束的操作中，返回的结果为空列表，它表示一个没有元素的数组。remove 程式会指定元素从序列中剔除，并返回新的序列，可以表达为如下程式：

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

本节内容将描述一个关于画图的语言，它将向我们展示数据抽象、闭包的能力。这门语言的设计遵循易于实验如下图的模式的目标，下图的模式使其中的元素不断重复扩大并形成偏移。此门语言中，数据对象以程式结合的形式出现，而不是列表结构。就像 cons 一样，这样比较符合闭包特性，也方便构建任意形态的复杂列表结构，同时此门语言中的运算也符合闭包特性，便于构建复杂的模式。

在本书开始时，我们就强调过一门编程语言的重点是提供的组合和抽象方法。构建图形语言时也是如此。

这门图形语言精练的地方在于只有一种元素—— 画笔（painter）。画笔画出的图像将填满指定的平行四边形，并根据这个平行四边形缩放变形。比如，当调用 wave 时将完成如下图的粗略画作。实际图像的形态靠平行四边形确定，如同下图的四张图像，虽然都是由 wave 画出，但根据边框形成了不同形态。

除此之外，画笔还可以画出更加细致的图形，当调用 rogers 时将画出 MIT 创建者的画像，如下图所示，它与上图的四张图像类似。

如果要组合图片，可以使用其他的操作通过原有画笔构建新画笔。例如，beside 将两个画笔构建为一个新画笔，它能够将前一个画笔产生的图形画在左边，另一个画笔产生的图形画在右边。类似地，below 也可以将两个画笔构建为一个画笔，将前一个画笔的图像画在后一个画笔图像的下面。还有些方法可以将一个画笔转换为另一种新画笔。比如，flip-vert 可以转换画笔，新画笔画出的图像与原来相比是上下颠倒的；与之类似，flip-horiz 创建的画笔画出的图像将左右反转。

下图展示了以 wave 为基础构建的新画笔画出的图像：

(define wave2 (beside wave (flip-vert wave)))
(define wave4 (below wave2 wave2))

上述例子阐述了图形语言中的组合方法是如何封装的。beside 和 below 可以组合画笔，可以提供画出复杂图像的能力。如果加上使用 cons 构建列表结构，只需要少量的组合操作便可以实现复杂的数据结构，其中数据的闭包特性是关键。

一旦能够组合画笔，便希望能够将组合画笔中典型的模式抽象出来。因为实现图形语言使用的是 Scheme，所以它的抽象方式与 Scheme 相同。因为组合画笔的程序就是 Scheme 中的程式，所以程式拥有的所有能力组合画笔的方法都拥有。例如，可以将前面例子中的 wave4 抽象，如下：

(define (flipped-pairs painter)
  (let ((painter2 (beside painter (flip-vert painter))))
    (below painter2 painter2)))

(define wave4 (flipped-pairs wave))

除此之外还可以利用递归的方式定义画笔组合程式。比如，可以按下图的形式按像框右侧平分的方式作画，具体实现如下：

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))

然后还需要实现即向上又向右平分作画的模式：

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-spliter painter (- n 1)))
            (right (right-split painter (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right right))
              (corner (corner-split painter (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right corner))))))

通过对 corner-split 图像的四次复制获得模式 square-limit，就是本节开头图片中的画作，具体实现如下：

(define (square-limit painter n)
  (let ((quarter (corner-split painter n)))
    (let ((half (beside (flip-horiz quarter) quarter)))
      (below (flip-vert half) half))))

除了可以抽象组合画笔的模式，我们还可以在更高维度抽象操作画笔的模式。可以将画笔的操作方法视作元素，这些元素可以被维护、被组合。

例如，flipped-pairs 和 square-limit 都将对应画笔产生的图像放置在画框的四角上，有所区别只是每个部分图像的朝向不同。下列程式展示了其中一种抽象方式，它通过四个参数将指定画笔的图像按这四个参数的操作放置在画框的四角。其中 tl、tr、bl 和 br 分别表示将图像转换后放置在左上、右上、左下和右下的程式。

(define (square-of-four tl tr bl br)
  (lambda (painter)
    (let ((top (beside (tl painter) (tr painter)))
          (bottom (beside (bl painter) (br painter))))
      (below bottom top))))

flipped-pairs 实现可以按如下修改：

(define (flipped-pairs painter)
  (let ((combine4 (square-of-four identity flip-vert)
                                  identity flip-vert))
    (combine4 painter)))

square-limit 也可以进行类似修改：

(define (square-limit painter n)
  (let ((combine4 (square-of-four flip-horiz identity
                                  rotate180 flip-vert)))
    (combine4 (corner-split painter n))))

在实现画笔和画笔相关的操作前，我们需要先考虑清楚关于画框的实现。一个画框通过三个向量描述，一个原点向量和两条边的向量。原点向量指画框原点相对于平面原点的向量，边的向量描述画框的角与画框原点的偏移。如果画框的边相互垂直，则画框是矩形，否则画框就是普通的平行四边形。

下图展示了画框与它的相关向量。由于有数据抽象的帮助，我们暂时还不需要考虑如何表示画框，只需要了解画框的构造器为 make-frame，选择器为 origin-frame、edge1-frame、edge2-frame。

并且会在一个单元正方形内使用坐标（）确定图像的位置。对于画框，还需要通过画框坐标转换移动和缩放图像以填充画框。转换的方法为计算当前向量 v = (x, y) 与画框的向量之和，公式如下

Origin(Frame) + x・Edge1(Frame) + y・Edge2(Frame)

例如，(0,0) 是画框的原点，(1,1) 是原点的对角线点坐标，(0.5, 0.5) 是画框的中心，于是可以通过下列程式计算画框的坐标转换。

(define (frame-coord-map frame)
  (lambda (v)
    (add-vect
     (origin-frame frame)
     (add-vect (scale-vect (xcor-vect v) (edge1-frame frame))
               (scale-vect (ycor-vect v) (edge2-frame frame))))))

frame-coord-map 将返回一个程式，这个程式会按照提供的向量参数计算产生一个新向量。如果参数向量位于当前的单元正方形内，则产生的向量将处于画框内。例如：

((frame-coord-map a-frame) (make-vect 0 0))

产生的结果为 (origin-frame a-frame)

画笔通过程式展开，需要向此程式提供画框作为参数，然后根据画框缩放和移动画笔绘出的图像，并填充整个画框。

基础画笔主要依靠绘图系统和绘画的图像类型实现。例如，假设我们可以通过程式 draw-line 在屏幕的两点间画出一条线段，利用此程式便可以创建绘画线段的画笔，并使用此画笔绘画多条线段。

(define (segments->painter segment-list)
  (lambda (frame)
    (for-each
     (lambda (segment)
       (draw-line
        ((frame-coord-map frame)
         (start-segment segment))
        ((frame-coord-map frame)
         (end-segment segment))))
     segment-list)))

程式参数中的一组线段是用于表示坐标单元正方形的坐标。每条线段的端点都会进行画框端点转换，并在转换后的坐标点间连上线段。

其中将画笔通过程式的方式构建有利于整个图形语言抽象屏障的建立。在整个系统中可以利用各种绘画能力创建、组合基础画笔。它们的实现细节并不重要，而且任何程式通过画框参数的参与都能作为画笔使用。

关于画笔的创建操作都需要原始画笔，最终将图像按照画框参数与画框适配。所以，flip-vert 并不需要了解画笔如何翻转作画，只需要知晓如果将画框上下颠倒即可。所以 flip-vert 的画笔一直是原始画笔，不过只是将画框翻转画出。

画笔的操作都是基于 transform-painter，它通过参数中的画笔和转换画框的相关信息完成新画笔的创建。其实是在对画框应用时依然使用原始画笔作画，被转换的是画框。transform-painter 程式的画框信息相关参数是标识新画框角的坐标点（使用向量表示）。当转换为画框时，第一个点表示画框的原点，另外两个表示两条边向量的终点。

(define (transform-painter painter origin corner1 conrner2)
  (lambda (frame)
    (let ((m (frame-coord-map frame)))
      (let ((new-origin (m origin)))
        (painter (make-frame
                  new-origin
                  (sub-vect (m corner1) new-origin)
                  (sub-vect (m corner2) new-origin)))))))

接下来是上下翻转图像的实现：

(define (flip-vert painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0)))

利用 transform-painter 便可以轻易定义新的转换程式。例如，想定义一个画笔能够将图像放置在画框的右上角时，可以如下实现：

(define (shrink-to-upper-right painter)
  (transform-painter
   painter (make-vect 0.5 0.5)
   (make-vect 1.0 0.5) (make-vect 0.5 1.0)))

逆时针旋转 90 度可如下实现：

(define (rotate90 painter)
  (transform-painter painter
                     (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0)))

或者沿中心压缩图片：

(define (squash-inwards painter)
  (transform-painter painter
                     (make-vect 0.0 0.0)
                     (make-vect 0.65 0.35)
                     (make-vect 0.35 0.65)))

画框的转换是定义更多画笔组合的关键。例如 beside 程式，它产生的新画笔会将参数中的一支画笔在画框的左半部分绘图，另一支画笔在画框的右半部分绘图。当对一个画框应用画笔时，会先将第一支画笔在转换后的画框左半部分绘图，再使用第二支画笔在转换后的画框右半部分绘图。

(define (beside painter1 painter2)
  (let ((split-point (make-vect 0.5 0.0)))
    (let ((paint-left
           (transform-painter
            painter1
            (make-vect 0.0 0.0)
            split-point
            (make-vect 0.0 1.0)))
           (paint-right
            (transform-painter
             painter2
             split-vect
             (make-vect 1.0 0.0)
             (make-vect 0.5 1.0))))
      (lambda (frame)
        (paint-left frame)
        (paint-right frame)))))

观察画笔是如何进行数据抽象的，当画笔作为程式存在时，beside 就十分容易实现。beside 程式并不需要了解画笔组件的实现细节，而是应该关注每支画笔应该在怎样的画框中作画。

图形语言的练习中包含了一些数据和程式抽象的重要概念，这些知识在前面的内容中已经介绍过。画笔是此门语言中最基础的数据抽象，它通过程式表达，这种方式为编程语言提供了使用不同绘图能力的统一方式。组合的方式也符合闭包特性，它使我们的复杂设计能够轻易实现。最后，所有程式的抽象方法都可以对画笔的组合方法抽象使用。

同时在这个练习中也顺便了解了关于语言和程序设计的重要概念。其中分层设计的观念指出，在构建复杂系统时需要按一系列的不同层级设计，每个层级只组合当前层级的基础层级方法，每个层级也只作为上一层级的基础层级使用。在语言的分层设计中，每个层级都会运用自己的基础元素，并进行组合和抽象。

分层设计在复杂工程系统中无处不在。例如，在电脑工程中，电阻和晶体管联合组成了与门、或门等部件，构成了数字电路设计中的基础。这些基础元素又构成了处理器、总栈和缓存等结构，以此构成计算机架构。计算机又构成了分布式系统，并通过网络连接等等。

作为分层设计的一个简化示例，图形语言使用的基础元素为画笔，并通过它绘制了点和线段，同时也对具体的绘画细节进行隐藏。图形语言中大量的描述都关注于对基础元素的组合，然后进行几何绘图。在语言的更高层级中，我们对这些操作进行了通用模式的抽象。

分层设计帮助程式变得健壮，它保证了基础协议实现的细微变化对于整个程序是一致的。假设我们此时需要修改 wave 的实现，只需要修改最低层级的 wave 细节后，整个程序在应用 wave 的地方表现的变化也是统一的。通俗地讲，分层设计使系统的每个层级都提供了表达系统的不同词汇，以及改变系统的不同能力。