关于 SystemStack/ADT Stack/NashronJS 求值结果不一样的问题，现在我经过取样测试发现 ADT Stack 的实现应当有误，而 Nashron 的结果不一样应该是浮点精度（数据类型不一致）造成的

我在 GHCi 和 Node, 以及我平常写的中缀链结合算法(函数式 chainl/r 版本)对相同输入进行求值， 前二者基本完全不同(Node 的浮点应该和 Haskell 的精度不一样，或者它不把 *.0 当浮点数)

至于 GHCi 和上面那个手写计算器的差别，发现是浮点/整数 类型不同导致的， AST 的结合是没问题，所以大可认为我从编译原理书上移植的算法是正确的，但要验证实际相等就要前序遍历，拓扑排序算符链了……

下面我会讲一下 上图的三个 infixChain 版本 以及用 Recursion class 抽象的重写方法， 最近给绝句设计了简单的逆向计算系统，所以有必要检验下，会找时间重写一个 +-*/ 计算器 REPL。

#learn #PL #CS 首先引出问题，什么是操作符链(中缀链)
1+2*3; 1*2+3 ，它们可以被简单理解为以 +-*/ 运算符(操作符)分割的单项
但其实不然，用形式化文法(以『左递归』)应当是这样：

Atom = [0-9]* | "("Expr")" | "-"Expr
Expr1 = Atom "*"/"/" Atom
Expr = Expr1 "+"/"-" Expr1

上面，我们定义了『表达式』和『基元(Atom)』两项，我们以 Expr, Expr1 区分了加减法、乘除法的优先级

但本质上，表达式是由基元和『中缀算符(infix operator)』构成（即便 OOP 的 o.x() 访问也可以是如此），这样更为清晰易懂，也无需使用“左递归”(P = P "x")。
Lua 的解析器会同时处理 unary 一元(如取负)和 binary 二元运算，不过我们认为一元运算和括号表达式就是 Atom ，无需参与运算符链(从而，此链代表了表达式)。

中缀链式结构只是它的形式，并不是它的内涵；所以为了按顺序执行计算，我们需要构造出树形结构—二叉树（之后的求值一般是左右 中(算符ID)访问, LRD）

1+2*3 = (+ 1 (* 2 3))
1*2+3 = (+ (* 1 2) 3)

注意乘法是先算的（离根节点远），而且这个结构还很迷，即便它只是 Expr = "("op Expr Expr")" | Num 的形式而已（所以说算法很复杂）

首先讨论数据建模，我们在算法里必须考虑算符ID(String) 和结合优先级信息(因为有类似 1^(2^3) 的右结合，可以建模为 Pair<Int, Int> 左右优先级、或 Assoc(prec:Int, isRAssoc:Boolean) )

这里选择左右优先级，优点是节约计算，而且如果要 preety print ，检查是否需加括号比较方便
为代码复用可以建立一个抽象类，待实现 readAtom/readInfix/getAssoc/join(op, a, b) 操作

抽象降低过程：
1. readInfix 返回 String, 然后隔离出 getAssocInfo(op: String): Int 信息，可以用符号或奇偶存储左右结合性（这是为了保证频繁调用操作便于定义、无抽象、低计算开销），接着 getAssoc 将其算为 Pair<Int,Int>
2. 不把 getAssocInfo 所存储的 String-Int 映射放在此类中，直接让 readInfix 返回 Pair<String, Int> ；节约一个 Map 对象。
3. 移除 getAssoc, readInfix 直接返回 Triple, 包含算符ID及其左右优先级, 为了方便创建再提供 createAssoc { mapOf("+" to it++, "^" to it.r) } 这样的辅助对象（本来如果不用 Map， getAssocInfo 是动态计算，不该做这样高开销操作，现在不存在选择了）

分步降低的目的是在尽可能不影响可读性的前提下减少计算和内存分配，提升性能。

在上图里：

版本1 是目前 ParserKt 在用的版本（除了不支持右结合外完全一致，我之前没有探索其他方法）
版本2 是更直白的版本1 ，没有用莫名其妙的 null （开始我这么写是因为被 LLVM Cookbook 的代码辣到眼睛了，害怕写出一丁点类似的代码……）
版本3 是类似之前 "ADT Stack" (用 LinkedList 替换系统栈)重写测试的版本，也是 Lua 5.1 的读取算法

