写在前面

SICP 整本书去年中旬就看完了，第一章到第四章的习题也已经全部解决，现在为什么 还要再来一遍？

  1. 说到习题，由于当时看这本书做习题时是在 windows 平台上，而 windows 系统并没 有现成的非常方便地运行 scheme 程序的工具 (例如 cmuscheme 用起来就很麻烦), 习题程序大部分都没有严格测试过，很多就是代码逻辑通顺就算完成，现在想来 bug 应该不少；
  2. 第五章从基于寄存器机器的设计引出解释器和编译器的原理，虽然说此章大多的习题 是叙述题所以没有做，但是 scheme repl 解释器的 c/c++ 实现还是值得一做的；
  3. SICP 的编程思想贯穿于今年学习 Cpp-Primer 以及 CLRS 的过程当中，这个我 很明确的感受到了：构造过程抽象 & 构造数据抽象，虽然我只能说是略有领会，但确 实在解决编程问题时提供了极大的帮助。编程工具会被淘汰，但编程思想永不过时， 特别是在实践之后再重温必有更多获益；
  4. Cpp-Primer & CLRS 在博客的相关博文中并没有详细的总结当时的代码思路，其 主要内容是代码及一小部分注释，注释部分或者是关于代码的难点，亦或者是提醒容 易出错的地方，这样的形式可读性很差，但要仔细组织文档的话，整体工作量又何止 增加一倍；而这一次既然是复习 & 查错，同时利用 orgmode 嵌入代码块及 scheme的 解释性语言的特点，可以在组织文章的同时运行～修改代码，这是效仿使用orgmode 文档嵌入 elisp 代码块构成 emacs 配置文件的做法，许多 emacs 大佬用这种手法提 高配置文件可读性。

有些书就是值得一遍又一遍的反复咀嚼，毫无疑问 SICP 就是其中的一员。

第一章

  1. 计算过程与程序
    1. 计算过程：存在于计算机里的一类抽象事物，可以操作一些称为数据的抽象事物；
    2. 程序：人们创建出的规则模式，以指导计算过程的进行；
    3. 设计良好的程序应该具有某种模块化的设计，各个部分都可以独立地构造，替换和 排除错误，某模块发生的错误影响限于模块内部，并不会影响其它模块和整体程序。
  2. Lisp 语言作为本书中讨论程序设计的基础
    1. 最重要的是因为：计算过程的 Lisp 描述（过程）本身又可以作为 Lisp 的数据结 构来表示和操作；
    2. 现存的许多威力强大的程序设计技术，都依赖于填平在“被动的”数据和“主动的”过 程之间的传统划分。

程序设计的基本元素

  1. 程序设计中的两类要素：过程和数据
    1. 非形式化地说，数据是一种我们希望去操作地“东西”，而过程就是有关操作这些 数据的规则的描述；
    2. 任何强有力的程序设计语言都必须能表述基本的数据和基本的过程，还需要提供 对过程和数据进行组合和抽象的方法；
    3. 本章只处理简单的数值数据，把注意力集中到过程构造的规则方面，当然这些规 则同样可以用于操作各种数据。

表达式

  1. 组合式是什么
    1. 构成方式就是用 一对括号 括起一些 表达式, 形成一个表，用于表示一个 过程应用;
    2. 表里最左的元素称为 运算符, 其它元素都称为 运算对象;
    3. 要得到这种组合式的值，采用的方式就是由 运算符 所刻画的过程应用于有关 的 实际参数, 而所谓 实际参数 也就是那些 运算对象 的值。
  2. 组合式的 运算符 前缀表示
    1. 完全适用于可能带有任意个实参的过程；
    2. 可以直接扩充，允许出现组合式嵌套的情况。

命名和环境

  1. 通过名字去使用 运算对象 的方式
    1. 将名字标识符称为 变量, 它的 值 也就是它所对应的那个对象；
    2. Scheme 中通过 define 的方式给事物命名，是我们所用的语言里最简单的抽象 方法；
    3. 构造一个复杂的程序，也就是为了去一步步地创建出越来越复杂的计算性对象。
  2. 环境
    1. 将值与符号关联，而后又能提取出这些值，解释器必须维护某种存储能力，以便 保持有关的 名字－值 序对的轨迹。

组合式的求值

  1. 组合式的求值过程是递归的，应该把递归看做一种处理层次性结构的极强有力战术；
  2. 数，内部运算符或者其它名字是基本表达式，内部运算符和其它名字可以看作符号， 环境所扮演的角色就是用于确定表达式中各个符号的意义；
  3. 一般性求值规则的例外被称为特殊形式（比如define，它并不是一个组合式），对 各种表达式的求值规则可以描述为一个简单的通用规则和一组针对不多的特殊形式 的专门规则。

复合过程

  1. 过程定义是一种威力更加强大的抽象技术，通过它可以为复合操作提供名字，而后 就可以将这样的操作作为一个单元使用了；
  2. 复合过程的使用方式与基本过程完全一样。

过程应用的代换模形

  1. 应用序：将复合过程应用于实际参数，就是在将过程体中的每个形参用相应的实参 取代之后，对这一过程体求值；
    1. 代换的作用只是为了帮助我们领会过程调用中的情况，而不是对解释器实际工作 方式的具体描述。
  2. 正则序：先不求出运算对象的值，直到实际需要它们的值时再去做，采用这种求值 方式，首先用运算对象表达式去代换形式参数，直至得到一个只包含基本运算符的 表达式，然后再去执行求值。

条件表达式何谓词

  1. cond: 条件表达式，如果无法找到值为真的

    , cond 的值无定义；

    1
