《计算机程序的构造与解释》笔记

这是本文档旧的修订版！

SICP：Structure and Interpretation of Computer Programs
本书使用 Lisp 方言 Scheme 来教学。ubuntu 14.04 可安装 scheme-r5rs包（不知道为何没有 mit-scheme包）

每一种语言提供了三种机制：
- 基本表达形式：语言关心的最简单个体
- 组合的方法：通过它们来从简单元素构造复合的元素
- 抽象的方法：为复合对象命名并作为操作单元
程序设计处理的两类要素：过程和数据（但并不严格区分）
1.1.1 前缀表达式 137 + 349 ⇒ (+ 137 349) , 可避免多参数歧义，可嵌套。
1.1.2 Scheme 用 define 命名变量
1.1.3 组合式的求值是递归的，计算过程为树形积累；不同于一般性求值规则的特殊形式，比如 define用于关联变量
1.1.4 过程定义。定义平方操作(define (square x) (* x x)), 过程定义的一般形式是:
```
(define (<name> <formal parameters>) <body>)
```
1.1.5 过程应用的代换模型。
- 正则序求值：完全展开二后归约；
- 应用序求值：先求值参数而后应用；
- Lisp 采用应用序求值，避免对于表达式的重复求值，替换范围过大时正则序处理变得复杂。

1.1.6 条件表达式。

另一个特殊形式：分情况分析cond：

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

执行时直到 px 真，则返回 ex.

if:

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

逻辑复合谓词，三个常见复合运算符：

; 有假则返回假，后续不判断，全真则返回 en
<and <e1> ... <en>)
; 有真则返回第一个真，后续补判断，全假则返回假
<or <e1> ... <en>)
; e 真返回假，e 假返回真
<not <e>)

练习1.6 为什么不能由conf定义if,而重新提供一个if. 因为由conf定义的if在参与递归时会先求值参数而导致无限递归，所以需要一个能先执行判断条件（而不是先求所有参数值）的特殊形式。
1.1.8 块结构：分析了允许一个过程带有局限此过程的内部定义的必要性。

1.2.1 线性的递归与迭代
1.2.2 树形递归
1.2.3 参考算法导论对于计算资源效率的定义，算法效率
分析了许多数学计算过程，不过都比较常见。详见书。

1.3.1 过程作为参数

1.3.2 用 lambada 构造过程；let表达式构建局部变量:

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ...
      (<varn> <expn>))
   <body>)
 ; 即在<body>中的<var1>具有值<exp1>，且<var2>具有值<exp2>...<varn>具有值<expn>

1.3.3 过程作为一般性方法的应用，分析了寻找方程根 f(x)=0 的区间折半方法等，详见书。
1.3.4 过程作为返回值
- 最少限制的可计算元素被称为具有第一级的状态，第一级元素性质包括：可用变量命名，可作为过程的参数，可作为过程的返回，可悲包含在数据结构中。
- Lisp 给了过程完全的第一级状态，所有有效的实现是个挑战。其它程序语言或多或少加了某些限制。（但是现代语言这几年的发展基本包括了这些性质）