数据导向编程

什么是数据导向编程？

cp ~cs61as/lib/data_directed_programming.rkt .

数据导向编程是一种进一步提升代码灵活性的手段：它把数据类型的处理模块化得更加彻底。我们不再在函数内部用 cond 子句来控制数据类型和运算符（过程）的信息，而是把这些信息记录到一个数据结构里，可以随时往里添加、从中检索。为此你会拿到两个工具：put 用来建立这个数据结构，get 用来查看它。直观地说，我们就是往一个类似表的数据结构里添加条目。

> (get 'foo 'baz)
#f
> (put 'foo 'baz 'hello)
> (get 'foo 'baz)
hello

在上面这段代码里，我们先试着取出键为 'foo 和 'baz 的条目。因为该条目不存在（我们还没有 put 它！），所以得到 #f。下一行把一个键为 'foo 和 'baz 的条目放进表里。最后一行取出了我们刚放进去的信息。

一旦你把某样东西放进表里，它就会一直待在那里。（这是我们第一次偏离函数式编程，我们允许你进行赋值。但我们的意图是在计算开始前把表建好，之后把它当作常量信息，而不是可变的东西。）目前我们把 put 和 get 当作原语；到第 3 单元，我们会看到如何构造它们。

要理解这一切和数据导向编程的关系，先观察这样一个事实：我们有一些操作，希望它们能作用于各种各样的类型。根据输入数据的类型，我们调用不同的过程来执行同一个基本操作。例如，两个有理数相加用的过程和两个复数相加用的过程就不同。我们基本上是在处理一个二维表：一个轴上是可能的操作，另一个轴上是可能的类型。注意，如果一个过程需要多个实参，那么”可能的类型”实际上可能是一个类型列表。

采用这种范式，给系统添加新类型不需要修改任何现有过程；我们只需要往表里添加新条目。

一个新的示例系统

正如上一节提到的，如果我们想继续用算术的例子，表的”键”就必须是类型的列表。这里先不处理这种不必要的复杂性，我们换一个更友好的例子，理解起来会容易一些。不过，其中重要的思想和刚才完全一样。

我们的数据类型是正方形和圆形，操作是求面积和周长。作为对比（顺便复习），这些操作的带标签数据版本是这样写的：

(define pi 3.141592654)

;; 这是带标签数据版本：类型由被调用的通用过程来处理
(define (make-square side)
    (attach-tag 'square side))

;; 这是带标签数据版本：类型由被调用的通用过程来处理
(define (make-circle radius)
    (attach-tag 'circle radius))

;; 这是带标签数据版本：类型由被调用的通用过程来处理
(define (area shape)
    (cond ((eq? (type-tag shape) 'square)
           (* (contents shape) (contents shape)))
          ((eq? (type-tag shape) 'circle)
           (* pi (contents shape) (contents shape)))
          (else (error "Unknown shape -- AREA"))))

;; 这是带标签数据版本：类型由被调用的通用过程来处理
(define (perimeter shape)
    (cond ((eq? (type-tag shape) 'square)
           (* 4 (contents shape)))
          ((eq? (type-tag shape) 'circle)
           (* 2 pi (contents shape)))
          (else (error "Unknown shape -- PERIMETER"))))

上面的代码你应该能完全看懂！本课剩下的部分，我们会一直用这个正方形和圆形的例子。

用 put 把它们组合起来

有了页面顶部介绍的那个数据结构，系统现在可以处理任意数量的类型，而不必改动现有代码！新代码如下（构造函数保持不变）：

;; 这是数据导向版本：类型和操作由一个存储这些信息的数据结构来处理
(put 'square 'area (lambda (s) (* s s)))
(put 'circle 'area (lambda (r) (* pi r r)))
(put 'square 'perimeter (lambda (s) (* 4 s)))
(put 'circle 'perimeter (lambda (r) (* 2 pi r)))

注意，表里每个单元格中的条目是一个函数，而不是符号。现在我们可以重新定义这些通用运算符（之所以”通用”，是因为它们对任何类型都能用）：

;; 这是数据导向版本：类型和操作由一个存储这些信息的数据结构来处理
(define (area shape-obj)
    (operate 'area shape-obj))

(define (perimeter shape-obj)
    (operate 'perimeter shape-obj))

(define (operate op obj)
    (let ((proc (get (type-tag obj) op)))
      (if proc
          (proc (contents obj))
          (error "Unknown operator for type"))))

魔法发生在 operate 过程里。给定一个操作和一些数据，它会查出应该把哪个过程应用到这些数据上。如果条目存在（说明我们知道如何处理该操作），就简单地应用这个过程；否则抛出错误。

对数据导向编程的一点澄清

不要以为数据导向编程仅仅意味着一个由运算符名和类型名组成的二维表！DDP 是一个非常通用、非常出色的思想。它意味着把系统的细节放进数据里，而不是程序里，这样你就能编写通用的程序，而不是极其专用的程序。

早年间，每家公司买了一台计算机，都得雇上一批程序员，给他们写工资管理之类的程序。他们不能直接用别人写好的程序，因为细节不一样，比如员工编号有几位。而今天，你可以用通用的商业软件包，每家公司都能用一个数据文件把程序”调”到适合自己的特定用途。

另一个展示数据导向编程通用性的例子是编译器。过去，如果你想发明一种新的编程语言，就得从零开始为它写编译器。但现在，我们有形式化记法可以描述语言的语法。（见课程读本末尾 Scheme Report 的 7.1 节，第 38 页。）单个程序就能读取这些形式化描述，编译任何语言。