项目 2：海龟绘图

引言

在第 4 课中，我们探讨了 cons 如何让我们构建任意复杂的列表结构。

在这个项目中，我们将创建一个简单的图形语言（picture language），能用它构建任意复杂的图画，比如下面这幅。注意图像是如何由平移和缩放后的重复元素构成的。

在探索这个图形语言的过程中，我们将看到数据抽象和高阶过程如何结合起来，把简单元素构建成复杂系统。

首先，把文件 ~cs61as/lib/picture.rkt 复制到你的目录，或者从这里下载。你还需要安装能让我们画图的 Racket 包。如果你在实验机上，在终端输入：

install-htdp

如果你想在自己的电脑上安装画图包，看看这个 Piazza 帖子的第一个跟进讨论。

安装完成后，你应该能在 Racket 中输入 (require graphics/turtles) 而不报错。

图形语言

我们在第 1 课开始学编程时，强调过：描述一种语言，要聚焦于它的基本元素（primitives）、组合手段和抽象手段。这里我们沿用这个框架。

这个图形语言的部分优雅之处在于只有一种元素，叫绘制器（painter）。绘制器画出的图像经过平移和缩放，放进一个指定的平行四边形画框（frame）。例如，有个叫 wave-painter 的基本绘制器，它画一幅粗略的线条画，如下所示。图画的实际形状取决于画框——下面四幅图都由同一个 wave-painter 生成，只是用了四个不同的画框。

组合绘制器

要组合图像，我们用各种操作，从给定的绘制器构造新绘制器。例如，beside 操作接受两个绘制器，产生一个新的复合绘制器：在画框左半边画第一个绘制器的图像，右半边画第二个绘制器的图像。类似地，below 接受两个绘制器，产生一个复合绘制器：把第一个绘制器的图像画在第二个绘制器图像的下方。

有些操作把单个绘制器变换成新绘制器。例如，flip-vert 接受一个绘制器，产生上下颠倒作画的绘制器；flip-horiz 产生把原绘制器图像左右翻转的绘制器。

下面是我们如何分两步从 wave-painter 构建名为 wave4 的绘制器：

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

结果图形如下：

抽象操作

能组合绘制器后，我们就想能抽象出组合绘制器的典型模式。我们将把绘制器操作实现为 Racket 过程。这意味着图形语言不需要特殊的抽象机制：因为组合手段就是普通 Racket 过程，我们自动获得了对绘制器操作做任何过程能做的事的能力。例如，我们可以把 wave4 中的模式抽象为

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

然后把这个模式的一个实例定义为 wave4：

(define wave4 (flipped-pairs wave))

递归操作

我们也能定义递归操作。下面这个叫 right-split，它让绘制器向右拆分和分叉：

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

下面是 (right-split painter n) 的通用模板：

这是 (right-split wave-painter 4) 的结果：

我们可以既向上又向右分叉，产生平衡的图案：

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split 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 painter n) 的通用模板：

这是 (corner-split wave-painter 4) 的结果：

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

本页最上方的那幅图（在下面复现）就是 (square-limit wave-painter 5) 的可视输出：

开始练习 1 之前

首先，如果你因为想直接跳到第一道练习而略读了上面所有内容，现在花一分钟仔细读一遍。这很重要！

另外，注意在做完练习 6 之前，你将无法测试任何代码的可视输出。我们描述的图形语言还不完整——你得先填补空白，我们才能开始用它！

练习 1：up-split

定义 corner-split 用到的过程 up-split。它类似 right-split，只是交换 below 和 beside 的角色。

方便起见，这里再次给出 right-split：

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

高阶操作

除了抽象组合绘制器的模式，我们还能在更高层次上工作，抽象组合绘制器操作的模式。也就是说，我们可以把绘制器操作当作可操作的元素，为这些元素写组合手段——接受绘制器操作为实参、创建新绘制器操作的过程。

例如，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 可以用 square-of-four 定义如下：

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

练习 2：split

right-split 和 up-split 可以表示成一个通用拆分操作的实例。定义过程 split，使得求值

(define right-split (split beside below))
(define up-split (split below beside))

产生过程 right-split 和 up-split，其行为与已定义的相同。

画框

在展示如何实现绘制器及其组合手段之前，我们必须先考虑画框。画框可以用三个向量描述——一个原点向量和两个边向量。原点向量指定画框原点相对平面中某个绝对原点的偏移，边向量指定画框各角相对其原点的偏移。如果两边垂直，画框就是矩形；否则画框是更一般的平行四边形。

