SICP 笔记
第一章 构造过程抽象
- 程序设计基本元素：基本表达形式、组合的方法、抽象的方法。
（在计算模型中，全局环境的概念非常重要，它代表着计算机可以维护某种存储能力。在图灵机模型和早期大型机中都将内部存储能力作为通用型计算机的核心特点。）
一般而言，我们应将递归看作一种处理层次型结构（像树这样的结构）极强有力的技术。事实上，“值向上穿行”形式的求值形式是一类更一般计算过程的一个例子。这种计算过程称为树形积累。
环境所扮演的角色就是用于确定表达式中符号的意义。
（在形式代数中，任何符号都没有绝对的意义，它也不代表真理，它只是逻辑的信徒。在Lisp中，任何符号在环境中都有值对应，只是有些符号的值是它本身，有些是内部提供的基本过程，而有些则是用户自定义的。）语法糖衣：Lisp的语法非常简单，也就是说，对各种表达式的求值规则都可以描述为一个简单的通用规则和一组针对不同的特殊形式（例如define）的专门规则。语法的糖衣会导致分号的癌症。
（Lisp简单的语法使得它获得了强大的表达复杂语义的能力。）过程定义是一种强大的抽象技术。数学函数和计算机过程的重要差异是，计算机过程必须是有效可行的（即可以转换为递归模型）。通俗地讲，它要给出行动性的‘怎么做’的知识。
（在几乎所有的现代编程语言中，都包含过程定义的能力，或者称为函数定义。可以定义子过程使得计算机编程的抽象能力大大提高。但最早期的一些大型机，例如ENIAC，都不能调用子过程，只能顺序执行设定好的程序。而图灵在ACE的方案设计中就已经引入了子过程特性。）代换模型：正则序和应用序
（归约 是一种通用的方法论，它体现了人类的认知规律。将复杂问题规约为简单问题的组合是计算机编程的核心思维模型。）条件表达式和谓词
（条件分支的特性是计算机模拟人类智能必不可少的能力。人类的智能很大程序上体现在判断决策、自主控制、修改现有观念状态等思维方式上，条件分支可以使得计算机拥有判断决策和修改自身的能力。）过程作为黑箱抽象，使用者不需要关心过程内部的实现细节。过程所使用的形式参数是局部变量或者称为约束变量。一个过程的定义约束了它的所有形式参数。（形式参数的作用域是这个过程的体。作用域的概念在几乎所有现代编程语言中都是基础核心的概念。）
内部定义和块结构。(块结构是构造大型复杂程序的基础)
线性递归和线性迭代。（两者的区别可以看作是计算状态的保存位置不同；另外在硬件实现方式上，递归需要一种称为栈的辅助数据结构。）尾递归：对于一个使用递归过程描述的迭代计算过程，尾递归总能在常量空间中来完成它；相比而言，没有实现尾递归的编译器就只能在线性空间中完成它。有了尾递归的实现，我们可以利用常规的过程调用机制表述迭代，这会使得各种复杂的专用迭代结构（如while、for、until和do等）变成不过是一些语法糖衣了。树形递归：
（在自然界中，到处都可以看出类似递归的结构，如贝壳的纹路，树枝的形态，种子等。）高阶函数 Lambda表达式:高阶过程的重要性就在于使我们能显式地用程序设计语言的要素去描述这些抽象,使我们能像操作其他计算元素一样去操作它们。
第一级状态：
- 可以用变量命名；
- 可以提供给过程作为参数；
- 可以由过程作为参数返回；
- 可以包含在数据结构中。
Lisp给予过程完全的第一级状态。
(Lambda表达式和闭包的概念有着紧密的联系。将过程作为参数或者过程的返回值，可以获得更强大的抽象能力。)
第二章 构建数据抽象
- 复合数据的使用可以进一步提高程序的模块性。这种将程序中处理数据对象表示的部分与处理数据对象的使用部分相互隔离的技术非常具有一般性，形成了一种称为数据抽象的强有力的方法学。
- 把对于具体表示方式的依赖性限制到少数几个界面（interface）过程，不但对修改程序有帮助，同时也有助于程序的设计。因为这种做法使我们能保留考虑不同实现方式的灵活性。……数据抽象方式使我们能够推迟决策（比如系统性能方面的优化）的时间，而不会阻碍系统其他部分的工作进程。
- 闭包：用于组合数据对象的黏合剂不但能用于组合基本的数据对象,同样也可以用于复合的数据对象。另一关键思想是，复合数据对象能够成为以混合与匹配的方式组合程序模块的方便界面（interface）。（Lisp中cons的闭包性质使得它可以用优雅简单的方式构造层次型数据。另外在自然界中都可以看到类似的结构。）
（对于编译器或者解释器来说，程序语言的任何语句都可以认为是符号表达式。） - 序对的实现模糊了数据与过程的界限，也就是，这种基础数据结构的内部可以完全是过程的形式。（Lisp的过程具有第一级状态，过程体本身其实也是一种存储信息的结构，广泛地讲，任何一种过程都包含信息，而数据是信息的可存储并可访问的一种形式）。与Lisp及其序对不同，C/Pascal/Fortran/Basic这些语言都没有内部的通用型粘接剂，因此无法以统一的方式去操作复合数据。（或许C/Pascal的程序员会说，Lisp程序员是从来不考虑效率的理想主义者。）
- （丘奇计数中去除了整数一般所认为的现实意义，即单纯表示数据，而是将其抽象为一种计数的过程。）
- 序列（List）
- 对表的映射: map是一种很重要的结构，不仅因为它代表了一种公共模式，而且因为它建立了一种处理表的高层抽象。从作用上看，map帮我们建起了一层抽象屏障，将实现表变换的过程的实现，与如何提取表中元素以及组织结果的细节隔离开。
- 树：递归是处理树结构的一种很自然的工具。
- List作为一种约定的接口：（流处理、枚举器、过滤器、累加器等）将程序表示为一些针对序列的操作，这样做的价值就在于能帮助我们得到模块化的程序设计，也就是说，得到由一些比较独立的片段的组合构成的设计。通过提供一个标准部件的库，并使这些部件都有着一些能以各种灵活方式相互连接的界面（接口），将进一步推动人们去做模块化的设计。在工程设计中，模块化结构是控制复杂性的一种威力强大的策略。
- 八皇后谜题（eight-queen-puzzle）
- 分层设计:一个复杂的系统应该通过一系列的层次构造出来,为了描述这些层次,需要使用一系列的语言。构造各个层次的方式，就是设法组合起作为这一层次中部件的各种基本元素，而这样构造出来的部件又可以作为另一个层次里的基本元素。在分层设计中，每个层次上所用的语言都提供了一些基本元素、组合手段，还有对该层次中的适当细节作抽象的手段。
- 数据抽象屏障是控制复杂性的强有力工具。
- 数据导向和消息传递：消息传递设计的特点是将数据对象设想为一个实体（与面向对象的程序设计中的类class相似）
- 在大型系统中,处理好一大批相互有关的类型而同时又能保持模块性,这是非常困难的问题。（面向对象语言中的类与其相关的继承概念被用来描述不同类型的对象之间的关系，被用来建立抽象、代码重用和模块化设计。但正是这种对类型之间通用性的处理带来了面向对象语言的大部分复杂性，错综复杂的各种类之间的关系成为程序员的噩梦。或许，这种问题是无法仅仅通过计算机语言设计的方式合理处理的。）
第三章 模块化、对象和状态
- (除了抽象的手段外，我们还需要帮助我们构造起模块化的大型系统的策略。)
- 对象与流：当我们对现实世界的系统进行模拟时，我们可以采取两种策略：第一种是以对象为中心，将大型系统看作一系列对象，特别重要的时，它们的状态会随着时间而变化；另一种则是将注意力集中在流过系统的信息流上。对象策略的实现需要与时间搏斗，它需要我们抛弃老旧的代换模型，而代之更机械式、理论上更难把握的环境模型；而流方式则能够用于松懈我们的模型中对时间的模拟与计算机求值过程中的各种事件发生的顺序。
- 局部状态变量和赋值运算符：由对象组成的系统中，各对象既独立又相互作用，对象的状态是模拟现实世界中<本体>存在的重要概念。（状态必须是有限的，且从某种角度来看，对象的同一性问题就和不同年龄的人是否是同一个人的问题一样难以解答。）set!赋值运算的环境模型解释
- 赋值的利益：从rand过程（实现蒙特卡洛模拟）来看，从一个复杂计算过程中一部分的观点来看，其他部分都在随着时间变化，它们隐藏起自己的随时间变化的内部状态。通过局部状态变量模拟系统的状态，对变量的赋值模拟状态的变化。总结来看，与所有状态都必须显式地操作和传递额外参数的方式相比，通过引进赋值和将状态隐藏在局部变量中的技术，我们能够以一种更模块化的方式构造系统。（蒙特卡洛模拟的收敛效率很低）
- 赋值的代价：不用任何赋值的程序设计称为函数式程序设计。变量所代表的不再是一个简单的名字，而是索引着一个位置，而这个位置所保存的值是可以改变的。同一和变化：赋值打破了引用透明性，使得同一的问题非常复杂。命令式程序设计带来的更困难的问题是它强迫人们去考虑赋值的相对顺序，特别在并发程序中，这个问题会更加得困难。
- 环境模型：看作一系列frame连接组成的序对表。每个frame看作一系列约束的表格。
- 用变动数据作模拟：可以大大增加序对的表达能力，使得我们可以构造出序列和树之外的其他数据结构（如队列、二维表和堆）。共享和相等：set-car!和set-cdr!可以修改序对所指向的数据对象，这些数据对象可以与其他序对共享，但赋值操作利用共享所带来的危险则是隐晦和难以跟踪。
- 队列和表格
- 数字电路模拟器、约束系统
- 并发性、时间和通信：这里的基本现象是不同进程之间的同步，建立起共享状态，或迫使进程之间通信所产生的事件按照某种特定的顺序进行。从本质上看，在并发控制中，任何时间概念都必然与通信有内在的密切联系。
- 流：使用时间函数来描述对象的状态随时间的变化，而函数本身是没有变化的。时间函数可以用一个（可能无穷的）序列去模拟。流，可以被看作一个序列，但不能简单用表来实现，我们需要引进延时求值的技术。流是一种非常巧妙的想法，使我们可能利用各种序列操作，但又不会带来序列作为表去操作而引起的代价。因为流的构造和使用能够交替进行，而这种交错又是完全透明的。作为一种数据抽象，流和表完全一样，它们的不同点就在于元素的求值时间。对于常规的表，其car和cdr都是在构造时求值；而对于流，其cdr则是在选取的时候才去求值。（延时求值的技术也被现代编程语言所采用，如python）。流的实现需要cons的特殊形式，这种特殊形式与常规过程不同，它不会立即求出所有参数的值。
- 无穷流，隐式地定义流：流计算模式可以方便地解决数列、级数等问题。同时可以系统地将迭代操作过程表示为流过程。（累加型迭代就是根据初始猜测值不断迭代获得下一个猜测值，直到猜测值足够好，这个过程完全可以通过流才实现，而不使用赋值或者局部变量。）（相同的问题如果不采用流过程则难以解决，例如对无穷数列和无穷级数的操作。另外，在使用表作为通用接口时，表的传输和构造需要大量的空间，特别是当表非常大时，程序的计算效率也会大大降低，而使用流则可以根据需要生成数据，而不是一次性得到所有数据。）
- 我们可以用一个序列加速器对流做一个变换，这种加速器可以将一个逼近序列变换为另一个新序列，该新序列也收敛到与原序列同样的值，只是收敛速度更快。如果不使用流，我们也可以实现这些加速技术，但流的描述方式特别优美和方便，因为整个状态序列就像一个数据结构一样，可以通过一集统一的操作直接地随意使用。
- 将流作为信号，可以方便地开发信号处理系统。
- 函数式程序的模块化和对象的模块化：流模型可以提供等价的模块化，同时也不必使用赋值。流实现了一个具有良好定义的数学函数，其行为根本不会变化，但用户看到的却是在这里与一个改变着的状态交互。正是由于用户方的时态的存在，为这个系统赋予了状态特性。（但是，函数式程序在处理非确定性时有着本质的困难，而非确定性在处理并发方面是本质的。）
- 我们将这一世界模拟为一集相互分离的、受时间约束的、具有状态的相互交流的对象，或者可以将它模拟为单一的、无时间也无状态的统一体。每种观点都有强有力的优势，但就其自身而言，又没有一种方式能够完全令人满意。我们还在等待一个大统一的出现。
- 对象模型对世界的近似在于将其分割为独立的片段，函数式模型则不是沿着对象间的边界去做模块化。当“对象”间不共享的状态远远大于它们所共享的状态时，对象模型就特别好用。
第四章 元语言抽象
- 建立新语言是在工程设计中控制复杂性的一种威力强大的策略，我们常常能通过采用一种新语言而提升处理复杂问题的能力，因为新语言可能使我们以一种完全不同的方式，利用不同的原语，不同的组合方式和抽象方式去描述所面对的问题，而这些都是为了手头的问题而专门打造的。
- 求值器的作用：求值器的工作并不是去描述语言的基本过程，而是提供一套连接方式，提供一些组合手段和抽象手段，借助于它们将基本过程联系起来，形成一个语言：
- 帮助我们处理嵌套表达式
- 使我们可以使用变量
- 使我们可以定义复合过程、
- 提供一些特殊形式，它们的求值方式与普通过程调用不同
- 我们把求值器看作是一部非常特殊的机器，它要求以一部机器的描述作为输入。给定了一个输入后，求值器就能够规划自己的行为，模拟被描述机器的执行过程。按照这一观点，我们的求值器可看作一种通用机器。（这其中反映了可计算性的概念，即任一个求值器都可以模拟其他的求值器，或者说只要一个求值器是图灵机等价的，它就可以作为通用机。）求值器本身可以很简单，但却可以模拟比自身还要复杂的各种程序。用户程序被看作是求值器的数据。
- 图灵停机定理：给定一任意的图灵机程序P和一组任意的输入数据I，不存在单个的图灵机程序，它在有限多步后停机，并告诉我们P是否结束输入数据I的处理。
- 惰性求值: 如果在某个参数还没有完成求值之前就进入一个过程的体,我们就说这一过程相对于该参数是非严格的；如果在进入某个人过程体之前某个参数已经完成求值，我们就说该过程相对于这个参数是严格的。
- 将流作为惰性表：利用惰性求值，表和流就完全一样了，所以也就需要任何特殊形式了，也不需要区分表操作或者流操作。将cons实现为非严格的过程即可。
- 非确定计算：非确定求值器支持一种假象：时间是有分支的，而我们的程序里保存着所有可能的不同执行历史。在遇到一个死胡同时，我们总可以回到以前的某个选择点，并沿着另一个分支继续下去。实现非确定程序设计的amb思想是John McCarthy在1961年第一次提出的。（这是一种将自动搜索策略结合进程序设计的方式。）
- 逻辑谜题、自然语言分析
- 逻辑程序设计：将逻辑直接作为程序设计语言并将计算作为受控推理的一种程序设计技术。对于传统的程序设计来说，算法的逻辑意义往往被程序复杂的控制成分所掩盖，使程序的正确性难以得到证明。科瓦尔斯基对传统的算法或对用通常高级语言编写的程序提出了一个著名的分析公式，即算法=逻辑+控制。其基本思想是要从根本上改变程序设计的方法：用户只需要编写程序的逻辑部分（逻辑程序设计之名由此而来），而系统中的解释程序则实施控制部分的职能。（参看Prolog语言）