[GTK+ 3 Reference Manual: GTK+ 3 Reference Manual](https://developer.gnome.org/gtk3/stable/)
[GtkPlug: GTK+ 3 Reference Manual](https://developer.gnome.org/gtk3/stable/GtkPlug.html)
[Widget Gallery: GTK+ 3 Reference Manual](https://developer.gnome.org/gtk3/stable/ch03.html)
[GtkListBox: GTK+ 3 Reference Manual](https://developer.gnome.org/gtk3/stable/GtkListBox.html)
[GtkPaned: GTK+ 3 Reference Manual](https://developer.gnome.org/gtk3/stable/GtkPaned.html)

话说 gtk3-demo , gtk3-widget-factory (竟然还有 GTK Inspector 这种高级玩意), gtk3-icon-browser 都很好玩啊（可惜没有在线资源，想就是有这种实例就够了）
还有 gtk-builder-tool, gtk-query-settings, gtk-encode-symbolic-svg, gtk-launch 以前都没见过

天哪， GTK 还有这种操作（虽然只是让 GDK 用不同后端渲染... 话说 ATK 和 GTK 又和 GDK 是什么关系， GTK 代表平台整体？）

broadwayd :5
export GDK_BACKEND=broadway BROADWAY_DISPLAY=:5
gtk3-demo& gtk3-widget-factory

访问 http://127.0.0.1:8085 即可，看起来是可以做远程视频演示（迫真，那肯定包含多人协作... 只是显式后端而已）
https://developer.gnome.org/gtk3/stable/broadwayd.html

这个“后端”好像涵盖了输入和渲染，所以这里没有 OpenGL ，而且好像是默认为(browser)触摸屏一样

记得以前有个 Android XSDL 的，也可以实现类似的效果，不过那个是 X Server 层面的，这个是 GTK 的显式后端

GTK_DEBUG=interactive gtk3-icon-browser 草 GTK+ 还有这种便利啊…… 像 browser 一样可以 inspect element (条件:libgtk 带 debug flag 编译)... 没想到 GTK 也走出自己的路子来鹅

我TMD 简直是欲哭无泪啊…… 本来以为这破烂四官格不是 GTK 的(怎么可能不是呢)而是由于没有 panel 的全局 drag-drop 状态导致的未解决问题，或者是 Gtkmm(即Gtk+) 自作主张给 PanedWindow(不是，这应该读 SeparatedWindow 吧) 加了这个辅助创建新 Panel 方向的特技，没想到竟然是 Notebook::header 里加了个 GtkTable... 特地这么设计的么？ 而且还没用流行的 Grid（吐嘈的点很奇怪啊）

要解决也很简单。 所谓的 Panel (带 TabWidget 的 DockWidget) ，每个的最右都默认带上这个 vcenter 的 GtkTable, 不过默认不显示
加一个 MainWindow (GtkApplication) 层面的 bool ，只要有 Panel 被拖拽，要么在 drag-over(drag-motion) 里检查并显示要么维护一个 Panel 列表然后每次 drag 去 foreach 显示， drop 或 drop-fail 时再隐藏就好

真搞不懂为什么要做成一直显示的设计，难不成是复制粘贴的代码太多了，连 PanelBox 也没抽象出来？ 🤔

https://developer.gnome.org/gtk3/stable/gtk-migrating-smclient-GtkApplication.html
不知道为什么，虽然自动化程度一般，我突然觉得要设计那个什么『鸿蒙操作系统』， GTK 的大佬都比蛤为有发言权…… 至少人家知道怎么给桌面应用程序提供它们需要的 service

#Kotlin #lang #Java #PL https://t.me/kotlin_cn/14006

let a=v in expr 是函数式 #FP 里常用的“赋值”方法（但不能重赋值，本质上类似内联的局部函数调用，仍属表达式）

仔细想一想，换成语句的思路也可以：
stmts.foldRight(Return) { expr, s -> if (s !is Assign) s else LetIn(s.variable, s.value, (expr as ExprStmt).expr) }
当然前提是都是表达式语句，的确可以这么弄啦，不然得用 run block

最近莫名想到了操作符链/二叉树 处理的一些问题，现在来讲讲

关于 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