选自塞尔的红袍法师学院标准教材 必修课一

写于4月16日

战斗法师

Alt text

#第二章 构造数据的抽象

”现在到了魔法抽象最关键的一步：让我们忘记这些符号所表示的对象。……（魔法师）不应在这里停步，
有许多操作可以应用于这些符号，而根本不必考虑它们到底代表着什么东西。
——Hermann Weyi，(魔法的思维方式)

第一章主要关注的是计算过程，以及过程在程序中所扮演的角色。这一章主要关注更复杂的数据。

###2.1 数据抽象导引
作者首先举了个例子，我们要计算有理数算术，有理数是 x/y，我们算分式加法的时候就要分别组合分子分母进行运算，lisp提供了一个基本过程cons，cons(1 2)代表一个序对，(car cons(1 2)) 和(cdr cons(1 2))分别可以取出这个序对的前一项和后一项，我们把cons成为构造函数，把car 和cdr称为选择函数。
利用cons我们可以定义一个有理数的数据结构.

1
2
3
4
5
;;构造函数
(define (make-rat n d) (cons n d))
;;选择函数
(define (numer x) (car x))
(define (denom x) (cdr x))

有了有理数我们可以定义有理数的加减乘除add-rat sub-rat mul-rat div-rat equal-rat？……

####2.1.2抽象屏障

————————————————————————————————
（使用有理数的程序）
————————————————————————————————

问题域中的有理数

————————————————————————————————
（add-rat sub-rat）
————————————————————————————————

作为分子分母的有理数

————————————————————————————————
（make-rat numer denom）
————————————————————————————————

作为序对的有理数

————————————————————————————————
（cons car cdr）
————————————————————————————————

当然，序对也需要实现
如上图所示，我们做了有理数系统的抽象，不同层次的构造和选择函数构成了抽象屏障。这一思想有许多优点，第一是这种方法使程序很好修改和维护，任意一种比较复杂的数据结构都可以以多种不同的方式用程序设计语言所提供的基本数据结构表示。

####2.1.2数据意味着什么

在这里作者提出一个很哲学的问题————数据意味着什么？

我们总可以将数据定义为一组适当的选择函数和构造函数
cons是基本过程么吗（在lisp里确实是）但是。。（关联上文，序对可以怎么实现）

