SICP - 石记

构造过程抽象

程序设计的基本元素

基本表达式用于表示语言所关心的最简单的个体
组合的方法通过它们可以从较简单的东西出发构造出复合的元素
抽象的方法通过它们可以为复合对象命名，并将它们当作单元去操作。

命名环境

(define variable value)

组合式的求值

求值该组合式的各个子表达式。
将作为最左子表达式的值的那个过程应用于相应的实际参数。

复合过程

包括：

数和算术运算是基本的数据和过程
1. 组合式的嵌套提供了一种组织起多个操作的方法
2. 定义是一种受限的抽象手段，它为名字关联相应的值。

抽象过程的定义

(define (funcName params) body)

过程应用的代换模型

为了求值一个组合式，解释器将对组合式的各个元素求值，而后将得到的那个过程应用于那些实际参数。

应用序求值先求值参数而后应用
正则序求值指“完全展开而后紧约”的求值模型

条件表达式和谓词

条件表达式的一般形式

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

受限形式

(if predicate consequent alternative)
(define (abs x)
(if (< x 0)
(- x)
x))

谓词

(and e1 e2)
(or e1 e2)
(not e)

过程作为黑箱的抽象

局部名过程的意义应该不依赖于其作者为其形式参数所选用的名字
内部定义和块结构我们要允许一个过程里带有一些内部定义，使它们是局部于这一过程的。

(define (sqrt x)
    (define (good-enough? guess x)
        (< (abs (- (square guess) x)) 0.0001))
    (define (improve guess x)
        (average guess (/ x guess)))
    (define (sqrt-iter guess x)
        (if (good-enough? guess x)
            guess
            (sqrt-iter (improve guess x) x)))
    (define (square x)
        (* x x))
    (define (average x y)
        (/ (+ x y) 2))
    (sqrt-iter 1.0 x))

(define (square x)
    (* x x))

(display (sqrt 8))
(newline)
(display (square (sqrt 8)))
(exit)

过程与它们所产生的计算

增长的阶

描述不同计算过程在消耗计算资源的速率上可能存在的差异。一般来说，定义一个不变量，要求它在状态之间保持不变，这一技术是思考迭代算法设计问题时的一种非常强有力的方法。

用高级函数作抽象

过程作为参数

用lambda构造过程

一般而言，lambda用与define同样的方式创建过程，除了不为有关过程提供名字

(lambda (formal-parameters) body)

e.g.
(define (plus4 x) (+ x 4))
;; 等价于
(define plus4 (lambda (x) (+ x 4)))

用let创建局部变量

let表达式的一般形式是
```
(let ((var1 exp1)
      (var2 exp2)
      .
      .
      (varn expn))
  body)
```
其实let表达式只是作为其基础的lambda表达式的语法外衣。 let表达式的特点
1. let使人能在尽可能接近其使用的地方创建局部变量约束。
2. 变量的值是在let之外计算的。

过程作为一般性的方法

过程作为返回值

一般而言，程序设计语言总会对计算可能使用方式强加上某些限制。带有最少限制的元素被称为具有第一级的状态。第一级元素的某些“权利或者特权”包括：

可以用变量命名
可以提供给过程作为参数
可以由过程作为结果返回
可以包含在数据结构中

构造数据抽象

层次数据和闭包性质

序对

(define x (cons 1 2))
(car x)
> 1
(cdr x)
> 2

序列

list

;; 创建列表
(list 1 2 3 4 5)
;; 合并列表
(append oneList twoList)
;; 获取列表的长度
(length oneList)
;; 反转列表
(reverse oneList)
;; map 对列表所有数据执行指定函数
(map funcName listName)

(list a1 a2 a3 ...)
等价于
(cons a1 (cons a2 (cons a3 (cons ...))))
;;  返回序列的第一个元素
(car listName)
;;  返回序列除第一个剩下的元素
(cdr listName)