下图展示了一个画框及其关联向量。遵循数据抽象，我们还不需要具体说明画框在 Racket 中如何表示，只需说有构造函数 make-frame（接受三个向量，产生画框）和三个对应的选择函数：origin-frame、edge1-frame 和 edge2-frame。

我们将用单位正方形中的坐标来指定向量；也就是说，我们用 $0 \leq x, y \leq 1$ 的空间区域。

画框坐标（选读）

这一选读小节描述画框坐标如何计算。

每个画框都关联一个坐标映射（coordinate map），用来把图像平移和缩放以适应画框。坐标映射用下面的公式，把单位正方形中的向量变换为画框中的向量：

其中 $x$ 和 $y$ 是输入向量的分量。

例如，向量 $(0, 0)$ 映射到画框的原点，$(1, 1)$ 映射到与原点的对角顶点，$(0.5, 0.5)$ 映射到画框的中心。

在 Racket 中，我们可以用下面的过程创建画框的坐标映射：

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

相同的向量，因为向量 $(0, 0)$ 映射到画框的原点。

练习 3：表示向量

从原点指向某点的二维向量 $v$ 可以表示为一个序对，由 x 坐标和 y 坐标组成。给出构造函数 make-vect 和对应选择函数 xcor-vect、ycor-vect，实现向量的数据抽象。

然后，用你的选择函数和构造函数实现过程 add-vect、sub-vect 和 scale-vect，分别执行向量加法、向量减法和向量数乘：

练习 4：表示画框

现在按上面的描述实现画框。

下面是两个可能的画框构造函数：

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (make-frame-2 origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

对每个构造函数，给出合适的选择函数。

表示绘制器

绘制器表示为一个过程：给定画框作为实参，画出经过平移和缩放以适应画框的特定图像。也就是说，如果 p 是绘制器、f 是画框，我们通过调用 (p f) 在 f 中产生 p 的图像。

基本绘制器怎么实现，取决于图形系统的具体特性和所画图像的类型。例如，假设我们有个过程 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)))

线段用相对单位正方形的坐标给出。对列表中的每条线段，绘制器用画框坐标映射（见上文）变换线段端点，并在变换后的点之间画线。

把绘制器表示为过程，在图形语言中竖起了一道强大的抽象边界。我们可以基于各种图形能力创建并混用各种各样的基本绘制器。它们实现的细节无关紧要。任何过程都能充当绘制器，只要它接受画框作实参，并画出缩放以适应画框的东西。

练习 5：表示线段

平面上的有向线段可以表示为一对向量——从原点指向线段起点的向量，和从原点指向线段终点的向量。用你上面的向量表示，定义线段的表示，含构造函数 make-segment 和选择函数 start-segment、end-segment。

练习 6：基本绘制器

用 segments->painter 定义下列基本绘制器：

• x-painter，连接画框对角顶点画一个”X”。
• outline-painter，画出指定画框的轮廓。
• diamond-painter，连接画框各边中点画一个菱形。
• wave-painter，画出这里常见的”波浪”图形。你的画不必完美复刻；只要看起来明显像原波浪图就行。

为了确保你走在正道上，定义 x-painter 后应立即测试代码。说明见下文”测试”一节。

(define diag-painter
  (segments->painter
   (list (make-segment (make-vect 1 0) (make-vect 0 1)))))

测试

现在可以开始测试代码了。注意下列命令在 SSH 上不起作用。

首先在终端输入下面的命令加载 picture.rkt：

racket -it picture.rkt

现在用 cs（“clear screen”，清屏）过程打开绘图窗口：

(cs)

你应该看到一个窗口出现，里面有个小三角形。

现在你可以用 full-frame 作为画框实参，让绘制器在绘图窗口中作画。例如，试试：

(x-painter full-frame)

你应该在绘图窗口中看到一个 X。如果什么都没出现，或者报错，别担心。用你学过的调试技能定位错误并解决它。需要帮助的话，在 Piazza 上发帖或联系 TA。

注意上面提到的绘制器变换（如 beside 和 square-of-four）此时还不会工作。你得完成练习 8 才能测试它们。现在，如果你的四个基本绘制器都能工作，就进入下一节。

变换和组合绘制器