2
3
4
5
6

    (cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      ;; 最后一个子句 <p> 可以替换为 else
      ;; 即前面所有子句都被跳过，会返回最后子句中 <e> 的值
      (<p3> <e3>))

  2. if: 条件表达式的受限形式，适用于分情况分析中只有两个情况的需要；

    1

    (if <predicate> <consequent> <alternative>)

  3. and: 特殊形式而不是普通过程，因为子表达式不一定都求值；

    1

    (and <e1> ... <en>)

  4. or: 特殊形式而不是普通过程，因为子表达式不一定都求值；

    1

    (or <e1> ... <en>)

  5. not: 普通过程

    1

    (not <e>)

练习 1.1-1.5

  • 1.1

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    10                  ;10
(+ 5 3 4)               ;12
(- 9 1)                 ;8
(/ 6 2)                 ;3
(+ (* 2 4) (- 4 6))         ;6
(define a 3)                ;a = 3
(define b (+ a 1))          ;b = 4
(+ a b (* a b))             ;19
(= a b)                 ;false
(if (and (> b a) (< b (* a b)))
    b
    a)                  ;3
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))            ;25
(+ 2 (if (> b a) b a))          ;6
(* (cond ((> a b) a)
     ((< a b) b)
     (else -1))
   (+ a 1))             ;16

  • 1.2

    1
2
3
4
5
6
7
8

    (/ (+ 5 4
      (- 2
     (- 3
        (+ 6
           (/ 4 5)))))
   (* 3
      (- 6 2)
      (- 2 7)))             ;-37/150

  • 1.3

    1
2
3
4

    (define (max-sum a b c)
  (cond ((and (>= a b) (>= c b)) (+ a c))
    ((and (>= a c) (>= b c)) (+ a b))
    (else (+ b c))))

  • 1.4

    1

    ;; 该过程将第一个传入数值与第二个传入数值的绝对值相加

  • 1.5

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    ;; (define (p) (p)) 定义了一个无参数过程 p，过程体就是调用它自己，对 (p) 进行求
;; 值会进入无限递归进而报错；

;; 应用序：报错，因为在应用序下要对组合式的各个子表达
;; 式进行求值，对第二个参数表达式求值将会触发上面第一条所讲的情况；

;; 正则序：通过，因为正则序求值是直到实际需要运算对象的值时再去做，而定义的 test
;; 过程在传入的第一个参数为0的情况下过程体谓词部分的值为 true, 根据 if 条件表达
;; 式的特殊求值规则，它包含 (p) 的 <alternative> 部分并不求值，所以不会触发第一
;; 条所讲的情况。

实例：采用牛顿法求平方根

  1. 函数与过程之间的矛盾，不过是在描述一件事情的特征，与描述如何去做这件事情 之间的普遍性差异的一个具体反映，也就是说明性的知识与行动性的知识之间的差 异。在数学里，人们通常关心的是说明性的描述，而在计算机科学里，人们通常关 心行动性的描述；
  2. 不用特殊的迭代结构，只需要使用常规的过程调用能力也可以实现迭代。

练习 1.6-1.8

  • 1.6

    1
2
3

    ;; 新定义的过程 prodecure 是一个普通过程，在调用它时将会对它的所有子表达式求值，
;; 无论 predicate 部分的结果如何，作为 else-clause 的 sqrt-iter 部分将会一直被调
;; 用从而导致一个无尽递归调用，解释器报错。

  • 1.7

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    ;; 对于特别小的被开方数，甚至比事先确定的误差值还要小的数，猜测值将主要依赖于误
;; 差值而不是被开方数；

;; 对于特别大的被开方数，猜测值的离散性也越明显，有可能导致猜测值的平方与被开方
;; 数的绝对值差永远大于事先确定的误差值。

;; a new good-enough? procedure
(define (good-enough? guess old-guess)
  (< (/ (abs (- guess old-guess)) guess) 0.001))

(define (sqrt-iter guess old-guess x)
  (if (good-enough? guess old-guess)
      guess
      (sqrt-iter (improve guess x)
         guess
         x)))

(define (sqrt x)
  (sqrt-iter 1.0 0 x))

  • 1.8

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    (define (good-enough? guess old-guess)
  (< (/ (abs (- guess old-guess)) guess) 0.000001))

(define (improve-guess guess x)
  (/ (+ (/ x (square guess)) (* 2 guess))
     3))

(define (cubic-iter guess old-guess x)
  (if (good-enough? guess old-guess)
      guess
      (cubic-iter (improve-guess guess x)
          guess
          x)))

(define (cubic x)
  (cubic-iter 1.0 0 x))

过程作为黑箱抽象

  1. 将程序分解为一族过程，每一个子过程完成了一件可以清楚标明的工作，使它们可 以被用作定义其他过程的模块；这直接反映了从原问题到子问题的分解；
  2. 在一个抽象层次上，任何能接受相同的参数计算出相同结果的过程都是不可区分的， 这就是过程抽象；用户在使用一个过程时，应该不需要去弄清它是如何实现的；
  3. 一个过程的定义约束了它的所有形式参数，形式参数被称为 约束 变量，以它被约束 于的那一集表达式称为这个名字的作用域；如果一个变量不是被约束的，那它就是 自由 的；
  4. 将所用的辅助过程定义放到内部，使它们局部于这一过程，这样嵌套的定义称为块 结构，是最简单的名字包装问题的一种正确方式；*词法作用域* 要求过程中的自由 变量实际引用外围过程定义中所出现的约束，即在定义本过程环境中去寻找它们。