const p = require('./fp').parserc;
let __ = p.wsP(), _ = p.ws0P();

function NumList(l, ws0, rxs) {
this.wss = []; this.ary = [];
this.wss.push(ws0); // {ws0} x...
if (rxs === ']') { return; }
this.ary.push(rxs[0]); this.wss.push(rxs[1]); // x {a}, y, ..
for (let [wl, x, wr] of rxs[2]) { this.ary.push(x); this.wss.push(wl, wr); }
}
let numP = p.someFold(p.elemP('0123456789'.split(''), 'digit'), [0, (a,x) => a*10+(x-'0')], f => 'number value expected');
let pa = p.seq([p.charP(','), _, numP, _], xs => [xs[1], xs[2], xs[3]]);
let List_ItemsP = p.manyFold(pa, [p.makeNew(Array), (v,xs)=>{v.push(xs); return v;}]);
let ListP = p.seq([ p.charP('['), _, p.possible([ p.charP(']'), p.seq([numP, _, List_ItemsP, p.charP(']')]) ]) ], p.makeNew(NumList));
pp = p.run(ListP);

尾逗号的问题是正常情况，因为这个毕竟是 manyFold, 解析到不能匹配了就 fail... 第一个 charP 还是可以解析那个尾逗号的
如果需要不支持尾逗号的话，还需语法变形才行...（当然你也可以设置 pa 的 msgr 为直接 throw error 的那种，所有组合基本都只会 handle pfail，不会 handle msgr 抛出的 exception）

完美

『就说呢，一定是可以做到的！』 这样就有了第一门自己的 markup language！

🤔 JavaScript 不能 copy... 好麻烦哦，我只好弄个函数 来帮忙造新 Array... 毕竟不能一直用一个实例去折叠...

怎么样~ 成功了吗？

接下来，一起实现这门新的 『DEF』 DSL （领域专属语言）语言吧！ #Parser #PLT

使用 FP.js 的解析组合子功能，就可以快速制造各种拥有良好用户界面和错误处理的的 DSL！

就像之前写 GeekSpec 的时候说的：

面向语言编程，是个不错的逻辑。如果你觉得要处理的问题使用某门语言的文法十分鸡肋冗长繁复难看，为什么不创建一门专门的语言来清晰地描述它呢？
在完成这门 『DEF』 DSL 只后，你还可以写更多更好、甚至写的更像一种通用编程语言的 DSL

并且，以后的编程路上，拥有这类 DSL 的能力会让你写出更优质的程序、提升你编程的速度，避免模板代码的编写、完成更有特色的程序...

从这里开始看哦

有了这些语法定义和之前对 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))