1
2
3
4
5
6
7
(define (cons x y)
  (lambda (m) 
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1 --CONS" m)))))
(define (car z)(z 0))
(define (cdr z)(z 1))

我们完全可以像上面这样不用任何数据结构，只使用过程就实现序对，而我们在使用cons car cdr将无法和“真正的”数据结构区分。（lambda是匿名函数，cond是switch。。）

这一实例也说明可以将过程作为对象去操作，因此就自动为我们提供了一种表示复合数据的能力。这些能力现在看起来好像只是好玩，但实际上，数据的过程性表示将在我们的程序设计宝库里扮演一种核心的角色。有关的程序设计风格通常称为消息传递。在第三章里讨论模型和模拟时，我们将用它作为一种基本工具。

###2.2层次性数据和闭包

####2.2.1序列的表示（表）

cons为我们提供了构造复合数据的基本粘合剂，这里的list，称为表，可以这么表示（基本对应js的数组）

1
2
3
4
5
6
(list 1 2 3 4)  =>
(cons 1 
    (cons 2 
        (cons 3 
            (cons 4 '()))))
;;; '()代表nil（null）

cons可以创建这种层次性的结构，而这种可以自己套自己组合数据的能力叫做闭包（没错，和函数套函数保存局部变量的那个闭包没关系，没错，lisp也有
函数闭包的概念，没错，就是这么混淆。。）

练习
求表的length，数组用index取元素 ，append ，reverse等等

1
2
3
4
5
6
7
8
9
10
11
12
;;;递归版
(define (length x)
  (if (null? x)
      0
      (+1 (length (cdr x)))))
;;;迭代版
(define (length x)
  (define (iter a count)
    (if (null? a)
        count
        (iter (cdr a) (+ 1 count))))
  (iter x 0))

对表的映射
map for-each
很熟悉了，但意义也比较重要，代表了处理表的更高层的抽象

####2.2.2层次性结构

因为闭包所以我们的表结构经过嵌套可以变成树结构
练习
求树的length（几片树叶），fringe方法（_.flatten），一个二叉活动体（这啥玩意，原始机器人）

对树的映射
练习
树叶的map

####2.2.3序列作为一种约定的界面

吐槽一下翻译，原文是Conventional Interfaces，约定的接口，翻译成约定的界面=。=
作者举了个例子
（前面一道例题）算一个树结构奇数叶子的平方和

1
2
3
4
5
6
7
(define (sum-odd-square tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-square (car tree))
                 (sum-odd-squate (cdr tree))))))
;;;null?判断是不是空表 pair？判断是不是序对

和计算偶数fib数列

1
2
3
4
5
6
7
8
9
(define (even-fibs n)
  (define (next k)
    (if (even? k)
        '()
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

上面的两个过程解耦后的相似性是：
第一个过程：
1.枚举树叶
2.过滤选出奇数
3.对每个数平方
4.用累加器算结果

第二个过程：
1.枚举从0到n
2.对每个数算fib
3.过滤偶数
4.用cons累加，从空表开始

我们可以向信号处理一样，处理这个信号流结构。。。。（再看管道、aggregate等的思想）

练习
几个累加器，和利用著名的honor规则，构造多项式的累加形式;计算矩阵的&*#@#￥……

嵌套映射

没太看懂，
几个常用的嵌套循环表述的计算，举了求某个区间素数的例子，和著名的“八皇后问题”

####2.2.4实例：图形语言

作者设计一个用图形表示的语言，实现了各种变换组合，过程看的是云山雾绕，最后得出结论是
我们已经看到了过程和数据抽象的关键思想，其中基本数据抽象和过程都可以用过程表示实现。（这点感觉后面会延伸）
复杂的系统需要分层设计，而每一层对应一系列为此设计的语言，它提供了基本元素，组合手段，还有对该层次适当细节的抽象
电阻晶体管组成（模拟电路的语言）——>与或非门（数字电路的语言）——>cpu、总线、存储器（描述计算机体系结构的语言）
——>分布式系统/网络（描述网络的语言）
从语言的设计角度介绍这种分层真是大开眼界

###2.3符号数据（symbol data）

####2.3.1引号
单引号表示（可以省略后面的引号，不闭合），类似字符串，但又不同，因为lisp里用双引号表示字符串，主要是为了给屏幕显示信息

练习
代数表达式（用’x ‘y表示数学里的x y啥的，很复杂，和上面构造有理数一样的抽象层次，lisp终于可以写代数表达式了）
2.3.2符号求导（lisp又一次用牛逼的算法求了导，拯救了数学界。。）

####2.3.3实例：集合

这里要实现一个不同于表（数组）存放的不同数据的集合。
直观的想法效率不高，添加一个元素要遍历集合检查有没有这个元素，步数是o（n），求全集和子集更是要o（n^2）
对于聪明的人类来说这简直不能忍，就从数据结构上想办法,我们的集合是平衡二叉树，这棵树的枝干是平均的，那么搜索的步数可以变成o（log n）
如何让他平均呢，都是设计一种新的数据结构，让搜索和插入都是o（log n），比如传说中的红黑树和b树

集合和信息检索

关于数据库，作者说可以创建简单而直接的初始实现，例如采用一个未排序的表，然后数据的表示可以更加精细，数据访问的基于这个抽象层次的选择函数
和构造函数，这样数据的表示改变就不会影响系统的其余部分
题外话
mongo的collection——>document就类似这样“初始实现”（猜想没那么简单），数据表示（查询返回）的最小单位是document，
但是使用原子修改器去修改document的字段，无疑就是使用这个抽象层次的选择函数
目前对关系型还不了解，没有对比。

例子
传说中的霍夫曼编码树（huffman）（被我无情略过。。）

###2.4 抽象数据的多重表示

####2.4.1复数
作者用复数举例子，可以有直角坐标和极坐标两种方式，在这里数据的抽象屏障除了水平的层次又出现了垂直的层次，一种数据的两种表示

####2.4.2带标志的数据
需要每个复数还有一个类型标志，去区分他们的表示方式（极坐标还是直角坐标）

####2.4.3
上面检查一个数据的类型，并据此去调用某个适当过程成为基于类型的分派。他有缺点，不具有可加性。
所以，有一种称为数据导向的程序设计（面向对象的思想）

###2.5带有通用型的操作的系统

####2.5.1通用型算术运算
实现了一个复数的加减乘除的运算包

####2.5.2不同类型数据的组合
具体就不写了。。。

###后记
这章给我的震撼是，想要有杰出的设计能力的前提除了熟练使用工具，更重要的是抽象能力。
人类的知识，人类的聪明才智，人类之所以能成为人，就在于人类的抽象能力，从最简单的轮子到现在顶尖科学家的脑力劳动，都是对这个世界的抽象。
和DND题材的法师做对比，想成高阶法师，需要沟通元素/深层魔网，不断的研究世界（抽象），然后逐步构建固化自己的认知世界。
程序员应该是有史以来现实世界里唯一有施法环境的魔法师吧。。。
卡马克大概就是传奇法师
淘宝这种服务大概就是某个魔法帝国法师团的大型战争禁咒吧。

hohohohohoho~~~~

个人学习笔记，做记忆索引之用.