SICP笔记 - 1 概述
Lec1a
1 总起
计算机科学这个词并不能准确描述我们所从事的学科，因为这门学科既不是关于计算机制造、使用，也不是一门科学，事实上，它更多的是一门工程学或者艺术，并且更多的类似于我们所认知的魔法。那么我们为何用计算机科学来命名这门学科呢？这就像几何学(geometry)的由来，geo(gaia)的意思是大地，metry（measure）的意思是测量，这个词来源于古埃及时期祭祀丈量土地。因为当时的祭祀认为几何学就是丈量土地的学科，所以就以此命名，但是几千年后我们知道这么命名是不准确的，因为几何学完全不止做这件事。而同样的，计算机科学也是如此。当一门学科刚刚开始的时候，我们人对它的了解还不深时就会以某种忽略其本质的方式来标记它。事实上，我们现在对计算机科学本质的理解甚至要远远低于当时的人们对于几何学的理解。那么，几何学的本质是什么？我们今天知道，它实际上是对空间和时间进行了格式化的表达，并归纳出一套相应的符号来进行表述，这后来导致了现代数学各种形式的诞生。那么计算机科学的本质呢？相信许多年后的人们会这么说，当时的人们开始对过程进行形式化表述，即how-to。而在课程里，我们将会使用一门称为lisp的语言作为我们的魔法咒语，来控制计算机中的精灵为我们工作。Lisp的语法很简单，就像象棋的规则很简单；但就像象棋很难成为大师，Lisp也同样。
2 降低复杂度的方法
计算机科学要关心如何降低系统的复杂性。计算机科学是一门抽象的科学，我们可以只关心我们需要关心的东西，而不必受其他现实环境因素的影响，比如电路设计中要考虑组件的阻抗等，而软件中则可以选择性的对其进行抽象忽略。计算机科学中用来降低复杂度的方式有：
黑盒抽象
也就是分层。需要学习以下知识来使Lisp完成此目的：
- 基本对象
基本数据类型及过程 - 组合对象
数据组合以及过程组合 - 抽象方法
给数据、方法命名以封装其复杂度 - 更高阶的抽象
Lisp中过程及数据的边界很模糊，可以以此创造出更高阶的抽象
约定接口
黑盒之后，各部分如何进行良好交互，这就需要通过暴露接口。
- 面向对象
- 流
构建语言
当有时系统复杂度还是太高时，我们可以通过创建一门新的语言来在根本上降低其复杂度，放大我们想关注的细节，屏蔽我们不想关注的细节。而Lisp对这轻车熟路。
3 Lisp
当我们接触一门新的语言时，首先要关注三个问题：
- 它的基本对象有哪些 PRIMITIVE
例如整型、字符串等。 - 组合方式有哪些 COMBINITION
如判断、循环等语法结构。 - 抽象方式有如何的 ABSTRACT
如何给生成的对象命名以构建更复杂的对象，例如class, defun等。
因为有了这三个要素，整个系统就能构建起来了。
基本元素 (PRIMITIVES)
Lisp中的基本元素与其他语言也没有太多区别，例如数字、字符串等。
组合 (MEANS OF COMBINATION)
Lisp中，最基本的组合是由list完成的：
(+ 1 2 3)
它由操作符、操作数组成，操作符、操作数也可以是其他list，因此可以无限延伸。括号用来区分不同list，当然也就区分了作用域。
Lisp代码可以以二叉树的形式表达出来，例如：
(+ 1 (* 3 4) 5)
==>
-/ | \---
-/ | \ \---
/ | | \-
+ 1 \ 5
\
--
--/+--
---/ | \---
-/ | \-
* 3 4
可以无限延展。
另一个组合结构就是判断。scheme中的判断结构有cond, if。例如:
(cond ((< x 1) (message "1"))
((> x 1) (message "2"))
((= x 1) (message "3")))
(if (> x 1)
(message "1")
(message "2"))
scheme中没有循环结构，而是用递归来实现。对比C语言，我们就会发现，C语言的三种语法结构：顺序、选择、循环，分别对应于list、cond、以及递归。
抽象 (MEANS OF ABSTRACTION)
scheme中抽象是通过define完成的，可以同时用来定义变量和过程。例如:
(define a-value (* 2 2)) ;; 变量 (define SQUARE (LAMBDA (x) (* x x))) ;; 过程
LAMBDA的意思就是创建一个过程。这可以简写为：
(define (SQUARE x) (* x x)) ;; 语法糖
定义的过程将跟基本操作符没有任何语法上的区别，例如我们完全无法区分操作符+到底是一个scheme提供的基本元素还是后来定义的过程。而这也是Lisp强大的特性之一。
Lec1b
了解Lisp语句具体的执行过程。
1 展开操作符
2 计算操作数
3 如果操作数为过程，则继续展开，直到不能展开为止（即整个表达式都由基本类型组成，"One of the things we have to learn how to do is ignore details. The key to understanding complicated things is to know what not to look at and what not compute and what not to think."）
还有其他的求值顺序，我们这里使用这一种。
"It's important, by the way, to get names for, to get names for the part of things, or the part of expressions. One of the things that every sorcerer will tell you is if you have the name of a spirit, you have power over it. So you have to learn these names so that we can discuss these things."
迭代与递归的区别
"I'd like to develop some intuition about how particular programs evolve particular processes, what the shapes of programs have to be in order to get particular shaped processes. This is a question about, really, pre-visualizing." 编程语言大部分都是这样，"Easy to learn, hard to master"。学会一门语言，或者说学会一门技艺，很大程度上就是又这种由经验形成的pre-visualizing。
这里，我们来看一下迭代与递归所产生的视觉形状的区别。
- 迭代
(+ 3 4) (+ 2 5) (+ 1 6) (+ 0 7) 7
时间复杂度：
O(x)
空间复杂度：
O(1)
迭代所要用到的每一步的信息都保存在参数里，例如如果突然发生了断电，只剩下了(+ 2 5)，我们仍然能够得到7。
- 递归
(+ 3 4) (1+ (+ 2 4)) (1+ (1+ (+ 1 4))) (1+ (1+ (1+ (+ 0 4)))) (1+ (1+ (1+ 4))) (1+ (1+ 5)) (1+ 6) 7
时间复杂度：
O(x)
空间复杂度：
O(x)
递归需要额外的空间保存执行的状态信息，而将这些信息延迟处理直到最后。假如发生了断电，只剩下(+ 1 4)而没有状态信息，我们是无法得到7的。