非常抱歉... 因为时间不够的原因，这次就只教这个了（请大家原谅呐

合影留念~

作为一个附属的内容，接下来我说一下作局部用域的问题。 #PLT #Parser
我自己是没时间实现更多的东西了... 大家了解这些理论呢... 可以回去尝试一下。
首先咱们谈谈 Lexical Scoping.

介个 lexical scoping，词法作用域呢，是 1932 年 Lambda calculus 引入的一个（迫真）概念

Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was first introduced by mathematician Alonzo Church in the 1930s as part of his research of the foundations of mathematics.

Lambda calculus 呢.... 就是早先没有那种泛型（就是可以依据程序做各种工作）电子计算机的时候，
希望对计算机处理进行基本的理论模型构造的理论（这是我第三次讲了，有喜欢的人肯定知道）

这个 lambda calculus 是理论，它是很抽象的。是一个由『项(item)』构造的形式化系统，
里面可以进行形式化定义好的操作。 有这么三种项：

var 这个叫做 variable，变量
λ vars . body 这个叫做 abstraction，抽象
( (λ ...) args ) 这个叫做 application，应用。动词是 apply

当然以上的项目是在一个上下文里讨论的。变量和抽象(λ) 引入了两个集合 — Variables 和 Lambda Terms（准确的说第一个集合只是『分配』集合...）
所有 Variable 都是 Lambda Term，并且 M,N in Lambda => (M N) 这种 application 可以引入新的 lambda term
(λx. M) 这样的 abstraction 也是一个道理
理论上的细节也就不讲了，都是会编程的...
此外，还有两比较基本的操作（都是希腊字母起的...）：

1. alpha-conversation
alpha-conversation 引入了 alpha-equivalence，表名只有变量名称不同的两个 abstraction 是等价(equivalence) 的
λx. x equiv λy. y
(λx. x) a equiv (λy. y) a

2. beta-reduction
beta-reduction 可以简化 lambda 项目，应用 lambda calculus 的『替换(substitute)』
((λx. M) a) equiv M [x := a]
这就表示了 M 里面的『free variable』 x 将被『替换』成 a。
比如 ((λa. λb. a + b) 1) 里面，我们最终得到的就是 (λb. 1 + b)
或者说：(λb. a + b) [a := 1]
那个 喂基 上讲的很细，有点啰嗦... 举个例子，这个 beta-reduction 居然是这么写：

