public:cs:sicp

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

  • SICP：Structure and Interpretation of Computer Programs
  • 本书使用 Lisp 方言 Scheme 来教学。ubuntu 14.04 可安装 scheme-r5rs包（不知道为何没有 mit-scheme包）, （实际安装的包名为scheme48), 使用命令scheme48开启命令行。
  • JS 版本在线阅读：SICPJS

第1章 构造过程抽象

1.1 程序设计的基本元素

  • 每一种语言提供了三种机制：
    • 基本表达形式：语言关心的最简单个体
    • 组合的方法：通过它们来从简单元素构造复合的元素
    • 抽象的方法：为复合对象命名并作为操作单元
  • 程序设计处理的两类要素：过程和数据（但并不严格区分）
  • 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.2.1 线性的递归与迭代
  • 1.2.2 树形递归
  • 1.2.3 参考算法导论对于计算资源效率的定义，算法效率
  • 分析了许多数学计算过程，不过都比较常见。详见书。

1.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 给了过程完全的第一级状态，所有有效的实现是个挑战。其它程序语言或多或少加了某些限制。（但是现代语言这几年的发展基本包括了这些性质）

第2章 构造数据抽象

  • 本章节大部分内容是关于怎么抽象数学运算，详细看书。

2.1 数据抽象导引

  • 序对： 
    (define x (cons 1 2))
 
(car x)
1
(cdr x)
2
  • 2.1.2 抽象屏障，多层次抽象，层次间为“屏障”，使用时可不用关心底层
  • 2.1.3 复合结构可用过程来表示，满足消息传递设计

2.2 层次性数据和闭包性质

  • 闭包性质：某种组合的操作得到的结果本身还可以通过同样的操作再进行组合。
  • cons 满足闭包性质；可建立起层次性的结构
  • 2.2.1 序对可构造序列， scheme 为方便提供了 list 基本操作
  • 表操作：list-ref, null?; map
  • 2.2.2 层次性结构： 序列表元素本身也是序列， 树
  • 树的 map
  • 2.2.3 模块化结构设计：序列作为程序统一的表示结构，程序的依赖性转移对序列操作的顺序组合上。
  • 嵌套映射
  • 分层设计

2.3 符号数据

  • 2.3.1 引号: 一个单引号放前表示作为数据对象看待，而不作为表达式。
  • 2.3.2 符号求导，代数表达式的表示
  • 2.3.3 集合的表示
  • 2.3.4 huffman编码树.

2.4 抽象数据的多重表示

  • 复数的表示：实虚表示，极坐标表示
  • 2.4.2 带类型标志的数据
  • 检查一个数据的类型，然后调用某个适当过程称为基于类型的分派
  • 数据导向的程序设计技术
  • 消息传递

2.5 带有通用型操作的系统

  • 这里思想类似面向对象程序设计，但是，书里注释说明，本书关心局部状态分析， 而不提“类”与“继承”，是因为现实问题是无法仅仅通过计算机语言设计的方式来合理处理的。
  • 多项式算术
  • public/cs/sicp.txt
  • 最后更改: 2023/04/21 13:22
  • 由 oakfire