三者都不好理解。
1+(2*3); (1*2)+3 的结合必须依靠栈，而输入永远是从左往右(L-R) 的，所以 1+2*3 必须要递归一层， 1*2+3 却一层也不用
这个问题本身也只关于相邻两算符的“操作数争夺”，相等优先级 (a+b)+c 左结合即可，没有偏序传递性之类花哨的逻辑
我们靠递归调用 infixChain() 来做到算法的“加括号”要素，那么“结合”要素的呢？

其实，以上算法结合性的本质都是在 zipWithNext ，长这样：
var a = initial
while (a != null) {
val b = next()
op(a, b)
a = b
}
它的递归形式（例为寻找流里的 a, -a ）：
fun Iterator<Int>.someOp(a: Int): Int {
val b = next()
return if (a+b == 0) a else someOp(a = b)
}
我们看看上面的 infixChain2
fun infixChain2(base: Atom, op1: Op): Atom {
val rhs = scanAtom() // (·b)
val op2 = scanInfix() ?: return op1.join(base, rhs) // (a·b)
return when {
op1 <= op2 -> infixChain2(op1.join(base, rhs), op1 = op2) // (1*2)+3
op1 > op2 -> op1.join(base, infixChain2(rhs, op1 = op2)) // 1+(2*3)
else -> impossible()
}
}
很明白了，如果是 *+, 直接照 base=`*`.join(1, 2) 放到新符的左边继续递归，等 op1==(+) 时读不出 op2, 结果 (1*2)+3
如果是 +*, 就会有一层 `+`.join() 等待递归 op1==(*), 同样在 op2 == null 开始归纳，得 1+ (2*3)

有没有可能优化呢？比如移除 base 参数？
可是没有 base 参数如何把 (1*2)+3 的 (1*2) 组织到 +3 上？可以的。

稍有常识的人就能看出， 在 (op1 <= op2) 也就是先结合的时候，我们的“递归”实际上等于重写参数，并没有创建新栈帧（可以理解为“部分”尾递归，或者说“部分”CPS(靠调用延续执行) 😂）。
infixChain3 就是用循环替代了无递归的部分，不过写得比较不优雅（把它理解为处理 a*b^c 这种优先级升序情况的处理器就可以了，而且优先级链其实也只是参考两项，从左至右 reduce { acc, it -> op(id, acc, it) } 而已）

现在我们看看 Lua 是怎么写的：

op = getbinopr(ls->t.token);
while (op != OPR_NOBINOPR && priority[op].left > limit) {
  nextop = subexpr(ls, &v2, priority[op].right);
  op = nextop;
}
return op;

注意 prec_op2 > prec_op1(limit) 的情况会继续递归读取 (a op2 b)，否则会级联返回到合适层
比如 1*2+3 的情况，看起来在 rec(0) rec(*)| op=(1*2) 时直接返回，实际上它只返回到 rec(0) 的层次， op=(+) 继续读取（……怎么这么像缩进块的读取，原来标准做法是这样么）

code = "a 1 b 2 c 3 d 3 e 2 f".split(" ")
def read(xz):
  x = next(xz)
  return (x, int(x) if x.isdigit() else None)
codez = iter(code)
n = 0
def subexpr(prec_base = 0):
  global n
  print(" "*n, "subexpr", prec_base, end=": ")
  item = read(codez)
  if item[1] == None: print(item[0]); item = read(codez)
  while item[1] != None and item[1] > prec_base:
    try: n+=2; item = subexpr(item[1])
    except StopIteration: return item
    finally: n-=2
  return item

得

 subexpr 0: a
   subexpr 1: b
     subexpr 2: c
       subexpr 3: d
       subexpr 3: e
     subexpr 2: f
     subexpr 2: 
=> ('2', 2)

这种方法只能在直接输出线性结构时使用，它在调用栈里保留树结构信息，但其实它与 zipWithNext 版是等效的。
即便有 1*2^3-4 这种优先级步降不为1 的情况，直接生成 (1*(2^3)) -4 也是正确的。 Lua 递归做法的实质是通过比较基优先级，直接把树（其中包括类似链表而在后序遍历中被铺平的 (a+b)+c ）遍历代码生成写到解析时，等于一次性完成生成和后序遍历（不必模仿，这样也有只可保留线性结构的缺点）

不过还有种用新版 abstract class Recursion 的更优雅的方法，待会发一下

其实我昨天花了四五个小时思考这个问题是失败的…… 本来目的是寻找 bug 来源，我从关于结合优先级最本质的算法开始想（实际上就是函数式 chainl/r 的切分法）而且还做了无数遍距离模拟（对！就是这个浪费时间），最后是没有成功（估计是因为本来就没有问题，当初的Int求值测试也不严谨，应该用算符ID拓扑排序结果的……）