(λa. λb. x x b) [x := zz]
equiv (λa'. λb' x x b') [x := zz]
equiv λa' b'. (z z) b'
nequiv λa'. λz. (z z) z

Lambda 演算是左递归文法的，就是说 (λf. f a b) 是 (λf. (f a) b) 的惯常表述方式

eta-reduction 和 currying 就不说了，FP.js 里也有 currying

举个例子，你看这个 identity... （输入即输出函数）
I = λx. x 它里面这个 x 叫『被前面的 λ bound（绑定） 了』
Kst = λy x. y = λy. λx. y => (Kst 1) 它里面的这个 y 被绑定到了 1，x 也被绑定了，没有被使用
λx. y 这个里面的 y 是 free-variable，它没有被 lambda abstraction 绑定
Lambda 演算是支持自己应用自己的 (λx. (x x))

不多赘述了，这里讲的那个 wiki 都很好（


所以先说这个 lexical scoping
看完了 lambda calculus 就应该知道啥是 lexical scoping 了

比如 infinity = λx. λy. (cons x (infinity y x))

beta-reduction (infinity a b) 后是 (cons a (infinity b a))...（递归情况）
当然不让命名也可以用 Y 组合子的

λx y. (λf. (λc. f (c c)) (λc. f (c c))) (λrec. cons x (rec y x) )

这里，我们注意到里面的 lambda 演算项 的 『y』 被绑定为 b
这个 y 引用了外层 lambda(λx.) 抽象绑定(bound)的变量，就叫做 Upvalue（上值）
这个函数 λy. 就叫做『内嵌函数(inner function)』、λx. 就叫做『外包函数』，由 λx. 绑定引入的变量，在 λy. 里面就称为上值。
包含词法作用域的函数被称为闭包（和匿名函数什么的区分开啊...）
接受（参数）或者产生（"返回"值）函数的函数叫做高阶函数（这本来就是数学上的概念）

那么理论暂时就到这里了。咱说说怎么实现。

lexica scoping 是很好的。为什么？ 一个只有全局变量的编程语言，你敢想像吗？现在绝大部分稍微正常一点的编程语言，哪怕是 bash 等 shell，基本都实现了 lambda 演算的部分基本概念（比如函数抽象）

这个 lexical scoping 本身和 lambda calculus 关系很大，但是在实际编程的时候，也不一定非得是纸面上的那一套，还可以有副作用、各种判断循环、引用... 不过有一点 — 就是『箭头函数』 — 创建一个闭包，而这个闭包拥有当前词法作用域上下文的引用，闭包『包含』了创建时语言的部分上下文，比如『绑定』们

def konst(k)
  return ->() { k }; end

konst(1)() #=> 1

一个『不那么引人注意』的细节就是 — 为什么这个 ->() （箭头函数）可以得到 k 的值？
虽然这很符合逻辑，但是恰恰也就让我们以为理所当然了 — 事实上在很多编程语言里这种代码都是无效的，因为他们不实现 lexical scoping

为什么呢？如果你使用 dynamic scoping（时序作用域），那就会明白：在 konst 函数返回这个函数的时候，它的『局部变量』 k 已经失效了、过期了，根本不能再次访问（除非复制，说你呢，Java 8）
可是有『嵌套序』作用域的话，就不会有这种问题了。所以就说是『词法』上才产生的作用域区分『词法作用域』。

实现这种解释器（这里特定于 AST-walker 讨论，但部分技巧不限于 AST-walker）的时候：

0. 除非你是在造玩具，否则不要通过遍历语法树手动替换该 abstraction 要 bind 的 variable
它比较慢，而且这种行为有点不够优雅...
1. 每层 abstraction 都可能覆盖上一层的 variable binding，注意 alpha-equivalence 是理论上的... 准确的说实现语言求值器不太需要考虑、程序分析和变换才去想
2. 每层 abstraction 都可能新建 binding，并且一个函数要可以保留自己词法作用域的拷贝（或者引用的 upvalue 什么的）
3. 离开当前词法作用域的时候必须撤销所有修改
4. 尽可能减少复制和使用数据结构的数量

咱就说三个情况。

1. 你是 Schemer/Haskeller，一般他们理论上讨论的很多，所以不会想太多复制开销什么的，

入门（ Haskell 就直接用 Data.Map.Strict



import Data.Map.Strict
kvs = fromList [ ("monkey", "猴子"), ("penguin", "企鹅") ]
monk = findIndex "monkey" kvs
peng = findIndex "penguin" kvs
terris = insert "pig" "猪" monk

然后在递归的求值程序里，造一个 env table（就是不断复制的 Map）...
这样就能保证『每层都有自己独立的 Map』『每层的 Map 都可以访问父作用域的所有变量』了...

要找符号引用就 findKey，给 body 做 variable binding，递归下去求值在 env 里 insert 一堆 key-value 就可以了

2. 你是和我一样的半吊子，采用了一种非常清奇但是又可行的方法实现

这种方法就是遍历 S-表达式列表，然后替换每个『符号』引用... 对自己实现使用语言的 GC 的依赖更明显一些
不过我开始的时候实现的是一个错的，比如

(lambda (x) (lambda (x) x))

实际上是一个『覆盖』，但是这种情况的话，只要有名称冲突（当然使用真正意义上的 Symbol 的除外）就炸了

正确的方法是，记录每一个 abstraction 的所有 variable binding，只要发现和自己正在填充的项目有冲突，就自觉在离开这个 abstraction 的 body 之前不要填充同名项目（维护一个 stack<set>），等待到时候再填

\x -> (\x -> x + 1) x
equiv \y -> (\x -> x + 1) y

填充完成 body 之后，我们就得到了 body [ x := 1, y := 2, ...] 什么的，可以直接拿去再次折叠求值了（递归下去，到了 primitive operator 那里就可以直接求值，否则再次应用函数，再次 substitute... 最终最多要遍历 n+n1+n2+... 次）

3. 你使用了副作用，类似 Lua 的实现

就是 1. 你实现了完整的 dynamic scoping(准确的说只是 local-scoping) 2. 你的实现还对 lexical scoping 依赖的词法闭包有支持

Lua 里一切作用域都是函数作用域（全局的也是全局函数作用域...）
一大堆 upvalue... 每个 UpValue 在 GC 层面有 open 和 close 两个状态，如果 closed，则代表 UpValue 集合所在的函数实例已经结束运行了，如果没有引用可以 free 掉

Lua 里就是这样：在 one-pass（一遍完成 tokenize词法分析/parse句法分析/codegen代码生成 ）解析的时候，就已经处理好了当前函数的 upvalue 问题（Lua 里只有闭包没有单纯的函数，闭包状态的被称为 FuncState），因为它会对每个符号寻找引用 — 是不是本地变量？（参数） 是不是 UpValue？ 否则就是全局变量。（Lua 官方实现的 singlevar 子程序）

对于每个外部函数(outter function)，你都做好了返回闭包的准备，而且闭包都是封闭的 FuncState 局部状态存储，引用了外层函数的 UpValue

这样自己要新建本地变量（参数） — 直接新建本地表即可
然后要找外层的引用 — 到 UpValue 里面找
交回执行权 — 删掉本地表，UpValue 的引用计数减去 1

UpValue 的创建也可以是即时的，不过不能缓存复用计算结果就很淡疼，到底还是免去了复制的开销...（只是保留了 FuncState，GC 压力还是免不了）

当然也可以不修改拿本地引用的代码，在覆盖/新增 UpValue 的时候惰性创建 Map/Set 记录修改，栈弹出本层执行实例的时候撤销对父级的修改即可。

那么这就是 lexical scoping 的三点，下面是（冰封哥讲过的，我也不说多了）dynamic scoping 的三点

dynamic scoping 有一个不符合直觉的点 — 就是它是看你函数实例嵌套的情况解析符号引用的

Global { g: 1 }

(stack) [
[current]
{ w: 'var1' },
{ v: 'var0' },
] (stack bottom)

你在当前层找本地变量/参数的名字，如果找到则矣，找不到就到父层找... 父层的父层找... （有点类似基于虚表不过没虚表缓存... 面向对象的继承，轻量级的 JavaScript 原型链...）

在不使用高阶函数的时候是看不出区别的（因为一般函数嵌套就是那个样子，和局部作用域对称），
不过这就有一个糟心的，就是产生覆盖的时候，和你要创建闭包的时候 —

(define g "global")
(defun get-var g)
(display (get-var)) ; "global"

(defun get-var-here (g) (get-var))
(get-var-here "overriden") ; "overriden"

看起来明明我们完全不知道 get-var 还有一个叫 g 的参数（本地变量），可它偏偏就冲突了（本来我们希望是 global 的 g，可是由于查找算法的莫名其妙，导致我们找到了『最近被定义』的 g），导致了这种莫名其妙的行为
（当然这个是没有使用独立具有唯一标识性的 Symbol 导致的，但还有一个没法解决的）

(defun konst (k) (function () k))

(display ((konst 1))) ; undefined

看起来不是非常正常，可是实际上运行时，k 就变成了 undefined...
因为 function (k) k 实际上运行时在『动态』寻找对 free variable k 的 binding，然而呢，找不到
你以为引用的是 UpValue 'k'，实际上 konst 的 k 当时没有被求值（因为是动态求值的），匿名函数要找的是作用域栈上最近定义叫 'k' 的变量定义.... 没有就挂了，最可怕的是『有』 — 这样的话你就完全不知道程序是要做什么了....

当然这个如此 trivial 的内容王垠也讲过，所以我不多说了，怎么实现它吧。

一般来说最直接的思路是在调用栈\与之对称的栈上面加上局部作用域表，就像上面的那个 stack 一样
这样两个选择 1. 每一层的所有 K-V 对都从父层作用域复制 2. 每次建立空表或者只包含参数定义的表，需要时再去找，找不到就到父层找、父层的父层找... 当然也可以找到了就在本层缓存下来，不过这有个性能问题。

冰封哥的中文博客上几年前也提到过，就是这个 小 Lice 语言 一般不需要多少参数，
首先就是每层实例建立个『作用域表』，太浪费了，毕竟是 HashMap 啊，为时间优化的数据，建立多了内存分配开销不起

然后几年前的 冰封哥就这么想：

1. 为什么不把这些东西的开销放在『编译期』，先做成 int id 的形式，然后每次去用 id 找本地变量数组/父层的本地变量，不就快狠多（实际上 Ruby 1.9 时期的 YARV 就是这么实现的，有个 (level, slot) ）
2. 或许可以做成 Map<String, Vector<Any>> ，代表『同名』变量在不同作用域有的不同值，可是 Vector 的开销也不小... 何况还是 synchronized 的；此外冰封的一位朋友也这么想

最后冰封哥想到了编译原理教程『龙书』（是 《编译原理、技术和工具》）也提供的一种优化方案 — 在进入作用域前先把这个可能的冲突记录好（比如某某某之前是 undefined、某某某之前是 1 现在被改成了 2），离开作用域就撤销修改（如果没有引入新变量也没覆盖变量就不存在额外开销，而且这个『记录表』还可以建立轻量点，比如可以只是二分查找 Map）
这样全局就一个『作用域动态解析表』了，但却可以有很多作用域。

https://ice1000.org/2017/03/10/DifferenceBetweenMeAndDragonBook/

是两年前的事情了（

当然我快一年前看完后也有点感想，就是为什么一定要把这个『保留备份』的时序放在开始求值 body 之前，为什么不能在需要赋值发生冲突 / 建立新变量键 的时候动态维护这个表，这样就不一定需要一个 let/application 了
当然这也是一种方法，就是 VersionizedMap 喽，有版本控制的 Map... 每次冲突的时候记录、需要的时候回滚
此外单单基于 JVM 也可以把这个 Map 的 Key 做成 『可能是 Any 也可能是 Stack』 的情况，如果是 某种 Stack 就代表变量名称存在冲突，需要选择某个作用域特定的版本


不过，我们都没有想到的是，分配一个唯一标识符『名称』想不冲突在存储程序型计算机甚至世界里都是简单而且低开销的... 我们都不知道，其实全局本来有一个 Map 就足够了，覆盖的情况其实不需要考虑，因为本来就不该是由程序员去考虑这个『变量表』『名称』覆盖问题的....

那么这次的两作用域就说到这里

感兴趣的同学可以再找一下 传参模型 — 传值(by value)、惰性(by name)、表达式(by expr)
和『值』、『类型』方面的问题，比如 Sum type、Product type、value reference/pointer 和 by copy/by ref

Telegram 什么时候支持 strike line 了，我还在用 unicode combination strikeout

̶u0336̶

#music 刚才在网易云听了《黑子的篮球》 OP1 ED1 完整版
啊！！！！！！

然后莫名其妙自闭了，虽然不看不科学的内容 也是 啊！！！！！！
而且科学的 #acg 《排球少年》 也是 啊！！！！！！
对我，就很不科学

说实在话一方面我操作 PC 也不是特别快，而且久坐伤身.... 我得考虑一下
可能以后不会经常学 CS 了 吧。 原因 一年.... 高考

不过还得完成最后一个.... 不知道会不会是今年 最后一个算是那种的呢？

拖延了好久.... 会被人唾弃的吧

最负责任的方法可能是现在 立刻完成 那些插件
以后不要碰电脑，只看手机和 CS 书籍

说实话，我对之前表现的那么差，学习成绩也不怎么样的自己 能够有这些进步 也很满意了
我希望这些进步的确是 已经不止在计算机 的能力上出现了 而且还扩展到了更远的地方

“欠我的”

不得不说，总是要学会学习的... 其实就是从你 不注意的『前端』方面，也会看到不少你觉得很巧妙的解决方式
你之前都不知道，或者存在误解\想的太简单（比如因为我不熟悉图形混成，把 shape 的 Background 当成了一定是背景色、不能是『底下』的 shape... 比如我不知道重复的 shape 可以使用很多 shape 组合成，而且还可以让混成器切掉一些叠合图）
虽然之前的确隐约有这种感觉（迫真自我安慰）
果然实践最重要

如果有喜欢前端的同学，我推荐 《Qt5.9 C++ 开发指南》那本，对（基于 Qt5 Paint 的）图形绘制和混成讲的很清楚。
不过我没有多看，而且说句题外话，我算法也不太好（不会动态规划，dfs bfs 勉强会一点点）

FP.js 是第一个我手写解析组合子的设计/实现
它还存在很多不足，比如错误信息的嵌套本来不应该传递字符串，以更好地表述解析错误的信息
比如 Feeder 架构冗余，而且没有实现本来绝对可以实现的随机 mark/reset
比如语法错误在 possible 解析器里处理的不好，会使得一些错误 unsound 并且导致报错信息莫名其妙；当使用 new Error workaround 的时候更是完全不可取，它还会破坏掉 runParser 的 Either 封装。

未来，如果还有机会，我会用 Java 8 重新实现一个 PEG 解析组合子，新组合子的错误处理将基于嵌套异常捕获计数（这样就可以在不依赖专门语言工具的情况下做到尽可能小的运行时开销）、解决 possible 的『盲目重试』问题（并且也将提供 更多类型的异常，SoundPfail）（补充：其实 def/let/just 的问题只是我个人对解析组合设计的不好而已，这是在讲以后框架上可能的一个改进）。并且将会可能支持一些解析器组合时的优化/动态分支重排序/字符串扫描 SIMD 优化什么的

#blog #recomended https://coolshell.cn/articles/2424.html #statement #OOP

3）Most comments in code are in fact a pernicious form of code duplication.

注释应该是注释Why，而不是How和What，参看《惹恼程序员的十件事》，代码告诉你How，而注释应该告诉你Why。但大多数的程序并不知道什么是好的注释，那些注释其实和code是重复的，毫无意义。

这个观点我非常支持。测试和文档应该描述侧面，不是你的实现本身。写过于重复的代码是愚蠢的，以用户的视角思考问题。

6）”Googling it” is okay!

Google只会给你知识，并不会教给你技能。那里只有“鱼”，没有“渔”，过度的使用Google，只会让你越来越离不开他，你越来越去要去立马告诉你答案，而你越来越不会自己去思考，自己去探索，去专研。如果KFC快餐是垃圾食品对我们的身体没有好处，那么使用Google也一种快餐文化对我们的智力发展大大的没有好处。

这个绝对赞 #statement 我很讨厌（永远只会）有问题就找 Google，抄代码的程序员，这样的程序员没有进步的空间，也说明他们不热爱自己的事业

7）If you only know one language, no matter how well you know it, you’re not a great programmer.

如果你只懂一种语言，准确的说，如果你只懂一类语类，如：Java和C#，PHP和Perl，那么，你将会被局限起来，只有了解了各种各样的语言，了解了不同语言的不同方法 ，你才会有比较，只有了比较，你才会明白各种语言的长处和短处，才会让你有更为成熟的观点，而且不整天和别的程序在网上斗嘴争论是Windows好还是Unix好，是C好还是C++好，有这点工夫能干好多事了。世界因为不同而精彩，只知道事物的一面是有害的。

看本频道的人应该已经在自己设计实现编程语言、DSL 了（跑

9）Design patterns are hurting good design more than they’re helping it.

很多程序员把设计模式奉为天神，他们过度的追求设计模式以至都都忘了需求是什么，结果整个系统设计被设计模式搞得乱七八糟，我们叫这种编程为“设计模式驱动编程”，正如第一点所说，如果你不懂得用自己的大脑思考的话，知其然，不知所以然的话，那么你不但得不到其好处，反而受其所累。

我们应该解决问题，不是崇拜刻板的方法论。最好的是最合适的，不是平均评价最高的

https://coolshell.cn/articles/3745.html #Haha #dev 笑死我了
https://coolshell.cn/articles/3778.html

水管工2：我去拿个扳手。

事主：好！终于！等等，你就拿来一个扳手？可是你们有三个人哦。

水管工1：不这样的，先生！我还是在这里做个初始的Presentation，我一会就走了。但是，我还是会对项目的进度非常感兴趣的。我会打电话过来参加明天的 stand-up meeting。

水管工2 ：另外，和你阐清一下，我们两个留下来的会分享同一把扳手，因为我们是结对水管工……

水管工3：……你能看到这会更有生产率，我们轮流使用这把扳手。并能保证很高的质量以及持续的工作激情！

事主：我没搞懂——你们以前应该就干过这个事了吗，不是吗？500美金的出场费还不能让你们有工作激情？

水管工1：你得想得长远一些，先生。你看，我们可以一起来经历整个过程。这是多么令人兴奋的事！我对此超级兴奋！

#China #Low 🇨🇳 富强！民主！文明！和谐！自由！.... 说不下去了还有7项呢。