对表的映射

map 它有一个过程参数和一个表参数，返回将这一过程应用于表中各个元素得到的结果形成的表。 null？用于检查参数是不是空表 pair? 用于检查参数是否为序对。

层次性结构

序列操作

filter 过滤一个序列，也就是选出其中满足某个给定谓词的元素。

符号数据

scheme的引号可以不闭合。

基本过程

symbol? 判断变量是不是符号
eq? 以两个符号为参数，检查它们是否为同样的符号。

抽象数据的基本表示

Huffman树

抽象数据的多重表示

对于一个数据对象也可能存在多种有有的表示方式，而且我们也可能希望所设计的系统能处理多种表示形式。例如：复数可以表示为实部和虚部（直角坐标系形式）和模和幅角（极坐标形式）。我们使用带标志的数据，操作时首先检查数据的参数标志，然后去调用处理该类型数据的适当过程。

数据导向的程序设计和可加性

检查一个数据项的类型，并据此去调用某个适当过程称为基于类型的分派

缺点：
- 每次增加一种新数据表示形式时，实现通用选择函数的人都必须修改他们的过程，而那些做独立表示的界面的人也必须修改其代码，以避免名字冲突问题。

带有通用型操作的系统

不同类型数据的组合

如果我们需要对两个或多个不同类型进行操作，我们可以如何处理？

强制

类型的层次结构

塔类型，可以将所有的数据都转换到高层。

层次结构的不足

类型不可能总是塔形的，会有各种复杂的情况。

模块化、对象和状态

赋值和局部状态

局部状态变量

我们可以使用set!这个特殊形式给变量赋值。

(set! <name> <new-value>)

可以使用begin对多个表达式顺序求值，并把最后一个表达式的值做为整个begin的返回。 (begin <exp1> <exp2> … <expx>)

引入赋值的代价

本书前部分中，不用任何赋值的程序设计，我们称为函数式程序设计。 引入赋值使我们不能再对程序使用代换模型做解释了,抛弃了引用透明性. 与函数式程序设计相对应的,广泛采用同仁的程序设计被称为命令式程序设计.

求值的环境模型

一个环境就是框架的一个序列,每个框架是包含着一些约束的表格(可能为空), 这些约束将一些变量名字关联于对应的值(在一个框架里,任何变量至多只能有一个约束). 每个框架还包含着一个指针,指向这一框架的外围环境.如果由于当前讨论的目的将相应的框架看作是全局的,那么它将没有外围环境.一个变量相对于某个特定环境的值,也就是在这一环境中,包含着该变量的第一个框架里这个变量的约束值.如果在序列中并不存在这一变量的约束,那c和我们就说这个变量在特定环境中是无约束的.

求值规则

如果要对一个组合表达式求值
1. 求什这一组合式里的各个子表达式.
2. 将去处符子表达式的值应用于去处对象子表达式的值.

局部过程

环境模型已经解释清楚了以局部过程定义作为程序模块化的有用技术中的两个关键性质:

局部过程的名字不会与包容它们的过程之外的名字互相干扰,这是因为这些局部过程名都是在该过程运行时创建的框架里约束的,而不是在全局环境里约束的.
局部过程只需将包含着它们的过程的形参作为自由变量,就可以访问该过程的实际参数.这是因为对于局部过程体的求值所在的环境是外围过程求值所在的环境的下属.

用变动数据做模拟

变动的表结构

修改序列的方法
1. set-car! (set-car! consObj obj)
2. set-cdr! (set-cdr! consObj obj)
3. append! (append! consObj1 consObj2)

共享和相等

我们可以使用eq?检查两个对象是否是同一个对象.

队列的表示

可以使用make-queue创建队列并记录它的头序对和尾序对的指针,当头指针为空那么序队为空,如果要添加元素只需要改变尾序队和尾序队对应的指针,需要删除元素只需要修改头指针为第二个序队.