很久没发帖了，已经从一个无忧无虑的学生变成了一个牛马社畜哩😭 ，没啥时间学习，最近硬挤了一点时间出来看了一下我很久之前就想看的书SICP，这本书可以说是比较经典的书了，没看过的鱼游强烈推荐，看完了会打开你对编程语言理论的大门。我做了一些笔记来分享一下，如果我笔记理解错了欢迎在评论区指出，阿里嘎多

ps: SICP的内容会有一些抽象，基础较差的鱼油可能看不懂，所以这里先说一下，在书中这一章中的“过程”这一个词可以理解成一个函数，这只是比较笼统的叫法不太严谨，后续会有关于这个词的定义，感兴趣的尽量去理解是什么意思吧，我本人是强烈推荐鱼油看过原书再来看这个笔记

构造过程抽象

程序设计的三个基本元素

• 基本表达形式

语言所关心的最简单的个体，比如：运算符，字面量，关键字等

• 组合的方式

通过基本表达形式构建出复合的元素，比如：多个表达形式组合成的一个表达形式则被叫做组合方式

• 抽象的方法

可以对复合对象命名，比如：变量名，常量名，类型名，函数名等等

程序设计的本质

不管多么复杂的程序都可以被抽象出两个要素，一是数据，二是过程

数据

文中这样描述“数据”的

数据是一种我们希望去操作的“东西”

所有bèicāo作的东西都是“数据”

过程

文中这样描述“过程”的

有关操作这些数据的规则的描述

设定怎么操作数据的规则，就是一个过程，说人话就是一个函数怎么对数据进行处理

往往数据和过程都是由三个程序设计的基本元素组成的

表达式

• 字面量
  最简单的表达式就是字面量
• 组合式
  程序的基本元素中提到组合的方式中有说

通过基本表达形式构建出的复合元素

也就是多个基础表达式组合起来的表达式叫做 组合式

命名和环境

命名代表着变量名、常量名、函数名等等
环境是整个程序期间的上下文，变量名、常量名、函数名都需要环境 提供 其意义，
这个 提供其意义 就是为变量名、常量名、函数名等等信息与对应的值进行绑定，
这个绑定一般被叫做 定义

组合式的求值

求值一个组合式的规则

1. 求值该组合式的各个子表达式
2. 将求值后的子表达式的值应用到实际参数上，也就是实参上

求值的原理如下

• 每个组合式都是 一个树状的结构
  1 + 2 * 2 等价于

                 + // 5
             /       \
         1          *       // 4
                  /      \
                 2      2
  

• 组合式的求值是一个递归的过程
  组合式中的每个表达式的求值操作其实都是在做对上面的“求值”规则进行应用或者说调用

• 递归本质
  递归是一种处理层次性结构的（像 树 一样的对象）极强有力的技术，从最下层的叶子进行计算然后将值返回到上层，类似“值向上穿行”的求值形式，被称为“树形积累”

• 组合式中的表达式
  重复求值的第一个步骤到某个点的时候，得到的并不是组合式而是最基本的表达式，比如字面量，内部运算符或者其他名字的值的时候，比如上面的树状图中求值到运算符、1和2的时候
  处理这类的情况有以下规则:

  1. 字面量的值就是它们所表达的数值
  2. 内部运算符的值就是它内部能完成相应操作的机器值令序列
  3. 其他名字的值就是在环境中它所关联这一个名字的值

通常将第二第三种情况视为特殊情况，它们是额外存在于环境 中的表达式，环境 所扮演的角色是为这些非字面量的“值”提供意义，也就是提供定义提供绑定的值

第二点比较抽象，意思是如果是求值到运算符或者是函数名这类表达式的时候，那么它们本身就是一个值

复合过程

过程的基本定义

• 数和算术运算是基本的数据和过程
• 组合式的嵌套提供了一种组织起多个操作的方法
• 定义是一种受限的抽象手段，将名字关联对应的值

说人话就是对数进行运算是一个过程，组合式就是一个过程的描述，定义就是给过程进行命名

复合过程则就是一个过程里有多个过程

过程应用的代换模型

本节只是为了让人理解计算过程
大致意思是将所有的组合式进行归约然后再进行求值

应用序和正则序

我个人理解成

• 应用序 = strict求值
• 正则序 = lazy求值

这里比较抽象，书中也是使用的代码进行图形演示的
但这只是我的个人笔记，不想花太多时间在描述这个概念上
感兴趣的人可以取自行搜索，关键词就是我在上面写的理解
c/c++ js java python ruby rust zig等等c系的ALGOL-like语言
都是strict evaluation的也就是采用的应用序求值

防杠：我知道eager evaluation更符合描述，但是我就是喜欢用
strict evaluation来描述:p

条件表达式和谓词

条件表达式没什么好说的就是 if then else
谓词则是一个返回 True 或 False 的表达式

练习

