SICP

这门课其实我很早之前就看过，但看到lec2b发现，我当时还是个2b。

于是，我就去修了接近1年，现在决定再来看

顺便，祝大家新年快乐

笔记

computer so-called science, actually has a lot in common with magic. – Abelson

计算机科学比起科学更像工程或艺术

而且，也不能说他关于计算机。

因为，几何学虽然字面上叫“地面测量”，但他是关于提供一种空间与时间的形式化表达什么的这样的东西的，而不是关于测量仪器的使用

计算机科学也像那样有糟糕的命名。

比起计算机，更应该说是对计算过程进行形式化表述：如何对解决问题的过程进行精确的，形式化的表述

但几何学只谈论“什么是真的”，而计算机科学谈论“如何解决问题”，而且格外精确

数学里，定义x的平方根y是一个其平分=x且大于等于0的数，这是陈述性知识，他告诉了你什么是，但没有告诉你怎么去找到一个

而计算机科学里，给出的是指令性知识：

要找到x的平方根，做一个猜测g，通过求g和x/g的平均值改善猜测，一直改善直到足够好【heron算法】

这是一个过程，告诉了你怎么做某事。

那过程通常来说是什么？

可以看成一个活在计算机里的精灵，根据你给的叫“程序”的规则模式指导他们做某事，而使用程序控制精灵完成某事就叫作过程

所以，计算机科学是巫术。

就像巫术要用咒语，计算机科学也需要，lisp就是其中一种。

咒语很简单，但就像人人都能很快学会象棋的规则并告诉别人怎么用但却不能理解其蕴涵的内容一样，编程语言也是如此，你可能会用但却不“会”

但程序有可能长达上千页，具有高度的复杂性，你也没法一眼全装进脑子，所以我们有在大系统中控制复杂度的技术，这就是计算机科学的关键，也是sicp所谈的。

别的领域也要控制复杂度，但cs的复杂度和他们不太一样：

cs不太现实。

别的领域有公差，近似值，噪音

但逻辑上cs没有。你可以随便搞，约束几乎没有。限制你的没有别的东西，而只有你思维的极限。

计算机里这个控制复杂度的方法叫作黑盒抽象，将某些东西组合并封装。比如求平方根，把这些操作视作盒子：找到x的平方根盒子

我们输入36,他给我6

所以某人想把a平方根+b平方根的时候就不用关心他是怎么实现得了，还可以构建新的盒子

基本就是把处理过程放进盒子里隐藏细节，以构建更大的盒子。毕竟，假如你在用电风扇，你不会想看到他一身都是复杂的电路什么的而没有外壳的。

函数的不动点是：F(y) = y，输入与输出相等

而求解有个技巧，就是把难解的问题转化为找某个精心设计的F的不动点

那么，我们就一直把y代入F(y)，再把结果塞进去，无限逼近不动点

换句话说，这不就是递归吗？换句话说，盒子可以套盒子，函数可以拿函数做输入，一个过程输出了另一个过程

同时，求和运算可以放到任何元素上，电信号，多项式，数，但显然他们加起来的方法不同，为了避免加个别的东西直接全坏掉，我们需要一种接口，一种按照约定实现的接口，对各种不同数据采用同一运算规则，只要每种数据类型都按约定实现这个函数

比如说，要写个收银机函数，我们一个一个全部在一个函数内判断什么的，会特别复杂，而且每次改都得重写

但我们如果先给每个商品加个类型的标签和对应的定价规则【比如正常，称重，促销】，再加个加个规则表，根据类型对应到各自的定价函数，在写一个通用结账函数，就不用改函数本身，只需要注册一个新的就好

我们现在有两种控制复杂度的方法了，黑盒抽象和约定接口

而第三种是设计新的语言，你可以看到同样的程序用c和py实现py就更简单，py就隐藏了部分细节，又强调了一些其他的细节，放到lisp上，lisp有一大堆方言，每个都为解决特定问题而生。

即元语言抽象，构建新的语言。

当有人展示一个语言时，你应该问他：构成语言的基本元素[Primitive Elements]有哪些？他们组合的方法是什么？抽象的方法是什么？

lisp的基本元素：3 17.4 5 +

组合他们的方法：【把求和运算符运用于他们】

(+ 3 17.4 5)

+ 是运算符[Operators]，那些数字是运算对象[Operands]

组合也可以成为运算对象，比如：

(+ 3 (* 5 6) 8 2)

构造组合式是组合的基本需求

lisp所用的是前缀表达式，即运算符在运算对象前

括号表示所括的东西是一个组合式，不闭合意思就不一样了

事实上这个表达式本身，是这样的一个树状结构：

括号只是将这种结构写成表达式的一种方法

你还可以定义一个名字给组合式

如

(DEFINE A (* 5 5))
(* A A) => 625
(DEFINE B (+ A (* 5 A)))

那我们想把给定一个数与其自身相乘起个名字怎么办？

(DEFINE (SQUARE X) (* X X)) 

(SQUARE 10) => 100

(DEFINE (SQUARE X) (* X X)) -> 要平方某物，将其乘以自身

其他命名方法：

(DEFINE SQUARE (LAMBDA (X) (* X X)))

lambda 表示构建一个过程

即，构建一个带有参数x的过程，返回x乘以x的结果

他和前面那个方法没有区别，只是写法不同，前者只是后者的一种语法糖

然后我们就可以

(SQUARE (+ 5 7))
(+ (SQUARE 3) (SQUARE 4))
(SQUARE (SQUARE (SQUARE 1001)))

如果你直接输入square，lisp会输出：复合过程 square

再复杂一些，可以：

(define (average x y)
    (/ (+ x y) 2))

(define (mean-square x y)
    (average (square x)
            (square y)))

你可以把他们用作基本元素

定义均方的人不需要管square是内建的还是什么

如果你输入 +

他会说这是复合过程 +

让我们来看看条件判断

我们知道abs（x）可以表示为一个当x小于0为-x，等于0为x，大于0为x的函数

那么lisp里可以这样表达：

(define (abs x)
  (cond ((< x 0) (- x))
        ((= x 0) 0)
        ((> x 0) x)))

(< x 0) 是一个谓词或条件，谓词在lisp是可以表达true或false的东西，（- x）是子句，根据谓词做某事

还有一种语法糖：

(define (abs x)
  (if (< x 0)
      (- x)
      x))

但我们没有循环，那么如何实现heron的平方根算法呢？

递归定义。

(define square (lambda (x) (* x x)))

(define (average x y) (/ (+ x y) 2))

(define (sqrt x)
  (define (improve guess)
    (average guess(/ x guess)))
  (define (good-enough? guess)
    (< (abs (- (square guess) x))
       .001))
  (define (try guess)
    (if (good-enough? guess)
        guess
        (try (improve guess))))
  (try 1))

要理解这个，代入随便一个值，把自己当成解释器试试就好了。

lisp的基本信息：

        过程        数据

基本元素： + * < = > 23,1.738
组合方法 (),cond,if
抽象方法 define

FAQ:

> (define a (* 5 5))
> (define (d) (* 5 5))

这两个写法有什么区别：

第一种定义了一个数据，第二种是一个过程：

> a
25
> d
#<procedure:d>

> (d)
25

> (a)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 25
>