不过我还思考成功了两个问题， Recursion 抽象类该有的设计以及反向计算必须的树路径查找（ findPaths { it !in globals } 这种）

我想最大的收获就是：明白了我在算法上除了更倾向设计的『创意式简单算法』，以及一定的控制流分析/反向追溯能力，完全没法理解稍微麻烦一点的数学思路…… 以后还是别多想吧 😅

🤔 理解了 #Lua 的做法后，我对「精雕细琢」这个词也有了新的领悟。 一个看起来完全不相关的算法，竟然可以拿来优化，真是妙不可言……

细思极恐啊， 这个直接对二元运算链进行后序遍历的算法，只是用了一点递归而已，这样的话无论是指令还是 StringBuilder 的代码生成都不必再次遍历二叉树了…… 只是不知我该不该选它

操作符链的本质是二叉树呢，还是代表优先级队列的逆序表示法呢，真的不明白啊……

但常见的解析法结果是这样：
sealed class Expr {
data class Op(val id:String, val a:Expr, val b:Expr): Expr()
data class Obj(val x:Any): Expr()
}
Lua 的解析法，如果有结果的话，是这样：

sealed class Expr {
  data class Chain(val stack: List<Any>): Expr() //从而避免 chainl/r 再次递归组织计算
  data class Paren(val expr: Expr): Expr()
}

能够自动铺平 (a+b)+c 类同优先级子式，然后可以批量转化/归纳需要提前计算的式子... 虽然整个都用栈就可以了吧 🤔

看起来 Lua 版的 GC 压力明显减小了啊，感觉是不是考虑一下废弃并建议更改更自然的 Expr 树为这种版本…… 反正 Expr 是特殊的，不用 visitBy ，给它提供一个 reduce 方法就可以了嘛 （就要堕落了emm 🤪，我是指 ParserKt 到底应该用二叉树数据还是栈数据，而且如果用的话， Recursion 类应该怎么写呢）

呃，其实 infixChain3 写的不对，它必须 peek 才能做到预判是否直接 expr = op.join(expr, scanAtom())...
修复版本是这样，必须有一个共用变量 op , 用于 peek

fun infixChain3(): Atom {
var expr = scanAtom()
var op = scanInfix() ?: return expr
fun scan(op1: Op): Atom {
val rhs = scanAtom()
val op2 = scanInfix(); op = op2
return when {
op1 <= op2 -> rhs
op1 > op2 =-> scan(op1 = op2)
else -> impossible
} }
while (op != null) expr = op.join(expr, scan(op))
return expr
}

这也太迷你了，我还有一个差不多迷你的，不打算测试了，我打算去看 #acg 动漫《一人之下》了：

class Recursion<LAYER, R>(private val placeholder: LAYER, private val reduce: (LAYER, R) -> R) {
private var top = placeholder
private val frames: MutableList<LAYER> = mutableListOf()
fun mapTop(transform: (LAYER) -> LAYER) { top = transform(top) }
fun newTop(value: LAYER) { frames.add(top); top = value }
fun reduce(initial: R): R {
var accumulator = reduce(top, initial)
for (i in frames.lastIndex downTo 1) accumulator = reduce(frames[i], accumulator)
top = placeholder; frames.clear()
return accumulator
}
}

可以像这样用
val rec=Recursion<Int, Int>(0) { r, acc -> r+acc }
rec.newTop(2)
rec.reduce(0)

举个实际例子，链表化

sealed class Linked<out T> {
  data class Cons<T>(val head: T, val tail: Linked</*out*/T>): Linked<T>() {
    override fun toString() = "$head : $tail"
  }
  object Nil: Linked<Nothing>() { override fun toString() = "[]" }
}

fun <E> List<E>.toLinkedOld(i: Int=0): Linked<E> = if (i < size) Linked.Cons(this[i], toLinkedOld(i+1)) else Linked.Nil

listOf(1,2,3).toLinkedOld() #1 : 2 : 3 : []

fun <T> List<T>.toLinked(use_fold: Boolean = false): Linked<T> {
  val rec = Recursion<T?, Linked<T>>(null) { it, acc -> Linked.Cons(it!!, acc) }
  forEach { rec.newTop(it) }
  return rec.reduce(Linked.Nil)
}

尽管不能做到需要返回地址保存的 a.eval()+b.eval() ，但通过 newTop/mapTop 可以更自然地写部分需要部分递归的算法
而且这个 Recursion object 还可以加 ThreadLocal 复用，不需要每次使用递归函数都分配新 frames: MutableList