sicp中的章节练习，书中采用 scheme 来编写，但本人更喜欢 Haskell所以采用 Haskell 编写练习

1.1

下列是一系列表达式，对于每个表达式，解释器将会输出什么样的结果？假定这一系列表达式是按照给出的顺序逐个求值的。

没啥好说的根据题目中的表达式翻译成haskell然后在ghci中依次输入就好了

ghci > 10
10
ghci > sum [5, 3, 4]
12
ghci > (-) 9 1
8
ghci > (/) 6 2
3.0
ghci > (+) ((*) 2 4) ((-) 4 6)
6
ghci > a = 3
ghci > b = (+) a 1
ghci > sum [((+) a b), ((*) a b)]
19
ghci > a == b
False
ghci > if b > a && b < ((*) a b) then b else a
4
ghci > if a == 4
ghci| then 6
ghci| else if b == 4
ghci| then sum [6, 7, a]
ghci| else 25
16
ghci > (+) 2 (if b > a then b else a)
6
ghci > (*) (if a > b
ghci| then a
ghci| else if a < b
ghci| then b
ghci| else -1) ((+) a 1)
16

• 1.2
  将下面表达式转变为前缀表达式

没啥好办法，摁转
5+4+(2-(3-(6+4/5)))/3*(6-2)*(2-7)

ghci > (/) ((+) 5 ((+) 4 ((-) 2 ((-) 3 ((+) 6 ((/) 4 5)))))) ((*) 3 ((*) ((-) 6 2) ((-) 2 7)))
-0.24666666666666667

1.3

请定义一个过程，它以三个数为参数，返回其中较大的两个数的和

a和b比较获取最大的数，然后再获取a和b两个较小的数，再用较小的数和c比较获取较大的数，这样就可以获取了
三个数中第一大和第二大的数，然后进行想加

ghci > :{
ghci| f :: (Num a, Ord a) => a -> a -> a -> a
ghci| f a b c = (max a b) + (max (min a b) c)
ghci| :}
ghci > f 1 2 3
5
ghci > f 3 2 1
5
ghci >

1.4

请仔细考察下面给出的允许运算符为复合表达式的组合式的求值模型，根据对这一模型的认识描述下面过程的行为

没看懂这个b题目，我就直接按照函数的行为描述了

aPlusAbsB :: Int -> Int -> Int
aPlusAbsB a b = (if b > 0 then (+) else (-)) a b

这个函数加上一个给a加上一个b的绝对值
当b大于0的时候返回 (+) 这个函数，小于0的时候返回 (-) 这个函数
然后将会变成 (+) a b 或者 (-) a b

在函数式语言中“运算符”都只是一个函数，并不是具有特殊意义的运算符或者叫token

1.5

Ben Bitdiddle 发明了一种检测方法，能够确定解释器究竟采用哪种求值序，是采用应用序还是正则序。它定义了以下的两个过程
然后进行应用，如果某个解释器采用的是应用序，Ben 将会看到什么样的情况？如果解释器采用正则序求值，他又会看到什么样
的情况？请对你的回答作出解释。（无论采用正则序或者应用序，假定特殊形式if的求值规则总是一样的。其中的谓词部分先进行
求值，根据其结果确定随后求值的子表达式部分。）

(define (p) (p))
(define (test x y)
    (if (= x 0)
        0
        y))
(test 0 (p))

chez scheme的是采用应用序求值，会看到在 test 函数应用 (p) 的时候会陷入无限递归的情况
这是因为在进行函数应用的时候就对 (p) 进行求值了，(p) 在定义的时候就是在做递归运算，
(define (p)) 就是在定义一个名字叫 p 并且没有参数的函数，然后 (define (p) (p)) 就是在
p 这个函数体中对自己递归调用 (p) 相当于其他语言的 p() 调用，chez scheme作为一个
函数式编程语言，它拥有尾递归优化，所以这里是等价与其他语言的死循环，且是 for (;;) 的死循环

let p = p
    test x y = if x == 0 then 0 else y
 in
    test 0 p

Haskell采用正则序求值，会看到0，因为正则序是会在值被需要的时候才会去求值，p
并不会被求值，如果 test 函数应用的参数是 test 1 p 则会陷入到无限递归的情况，
这是 x 不等于0了，所以返回 y ，这个时候就会对 y 进行求值，也就是对 p
进行求值，从而陷入到无限递归的情况，Haskell也拥有尾递归优化，所以同上

结语

最后可能有一些人理解不了过程和组合式有什么区别，其实就是函数和表达式的区别，表达式中有多个嵌套表达式，比如 foo(bar())，这就是一个组合式，foo和bar本身是一个过程，当你应用或者说调用它们的时候就是一个表达式比如 foo() bar()，但是你让它们组合在一起应用比如 foo(bar())，则就是组合式了，你再在这个组合式的基础上再定义一个过程也就是函数，function foobar() { foo(bar()) }则又是一个过程了。