SICP - jwyx/ForFun GitHub Wiki

scheme-r5rs

atoms & lists
experimental character & its emphasis on symbol manipulation
最重要的特征：
  Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data
Every powerful language has three mechanisms for accomplishing this:
  primitive expressions, which represent the simplest entities the language is concerned with,
  means of combination, by which compound elements are built from simpler ones, and
  means of abstraction, by which compound elements can be named and manipulated as units.
In programming, we deal with two kinds of elements: procedures and data.

牛顿迭代法：如果对x的平方根有一个猜测y，那么通过一个简单猜测去求得一个更好的猜测：y和x/y的平均值（更接近于实际的平方根）。

orders of growth

以过程为参数，或者以过程作为返回值，这类能操作过程的过程称为高阶过程。

找平方根和找不动点都是通过不断改进猜测，直到结果满足某一评价标准为止。
控制不收敛问题：不让有关猜测变化太剧烈。'平均阻尼'技术，不动点搜寻中作为帮助收敛的手段。

程序设计语言总会对计算元素的可能使用方式强加上某些限制。带有最小限制的元素倍称为具有第一级的状态。第一级元素的某些"权利或者特权"包括：
- 可以用变量命名
- 可以提供给过程作为参数
- 可以由过程作为结果返回
- 可以包含在数据结构中

Lisp不像其他程序设计语言，它给了过程完全的第一级状态

将数据对象组合起来，形成复合数据(compound data)的方式
为什么需要复合数据？
- 提升程序设计所位于的概念层次
- 提高设计的模块性
- 增强语言的表达能力

将程序中处理数据对象的表示部分，与处理数据对象的使用的部分相互隔离的技术非常具有一般性，形成了数据抽象的设计方法学。

闭包(closure)
混合和匹配(mix-and-match)
符号表达式(symbolic expressions)
通用型操作(generic operations)
数据导向的程序设计(data-directed programming)

数据抽象的基本思想，就是设法构造出一些使用复合数据对象的程序，使它们就像是在"抽象数据"上操作一样。
程序中使用数据的方式应该是这样的，除了完成当前工作所必要的东西之外，它们不对所用数据做任何多余的假设。
与此同时，一种"具体"数据表示的定义，也应该与程序中使用数据的方式无关。
在我们的系统中，这样两个部分之间的界面将是一组过程，称为 选择函数 和 构造函数。

wishful thinking: 先定义 选择函数 和 构造函数，然后基于此实现需要的操作，然后再考虑如何具体构建复合数据

序对(pairs)
The single compound-data primitive pair, implemented by the procedures cons, car, and cdr, is the only glue we need.
Data objects constructed from pairs are called list-structured data.

抽像屏障(abstraction barriers)

每一层次中的过程构成了所定义的抽象屏障的接口，联系起系统中的不同层次。
procedures at each level are the interfaces that define the abstraction barriers and connect the different levels.

将过程作为对象去操作，自动地提供了一种表示复合数据的能力。
实际上，数据的过程性表示将在我们的程序设计宝库里扮演一种核心角色。
有关程序设计风格通常称为 消息传递。

盒子和指针表示方式(box-and-pointer notation)

我们可以建立元素本身也是序对的序对，这就是表结构得以作为表示工具的根本基础。
我们将这种能力称为cons的闭包性质。一般说，某种组合数据对象的操作满足闭包性质，那就说，通过它组合起数据对象得到的结果本身还可以通过同样的操作再进行组合。

术语“闭包”来自于抽象代数，元素称为在某个运算之下封闭，如果将该运算应用于这一集合中的元素，产生出的仍然是该集合里的元素。
但是在Lisp中，闭包被应用于另外一个概念，表示带有自由变量的过程而用的实现技术。

闭包性质是任何一种组合功能的威力的关键要素，因为它使我们能够建立起层次性的结构。

序列 (list <a1> <a2> ... <an>)
     (cons <a1> (cons <a2> (cons ... (cons <an> nil) ... )))

car表示值，cdr指向下一个元素

表(list)表示那些有表尾结束标记的序对的链。
表结构(list structure)表示所有的由序对构造起来的数据结构，而不仅是表。

(car list-name): 选取第一个元素的值
(cdr list-name): 跳转到第二个元素
(cons 10 list-name): 将10加入到list-name的头部
"'()"/nil: 用语表示序对的链结束，也可作为空表
(cadr <arg>) = (car (cdr <arg>))


对表的映射: 将某种变换应用于一个表的所有元素，得到所有结果构成的表。

Scheme标准提供一个map过程，它比这里描述的过程更具一般性。
这个更一般的map以一个取n个参数的过程和n个表为参数，将这个过程应用于它们的第二个元素，如此下去，最后返回所有结果的表。

map帮我们建立起一层抽象屏障，将实现表换的过程的实现，与如何提取表中元素以及组合结果的细节隔离开。