计算机的程序构造和解释 SICP

构造过程抽象
1. 程序设计的基本元素
  1. 总述
    1. 基本表达形式：简单的元素
    2. 组合的方法：由简单元素组合到复合元素
    3. 抽象的方法：为复合元素命名，作为独立单元进行操作；
  2. 表达式：将表达式用括号包起来，形成了组合式，左侧是前缀的运算符，右侧是运算对象；运算符背后代表一种过程，它也是过程的一种抽象；运算对象背后代表一个值；
  3. 命名和环境
    1. 命名：获得通过名字去使用计算对象的方法，简化细节，其实这也是一种最基本的对计算过程的抽象；
    2. 环境：一种存储的能力，实现名字-值的对偶关系的追溯；用于确定表达式中各个符号所代表的意义；
  4. 组合式的求值
    1. 求值规则：
      1. 先对子表达式进行求值，其次将最左子表达式作为过程，右侧子表达式的结果做为运算对象，再次进行求值；（这个过程不断调用规则本身，本质上是一种递归的思想）
      2. 由通用规则和一些特殊形式的规则组成；而事实上，特殊形式的规则也不过是对一些通用规则的封装，更便于使用和理解，即语法糖（据说语法糖太多也不好，会增加复杂性）；
    2. 递归：一种处理层次性结构的好办法；
  5. 复合过程
    1. 对复合操作的一种抽象，用一个名字来表示这种复合的操作；
  6. 过程应用的代换模型
    1. 正则序：先展开而后归约（展开：先用表达式去替换参数，而不是先对参数进行求值；一直等到需要的时候，再去对表达式求值；如果因为某些条件判断导致一直没有需要，则此表达式不求值）（听起来像是惰性求值的样子）
    2. 应用序：先求值参数而后应用
    3. 实际上，解释器并不是通过“代换”参数的形式在工作，而是通过“局部环境”来取得相同的效果；（估计是在不同的局部环境中切换）
  7. 条件表达式和谓词
    1. (cond (
      ) ( )…( )；
      
      如果所有条件都不为真，则 cond 没有值
      
      最后一个条件可以用 else 来表示永远为真，这样最后一个总是会被执行；
    2. if 是 cond 的特殊形式，只适用于只有两个条件的情景下；
    3. and, or, not
      1. and 和 or 不是普通过程，因为它的子表达式不一定会求值，它们是一种特殊形式（或许可以理解为它们是一种复合过程，对普通过程进行了封装）；
      2. not 是普通过程；
  8. 过程作为黑箱抽象
    1. 局部名：如果一个名字，只能在它所在的那集表达式中使用，称为名字的作用域；
    2. 内部定义和块结构：一种局部环境的思想，涉及词法作用域的理念，即名字只在定义这个过程的局部环境中去寻找；
2. 过程与它们所产生的计算
  1. 总述：
    1. 看清各种不同种类的过程，会产生什么样的计算过程；
    2. 计算过程会以不同的速度消耗各种重要的计算资源（时间和空间）；
  2. 线性的递归和迭代
    1. 递归：由一个个推迟进行的操作所构造起来的链条；
    2. 迭代：可以用固定数目的状态变量进行描述的计算过程（优点：空间资源相对消耗少）；
    3. 递归计算过程和递归过程表达的是不同的意思，前者表示某个计算过程是由一个个推迟进行的操作所构成的链条，是一种计算的进展方式；后者表示某个过程定义，引用了过程本身；
    4. 尾递归：它是一个递归过程，会调用自身，但是它只在常量空间里执行迭代计算，即空间消耗没有变化；
  3. 树形递归
    1. 好处：程序容易理解和设计
    2. 坏处：可能开销很大，存在很多冗余计算（一种常用的解决方式叫动态编程，即将过程中的计算结果存储下来，每次新的计算，优先查找已存储的历史结果，如果没找到，再进行计算）
  4. 增长的阶
    1. O(n)：读 theta n，用来计算当 n 变化时，所需消耗的资源量的一个粗略估算值；
  5. 求幂
    1. 设计一个变量，让它在迭代过程中记录结果，并带入下一个迭代，从而实现尾递归，常用于设计迭代算法；
3. 用高阶函数做抽象
  1. 过程作为参数
    1. 将某种公用模式的计算过程，抽象为一个函数，此函数接受其他函数做为参数，并将其他函数的值，用已抽象好的计算过程去求值；
  2. 用 lambda 构造过程
    1. lambda 表达式可以直接作为另外一个表达式的过程前缀，跟常规的用名称来表示过程是一样的效果；即：( lambda )
    2. let 可以用来创建局部变量，使用效果上跟 define 来创建变量是一样的；let 表达式更多是做为 lambda 的语法外衣，使得代码更容易阅读和理解；
      1. ( let ( ( )
        
        ( ))
      2. )
    3. let 让我们可以在接近局部变量使用的地方创建变量，这样更进一步方便代码的阅读理解；
    4. let 定义的变量的表达式所用到的变量的值，是在 let 外面计算的；
  3. 过程作为一般性的方法
    1. 用来表述一般性的一个计算过程，与其中涉及的特定函数无关；
    2. 通过区间折半寻找方程的根
      1. 假设 f 是一个连续的函数
      2. 对于给定的 a 和 b ，存在 f(a) < 0 < f(b)
      3. 那么存在一个点 k，使得 f(k) = 0；
    3. 找出函数的不动点
      1. 如果存在 f(x) = x
      2. 则 x 称为函数 f 的不动点（将 x 做为参数代入函数 f 进行计算后，结果仍然得到 x ，所以叫做不动点？）
      3. 平均阻尼技术：取逼进一个解的一系列值的平均值的方法；常常用于不动点的搜寻场景，可以用来帮助收敛；
      4. 寻找不动点的用途，貌似这种技术可以做为一些函数的解法，比如求平方根，求立方根，它内在的本质，貌似也可以算是一种收敛性的猜测，即给出一个猜测值，然后根据结果缩小猜测范围的猜测下一个值，为避免出现例外情况，此处引入平均阻尼的方法（如果没有引入平均阻尼的方法，不动点技术不一定在空间上有太多优势，因为有可能它收敛的很慢，甚至振荡而不收敛，当然，貌似它也可能收敛的很快，但目测再快也没有平均阻尼快了；又想了想，好像也不一定）；
      5. 不动点技术是一种有趣有用的好技术，但不是所有的函数都存在不动点；如果一个函数没有不动点，则这个技术就不适用了；
  4. 过程作为返回值
    1. 当一个过程，需要以函数作为参数时；此时另外一个过程，其返回值是一个函数，那么这两个过程就可以进行组合了；
    2. 牛顿法：这又是一个神奇的方法，通过使用函数的导数，进行不动点的迭代，求得方程的根；
    3. 抽象和第一级过程
      1. 第一级元素的特权
        
        可以用变量命名；
        
        可以提供给过程作为参数；
        
        可以由过程作为结果返回；
        
        可以包含在数据结构中；
      2. scheme 给了过程第一级元素的状态，这使得 scheme 获得了强有力的描述能力；它的代价是，需要为过程中的自由变量保留空间，即使这一过程并不执行；这些变量被存储在过程的环境里；(说明过程是提前被存储起来的，猜测就像变量一样存储在内存常量区？答：是的，所有过程本质是都是一系列指令的集合，当它们被编译器转成机器指令时，需要占用内存空间，但根据条件不同，有时候不一定会跳转到该段位置执行指令）
构造数据抽象
1. 数据抽象导引
  1. 本质：将数据的构造细节和使用方式进行分离；
  2. 好处：可以在程序中建立起抽象屏障，将“使用”数据对象的程序（上层）与“实现”数据对象的程序（下层）分开来；
    1. 示例，有理数的表示
      1. (define (make-rat n d)
        
        (cons n d)) \此处通过序对来表示有理数
      2. (define (numer x)
        
        (car x)) \基于上面序对的表示方式，定义了取得分子的过程；
      3. (define (denom x)
        
        (cdr x)) \定义了取得分母的过程；
    2. 在有了上面三项之后，未来如果想要更改序对的表示方式，只要同时更新分子和分母的获取实现过程即可，但不改变 make-rat、numer、denom 的名称，这样就可以使得那些基于这三个名称构建出来的程序，完全不必修改，仍然可以正常工作；
  3. 思想：
    1. 构造出一些使用复合数据对象的程序，而不是基本数据对象，这样程序像是在“抽象数据”上操作一样；好处是建立了抽象屏障，底层数据构造细节的变化，不变影响到上层的程序；数据是如何构造出来的，跟数据是如何使用的无关（此处让我想起了面向对象编程中的对外暴露的方法，即访问一个对象的数据，是通过该对象的方法来获得，而不是直接访问对象的属性本身，这样其实也是实现了一种抽象和隔离，让未来对象数据结构的变化，带来的影响减至最小）；
    2. 为每一类数据对象标识出一组基本操作，使得针对这些数据对象的所有操作，都可以由这些基本操作来组成，并且也只用这些基本操作组成；
  4. 构造函数：用来构造数据对象；
  5. 选择函数：用来访问数据对象；
  6. 数据：由一组适当的构造函数和选择函数组成，以及它们必须满足的一组特定条件（以便使构造和选择过程可以成为合法的表示）（思考：貌似面向对象的思想，就是一种数据抽象封装的方式）（由此想到，对于对象的数据的访问方式，应该通过定义好的方法，而不应该通过对象的属性进行直接访问，因为这样缺少隔离的屏障，甚至不小心修改了对象的属性，很危险）
  7. 从序对构造起来的数据对象称为表结构数据（为什么叫做表结构数据呢？）
  8. 区间算术：由于区间表示的数本身具备一定的不确定性，即缺少唯一性的问题，所以，区间算术的运算，根据运算形式的不同，结果有可能不同；在一次运算过程中，不确定性变量出现的次数越多，最后结果所包含的不确定性就会越大。因此，如果能够通过算术变换，尽量减少不确定性变量的使用次数，那么结果会更加收敛；
2. 层次性数据和闭包特性
  1. 闭包是指通过某个过程组合起来的数据对象结果，仍然可以使用相同的过程再进行组合；在代数术语中，它的意思是某个集合里面的元素，经过计算后，得到的结果，仍然属于这个集合；
  2. 序列：
    1. 定义：一批数据对象的一种有序组合；
    2. 实现的方式有很多种，通过嵌套的序对来实现是其中的一种方法；
    3. 通过嵌套的 cons 来实现的序列，称为一个表；它还可以使用关键字 list 来创建，这样写起来更方便一些；（list 是链表结构，其他还有数组结构，链表结构的优点是可以用O(1)实现更新和删除，但查找需要O(n)；而数组的方式，优点是查找只需要O(1)，但更新和删除是O(n)（如果使用哈希表呢？是否更新、删除、查找都是O(1)？）；
  3. 表：
    1. car 可以用来在表的前面增加一个元素，但不能用来在表后面增加元素；可以用 append 在表的后面增加元素，不过貌似要自己定义这个函数，没有内置；（注：append 是O(n)的成本）
    2. nil 可以用来表示序列链的结束，也可以用来表示一个空表；
  4. null? 它是 scheme 自带的一个函数，用来判断一个表是否为空表；
  5. 层次性结构：树，表中又包含表；
  6. 表的映射：(define (map proc items) … )，用 car 逐项处理 items，并用 cons 将处理结果和剩下的 cdr items 递归处理结果进行连接；（这玩意儿看上去就是一个迭代的过程，好比 js 或 python 里面的 map 函数，简直一样样的）；
  7. 树的映射
    1. 方式一：分支判断，递归左分支和右分支；用 cons 连接递归结果；
    2. 方式二：(map lambda tree)，其实跟上面本质相同，只是将 cons 和递归抽象在 map 中，将处理抽象在 lambda 中
  8. 使用约定的接口
    1. 定义一些标准的部件库，这些部件定义约定的接口，以便部件之间能够相互灵活的连接，组合出更模块化的程序；
      1. 示例：例如枚举，映射，过滤，累加等几个函数，通过它们的组合，达到模块化的效果；
    2. 将程序操作转换为对序列的操作，然后只需依赖几个为数不多的序列，就可以实现复杂的操作效果；
    3. 嵌套映射：(define (flatmap proc seq)) ，用 map 做映射，然后用 append 对结果进行累积；
3. 符号数据
  1. eq? 用于判断两个符号是否相同；
  2. memq 判断某个符号是否在某个表中，如果不在，返回假；如果在，返回这个符号首次出现的位置余下的表；
  3. equal? 用于判断两个表是否相同；
  4. number? 用于判断某个变量是否为数字；
  5. symbol? 用于判断某个变量是否为符号；
  6. 代数表达式的表示：用符号组成的表来表示，并定义出加减乘除的方法，这样就可以在这个基础上进行符号计算了；
  7. element-of-set？用于判断给定元素是否为某个给定集合的成员；
  8. 集合的表示
    1. 集合为未排序的表：O(n^2)；
    2. 集合为已排序的表：O(n)
    3. 集合作为二叉树：O(log n)
  9. 集合与信息检索
    1. 定长编码：比较浪费空间；
    2. 变长编码：利用相对频度，改变符号在树中的位置，可以明显节约空间；
      1. Huffman 编码树
        
        原则：最低频度的符号出现在离树根最远的地方；
        
        算法：找出最低频度的两个符号，生成一个新节点，加入原集合中，去掉这两个符号；重复这个过程，直到处理完所有的符号；
        
        表示：
        
        叶子：(define ‘leaf symbol weight)
        
        节点：(list left right symbols weight)
4. 抽象数据的多重表示
  1. 显式分派风格
    1. 使用带标志的数据；选择函数首先检查参数的标志，然后对应寻找到处理这类数据的过程；
      1. (define (real-part z)
        
        (cond ((rectangular? z)
        1. (real-part-rectangular (contents z))
        
        ((polar? z)
        
        (real-part-polar (contents z)))
  2. 数据导向风格
    1. 将数据的不同表示方式和操作，加上标志，独立出来组成一个表格，形成一个包；当需要使用的时候，传入标志参数进行调用；
    2. 好处：
      1. 如果未来有新的方式，只需要在表格中进行注册即可；其他地方都可以不用更改；
      2. 表格中注册的每种方式，由于是各个标志进行内部的命名，作用域方面也不会存在冲突；这样可以最大程度的整合不同人员的不同表示方式；
  3. 消息传递风格
    1. 将数据对象做为一个实体，以消息的方式接收到所需操作的名字
      1. (define (make-from-real-imag x y)
        
        (define (dispatch op)
        
        (cond ((eq? op ‘real-part) x)
        
        ……(略)
        
        dispatch)))
5. 带有通用型操作的系统
  1. 通过数据导向的设计，将不同类型的操作放进包中；
  2. 包中的过程，可以引用已有的包，在其基础上进一步抽象，让它变得更加通用；
模块化、对象和状态
1. 面向对象是一种设计策略，目的在于让程序更加健壮，易于拓展；相对于函数式的代换模型，它引入了环境模型，更加机械化，理论上更不容易把握，因为我们需要与时间做搏斗；流模型可以解决与时间的冲突，它通过延迟求值的方式实现；
2. 赋值和局部状态
  1. 为了模拟真实系统里面的实际对象，我们需要使用局部状态变量，来描述对象的状态；由于实际对象的状态会随着时间而变化，因此我们又需要引入赋值，来改变这个状态变量；
  2. 引进赋值的收益：引进赋值，可以让我们将对象的状态隐藏在内部，避免对外显示的操作和传递，这样可以减轻我们的负担，使我们更容易模块化的构造系统；
  3. 引进赋值的代价：由于时间和状态的存在，同一个东西在不同的时间不再可以相互替换，因为它们导致的结果可能不同，因此我们也将失去引用的透明性；这将使对使用赋值的程序做推理变得非常困难；（我们失去了同一性，不再能两次踏进同一条河流）
  4. 引进赋值的缺陷：由于状态的存在，迫使我们不得不考虑赋值的相对顺序，以确保变量在引用的时候，是最新正确的版本；当程序需要应对并发的时候，这个情况将会变得很糟糕；
3. 求值的环境模型
  1. 什么是环境？环境是框架的一个序列；
    1. 序列是被排成一列的对象，每个元素不是在其他元素之前，就是在其他元素之后，元素之间的顺序很重要；
    2. 框架是包含着一些约束的表格；约束将变量关联于某个对应的值；每个框架还包含着一个指针，它指向这个框架对应的外部环境；
  2. 一个表达式的意义依赖于它所在的环境，因为这个环境提供了解释这个表达式意义的上下文；
  3. 环境模型中，过程的应用和定义使用以下两条规则：
    1. 相对于某个给定环境，求值一个 lambda 表达式，将创建一个过程对象，这个过程对象是一个序对，由两部分组成，一部分是 lambda 表达式的正式，一部分是指向环境的指针，指向创建这个过程对象的环境；
    2. 将一个过程对象应用于一组实际参数时，它将构造出一个新框架，在这个新框架中，过程原来的形式参数，将约束于实际参数，然后在构造起来的这个新环境里面，求值过程体；这个新环境的外围环境，指向定义过程对象的那个环境（这里很重要，它不是指向调用它的那个环境，而是创建它的环境）；
  4. 当在当前环境找（假设为C）不到变量的约束时，将会去当前环境指向的外围环境（假设为B）进行查找，如果还是找不到，将会一路往上，直到全局环境（假设为A），如果仍然没有找到，则会报错提示；特别地再次提醒，一旦找到（假设在A找到），并且变量的约束关联的值，是一个过程对象，那么这个过程对象所创建的新环境，其外围环境是指向定义这个过程对象的环境（即A，而不是B）；
  5. 内部定义的特质
    1. 内部定义会创建一个局部环境，局部过程对象存在于这个环境中，它们不会与外围环境的同名过程对象发生命令冲突；
    2. 对局部过程对象的调用，会构建一个新的子环境，在这个子环境中，可以访问母环境的实际参数，因为实际参数的值被约束在母环境的形式参数中；虽然在局部子环境不能找到要使用的变量的约束，但向上一级的母环境中查找，就可以找到了；
4. 用变动数据做模拟
  1. 如果一个数据对象定义了变动数据的操作，称之为变动数据对象；（如果我们不马上求值，我们就不需要马上对求值结果进行保存，从而使得暂时不需要赋值和数据变动，莫非这就是延迟求值技术的核心理念所在？）
  2. 变动的表结构（表此处即 list，可以通过 cons 来构造）
    1. 共享和相等：在 scheme 里面，对应每个名字的符号是唯一的，scheme 不提供改变符号的方式；而不同序对的实现，是通过构造新序对，然后通过指针指向所需要的符号来实现的；这种实现方式，不可避免的会造成两个不同的序对，共享相同的符号；
      1. 好处：scheme 可以通过判断指针是否相等来实现 eq？
      2. 坏处：指针的指向有可能造成循环；
    2. 改变即赋值：赋值与变动具有相等的地位，因为可以将环境也看做一种数据结构。从理论上说，为了表示变动数据的行为，所需要的全部东西，只是赋值就够了，即只要将赋值纳入语言即可实现；
  3. 队列的表示
    1. 由于通过 cons 构造的表，节点之间已经通过指针形成了链接，意思是当知道了头，就可以顺藤摸瓜找到尾，因此通过一个新序对，将它分别指向链表的头和尾，就可以构造出队列，即(cons front-ptr rear-ptr)
    2. 双端队列的表示：通过 (cons (cons item prev) next) 双层结构来构建（思考：如果有更复杂的要求，或许可以考虑使用3层、4层或更多层的结构来实现？）；
  4. 表格的表示
    1. 一维表格：通过双层结构的序对实现
    2. 二维表格：通过两个关键码+子表格实现（基于一维表格的双层结构）；
    3. 多维表格
错误集
1. define 既可以用来定义函数，也可以用来赋值，语法为： (define var value)，这里 value 可以是一个值，也可以是一个表达式；
2. 当需要返回一个过程时，函数体里面使用的是 lambda 来定义这个过程，如果没有使用 lambda 就不会返回过程，而变成返回数值了；
3. (define (cons x y)
  1. (define (dispatch m)
    1. …)
  2. dispatch) ;注意此处返回了一个过程；当定义一个函数，需要返回一个过程时，可以使用这种方式；
4. let 定义的变量只能在 let 的 body 内使用，无法让跟 let 平级的其他函数使用；但使用 define 定义的变量，可以被和它平级的内部环境的函数使用；
5. 在递归调用的时候，如果想要实现赋值，需要在 let 定义变量后，再使用内部定义新函数，建立起一个局部环境，在这个局部环境中，可以访问 let 定义的变量，并对其进行赋值，从而记录状态，而不能直接调用全局环境的父函数来实现递归，因为那样会导致另外重新构建另外一个新环境，得到另外一个平行的 temp，这样局部环境的赋值就失效了；正确的做法应该是在父函数建立起来的环境内部，创建局部环境实现递归；
6. cons 函数会返回一个新序对，不会改变老序对；如果需要赋值，需要通过 set! 来实现；

计算机

#编程

计算机的程序构造和解释 SICP

https://ccw1078.github.io/2017/10/22/计算机的程序构造和解释 SICP/

作者

ccw

发布于

2017年10月22日

许可协议

js多重继承上一篇

jQuery 下一篇