绘制器上的操作（如 flip-vert 或 beside）通过创建绘制器来工作：新绘制器相对于从实参画框导出的画框调用原绘制器。因此，例如 flip-vert 不需要知道绘制器怎么工作就能翻转它——它只需要知道如何把画框倒过来：翻转后的绘制器就用原绘制器，但在倒置的画框中。

绘制器操作基于过程 transform-painter：它接受一个绘制器和如何变换画框的信息，产生新绘制器。变换后的绘制器被调用时，变换画框，并在变换后的画框上调用原绘制器。transform-painter 的实参是指定新画框各角的点（用向量表示）：映射进画框时，第一个点指定新画框的原点，另外两个指定其边向量的端点。因此，单位正方形内的实参指定的画框包含在原画框内。

(define (transform-painter painter origin corner1 corner2)
  (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)   ; edge1 的新端点
                     (make-vect 0.0 0.0))) ; edge2 的新端点

用 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-point
                              (make-vect 1.0 0.0)
                              (make-vect 0.5 1.0))))
      (lambda (frame)
        (paint-left frame)
        (paint-right frame)))))

注意绘制器数据抽象，特别是把绘制器表示为过程，如何让 beside 易于实现。beside 过程除了知道每个绘制器会在指定画框中画东西外，不需要了解组件绘制器的任何细节。

练习 7：flip-horiz 和旋转

定义变换 flip-horiz，它水平翻转绘制器。

然后定义 rotate180 和 rotate270，分别把绘制器逆时针旋转 180 度和 270 度。

练习 8：below

定义绘制器的 below 操作。below 接受两个绘制器作为实参。产生的绘制器得到画框时，用第一个绘制器画在画框下半部分，用第二个绘制器画在上半部分。用两种不同方式定义 below——先写一个与上面 beside 过程类似的过程，再用 beside 和合适的旋转操作（见上一练习）定义。

稳健设计的语言层级

我们的图形语言现在完整了。退一步来评估一下。

这个图形语言运用了我们介绍过的一些关于过程抽象和数据抽象的关键思想。基本数据抽象——绘制器——用过程表示实现，这让语言能以统一的方式处理不同的基本绘图能力。组合手段也是过程，这让我们能轻松构建复杂设计。最后，所有抽象过程的工具都能用来抽象绘制器的组合手段。

我们还瞥见了另一个关于语言和程序设计的关键思想。这就是分层设计（stratified design）方法：复杂系统应构建成一系列层级，每一层用一种语言描述。每一层由在该层被视为基本元素的部分组合而成，而每层构建的部分在下一层用作基本元素。分层设计每一层使用的语言，都有适合该层细节程度的基本元素、组合手段和抽象手段。

分层设计遍及复杂系统的工程。例如，在计算机工程中，电阻和晶体管组合起来（用模拟电路的语言描述）产生与门、或门之类的部件，它们构成数字电路设计语言的基本元素。这些部件组合起来构建处理器、总线结构和存储器系统，它们再组合成计算机，用适合计算机架构的语言描述。计算机组合成分布式系统，用适合描述网络互连的语言，如此等等。

分层设计有助于让程序稳健——也就是说，它让规格说明的小改动很可能只需要程序的小改动。例如，假设我们想修改基于 wave-painter 的图像。我们可以在最低层改 wave-painter 元素的细节外观；可以在中层改 corner-split 复制波浪的方式；或者可以在最高层改 square-limit 排列四份角落拷贝的方式。总的来说，分层设计的每一层都提供了表达系统特性的不同词汇，以及改变系统的不同能力。

练习 9：Square Limit

在上面描述的每一层上工作，修改波浪绘制器的 square limit。具体来说：

• 给练习 6 的基本 wave-painter 添加一些线段（例如加个微笑）。
• 改变 corner-split 构建的图案（例如，只用一份 up-split 和 right-split 图像，而不是两份）。
• 修改用 square-of-four 的 square-limit 版本，以不同图案组装各个角落。（例如，你可以让波浪图形从正方形每个角朝外。）

最后步骤

按上面”测试”一节的说明，测试其余的绘制器。务必也测试你所有的绘制器变换过程。

要提交项目，在终端进入你的项目目录，然后输入

submit proj2

仅供娱乐：导出图画

不想弄丢你的杰作？渴望在 Facebook 或 Instagram 上分享你的创作？现在可以用下面的命令把图画存成 PNG 文件：

(export "filename.png")