看来递归算法还是博大精深，这个抽象根本不可能做到 Kotlin suspend function 能做到的 DeepRecursiveFunction ，只能拿来写类似 infixChain 的这种算法，给它起名为 FlatRecursion 吧…… 因为有 mapTop/newTop 的区分

如果打算不用 Infix 树了，换成 reduce 栈之类的来减小开销， Lua 的嵌套深度算法也可以用 FlatRecursion 抽象来完成，不过必须多提供一个 reduceUntil({ limit < it }) {} 部分归约才行……

昨天晚上突然想明白 #Kotlin 的新 inline class 有啥用了，我之前一直以为就是个 typealias 的语法糖（比如 inline class IntHandle(val num: Int) 不就是其所有成员作 extension val/fun 加个 receiver=Int 么）

才发现即便限制构造器属性的个数为单个，它的类型参数也仍然是有用的，比如可以实现 Either<A,B> 么，这样 Kotlin 就和 TypeScript 一样可以弄 String|Int 的并集类型了？|･ω･｀)

inline class Either<out A, out B>(private val item: Any?) {
  val left get() = (item as? A)
  val right get() = (item as? B)
}

之前我一直不解类为什么可以内联，最开始给绝句设计的内联类，可以有多个构造属性但“不能有this”（就是说只能在局部构造，使用其成员但没法直接用），现在我知道单个构造属性可以特殊处理了。
零开销抽象真是太有趣了！

这两天我想实现最近设计的逆向计算表达式生成（就是把 +* 变 /- 的这种逆序+反向，只是未知只能有一个，具体要实现一个 findPaths { it !in globals } 细节不多说）

