🚧 SICP Notes

Work In Progress

浅记一下SICP学习笔记与MIT 6.001实验笔记

LISP环境配置

mit-scheme过老, 没有各种新特性, 因此选择使用racket + vscode作为日常scheme coding

install

  • 安装racket: brew install minimal-racket
  • 安装SICP方言: raco pkg install sicp
    • sicp collection. 通过在文件开始#lang sicp载入. 如果需要在交互式命令行中启用sicp方言,则使用如下命令: racket -I sicp
  • 安装vscode插件: magic-racket
    • 安装racket language server: raco pkg install racket-langserver

在安装racket-langserver时遇到一些奇怪的错误, 大致如下图所示:

但是手动wget能拉下来包. 怀疑是代理的问题. 通过手动安装的方式解决:

  1. 手动将安装包下载到本地: wget http://www.neilvandyke.org/racket/html-parsing.zip
  2. 手动安装该依赖包: raco pkg install -t file ./html-parsing.zip
    • 期间若有其他包有同样类似的报错, 也可以采用上述操作. 安装完成后将zip包删除即可.

然后就可以开始快乐地写Lisp啦

Hints

symbol

scheme中的符号(symbol), 绝不同于字符串(string), 它是对具体数据的一种抽象描述. 通过定义symbol, 能够极大地提升程序的抽象能力.

类型标志本质上就是对symbol的一种妙用. 通过构造symbol和content序对, 定义如下的选择函数和构造函数, 也就得到了带类型标识的数据

