201510 SICP系列 第1讲 课程介绍 学习笔记 - xiaoxianfaye/Learning GitHub Wiki
- 0 Preface
- 1 Courses Overview
- 2 Techniques for Controlling Complexity
- 3 Programming Exercises (SQRT)
- 4 Procedures & Processes: Substitution Model
- 5 Iteration & Recursion
- 6 Summary
这一讲的主要内容有：计算机科学、过程(Process & Procedure)和替换模型、控制软件复杂度的技术、迭代与递归，并穿插了几个编程练习。
上图是《SICP》这本书的封面。中间的符号是"λ"，《SICP》是MIT大学的课程，这个课程的前导课就是《λ演算体系》的课程，这里的"λ"就是Alonzo Church的λ演算体系，整个《SICP》这本书中所有的设计思想都是基于Alonzo Church的λ演算体系(函数式编程)。巫师手中拿的水晶球上画了"Eval"和"Apply"，"求值"和"应用"是LISP程序的求值器的两个互相规约的过程，你中有我，我中有你。这本书是一本教授"魔法"的书。
这本书的作者是Harold Abelson、Gerald Jay Sussman、Julie Sussman。前面两位都是MIT的教授，第三位是一个独立撰稿人、类似于技术专家。
计算机内部是如何工作的？它为什么这样工作？是谁把它设计成这样子？我们平常编写的程序让计算机执行起来，为什么有时候结果符合预期，而有的时候结果是"烫烫烫…"？
- Not About Science
- Not About Computer
- Geometry not really about measuring devices, but rather about declarative knowledge
- CS is actually about the kind of knowledge that computer makes available to us
"Computer Science (计算机科学)"这个词我们很熟悉，但这个提法容易引起误导。
首先，"Computer Science"不是一门科学。为什么呢？想一下我们编程的过程。我们有一个问题(Problem)，思考(Thinking)以后，得到一个解决方案(Solution)，但这个过程无法形式化和自动化。如果我们能够做到把这个问题直接描述给计算机(Computer)、让计算机帮助我们得到解决方案的话，并且把这个过程形式化、自动化，只有这样才可能称为科学。从这个角度来说，我们现在没有办法做到：对着计算机说些什么、描述些什么，它就自动地帮我们生成解决方案，所以"编程"这个工作本身并不能称之为"科学"。
当然，在某些特定领域，参与的人非常了解这个领域，所以他们能够针对这些特定领域写出一些Domain Spec，经过较为复杂的Interpreter(解释器)，最终生成Solution(解决方案)。这其实也是我们追求的目标。但这样的一种解决方式并不具有普适性，也不是所有领域都能这样去做，而且不同的人、不同的经验、不同的技能所产生的解决方案千差万别。
其次，"Computer Science"和计算机也没有关系。就像当我们谈到物理学，我们不能说物理学就是粒子加速器、反应堆；当我们谈到生物学，我们不能说生物学就是显微镜和培养皿；当我们谈到几何学，我们不能说几何学就是圆规、尺子等这样一些工具。
"Geometry"和"Computer Science"这两个词在误导性上有一定的相通性。先来看一下"Geometry"这个单词：
我们提到"Geometry"的时候，会马上想到圆规、尺子等测量测绘仪器或者工具。为什么会有这种说法呢？"Geometry"这个词最早起源于人类文明的发源地古埃及，古埃及靠近尼罗河流域，尼罗河每年都会发生洪水泛滥，古埃及人需要精确地知道洪水何时到来、何时退去，洪水到来时到达的田地边界，所以古埃及人发明了利用太阳的参照体系和天王星的参照体系一起来对时间做一个日历的估算，并发明了一些测绘工具，能够对田地进行一些测绘。这些就是我们说的一些测绘工具。
为什么说"Computer Science"和"Geometry"有同样的误导意义呢？认为"Geometry"描述的是测绘工具，而"Computer Science"描述的是计算机。计算机最早开始是为了去解决一些复杂的数值运算。在我们做很多事情之初，我们往往会混淆做这件事情的本质和做这件事情所使用的工具。
就像几千年前古埃及人不知道他们自己做的到底是一件什么样的事情，以为自己就是拿着一些测绘工具看看太阳、看看星星，然后知道洪水明天来或不来。也像几十年前我们的前辈们摆弄那些计算机的小的部件去做那些复杂的数值运算的时候，他们其实也并不清楚他们做的是一件什么样的事情。很多事情的本质，是在这件事情不断地在做、随着时间的发展、随着我们对问题的不断深入，需要回过头再来去看的这样一件事情。
"Geometry(几何学)"形式化了时间跟空间的概念，最重要的是它形式化了在数学意义上"是什么"、什么是"真"，并提供了一个精确的描述方法或者说提供了一个精确的框架去描述声明性的知识(declarative knowledge)。
几何学是形式化了数学意义上什么是"真"这样一个概念。由于工具的出现，几何学是那些通过工具得以被具象化、得以被我们能够去了解清楚、并且能够为我们所用的知识。同理，由于计算机的出现，计算机科学是那些通过计算机得以被具象化、得以被我们能够去了解清楚、并且能够为我们所用的知识。
- How to formalize intuitions about process
- How to do things
- Developing a way to talk precisely about how to knowledge – Imperative Knowledge
那么，计算机科学到底是什么呢？计算机科学形式化了我们头脑中对process这样一个词的概念。什么叫process？计算机如何去做、如何去执行、如何完成要做的事情(How to do things)。
Geometry是"什么是真、是什么"，而Computer是"How to do、怎么去做"。前面的方法是能够精确地描述声明性的知识(Declarative Knowledge)，这里的方法是能够精确地描述命令性的知识(Imperative Knowledge)。
What is true "knowledge"?
提供了"是什么"的定义。例如，什么是x的平方根？有一个数y，y的平方等于x且y大于等于0，就说明y是x的平方根。
这个定义没有提供任何方法或步骤告诉我们怎么才能找到这样一个数，这个数恰巧就是x的平方根。这就是声明性的知识。
"How to" Knowledge
Imperative Knowledge是描述如何做、怎么做、一些具体的步骤。
To find an approximation of square root of x.
- Make a guess G
- Improve the guess by averaging G and x/G
- Keep improving the guess until it is good enough
牛顿法求平方根。可以看到，前面的"Declarative Knowledge"只可能是给定一个数，我能判断这个数是不是x的平方根，但是无法知道如何求解出x的平方根。这里的步骤告诉了我如何做可以求解出x的平方根，这就是"Imperative Knowledge"。
Why "how to knowledge"
- A series of steps to be followed to deduce a particular value
- A recipe
- Call this a procedure
- Actual evolution of steps inside machine for a particular version of the problem – called a process
计算机科学是精确地描述"How to"、命令性的知识。process是存在于计算机里面、看不见摸不着但又实实在在存在着的东西。因为它能帮助我们完成我们想要完成的事情，就像计算机里面有一群小精灵，我写了程序让小精灵去做，小精灵就帮我做了，但它们怎么做的我目前还不清楚，但我知道怎样去指挥那些小精灵。我指挥这些小精灵的是一些按一定模式组织起来的规则，这些规则叫做procedure。
因为process和procedure翻译成中文都叫"过程"，所以再强调一下。process是在计算机中、由小精灵帮助我完成的一些事情。我要用按一定模式组织起来的规则(procedure)来指挥这些小精灵完成我想要做的事情。procedure就像巫师下的咒语或魔法，在procedure中描述了我们对于计算机中的那个process的期望。process虽然看不见摸不着，但它是计算机中的一个计算的过程或机器执行的步骤。procedure是对"How to Knowledge"如何进行的一个描述性的步骤，在我们这个课程里，可以认为是λ的函数过程。
procedure是我们要施行的魔法，process是魔法起效后在计算机里做的那个过程。procedure是函数过程，process是机器中的计算过程。procedure是描述性的步骤，process是真正在去做的执行性的步骤。
"How to"是一步一步地，按照每一步来做就能得到最终想要的那个特定的结果，就像菜谱(recipe)一样。
- Need a language to describing process
- Vocabulary
- Rules for writing compound expression – syntax
- Rules for assigning meaning to constructs – semantics
- Rules for capturing process of evaluation – procedures
用一定形式组织起来的规则procedure去描述我们对process的期望，去指挥小精灵工作，所以需要一个程序语言来帮助我们把这些规则写出来，去描述我们对process的期望。
程序语言要包括：
- 首先，要有一些基本的"词汇(Vocabulary)"。这些词汇描述出一些基本的、简单的"How to"knowledge，简单的一些过程、内置的一些东西。
- 只描述一些简单的"How to"，威力还不够大，希望能够描述一些更加复杂的"How to"。所以希望会有一些规则，这些规则能够把一些简单的表达式、简单的"How to"规则有机地组合起来，去描述一些更加复杂的复合表达式。这就是"语法(Syntax)"。
- 有了"语法(Syntax)"以后，我们需要给程序语言中的一些特定的构造赋予一定的语义。语法组织起来还不够，到底是什么样的语义呢，这样的语法代表什么样的一个事情呢，所以还要有一些规则对这些语法构造给予一定的含义。这就是"语义(Semantics)"。
- 最后我们还需要有一些规则能够捕获或者描述出我们对process的执行步骤、求值过程的每个规则的描述。这就是"函数过程(Procedure)"。
《SICP》书中选择了Scheme语言，Scheme是Lisp语言的方言之一。"Lisp"的意思是"表处理(List Processor)"。Lisp是20世纪60年代由John McCarthy设计的，最早是用来做符号运算的，正因为如此，在Lisp语言中有当时比较新的两个数据结构：原子和表。Scheme语言是MIT为了教学由Harold Abelson在1975年设计出来的。
Lisp语言的语法规则简单、一致，只有很少的特殊规则，但却能有无穷的变换。而且Lisp语言中有着非常强大的一点：我们通常会说传统意义上过程(函数过程)是主动的、数据是被动的，但在Lisp语言中，过程就是数据，可以把过程当作数据一样来进行操作。这使得Lisp语言的元编程能力非常强大。正是由于这个特性，很多强大的语言设计技术正是因为模糊了过程和数据的界限催生出来的。
在我们的课程里，我们会使用Erlang语言。Erlang和Scheme语言有一些相通之处，它们都是符号化的语言，元编程能力都非常强，够柔软。好的语言有这样一个特性：每个人都会觉得这个语言就是为我量身打造的。
但要注意的是，虽然语言简单、规则简单，但要理解规则背后的深意，并且要能够巧妙地运用这个深意，是自己成为一个好的程序员、master，这是一个非常难的过程。
- The key of CS
- Techniques of control complexity
- Complexity of Physics System
- Computer science is like an abstract form of engineering
我们研究计算机科学，就是希望能够用计算机为我们现实世界中那些非常大的、超大规模的系统建模，帮助我们完成我们想让它去做的事情。但要知道，当系统特别大的时候，有没有一个人能够把所有代码都放在头脑中，并且还能在头脑中非常清楚地知道整个系统运行起来的动态视图和静态视图，整个流程是否还能够想得清楚？没有人能做到。如果我们做不到的话，又怎么去指挥计算机中的小精灵，让它们正确地为我们做事情呢？答案就在于计算机科学里有很多技术，这些技术能够帮助我们控制构建大型软件系统的复杂性。这个课程也会教授控制大型系统复杂性的这些技术。
控制复杂性在现实世界中无处不在，桥梁、轮船、火箭、电子线路等，为什么要专门成立一个计算机科学这样一个学科来控制复杂性呢？
- 桥梁、轮船、火箭、电子线路等这些都是真实的物理系统。这些物理系统的复杂性来自于自然规律的约束，这些约束都是实实在在存在的，可以预见、可以列举出来的。
- 而在软件系统中则不是这样的。在软件系统中，我们要处理的领域的复杂性、多样性和可能性远远超过现实中实实在在存在的物理系统。
- 如果说物理系统中存在的那些约束来自于自然规律的约束的话，那么在软件系统中，构建大型软件系统的约束来自于程序员，受限于程序员的思维。因为在软件系统中，在软件世界中，在计算机的世界中，你所能想到的跟你实际能构建出来的，没有任何差别。你面对的都是理想化的组件，不受任何自然规律约束。
不管你的梦想有多大，你的思想都要能hold住。——孙鸣
计算机科学不是科学，更像是工程，更像是艺术，要有一点点魔法，才能去做。计算机科学是抽象化形式的工程，不受物理界自然规律的约束。
控制大型软件系统复杂性的技术包括三大部分内容：黑盒抽象、通用接口和Eval&Apply。这里先做一个简单的介绍。
黑盒抽象并不是由于计算机科学出现才有的，在很多其他领域中都有黑盒抽象。它的本意是能够隐藏实现细节、并能够用来构建更大、更复杂的函数过程和更大的盒子。
不管怎么求平方根，这里有一个求平方根的"SQRT"函数，把实现封在里面，每个人都能用。不针对特定数，把实现放在一个黑盒里，输入x，输出x的平方根，本身就是对这个求解过程的一个抽象。
隐藏了实现细节，就能构建出更大的、更复杂的过程、更大的盒子。比如现在有了SQRT，给定直角三角形两个直边的长度，用SQRT和勾股定理来算一下斜边的长度。
SQUARE和SQRT这些盒子的存在都是为了能方便构建出更有复杂意义上的"How to"。这些盒子隐藏了细节，谁都可以来用它们。
还有另外一种情况，也是一种黑盒抽象。
在计算机科学中，我们想要去描述一些"How to"Knowledge。当我们描述一项"How to"的时候，我们发现这项"How to"是另外一项"How to"的特例的时候，我们希望在语言或工具中把这个知识描述出来。
Imperative Knowledge "How to"
To find an approximation of square root of x.
- Make a guess G
- Improve the guess by averaging G and x/G
- Keep improving the guess until it is good enough
这是求平方根的"How to"。
Method for Finding a Fixed Point of a Function F (That is, A value Y such that F(Y)=Y)
- Start with a guess for Y
- Keep Apply F over and over until the result doesn’t change very much
Example: To compute
这是求函数不动点的"How to"。函数不动点是指：函数F，给定一个输入Y，如果F(Y)的返回值还是Y的话，称Y是函数F的不动点。
思考一下求函数不动点的"How to"和求平方根的"How to"区别在哪里？
都是第一步先给定一个猜测，第二步是改进这个猜测，然后是不断地改进猜测直到满足条件。求解平方根的"How to"是求解函数不动点的"How to"的特例。
求解函数不动点，输入是一个函数F，输出是能够求解出函数F不动点的另外一个函数过程。求解平方根的"How to"是求解函数不动点的"How to"的特例，输入是"avg(Y, X/Y)"，输出就是SQRT。
可以看到，SQRT是一个"How to"的函数过程，"Fixed Point"也是一个"How to"的函数过程，这两个函数过程的联系是通过另外一个"avg(Y, X/Y)"函数过程。
SQRT虽然很小，但它也是一个抽象，给定一个值，返回另一个值。"Fixed Point"是给定一个函数过程(Procedure)，返回另外一个函数过程(Procedure)。
可用黑盒抽象来表达一个"How to"是另一个"How to"的特例。
- Primitive Objects
- primitive procedures
- primitive data
- Means of Combination
- procedure combination
- construction of compound data
- Means of Abstraction
- procedure definition
- simple data abstraction
- Capture Common Patterns
- high order procedures
- data as procedures
上面是课程里会讲的与黑盒抽象相关的内容。
原生对象包括原生函数过程和原生数据。是否觉得原生对象出现在黑盒抽象这里很奇怪？我们平常看到的、用到的那些数据真的就是数据吗？其实它们也是抽象，你不知道里面的实现细节，比如Number 1就是1吗？1其实只是一个符号，它代表数字，但1在计算机里面到底是什么。原生对象一般都是由编程语言来提供的，这些符号化的、代表的这些值的意思，其实是一个黑盒抽象把它描述出来。当我们写"1"的时候，写的是符号，想在程序中指示的是它的含义。
光有这些原生对象还不够，在描述一些更加复杂的东西的时候，我们希望有一些组合的手段，包括函数过程的组合、复合数据的组合。函数过程的组合是为了能够去描述更加复杂的"How to"。会有些复合数据的组合，是因为我们对现实世界中的一些领域进行建模的时候，会发现有很多除了原生数据对象以外、更加复杂的对象，我们希望对它们也能进行一些概念的提取，能够对它们去进行建模。
除了组合手段以外，我们还需要有一些抽象的手段，包括过程定义和简单数据抽象。过程定义其实就是给一个名字，给名字也是一个抽象，而且威力非常大，有了名字以后就可以像原生对象一样被组合，就和原生对象没有任何区别。简单数据抽象是用来控制复合数据复杂性的。
有了组合以后，能够为更加复杂的东西建模了，可以描述更加复杂的过程，可以构建更加复杂的、复合的数据对象去描述领域中要处理的数据。有了组合手段以后，为什么还需要抽象手段呢？有了组合手段以后，我们所去描述的复杂的计算过程、要去处理的复杂的数据对象都是特定的，有了名字以后，就不再拘泥于处理的是Specific Domain，而是这个领域内所有的问题，不再是单独的"一个"问题。抽象手段是为了给一个名字，给一个真实存在的概念，使得我们在对问题领域建模的时候，能够提升语义层次，达到跟领域相匹配的这样一个层次去表述这些概念。
捕获通用模式，比如当我们描述一个"How to"是另外一个"How to"特例的时候。高阶过程是指函数过程本身接收的参数或者返回值也是一个过程。LISP程序中，函数过程就是数据，传统意义上有主动的过程和被动的数据，被动的数据是指保存了一些知识信息在数据里、等着别人来操作我，主动的过程是指描述了一些规则去操作、修改这些数据，但这都是传统意义上的。随着抽象层次越来越高，随着公共模式走得越来越远的时候，就会发现在计算机世界中真的需要有数据这个东西吗？数据可能就是一个函数过程。
再来看一个"线性组合"的例子。线性组合的概念就是两个东西相加、或者各自放大以后再相加，意思都是一样的。
上图中具备了线性组合概念的有：数值运算、多项式运算、向量运算、信号相加并放大。这些看似不相干的领域里的计算其实都有线性组合的概念。
在我们目前所使用的通用语言里，无法表达线性组合的概念。如果现在由我们来构建一个系统，这个系统能够把支持线性组合概念的所有这些种类都囊括进来，并且还能加入新的种类，比如矩阵也支持线性组合要加进来，怎样才能做到把矩阵加进来以后，矩阵能工作且不影响其它的种类？
在构建这个系统的时候，我们要考虑两类问题，把知识摆进去：
- 有多少种类可以支持线性组合的概念？
- 它们是如何支持线性组合的概念的？
可以看到，在线性组合中，一个是相加、一个是放大。有哪些种类可以支持线性组合的概念。这些种类在支持这些操作、计算的时候是如何相加、如何放大的。在系统中如何组织，把它们放到合适的地方，模块化、结构化，怎么把这些知识摆进去。
通用接口。
- Generic Operations
- Large-Scale Structure and Modularity
- Object-Oriented Programming
- Operations on Aggregates
Generic Operations是泛型操作、泛型算子。
黑盒抽象能够帮助我们去描述更复杂的过程、更复杂的数据，也能有一些抽象的手段，使得我们不仅是解决一个特定的问题，而是解决一类问题。那为什么要有"Conventional Interface"呢？因为光有抽象还不够，在我们构建大型系统的时候，我们需要对大型系统的结构化和模块化的组织策略方面会有些要求、技巧。一般来说会有两种方式：
- Object-Oriented Programming：面向对象：把所要构建的大型系统看作是一个小社会，这个小社会是由很多小个体组成的，这些小个体之间是通过发送消息来进行交互的。
- Operations on Aggregates：把系统看作一个聚合类或者聚合物，一般称为"流(Stream)"。把系统看作一个整体，不再关注单个状态的变化，关注从这个系统上流过的信息流。
面向对象是用有局部变量的这样一些模拟对象去模拟现实世界中那些有局部状态的那些实际对象，并且用计算机中间随着时间的变化模拟现实世界中随着时间的变化。那些被模拟对象的状态发生了变化，是由计算机里面那些被模拟对象的局部变量的赋值来体现的。这是面向对象看待系统的行为。换个角度，从纯数学意义上来看这样一个事情。如果把一个x随着时间变化的行为看作是一个t的函数：
如果现在关注的是每一时刻x的值，得到的结果是状态在发生变化，这就是面向对象看待系统的思路。如果不这么看，不关注每一时刻x的值，关注的是x在整个时间上的时间史，是没有发生变化的，因为整个x随着t的变化就是这个函数本身，这个函数本身没有发生变化。同样一个数学函数，从不同的角度看，关注单个点的行为是OO的建模思维，关注整个时间史、整个函数变化(没有发生变化)是Stream的建模思维。
我们的最终目标是设计一个新的语言。为什么要设计一个新的语言？设计新语言的目的是为了突出系统中不同层次的侧面，强调系统中的一些细节，忽略或者省却掉系统中的另外一些细节，这些都是为了控制系统的复杂性。不能平等地对待每一个细节，这样会让系统无比复杂。我们说设计的语言更加贴合领域规则、更加和领域匹配，其实是因为领域会强调一方面的关系，而弱化掉一些通用语言提供的关系。
这部分内容包括：
- 构建一个语言的技术、以及一个语言组成的关键要素。很重要，不仅构建语言的时候需要，在衡量、看待、评价一个语言的好坏的时候也需要。
- 编写一个嵌入在Erlang语言中的图形操作语言，或者叫画家语言。把领域关系找出来，降到实现语言(Erlang语言)的层次。
- 把语言层次往上提，提到领域所要表达的层次，构建一个人工智能中要用到的模式匹配和基于规则替换的语言。
- 做一个LISP程序的求值器。在LISP程序的求值器中，可以看到Eval和Apply两个函数过程的相互规约，不断地你中有我、我中有你的过程。
- Y Combinator(YC)。在Alonzo Church的λ演算体系中没有循环、没有递归，但这个体系的计算能力和图灵机的计算能力是等价的，也是图灵完备的。既然要图灵完备，就要能支持无限循环。所以，会讲一下在只有函数过程的λ演算体系里怎样去做无限循环。
- Meta-Linguistic Abstraction (元语言的抽象)
- Interpretation
Apply-Eval，LISP求值器。
- Example – Logic Programming
所有语言的构建技术和关键要素都是一样的，我们会去做一个逻辑语言出来，在这个逻辑语言中，关注的是Relation(关系)。
- Register Machines
揭开神秘的面纱，看一下那些小精灵们在计算机中间到底是如何工作的。寄存器该如何操作，寄存器的语言，设计一个LISP程序的显式控制的求值器。在这个过程中，对寄存器机器的设计做一个抽象。我们是硬件设计师，站在把计算过程给机器具体执行的角度，把寄存器的机器设计出来，对寄存器的机器做一个抽象，对软件写的LISP求值器进行显式控制。
对一个问题的认识分为三个部分：
- 先在头脑中想，想清楚；
- 用程序精确地描述出来；
- 计算过程的执行。
自己定义一个寄存器的语言，自己对寄存器的机器做一个抽象，把计算过程执行起来。这个过程也有点像Eval & Apply，我们的思维过程从我们的头脑到我们的程序表达出来，交给计算机去执行。计算机为什么是这样，机器为什么设计成这样，其实机器虽然是硬件，但它的设计思想也是来自于软件的抽象。
计算机科学描述的是"How to"，终极大招是设计一个新的语言。希望新的语言能够提升到和领域相匹配的层次，使得我们能够声明性地描述领域知识。即便是一些"How to"的Knowledge，也可以用声明性的方式把它们描述出来。而且在理想的层次上，我们希望无论是高层还是底层都能够用声明性的语言描述，高层的声明性的语言描述会被解释成下一层的"How to"，下一层的"How to"也可以用声明性的知识描述，这个声明性的知识在下下一层又被解释成"How to"，这是我们追求的终极目标，希望从上到下都是声明性地描述"How to"，一切皆解释。
了解语言的关键要素对于设计、学习、看待语言都很有帮助。语言的三个要素包括：
- 原生的元素(Primitive Elements)
与生俱来的、内置在语言中间的这些元素。它们的丰富性决定了你可以写简单"How to"的能力。
- 组合的手段(Means of Combination)
- 抽象的手段(Means of Abstraction)
抽象的手段一定要足够好，好到可以跟语言融为一体，形成一个闭包，再去做更大的计算。可以客观地评判语言的好坏，例如：LISP语言不是说适合做某个特定的东西，而是说适合你打造出你想要的东西。
下面来看一下，在Erlang语言中，这三个元素是如何对应的：
- Make a guess G
- Improving the Guess by averaging G and X/G
- Keep improving the Guess until it is Good Enough
- Use 1 as an Initial Guess
如果用这个方法求解平方根，最重要的一点是"收敛(Convergency)"。下面来稍微证明一下，这个方法肯定能求解出来，是能收敛的。
在这个算法中，我们在不断地改进猜测值，猜测无非两种情况，猜测值比平方根值小或者猜测值比平方根值大，如果这两种情况下，在下一次改进的过程中都能更加靠近平方根值，就说明这个过程是收敛的。
以下推导过程中，假设y是猜测值：
-module(sqrt).
-compile(export_all).
-define(TOLERANCE, 0.001).
sqrt(X) ->
try_once(1, X).
try_once(Guess, X) ->
case good_enough(Guess, X) of
true ->
Guess;
false ->
try_once(improve(Guess, X), X)
end.
good_enough(Guess, X) ->
abs(square(Guess) - X) < ?TOLERANCE.
improve(Guess, X) ->
average(Guess, X / Guess).
square(X) ->
X * X.
average(X, Y) ->
(X + Y) / 2.
test() ->
true = abs(sqrt(4) - 2) < ?TOLERANCE,
true = abs(sqrt(9) - 3) < ?TOLERANCE,
test_ok.
可以把good_enough的判断条件修改一下，如果这一次的猜测值和上一次的猜测值足够接近了，也就是说足够收敛了，就足够好了。
-module(sqrt_2).
-compile(export_all).
-define(TOLERANCE, 0.001).
sqrt(X) ->
try_once(1, X).
try_once(Guess, X) ->
NextGuess = average(Guess, X / Guess),
case good_enough(NextGuess, Guess) of
true ->
NextGuess;
false ->
try_once(NextGuess, X)
end.
good_enough(NextGuess, Guess) ->
abs(NextGuess - Guess) < ?TOLERANCE.
average(X, Y) ->
(X + Y) / 2.
test() ->
true = abs(sqrt(4) - 2) < ?TOLERANCE,
true = abs(sqrt(9) - 3) < ?TOLERANCE,
test_ok.注意try_once()函数第一行和第二行以及good_enough()函数的变化。
在前面的"Black Box Abstraction"小节的内容中提到了求解函数不动点：函数F，给定一个输入Y，如果F(Y)的返回值还是Y的话，称Y是函数F的不动点。
"求解平方根的"How to"是求解函数不动点的"How to" 都是第一步先给定一个猜测，第二步是改进这个猜测，然后是不断地改进猜测直到满足条件。"求解平方根的"How to"是求解函数不动点的"How to"的特例。
求解函数不动点，输入是一个函数F，输出是能够求解出函数F不动点的另外一个函数过程。求解平方根的"How to"是求解函数不动点的"How to"的特例，输入是"avg(Y, X/Y)"，输出就是SQRT。
从这个角度写了一个实现。
-module(fixedpoint).
-compile(export_all).
-define(TOLERANCE, 0.001).
fixedpoint(F) ->
fun(Guess) ->
fun(X) ->
try_once(Guess, F, X)
end
end.
try_once(Guess, F, X) ->
NextGuess = (F(Guess))(X),
case good_enough(NextGuess, Guess) of
true ->
NextGuess;
false ->
try_once(NextGuess, F, X)
end.
good_enough(NextGuess, Guess) ->
abs(NextGuess - Guess) < ?TOLERANCE.
test_sqrt() ->
F = fun(Y) ->
fun(X) ->
(Y + X / Y) / 2
end
end,
Sqrt = (fixedpoint(F))(1),
true = abs(Sqrt(4) - 2) < ?TOLERANCE,
true = abs(Sqrt(9) - 3) < ?TOLERANCE,
test_sqrt_ok.
test_cuberoot() ->
F = fun(Y) ->
fun(X) ->
(X / (Y * Y) + 2 * Y) / 3
end
end,
Cuberoot = (fixedpoint(F))(1),
true = abs(Cuberoot(8) - 2) < ?TOLERANCE,
true = abs(Cuberoot(27) - 3) < ?TOLERANCE,
test_cuberoot_ok.
test() ->
test_sqrt(),
test_cuberoot(),
test_ok.可以看到，fixedpoint和sqrt_2的主要代码很类似，只是F是传进来的，Guess和X柯里化了一下。
有了这样的黑盒抽象以后，实现立方根(Cuberoot)非常容易，只需要传入不同的改进函数即可，求函数不动点的过程完全不用动。
Process是在计算机中间机器的一个执行步骤。Procedure是我们写出来的、去控制小精灵帮助我们完成事情的函数过程。程序员的日常工作就是写出这些Procedure，去指导小精灵完成计算机中的Process。
我怎么知道我写出来的Procedure，它的Process是什么样子呢？替换模型是帮助大家理解我们写出来的函数过程、它产生的计算过程是什么样子，建立一个直观的认识。
替换模型是一个"Mechanic Model"(机器工作机制模型)，为什么这么说呢？千万不要以为在计算机中间机器工作起来就是这个样子。这个替换模型是非常有用的。替换模型看上去比较简单，其实它真正严格的数学定义是非常复杂的。
在Erlang语言中间一共有几种表达式(Kinds of Expression)：
- Number：数字
- Symbol：符号
- Fun(Args)：函数定义，放到以后课上再说
- Apply：过程调用
- Cond：条件表达式
这个机制模型到最后真正在计算过程中间：
- Number：把看到的1就当做是数值1
- Symbol：在计算过程中再也看不见了，会被符号本身所代表的那些东西替代
- Fun(Args)：函数定义，放到以后课上再说
- Apply：函数调用过程，一会儿讲
- Cond：条件表达式，一会儿讲
To evaluate an application
- Evaluate the operator to get procedure (Step 1)
- Evaluate the operands to get arguments (Step 2)
- Apply the procedure to the arguments (Step 3)
- Copy the body of the procedure (Step 3.1)
- Substituting the argument supplied for the formal parameters of the procedure (Step 3.2)
- Evaluate the resulting new body (Step 3.3)
先来看一下函数调用的替换规则。
我们要去求值一个函数的调用。首先，求值操作符，求值操作符是为了获取一个函数过程；接着再求值操作数，求值操作数是为了获取参数；然后把函数过程应用到这些参数上。
如何将函数过程应用到参数上呢？首先把函数过程中间的函数体拷贝出来，然后把所有形参用传进函数的实参替换，这时就会得到一个新的函数体，对这个新的函数体进行一个求值。
下面简单地来看一个例子，定义一个函数过程Sum of Square：
在上面这个小例子中，应用序和正则序的差别在于：在正则序中，(1+2)算了两遍。
绝大多数的语言会选择应用序，一方面是出于性能方面的考虑，另一方面是在正则序中，引入对象或状态的时候，先展开再归约的行为会使得逻辑控制比较复杂。
但也不是说正则序就丝毫没有用处。正则序的好处是直到碰到原生操作符才会进行计算，这是一种受限形式的懒式计算。这种懒式计算在模拟无限的情况下非常有用。
一般来说，一个应用如果能够产生合法值，不管是使用应用序还是正则序，产生的值是一致的。但对于非法值，虽然都用替换规则，但应用序和正则序产生的值可能不一致。
如果感兴趣的话，可以看一下《SICP》P13 练习1.5。
To evaluate an IF expression
- Evaluate the predicate expression
- If it yields TRUE
- Evaluate the consequent expression
- Otherwise
- Evaluate the alternative expression
- If it yields TRUE
刚才提到过，表达式除了Number、Symbol、Apply，还有一些条件语句。在Erlang语言中，条件语句有好几种，类似于Pattern Matching、When这些都是条件语句，还有真正的条件表达式if、case等。
来看一下if的替换规则。首先求值谓词，如果发现谓词为真，求值consequent表达式，否则求值alternative表达式。
需要注意的是，刚才用Pattern Matching去做其实是一个函数的调用，函数调用的语义跟真正的特殊表达式(if、case)的语义还是不一样的。在某些情况下，它们是可以等价的，但有些情况不是。不是所有时候都能拿函数调用去模拟if表达式和case表达式。如果函数调用能够完全模拟if表达式和case表达式，那为什么还要存在这种特殊的表达式呢？《SICP》P14 练习1.6。(按应用序看，方便理解)
程序员想要成为Master，我应该对我写的程序在计算机中能够产生什么样的计算过程要能有一个直觉的认识。这是需要训练的。有一些简单的过程能够帮助我们去了解什么样的Procedure产生什么样的Process，虽然看起来很微不足道，但它们能够帮助我们去内化这种直觉知识，帮助我们成为大师。
皮亚诺算法，只用递增和递减求解两个整数之和。
Two ways to add whole numbers:
add(0, Y) -> Y;
add(X, Y) -> add('-1'(X), '+1'(Y)).
add(0, Y) -> Y;
add(X, Y) -> '+1'(add('-1'(X), Y)).这两种写法基本上是一样的，差别在于'+1'出现的位置不一样。我们用替换模型来看一下这两个Procedure会产生什么样的Process。
从直观上看，能看到第一种写法的形状是笔直到底、第二种写法的形状是先展开再归约。下面从三个方面来比较一下这两种写法的不同。
假想机器按照替换模型工作，这个机器需要多少空间和多少时间。对机器来说，需要多少时间就是执行多少计算步骤。从上面画的例子来说，高度就是时间的复杂度，宽度就是空间复杂度。
第一种写法的时间复杂度是O(X)、空间复杂度是O(1)(无论X多大，都是一个常量)。第二种写法的时间复杂度是O(2X)、就是O(X)，空间复杂度是O(X)。第一种写法是"Line Iteration (线性迭代)"，第二种写法是"Line Recursion (线性递归)"。
从语法角度来说，函数直接或间接调用自身叫做一个递归的计算过程，需要的空间是正比于输入参数的，而迭代的计算过程所需要的空间与输入参数无关、常量空间即可完成。
上面是先有一个直观的认识，下面再从另外一个方面来看一下。
图中，GJS是Gerald Jay Sussman的缩写。
迭代的计算过程。GJS想算一个3+4，写了一个纸条"3,4 GJS"交给下一个人，说："你算完以后把这个值交给我"。这个人拿到纸条以后，分解一下："只要知道2+5不就能知道3+4吗？"(Peano算法加法的两种写法之所以都能工作，是因为它们都在缩小问题的规模，不管’+1’出现在什么位置。)，他对问题是这么分解的。他写了一个纸条"2,5 GJS"交给下一个人，说："把2+5算出来以后直接交给GJS、我不想再看到这个纸条了"。类似步骤一直往下，直到最后一个人，拿到的纸条是"0,7 GJS"，太简单了，就是7，算完以后就直接交给了GJS。
递归的计算过程。GJS想算一个3+4，写了一个纸条"3,4 GJS"交给JOE，JOE说："要算3+4，把问题规模缩小，我要知道2+4的话，在此基础上加1就可以知道结果了"，他就写了一个纸条"2,4 JOE"交给HARRY，说："你把2+4算完，但是别忘了要把结果还给我，因为我拿到结果以后还要再加1，才能交给GJS"。类似步骤一直往下，直到最终结果回来。在每次回来的过程中，当拿到返回结果的时候，这个人都会在这个结果上加一个刚才被延迟计算的1，最后返回给GJS。
仔细体会一下这两幅图的差别：在ITERATION图中，除了GJS有名字以外，其他人都没有名字的；每张纸条都是要交给GJS，一个人把纸条交给下一个人以后，纸条就可以不要了。在RECURSION图中，除了GJS有名字以外，参与的任何人也都有名字；每张纸条要交给的人都是不一样的，一个人把纸条交给下一个人以后，还得拿着，返回的值要加1。
如果把计算过程看作一个时间史(时间跨度)的话，在递归计算过程中，有更多的人、更多的纸条同时参与进来，而且参与的时间跨度，特别是对第一个人来说，是从初始到终止；但迭代计算过程则是一个转瞬即逝的过程。
这两幅图也被形象地称为官僚模型(bureaucracy)。这两幅图的差别，是为了让大家体会一下迭代计算过程和递归计算过程的差异。
到底有多少东西不在明面上？
还是迭代和递归这两个计算过程，如果在其中的某一步喊一声"Stop!"，再"Resume"的时候，思考一下这两个计算过程需要多少信息才能Resume起来？
对迭代计算过程来说，它Resume所需要的信息就是函数参数变量；对递归计算过程来说，无法根据函数参数变量知道前面pending了多少个'+1'。
对于一个用替换模型来工作的机器，在迭代计算过程中，所有的状态信息和控制信息全部都被显式地数据化了，并保存在过程参数信息中，所以很容易恢复。在递归计算过程中，除了这些参数以外，所有pending '+1'信息是由执行递归计算过程的机器帮你保存的，stop了以后，状态信息可能会丢失。
斐波纳契数列: 0 1 1 2 3 5 8 13 21 … N: 0 1 2 3 4 5 6 7 8 …
给定一个序号N，求解出斐波纳契数值。
-module(fib).
-compile(export_all).
fib_r(N) when N < 2 -> N;
fib_r(N) -> fib_r(N - 1) + fib_r(N - 2).
test() ->
[0, 1, 3, 5, 8] = [fib_i(0), fib_i(1), fib_i(4), fib_i(5), fib_i(6)],
test_ok.按照前面讲的替换模型画一下：
如果还是替换模型的机器，来看一下时间复杂度和空间复杂度。
根据fib的求解规则，每个数求解的时候，最后都会被降解到两个base case：0和1，所以统计一下0和1有多少次，至少能对计算步骤有一个直观的认识。也就是说，时间复杂度是一个数能被拆解成多少个0和1。
可以用数学归纳法推导出时间复杂度是Fib(N+1)：
光有Fib(N+1)还不够，还是不知道时间复杂度到底是多少。可以这么来想：现在是fib(4)，现在来计算fib(5)(加1)，拆解成计算fib(4)和fib(3)，拆解后的fib(3)和fib(4)下的fib(3)的计算是重复的。直观的感受就在于：当我们画出这棵树的时候，如果发现当规模从N变成N+1的时候，有相当大的一部分子树需要被重复计算或者需要被计算(不一定是重复计算)的时候，时间复杂度肯定是指数级。这个形状叫做树形递归(Tree-Recursive)。时间复杂度为指数级的算法一般都是不可用的。
时间复杂度具体是多少呢？ Fib(N)是最接近$Φ^n/\sqrt{5}$的整数，其中$Φ=(1+\sqrt{5})/2$ (黄金分割数)。这也可以用数学归纳法证明：《SICP》P28 练习1.13。
针对树形来说，一般它的时间复杂度正比于树的所有节点数。它的空间复杂度正比于树的高度，可以这样建立一个直觉的认识：在某一处调用，回来以后需要知道路径上的每一级父节点，所以至少要把树上的这条路径信息保存下来，不断往下分解的过程中需要保存往上回去的路径。
把递归的计算过程转换为迭代的计算过程的时候，要把控制信息数据化的过程是非常难的。
Fibonacci的递归版本就是数学定义。在迭代版本中，需要把状态自己给显式化出来，而不是在计算过程中被显式化。
-module(fib).
-compile(export_all).
fib_r(N) when N < 2 -> N;
fib_r(N) -> fib_r(N - 1) + fib_r(N - 2).
fib_i(N) -> fib_i(N, 0, 1).
fib_i(0, A1, _) -> A1;
fib_i(1, _, A2) -> A2;
fib_i(N, A1, A2) -> fib_i(N - 1, A2, A1 + A2).
test() ->
[0, 1, 3, 5, 8] = [fib_r(0), fib_r(1), fib_r(4), fib_r(5), fib_r(6)],
[0, 1, 3, 5, 8] = [fib_i(0), fib_i(1), fib_i(4), fib_i(5), fib_i(6)],
test_ok.按照前面讲的替换模型画一下：
当N=3的时候，手绘的移动过程如下图所示：
Wishful Thinking
That’s George’s matter! 用Wishful Thinking的方式来思考问题。在做某个事情的时候想：如果谁要是把这个做完，这个就好了。但不能是：你帮我做了、我就交差。
要能处理一个大型的复杂系统，一定要能够忽略细节、不考虑细节。用这种方式控制自己的注意力转移到现在要考虑的事情上。这一点很重要！
需要注意的是，不是所有的Wishful Thinking都管用，Wishful Thinking在这里管用，是因为规模不断地在缩小。
-module(hanoi).
-compile(export_all).
% Recursive Version: output io:format
hanoi_r(0, _, _, _) ->
done;
hanoi_r(N, From, To, Spare) ->
hanoi_r(N - 1, From, Spare, To),
io:format("~p: ~p -> ~p~n", [N, From, To]),
hanoi_r(N - 1, Spare, To, From).如果能把N-1借助于To、从From移到Spare，N就可以直接从From移到To，最后再把刚才的N-1借助于From、从Spare移到To。
可以看到，递归版本写出来是非常符合问题定义的，很简单。
运行结果和前面画的图中的过程是一样的。
直观感受的时间复杂度是指数级别的。N分解为N-1、1、N-1，当要计算N+1的时候，分解为N、1、N，N的这部分要被重新计算，是一个树形递归的过程。
再用替换模型来形式化地分析，看看这个时间复杂度到底多大？
为了便于比较递归版本和迭代版本的结果，把递归版本修改成生成一个移动序列。
% Recursive Version: output a sequence
hanoi_r_2(N, From, To, Spare) ->
hanoi_r_2(N, From, To, Spare, []).
hanoi_r_2(0, _From, _To, _Spare, Acc) ->
Acc;
hanoi_r_2(N, From, To, Spare, Acc) ->
NewAcc1 = hanoi_r_2(N - 1, From, Spare, To, Acc),
NewAcc2 = move_r_2(N, From, To, NewAcc1),
hanoi_r_2(N - 1, Spare, To, From, NewAcc2).
move_r_2(N, From, To, Acc) ->
Acc ++ [{N, From, To}].运行结果和前一个版本的运行结果本质上是一样的：
平常看上去习以为常的东西，其实是计算机帮你做了很多，而你并不知道，稀里糊涂地写程序。
把递归的计算过程转换为迭代的计算过程的时候，希望能把所有控制的状态信息显式地数据化。
针对每一块要知道：第几块、从哪儿移到哪儿。针对整个序列，先移这个、后移那个。
"Explicit" Control for Each Disk
- What is the first moving step?
- What is "to" disk of the first movement?
- How many steps between two movements?
注意：圆盘编号从上到下编号为1到N。
不从移动序列的整体来思考，而是从每个圆盘的角度来思考，对某个圆盘来说要想清楚：
- 第一次移动是什么时候(步骤序号)开始移的？
- 第一次移动的目标柱子是哪个？(因为所有圆盘的第一次移动的源柱子都是一开始的源柱子，所以知道目标柱子就可以了)
- 再隔多少步(在序列中)又轮到该圆盘移动？(如果第一次是从"From"到"To"，下一次一定是从"To"到"Spare"、如果再从"To"到"From"，是做无用功。再下一次一定是从"Spare"到"From"，同理如果再从"Spare"到"To"，也是在做无用功。) 有了这些信息，一个圆盘的移动序列就知道了。因为有每个圆盘第一次移动的序号，所有圆盘的移动序列合在一起，整个移动序列就知道了。
下面来推导一下，证明这个方法是可行的。
- 对编号为N的圆盘，它的第一次移动是第几步呢？ 要移动第N个圆盘，要先把上面的N-1个圆盘全部移走，根据前面的推导需要"$2^{N-1}-1$"步。那么第一次移动第N个圆盘是第"$2^{N-1}-1+1$"，即"$2^{N-1}$"步。
- 对编号为N的圆盘，它第一次从哪儿移到哪儿？ N：From -> To N-1：From -> Spare (Wishful Thinking: 要把N从From移到to，要先把上面的所有圆盘从From移到Spare，那么N-1肯定要从From移到Spare) N-2：From -> To (Wishful Thinking: 要把N-1从From移到Spare，要先把上面的所有圆盘从From移到To，那么N-2肯定要从From移到To) …
- 对编号为N的圆盘，两次移动之间有多少步呢？
孙鸣老师课堂上给出的代码如下图所示：
% Iterative Version SunMing
hanoi_i(N, From, To, Spare) ->
InitSteps = init_steps(N, From, To, Spare, []),
InitSeq = lists:zip([{power2(T - 1), T, power2(T)} || T <- lists:seq(1, N)], InitSteps),
generate_seq(InitSeq, power2(N) - 1, 1, []).
init_steps(0, _From, _To, _Spare, Acc) ->
Acc;
init_steps(N, From, To, Spare, Acc) ->
init_steps(N - 1, From, Spare, To, [{From, To, Spare} | Acc]).
generate_seq(Seq, Total, Cur, Acc) ->
{No, From, To, NewSeq} = get_cur(Cur, Seq),
NewAcc = move(No, From, To, Acc),
if
Cur =:= Total ->
NewAcc;
true ->
generate_seq(NewSeq, Total, Cur + 1, NewAcc)
end.
get_cur(Cur, [{{Cur, No, Step}, {From, To, Spare}} | T]) ->
{No, From, To, [{{Cur + Step, No, Step}, {To, Spare, From}} | T]};
get_cur(Cur, [H|T]) ->
{No, From, To, New} = get_cur(Cur, T),
{No, From, To, [H|New]}.
move(No, From, To, Acc) ->
Acc ++ [{No, From, To}].
power2(0) -> 1;
power2(N) -> 2 * power2(N - 1).- 初始序列InitSeq：
- power2(T-1)是圆盘T第一次移动的步骤；
- T是圆盘序号；
- power2(T)是圆盘T隔这么多步再做下一次移动。
- 获得当前移动步骤的相关信息get_cur：
- Cur是当前移动步骤的编号，递增1；
- 用Cur在当前序列里找，如果找得到，对应的圆盘就可以移动了，产生出对应的移动步骤，但这还不够，还要把这个圆盘下一次移动步骤的相关信息产生出来加到序列中；
运行结果如下，和递归版本的结果一样：
在孙鸣老师的代码中get_cur实现得比较巧妙，但是我刚看到的时候理解起来还是有些困难，于是，我根据get_cur的语义描述，重新写了一个lists:keyfind的版本。
% Iterative Version Faye
hanoi_i_2(N, From, To, Spare) ->
InitSteps = init_steps_2(N, From, To, Spare, []),
InitSeq = init_seq_2(N, InitSteps, []),
generate_seq_2(InitSeq, power2(N) - 1, 1, []).
init_steps_2(0, _From, _To, _Spare, Acc) ->
lists:reverse(Acc);
init_steps_2(N, From, To, Spare, Acc) ->
init_steps_2(N - 1, From, Spare, To, [{From, To, Spare} | Acc]).
init_seq_2(0, [], Acc) ->
Acc;
init_seq_2(N, [{From, To, Spare}|T], Acc) ->
init_seq_2(N - 1, T, [{power2(N - 1), {N, power2(N), From, To, Spare}} | Acc]).
generate_seq_2(Seq, Total, Cur, Acc) ->
{No, From, To, NewSeq} = get_cur_2(Cur, Seq),
NewAcc = move(No, From, To, Acc),
if
Cur =:= Total ->
NewAcc;
true ->
generate_seq_2(NewSeq, Total, Cur + 1, NewAcc)
end.
get_cur_2(Cur, Seq) ->
case lists:keyfind(Cur, 1, Seq) of
{Cur, {No, Step, From, To, Spare}} ->
NewSeq = lists:keydelete(Cur, 1, Seq),
{No, From, To, [{Cur + Step, {No, Step, To, Spare, From}} | NewSeq]};
false ->
error
end.- 为了便于使用lists:keyfind，调整了一下初始序列InitSeq的数据结构，init_steps的输出也相应调整了一下，返回之前reverse了一下，圆盘N在前，圆盘1在后：
- get_cur_2用lists:keyfind和lists:keydelete实现的。
运行结果如下，和前面版本的结果一样：
在上一个版本中，是把所有控制状态信息都数据化并保存在Procedure传递的参数中，但参数信息是正比于N的。虽然已经很好了，已经可以任何一个地方Stop、再Resume，但这样还不够。还有一种实现方法，只需要用到常量空间就可以完成。
刚才推导出了每一个圆盘的状态。现在，希望根据目前的步骤编号Cur就能知道现在应该移第几个圆盘。
% Iterative Version Const
hanoi_i_3(N, From, To, Spare) ->
hanoi_const(power2(N) - 1, 1, even_odd_mover(N, From, To, Spare), []).
hanoi_const(Total, Cur, {EvenMover, OddMover}=Gen, Acc) ->
{SpikeNo, SubCircularStep} = spike_substep(Cur),
io:format("Cur ~p SpikeNo ~p SubCircularStep ~p~n", [Cur, SpikeNo, SubCircularStep]),
{From, To} =
if
SpikeNo rem 2 =:= 0 ->
EvenMover(SubCircularStep);
true ->
OddMover(SubCircularStep)
end,
Acc1 = move(SpikeNo, From, To, Acc),
if
Total =:= Cur ->
Acc1;
true ->
hanoi_const(Total, Cur + 1, Gen, Acc1)
end.
even_odd_mover(N, From, To, Spare) when N rem 2 =:= 0 ->
{gen_mover(From, To, Spare), gen_mover(From, Spare, To)};
even_odd_mover(_N, From, To, Spare) ->
{gen_mover(From, Spare, To), gen_mover(From, To, Spare)}.
spike_substep(Cur) -> spike_substep(Cur, 0).
spike_substep(Cur, N) when Cur rem 2 =/= 0 ->
{N + 1, ((Cur + 1) div 2) rem 3};
spike_substep(Cur, N) ->
spike_substep(Cur div 2, N + 1).
gen_mover(From, Spare, To) ->
fun(1) ->
{From, To};
(2) ->
{To, Spare};
(0) ->
{Spare, From}
end.Faye：理解spike_substep()函数的实现，需要注意到一点：当Cur为奇数时，都是移动第1个圆盘。
增加了打印信息的运行结果如下图所示：
首先，计算机科学不是一门科学。如果我们能够直接向计算机描述一个问题，计算机能够自动地帮我们生成解决方案，才能称之为"科学"，现在显然还不能。
其次，计算机科学和计算机也没什么关系。因为计算机只是计算机科学所使用的工具、不是计算机科学的本质，不要混淆了某件事的本质和做这件事的工具。
计算机科学是那些通过计算机得以被具象化、得以被我们能够去了解清楚、并且能够为我们所用的知识。计算机科学形式化了计算机如何完成要做的事情(How to do things)。计算机科学是精确地描述"How to"、命令性(Imperative)的知识。
这里谈一点我自己的感受。因为小朋友在学奥数，所以我会尝试写程序来求解奥数题。以前总是模模糊糊地觉得小朋友的解法(不区分算术和方程)和我写程序的解法思路不一样，但又想不透彻到底怎么不一样。学了这节课以后，终于明白了这个"不一样"是数学的声明性(Declarative)和计算机科学的命令性(Imperative)的差异，是"What"和"How to"的差异。比如，我们可以仔细体会一下数学上的求平方根和计算机科学里的牛顿法求平方根这两种方式之间的差异。
我们研究计算机科学，是希望能够用计算机为我们现实世界中那些超大规模的系统建模，帮助我们完成我们想让它去做的事情。计算机科学里有很多技术，这些技术能够帮助我们控制构建大型软件系统的复杂性。软件系统的复杂性不同于物理系统的复杂性，物理系统的复杂性来自于自然规律的约束，而软件系统的复杂性不受自然规律约束，仅受限于程序员的思维，所以需要计算机科学这样一个专门的学科来控制软件复杂性。
设想计算机中有一群小精灵，小精灵帮我们完成的一些事情就是process，而指挥小精灵完成这些事情的描述性的步骤就是procedure。
procedure是我们要施行的魔法，process是魔法起效后在计算机里做的那个过程。procedure是函数过程，process是机器中的计算过程。procedure是描述性的步骤，process是真正在去做的执行性的步骤。
程序员的日常工作就是写一些Procedure去指导小精灵完成计算机中的Process。那么，我怎么知道我写出来的Procedure，它的Process是什么样子呢？替换模型可以帮助我们理解我们写出来的函数过程、它产生的计算过程是什么样子，建立一个直观的认识。
应用序：先求值后规约，正则序：先展开再规约。大部分语言是应用序。
控制大型软件系统复杂性的技术包括三大部分内容：黑盒抽象、通用接口和Eval & Apply。
黑盒抽象的本意是能够隐藏实现细节、并能够用来构建更大、更复杂的函数过程和更大的盒子。另外，当发现某项"How to"是另外一项"How to"的特例的时候，也可以用黑盒抽象来描述这个知识。黑盒抽象还能通过一些抽象的手段使得我们不仅是解决某个特定的问题、而是解决一类问题。
但光有抽象还不够，在构建大型系统的时候，在对大型系统的结构化和模块化的组织策略方面会有些要求、技巧，就是通用接口。一般来说会有两种方式：
- Object-Oriented Programming：面向对象。把所要构建的大型系统看作是一个小社会，这个小社会是由很多小个体组成的，这些小个体之间是通过发送消息来进行交互的。
- Operations on Aggregates：把系统看作一个聚合类或者聚合物，一般称为"流(Stream)"。把系统看作一个整体，不再关注单个状态的变化，关注从这个系统上流过的信息流。
我们的最终目标是设计一个新的语言，目的是为了突出系统中不同层次的侧面，强调系统中的一些细节，忽略或者省却掉系统中的另外一些细节，这些都是为了控制系统的复杂性。我们说设计的语言更加贴合领域规则、更加和领域匹配，其实是因为领域会强调一方面的关系，而弱化掉一些通用语言提供的关系。
为了能更好地设计语言、更有方向地学习、更客观地看待某种语言，我们应该关注语言的关键要素：原生的元素、组合的手段和抽象的手段。
在这次课程里，以Peano Arithmetic、Fibonacci和Hanoi为例，从以下三个方面详细讲述了递归计算过程和迭代计算过程。
- 时间复杂度和空间复杂度。
- 从时间跨度来讲，递归计算过程是整个时间跨度，而迭代计算过程则不是。
- 在迭代计算过程中，所有的控制状态信息都被显式地数据化了，并保存在过程参数信息中，所以停止后很容易恢复。而在递归计算过程中，除了这些参数以外，还有一部分信息是由执行递归计算过程的机器帮你保存的，停止以后，状态信息可能会丢失。
Substitution Rule 《SICP》P13 练习1.5、P16 练习1.6。
Fib(N)是最接近$Φ^n/\sqrt{5}$的整数，其中其中$Φ=(1+\sqrt{5})/2$ (黄金分割数)。这也可以用数学归纳法证明：《SICP》P28 练习1.13。