顺便也进一步理解了 ParserKt 最常用的结构们：
Stmts (Stmt ';'|newline) -- elementIn
Stmt ('L' Expr '=' Expr) | Expr -- OpChain.disambiguate, Seq(a,b,c)
Expr opChain(Atom, "+- *\")
Atom Int|Name|Paren where
letter [a-zA-Z_]
digit [0-9]
Int {digit} -- Repeat, toDefault
Name letter {letter|digit}?
Paren '('Expr')' -- Decide, Deferred

总结就是 Seq,Decide,Repeat,item,elementIn; Deferred,toDefault,calm 以及这次要测试的 OpChain(包含 .OpTree 和 .LazyStack 的版本, 这次的 DSL 你不给 infixl/r 提供 join 那就默认是 OpTree 了哈, 真给力)
以前 Seq 不是基于 Pair/Triple 的时候肯定还有 Pattern.convert, 哈哈

悟出了一个道理，就是如果对问题的理解不对，技术越高结果乱得越吓人。

在 funcly-ParserKt 的可用化过程中，我了解了如何处理 !(obj.prop[0])+1这种常见的算符链实际上需要左递归(chainl 也行) 不然 !xs[0] 的优先级会错、明白了 Java 的 field/method 成员、 Python 式 name: type = init 如何用 concat(p1, p2) 和 OpChain.disambiguate(Name) { if (peek == ":") /**/} 表达式前缀关键字的消歧义（其实不需要真正的 lookahead 来解决）

加强了 Piped 组合器(包含 showBy,run,greedy,leftRec 等便利组合)，解决了 ParserKt 通往实际可用于 C/Java/JS/Kotlin 解析乃至文本链接/日期/关键词读取的“最后一公里”（迫真）

不过在我解决 LexerFeed 的时候出现了个问题：
首先说明，这个 LexerFeed 是利用 ParserKt 最具特点的 peek/consume() Feed 流预先跳空格的过滤流，利用嵌套流是最近才想到的点子（之前一定要像普通 PEG(parser exp. grammar) 一样非得在 Pattern 里侵入式读取/略过空格 违和感太强，是我傻逼了） （老实说这次重新设计我感觉自己以前的就是傻逼设计，竟然不把 BidirMap 提出来…… 害的存在 PairedTriePattern 这种莫名其妙的东西，简直和因为没有 peekMany 而造成的 StickyEnd 问题一样草）

如果是 C 式辣鸡文法，用单层状态机也就可以了，可咱的 Kotlin 当属语言小王子，我的 LexerFeed 是为下一层的文法定义自动过滤掉所有空格（当然也可以选择保留缩进或者剔除换行，只要不影响语义），这样 "1 + 2" 过一遍就只见 "1+2" 了。

至于 /* */ 式必须再 peek(1) 的注释就需要有请子类 SkipWhiteFeed 处理了，它实现 FeedControl.peekMany （话说我最近的设计对 instanceof interface 用得真多…… 太过分了），当然注释也是可以保留的， SkipWhite 类会有一个 beforeWhites: MutableMap? 保存 AST 对应的前部空白，具体做法是用 pat.alsoDo 。

但 Kotlin 首先支持 "${"a"}b" 这种嵌套模板字符串（现在很多语言如 C#, Groovy 都支持），其次是它的中缀链有不能跳过空格的部分（ a+b*c 你能跳， a to b in args is Boolean 你敢跳么？跳了就变单个标识符了）

对这两个问题， Kotlin 官方“利”用 ANTLR4 的丑陋回答是 KotlinLexer.g4 几乎包含了所有 Kotlin 的文法结构，远远超过词法定义该有的范围，要不然没法处理空格啊呵呵呵→_→

幸运的是 ParserKt 才没有这些破事，作为一个拥有组合解析器优越性和强大生命力的框架，它不必分出什么 tokenizer 和 parser 所以自然不会把 fun :List<T>=1 这种搞混（即便现在我部分隔离出了一个 LexerFeed 流过滤器来跳过空格）

对于第二个问题的前置部分，要么然利用原有 Function 值的解析器来读取需要保留的 字符串/关键词("fun ", "class " 里的空格，但这不科学（ funcly-ParserKt 是基于函数式内联提升性能的，不可能窥见 Seq,Decide 到底得到了。啥参数）

确实可以让部分组合读成字符串或计数的形式，但这样 LexerFeed 必然在下层请求 consume() 的时候从一个队列里拿结果，而且这等于字符串什么的都读了两遍（只能是字符流， "\"s" 这种转义还是要处理），这与 ParserKt 所推崇的 single-pass 解析是背道而驰的（本来递归下降法都会在调用栈上分配相当多的空间了，何必预读甚至多遍处理）

当然也可以选择加个 QueueFeed, 然后在另一线程同步运行 "keep" Pattern, 只要发现在运行就不跳空格，但为保证 wait condition 会调度上，每 accept(peek) 一次都得 Thread.sleep(0) 保证同步，看起来是只过一遍，实际上比过10遍还费资源（而且不支持KJS）。

于是，只能从主动读取的自顶向下解析换成被动状态转移的自底向上…… 只要 state != 0 就不跳空格

我设了几个基于 Array<Int> 的猜想，最后创建了一个基于 MutableList<LexerStateMover.T/*(chars,next,fail)*/> 的编号状态机及其构造 DSL
比如 "\"s" 的字符串可以表达为

val mover = LexerStateMover(s_zero=0)
mover.build { seq("\"") then br("\\" to seq(any), "\"" to seq("\""), any to keep) ) }

这样鬼畜的状态转移式而不定义式（其实也比较巧妙，我给它制订了 charTest 和 action 这些基础功能）

好先说第二个问题，我发觉 Lexer 流根本不可能比 parser 先知道是 "1 +2" 还是 "1 to(2)"，它连合并空格都做不到（毕竟视口只有1）

于是看起来唯有通过 peekMoreWhile {it.isBlank()} 这种黑魔法来做了，它看起来有点像 chunked():

fun <T> Iterable<T>.chunked(chunk_size:Int, op: (T)->Unit) {
  var n = chunk_size
  var list = take(n)
  while (true) {
    for (i in 0..n) op(list[i])
    n += chunk_size
    list = take(n)
  }
}

大概就是不断以 0..i<n 的 list 子集调用 op 且以 chunk_size 为批量来预取，比单层循环每次看 size 够不够再扩充或许快一些。
我应该是魔怔了，竟然觉得这个好像很有意思一样。

后来我发现了个绝妙的解决方案：让解析部分和流部分合作，不必复制粘贴解析器来写分词器。
解析器只负责处理表达式部分的空格，与 Lexer 交换解析状态和跳空格方法
这也意味着状态栈——ParserKt 部分是递归的，所以不止嵌套表达式能读取，字符串内联的递归问题也解决了（如果要跳过可嵌套注释，也能解决）
本来用 action 也能手动实现状态栈，现在给标准化了，嘿嘿(º﹃º )

总之，遇到总觉得不优雅之处还得多想想，或许会有更好的解决方法呢？

kotlin 怎么传 Function<T, R> 的参

1.4给了 fun interface的SAM

说起来我看 ice1k 的 agda 群组常年没人讨论，还打算加两条OT一样的
https://t.me/ice_learn_agda_chat/267

后来发现我这好心根本就是鬼扯，其实人家根本不缺废话；何况我不处理 Haskell/Scala 系语言和其它编程范式的