第一章
核心在讲: 用一组经过严格检验的步骤可以把问题解决了. 而且 , 不一定需要代码. 可以是任意存在(比如几何画板. sign)
第二章
严格介绍了状态空间的定义, 以及状态转移(是我曾经想过的内容)
S 有关的设备
R 后条件
weakest pre condition, 其实就是代码大全里的”防御式编程”
可以把 wp 理解成一个元组, 描述了一个抽象的计算机在给定的初值下能否约化为最后结果.
从理论计算机的角度就是图灵机纸带能否输出.
rust trait
基于 trait bound 写代码
P59 对分号的定义.
分号表示了一个操作的结束
从状态空间的角度看, 就是一个状态转移到了新的状态.
如果把变换看作一个函数过程, 那
; 表示一个过程的结束.原来这就是 procedure 吗. woc
if 约束实际是一种减少状态空间的做法.
假设全局变量有 a b c, 取值分别有 m n p 种, 那么状态空间
但是 if 语句对取值空间进行了剪枝. 也就是所谓的 guard
9
最后讲了停机问题。
10
提到了怎么把程序代码转成数字电路。
- 整理出变量的状态空间
- 编号
- 状态转移图
- 数字电路
还提到了 Fortran 的不声明变量就能使用的缺点。bash，awk，js 也这个问题。
undefined has no method xxx
bash 会自动替换成空字符串，被坑过不止一次
后面讲了词法作用域。里面提到的显式捕获在 py，cpp，rust 里都有体现。
py：
nonlocal global locals() globals() cpp:
[&](){} [=](){} rust: 内层 fn 需要写明所有用到的外部变量，用 & 传进去。或者 lambda
还讲到了遇到未定义的变量怎么办
-
undefined，like js
-
NULL,nullptr, c/cpp
- 用隐式 default，比如 cpp 的默认构造函数
P173 的重复结构赋值。本质在说 mut
因为假如去掉重复结构，那就是在用递归写（递归和循环等价）
而递归返回一个值，把值 bind 到一个变量上，就是书里说的初始化。
书里说的重复结构，就是递归的栈的变量变成了循环里的变量，即“用同一个名字表达不同的值”
书里的全局非初始化就是
let mut x = OnceLock / LazyLock
可变是 let mut
全局不可变是 const
局部可变要么 const 要么 let
11
提到的并发赋值
rust 不会有这个问题。。因为
- 要么是 swap 解决
- 可能有语法糖
都会出现两个
&mut 的情况，affine type 会自动排除。不然就是写竞争。
提到的我们要把数组看作一个变量。这也是 rust 做的。不能用 index 去修改。要
as_mut_slice。 hashmap 也不能，要 clone 出来。如果真的遇到了 hashmap 要 get 还要 set 同一个 val, 官方提供了
entry , 思路和 swap 一样.
P195
原来 lua 的 obj:method 是从这里抄来的。。
P201
书后面是定义了一个 vector 以及相关操作。甚至预言了 vec.swap。相比 i,j = j,i
- 解决了 i == j 的问题
- 只有一个 &mut
- 短，语义清晰
怎么感觉一直有 rust 的影子。。
以及算法 4 里也是这么定义 swap 的
🚿时突然意识到。。因为 i,j = j,i 本质有 4 个自由变量。但是 vec.swap 只有俩。利用 api 对参数空间开 sqrt 了。
P207 结尾还黑了一把提前优化的数学家们。
12
线性检索定理。
其实就是 take_while
13
有个隐藏的思想:
考虑对一个 arr 进行求 next_perm 的操作, 不动点是逆序排列. 所以找到第一个不满足逆序的. 就是需要修改的
i .P221
算法 4 的 swap 实现.
16
讲解了如何写归并.
重点是, 它里面形式化并且很认真讨论了一堆开始怎么让命题为真, 后面怎么让命题始终为真, 直到边界. 利用 guard.
换句话说在指令式编程里做到了函数式编程的效果.
一个例子: 证明最后有 5 个元素
循环开始时, v 是空的, 对应 i = 0, 0 个元素. 在每次循环结束后, v 里面都有 i 个元素 最后 i == 5, 对应 v 里面 5 个元素, 循环不变量. 关注循环的结果而不是追踪单个变量.
书里还提到了要求递增
用 gen 写一下是这样.
17
经典的 2 3 5 倍数的队列
本质是一个无穷生成器, “类似” fib 数列. 递推式是
所以需要保留”全部”的已生成的列表. 说是全部, 实际上由于 2 * 的关系, 只需要保留最新的 1/2(此处略去这个实现)
3 个 while 本质是求了 find first meet (第一个为真. 又因为数列递增的条件始终不被破坏), 保证下面的 append 不破坏递增.
用生成器的 style 写一下是这样.
在 sicp 3.56 里提示了用 stream 写
21
类似求图的直径
相关优化的思路还需要再看看.
22
先思考中间态, 去证明 State -> succ(State) 是正确的. 然后提出一个慢的算法, 再逐步优化.
这个比 今天来学最小生成树, 会学 2 个算法, 用到贪心的思想 . 这种讲法好多了
书里介绍的算法是 Prim 算法, 提到的另一种排序边的是 Kruskal 算法
23
并查集, 但是重点是怎么讲的.
先提出问题: 高效找等价类.
然后常规方案非常慢.
24
前面的 3 维凸包不是重点. 重点是 dijk 在尝试表达一种思考
给定初始集合 A = S, B = empty
反复执行操作使得 A = empty, B = A 的传递闭包.
CPS 变换
sicp
25
太长了, 不看了, SCC
我觉得 dijk 已经把我想过的问题全给过答案了
我只是在徒劳地走过他走过的路
Asuka Minato, [18:26]
突然有了个很神奇的想法..
代码里的 if 除了 early-return 全换成 while (书里提到的 guard
多分支用 match ( explicit 写出匹配到的分支
这大概就是 dijkstra 很想表达的内容了, 所以与其说他创了一门语言, 倒不如说他制定了一些 lint rules...
牛, [18:30]
语言跟 lint rules 没有区别
Asuka Minato, [18:34]
区别是 lint 的发出者 是 解释器 / 编译器 / 人 . 代码就是一些 ast 表达的控制顺序.🤯
原来还能这么看
