从这里开始看哦

有了这些语法定义和之前对 def abc = 123 \ [1,2,3,4] 的解析程序，我们现在已经可以实现这样的语法了：

TheDefLang = {{ Def }}
Def = (<def> Name <=> Value NL) | (<lets> Name Name) | (<just> Name)
NL = '\n'|'\r'
Letter = ('a'~'z'|'A'~'Z'|'_')
Digit = ('0'~'9')
Name = Letter (Letter|Digit)*
Value = Bool | Num | Str | Name | Array | Map

Bool = <true> | <false>
Num = Digit+
Str = <"> char* <">
Array = <[> (<]> | Value { <,> Value } <]>)
KVPair = Name <:> Value
Map = <{>  (<}> |  { KVPair { <;> KVPair } <}>)

Def 语言是一门简单的数据描述语言，你可以定义（全局）变量、引用变量、赋值变量、返回变量。
用啥 XML 呢？？？万能的 XML。

幸运的是，这意味着你已经可以编写 GeekSpec 这样的 DSL 了！（记得 GeekSpec 可是把之前需要两天的『劳动密集』繁复任务量，缩减到了两个小时！）可能过一段时间我会再写更多的，甚至实现一个 ES5 （JavaScript）的解析器... 之前本频道也有教写计算器（动态二元运算符优先级解析程序）什么的

下面我只发实现，如果你还不知道怎么做，请复习一下刚才的内容，动手实践一下
如果还不知道的话，大概是需要时间理解了。

利用惰性导出和代理，来实现递归（没 Y 组合子的好，迫真，虽然 Y 组合子是递归自己...）

那个.... 为了演示方便（REPL 的话也行，因为这门语言不需要跨行的语句）
就只做 Def 本身的解析器 Term 了 😽

也方便大家学习一些（虽然第一次写，所以写的不怎么样）

第一个完全自己写的数据描述语言？ 🤔
编写的直播到此就 告一段落了，接下来是一些语言工具设计的考虑。

真香

很好的功能，国内呵呵。
就凭国内大部分程序员的水平，和小部分真·大佬的速度和创意，想\做不到这种东西

Google 电话应用将允许用户在不说话的情况下向 911 接线员发送信息

https://www.xda-developers.com/google-pixel-phone-911-no-talking/

挺好的功能，国内就别指望了（废话）

至少在信号处理和语音合成层面，国外比国内强很多

三个附加项目 —
0. 如何实现 DEF 语言的 AST Walker 求值器
1. 如何实现 DEF 语言的 REPL（不包含如何给 LookAhead1 流加不需要打两个 <NEWLINE> 即可求值的技术，因为我也不知道，好像很困难或者不容易零开销\太具侵入式）
2. 如何实现 DEF 语言的自动格式化 — 包含两种
一种是直接从 AST 输出、一种是检查 & 自动化提供矫正方案（在某个位置删除几个空格）

首先是咱们的求值器，咱的复用解析器，已经被作为一个 CommonJS 模块包装好了。
下面来科普下，怎么写简单的求值器 — 就是后序遍历语法树。

为什么我们要自顶向下、从左到右解析这个代码呢？因为代码存在诸多分支和不确定，右边最终 reduce 出的结构可能依赖左边的输入字符来决定。LookAhead(1) 也是这个原因（因为不允许重置流，但有时候如果没有手段去重置的话，很多语法哪怕是 "" 字符串都几乎不能实现）

为什么我们要后序遍历语法树？

求值的顺序（AST Walker 对语法树遍历，或者说扩普排序的顺序）有关系吗？
如果保证所有节点都是『纯』的，它不依赖也不改变外部的环境（不是说对子节点的那种『值』的依赖）
则求值序实际上关系不大，因为只有对值本身的依赖

后序是什么意思？

语法的属性上，有综合节点和继承节点的说法：前者的『值』依赖自己的子节点；后者的『值』依赖自己的父节点
因为大部分节点都会依赖自己子节点的值，所以往往要先求值子节点、再父节点

data Add = Lit Int | Add (Add, Add)
sum :: Add -> Int
sum (Add a, Add b) = sum a + sum b
sum (Lit x) = x

— edit: 之前误把这个 Add 定义成 newtype (single product) 了，我没主意到它其实是 sum type(tagged union)... 现在已经修复 致歉

所以要先算子节点，在依据孙子们的值，去解决爸爸（跑

— 所以应该怎么写

咱只需一席话语，̶饶̶舌（跑

考虑一下咱的实际语法，归纳一下呗。然后定义一个抽象语义。

我们的 Entry 是 Term — 就是一个 def|lets|just 项目

Term = DefT | LetsT | JustT

DefT = 'def' _ Name '=' Value
letter = [a-zA-Z_]
digit = [0-9]
Name = letter (letter | digit)*
Value = Name | Bool | Num | Str | List | KvList
Bool(Name) = "true" | "false"
Num = digit+
Str = '"' [any ->]* '"' -- '->' 的意思是 [any - '"']*

ListItems = (',' Value)*
List = '[' ( ']' | Value ListItems ']' )

KvPair = Value ':' Value
KvListItems = ( (','|';') KvPair)*
KvList = '{' ( '}' | KvPair KvListItems '}' )

LetsT = 'lets' Name Name
JustT = 'just' Name

我们认为，这些东西的语义应该是『对数据结构进行组织』
所以：

def name = value 没有值，但是有一个副作用 — 把 value 赋值到全局环境的 name
lets name funame 没有值，但是有一个副作用 — Global[name] = getFun(funame) (Global[name])
just name 没有值，但它把 Global[name] 推入输出值列表

Value:
Name ident 的值是 Global[ident]
Bool 的值是 true / false
Num 的值是 Number 数字
Str 的值是 String
List 的值是 Array
KvList 的值是 Object

就这样，我们的求值程序的目标是逐条语句执行这些代码，操作全局状态机；最终输出 just 操作过的列表。

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

合影留念~

作为一个附属的内容，接下来我说一下作局部用域的问题。 #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 了 吧。 原因 一年.... 高考

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

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