(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 (content datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

此时, 类型的判断也就化作了tag的比较. 如判断是否为极座标类型

(define (polar? data)
  (eq? (type-tag data) 'polar))

基于类型的分派也就是简单地通过不同的类型标志, 调用不同的选择函数, 构造函数. 可以通过一个简单的cond实现. 但是带来的作用却是巨大的. 因为其屏蔽了不同实现之前的差别, 并实现了兼容. 此时, 就有了一个强大的抽象系统. 实现了彻底的分层. 但是也带来了弊端, 即构造, 选择函数必须知道所有实现. 这无疑给编码和维护的人员带来了巨大的心智负担.

数据导向的程序设计则是对基于类型的分派的进一步抽象: 与其让每个实现分别做分派, 不如再加一层中间层, 其维护一个table, 其中记录了由操作与类型惟一确定的函数. 此时, 该中间层起到代理的作用. 每当被调用, 它就去检查调用者发起的操作以及被操作的数据的类型, 通过查表得到唯一确定的实际功能函数, 并委托其进行真正的数据操作.

数据导向

部分练习题详解

1.30

\[\sum_{i=0}^{n} f(x) = f(x_{0}) + f(x_{1}) + \cdots + f(x_{n})\] 
(define (sum f a next b)
  (define (sum-iter a result)
    (if (> a b) result
        (sum-iter (next a) (+ (f a) result))))
  (sum-iter a 0)
  )

此处f和next为两个procedure. 分别产生值与下一个自变量. f即为公式中的 \(f\), next含义为 \(x_{i} = next(x_{i-1})\). 因此将其转换为迭代计算过程就非常容易. 通过一个result缓存记录从开始到当前值的累加结果即可.

1.29

\[\int_{a}^{b}f(x) \approx \frac{h}{3}(y_{0} + 4y_{1} + 2y_{2} + 4y_{3} + 2y_{4} + \cdots + 2y_{n-2} + 4y_{n-1} + y_{n}) \\ h = \frac{b-a}{n} \mbox{ while } n \mbox{ is even} \\ y_{k} = f(a + kh)\] 
(define (simpson-integral f a b n)
  (define h (/ (- b a) n))
  (define (next-item a) (+ a h))
  (define (y x)
    (cond ((= x a) (f x))
          ((= x b) (f x))
          ((even? (/ (- x a) h)) (* 2 (f x)))
          (else (* 4 (f x)))))
  (* (sum y a next-item b)
     (/ h 3.0))
  )

下一自变量仅需将当前自变量加上h即可. 因此重点在于转换f(x), 不能使用原生提供的f(x)而应当将累加因子中的1, 2, 4纳入”f(x)“的计算之中. 因此定义新的y如下:

\[\begin{equation} y(x) = \left\{ \begin{array}{ll} f(x) & \mbox{x = a or x = b} \\ 2f(x) & \mbox{x is even} \\ 4f(x) & \mbox{x is odd} \\ \end{array} \right. \end{equation}\]

将改y(x)作为新的累加项生成器即可.

1.32 

(define (accumulate combiner null-value term a next b)
  (define (accumulate-iter a result)
    (if (> a b) result
        (accumulate-iter (next a) (combiner result (term a)))))
  (accumulate-iter a null-value))

(define (accumulate-sum f a next b)
  (accumulate + 0 f a next b))

此处的accumulate仅需对sum进行一次抽象即可. 立即可知sum是accumulate中combiner为+, null-value为0的特殊情况.

2.4

非常之神奇. 主要利用了过程闭包的性质

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

cons返回的是一个过程, 而这个过程的参数也是一个过程. 参数中的过程作用于构造序对的参数x, y.

将(car (cons x y))进行正则序展开:

((cons x y) (lambda (p q) p)) ;; =>
((lambda (m) (m x y)) (lambda (p q) p)) ;; =>
((lambda (p q) p) x y) ;; =>
x

m即为(lambda (p q) p)

cdr同理

2.6

我直接大脑升级了

先展开演算一下one和two, 看看能不能找到什么规律

;; !!!important!!!
(zero f) ;; =>
((lambda (f) (lambda (x) x)) f) ;; =>
(lambda (x) x)

;; one: (add-1 zero)
(add-1 zero) ;; =>
(lambda (f) (lambda (x) (f ((zero f) x)))) ;; =>
(lambda (f) (lambda (x) (f ((lambda (x) x) x)))) ;; =>
(lambda (f) (lambda (x) (f x))) ;; =>

;;; !!!important!!!
(one f) ;; =>
((lambda (f) (lambda (x) (f x))) f) ;; =>
(lambda (x) (f x))

;; two: (add-1 one)
(add-1 one) ;; =>
(lambda (f) (lambda (x) (f ((one f) x)))) ;; =>
(lambda (f) (lambda (x) (f ((lambda (x) (f x)) x)))) ;; =>
(lambda (f) (lambda (x) (f (f x)))) ;; =>
(lambda (x) (f (f x)))

因此感觉上, 可以猜测n是f作用于x的次数.

事实上也确实是这样. 具体定义点这里. 形式化证明通过数学归纳法简单地推导一遍就出来了.

此时加法过程定义如下:

(define (add m n)
  (lambda (f) (lambda (x) (m ((n f) x)) x)))

2.13

本质上是在推导误差对于结果的影响. 因此, 可以简单地从数据层面进行一拨论证:

\[\mbox{assume the errors of } R_{1},\ R_{2} \mbox{ are separately } a,\ b \mbox{ then, } \\ R_{1} \in [(1-a)r_{1},\ (1+a)r_{1}], \ R_{2} \in [(1-b)r_{2},\ (1+b)r_{2}] \\ R_1 + R_2 \in [] \\ R_1 \cdot R_2 \in [] \\ \mbox{therefore, } \\ \frac{R_1R_2}{R_1 + R_2} \in [] \\ \frac{1}{1/R_1 + 1/R_2}\]

2.28

本质是对树的层序遍历, 但是是递归做法.

(define (fringe x)
  (cond ((null? x) nil)
        ((not (pair? x)) (list x))
        (else (append (fringe (car x)) (fringe (cdr x))))))

因此, 借助append归并两个子树的序列即可.

2.29

定义right-branch, branch-structure时要注意list定义序偶的返回值: $list(a, b) \Rightarrow (a, (b, nil))$. 因此, (cdr branch)的返回值不是structure而是(structure, nil). 需要再对其进行car才能拿到真正的structure

(define (make-mobile left right) (list left right))
(define (left-branch x) (car x))
(define (right-branch x) (car (cdr x)))

(define (make-branch len structure) (list len structure))
(define (branch-length branch) (car branch))
(define (branch-structure branch) (car (cdr branch)))

返回总重量本质是对树的遍历. 由于函数式对递归的”偏好”,深搜即可

(define (total-weight root)
  (cond ((null? root) 0)
        ((not (pair? root)) root)
        (else (+ (total-weight (branch-structure (left-branch root)))
                 (total-weight (branch-structure (right-branch root)))))))

平衡要求任一子树都是平衡的. 而对单一子树, 平衡要求 $左子树重量 \times 左子树长度 \equiv 右子树重量 \times 右子树长度$. 而子树重量很容易联想到上一问的函数total-weight. 但是要注意到这样一个事实: 即如果像下面这样直接使用total-weight会导致指数级的递归计算过程.

(define (check-balance root)
  (if(null? root)
     #t
     (and (check-balance (branch-structure (left-branch root)))
          (check-balance (branch-structure (right-branch root)))
          (= (* (branch-length (left-branch root)) (total-weight (branch-structure (left-branch root))))
             (* (branch-length (right-branch root)) (total-weight (branch-structure (right-branch root))))))))

因为树每向上增长一级, total-weight都要再重新计算整颗子树.

因此, 可以考虑在计算子树weight时”顺带”检查平衡性, 并将平衡检查的结果连同weight一起返回.

(define (check-balance root)
  (define (make-result is-balance weight) (cons is-balance weight))
  (define (result-is-balance result) (car result))
  (define (result-weight result) (cdr result))

  (define (check root)
    (cond ((null? root) (make-result #t 0))
          ((not (pair? root)) (make-result #t root))
          (else (let ((left-result (check (branch-structure (left-branch root))))
                      (right-result (check (branch-structure (right-branch root)))))
                  (make-result (and
                                (result-is-balance left-result)
                                (result-is-balance right-result)
                                (= (* (branch-length (left-branch root)) (result-weight left-result))
                                   (* (branch-length (right-branch root)) (result-weight right-result))))
                               (+ (result-weight left-result) (result-weight right-result)))))))
  (result-is-balance (check root)))

2.38

fold-left和fold-right的计算过程可以抽象为以下操作. 其中 \(\circ\) 表示操作符op, \(\mathbb{S}\) 表示所操作的集合(sequence):

\[\begin{array}{llll} \texttt{fold-right} & (\circ, S_{initial}, \mathbb{S}) & = & S_{0} \circ \cdots (S_{n-1} \circ (S_{n} \circ S_{initial})) \\ \texttt{fold-left} & (\circ, S_{initial}, \mathbb{S}) & = & ((S_{initial} \circ S_{0}) \circ S_{1}) \cdots \circ S_{n} \end{array}\]

因此, 若要fold-left和fold-right结果相同, 则要求op满足交换律和结合律

2.46 - 2.51

首先研究frame-coord-map这个函数

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

frame-coord-map接受的参数是一个框架frame, 返回的是一个过程: 将单位正方形中的向量映射到给定的frame中. 它的作用便是使画家忽略不用框架之间的区别.

然后考虑painter这个对象. 一个抽象的画家是一个过程: 它接受一个frame并在这个frame上进行一些绘画操作. 为了执行绘画操作, 不仅需要绘画所在的框架, 还需要绘画具体的内容, 如线条, 灰度等等. 因此, 一个具体的画家, 应当以绘画要素为参数, 并返回一个抽象的画家那样的过程. 即, 抽象的画家是一个接口, 它定义了画家与框架之间的关系. 具体的画家则是一个”高阶过程”: 接收一些参数, 并返回一个抽象的画家那样的过程. 因此, 具体的画家更类似于”画家生成器”.

如SICP中定义的segments->painter:

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

其接收一组segments作为参数, 并返回这样一个过程: 以frame为参数. segments->painter的用法自然为((segments->painter segments) a-frame). 同时注意到, 此处的segments应当是在单位正方形内的一组线段..

在搞清楚上述过程的情况下, 再来观察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-vert (m corner1) new-origin)
                     (sub-vert (m corner2) new-origin)))))))

该函数的本质是: 通过改变画家眼中的框架, 实现图像的仿射变换. 效果等同于生成一个新的画家. 参数是一个画家painter, 新的起点origin和新的两个边的终点corner1, corner2. 因此, 新的边向量为corner1 - origin, corner2 - origin.

又frame-coord-map所执行的变换是线性的, 因此有了下面的等式:

\[m(edge_1) = m(corner_1 - origin) = m (corner_1) - m(origin) \\ m(edge_2) = m(corner_2 - origin) = m (corner_2) - m(origin)\]

这也是make-frame中两个sub-vert参数的由来.

此时也应当注意到, origin, corner1, corner2所代表的, 是将单位正方形进行变换后的新的起点和两个边的终点.

Again, transform-painter本质上是对框架的变化.

2.56

大脑又升级了. 符号求导.

根据sum和product很容易得能构造出exponentiation相关函数并改造deriv.


;; (** a b) -> a^b
(define (exponentiation? exp)
  (and (pair? exp) (eq? (car exp) '**)))
(define (base exp) (cadr exp))
(define (exponent exp) (caddr exp))
(define (make-exponentiation base exp)
  (cond ((=number? exp 0) 1)
        ((=number? exp 1) base)
        (else (list '** base exp))))

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (multiplicand exp)
                        (deriv (multiplier exp) var))))
        ((exponentiation? exp)
         (make-product (exponent exp)
                       (make-product (make-exponentiation (base exp) (- (exponent exp) 1))
                                     (deriv (base exp) var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

2.58

// TODO:(xylonx):