还蛮好玩的，可惜不完整

#thinking #life #China 🤔

我觉得我之前有一次关于『儿童编程』提的建议不好。

虽然就儿童编程来说，我也算是老人了，我小学六年级在一位朋友的带动下认识了 Scratch、并且之前一段时间还去听过网课，但其实之前我的人际交流能力有很大的改善空间。

公交车上，一个带小孩的妈妈看到我拿着 Kotlin 极简教程这本书后，问我『这门语言是有界面的吗？』

我只后的回答果然还是极简... 说了一大堆，就是坦明有没有界面和是什么语言没有关系而已，这丝毫没有参考价值。

这种交流... 势必没有什么效果。

其实考虑到这位母亲的需求，应该是想给小孩找一个编程培训班，我本来应该给她提点相关的建议的，可是我却只是考虑到了技术上的问题，这就叫浅薄。

因为技术本来就是为生活而生的，不应该去抛开别的单单当一个疯子（排除合作的情况下）


其实，这么答或许才是真正好的：

呃，如果你说的界面，是指平常用的电脑上那些窗口、界面的话，其实和什么编程语言没有太大关系。

不管是新语言、老语言现在基本都可以做上面所说的那种界面，对于普通人来说能接触到的语言都可以写界面。

不过如果一定要给个建议的话，如果以后想让孩子能写『界面』，我建议不要学 C 语言，C 语言比较繁琐，编程效率很低，而且新手不容易写好，不适合用于入门选择。

现在有很多编程培训班，不管是网上的还是传单上的，基本都会提供很多课程选择，他们几乎都会提供能做出好看东西的课
不过和上面说的界面有点区别，更类似能交互的动画一些、编程的时候也可能是有界面像堆积木一样编程的，我觉得这个选择可能比较好，
如果要这么选，最好是选有创新、有资质、有自主研发产品的公司，不要相信说自己使用『外国技术』的，这种往往比其他的课好。

刚才阅读代码加强理解的时候忽然发现不对，这个 chianr1 怎么和 chainl1 是一样的，对着冰封的博客，发现我写错了...

r 要改成 scan

改了一下还是错的，然后我就上 Haskell 的 Text.Combinators 源代码抄了... 觉得没区别啊..

弄了半天冰封哥也写错了... 🤪

我当时就想加个 return $ rest f l r... 不行，看来我还是 naive
不过还是隐隐约约有点感觉的（因为我注意到了要利用调用栈归约出右结合的树，既然右边是 rhs 解析结果那么自己肯定得先返回，结果冰封发的这弄成递归下去了... 结果为啥就和 chainl1 的没区别...）

不过是一个 return 之差，是递归还是返回：

chainr1 i o = scan
where
scan = i >>= rest
rest lhs = do
f <- o
rhs <- i
return $ f lhs rhs
<|> return lhs
—
chainr1 i o = scan
where
scan = i >>= rest
rest lhs = do
f <- o
rhs <- i
rest $ f lhs rhs
<|> return lhs

就酿成了奇妙的惨剧，这是为什么？

我们来符号抽象执行分析一下

首先我们有 numP

numP :: ReadP Int

有一个 (^) 运算解析器

powOp :: ReadP (Int -> Int -> Int)

得到一个 chainr1 Parser

powP = chainr1 numP accentP

然后 runParser

putStrLn . show . (runParser powP) $ getStrLn

输入 1 ^ 2 ^ 3

第一个 chainr1 程序

i = 1
lhs = 1
f = (^) — pow 1 ...
r = <scan>
i = 2
lhs = 2
f = (^) — pow 2 ...
r = <scan>
i = 3
<|> return 3
return $ f i r — pow 2 3
return $ f i r — pow 1 (pow 2 3)

然后开始回溯，最后 unmatched 的值成为上一层 operation 的一个参数

生成

let pow = (**) in
  (pow 1 (pow 2 (3))

正和我们的希望

然而如果用 rest 继续递归而不是 return 呢？

就是下面一副景象了

lhs = 1
op = (^)
rhs = <scan>
lhs = 2
op = (^)
rhs = <scan>
lhs = 3 => rest 3 (unmatched) = return 3
rest $ op lhs rhs — rest (2 ^ 3) = return (2 ^ 3)
rest $ op lhs rhs — rest (1 ^ (2 ^ 3)) = return (1 ^ 2 ^ 3)

... 这是有什么问题啊...

GHCi, version 8.2.2: http://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling Main ( BinOps.hs, interpreted )
Ok, one module loaded.

*Main> runParser (chainr1 numP $ binOp "" (-)) "3 2 ** 3"
[(3.0," ** 2 ** 3"),(1.0," ** 3"),(4.0,"")]

*Main> runParser (chainr1 numP $ binOp "" (-)) "3 2 ** 3"
[(3.0," ** 2 ** 3"),(1.0," ** 3"),(4.0,""),(-2.0,"")]

我利用 readP_to_S 看了一下匹配回溯栈...

(3 ** 2) ** 3 = -2 其实是 (-) 算的... 忍者吧
可
3 ** (2 ** 3) = 3 - (2 - 3) 才是正确答案，chainr1 定义有误

看一下他们的栈前三项
l=3.0 r=" ** 2 ** 3"
l=1.0 r=" ** 3"
l=4.0 r=""
都是一样的
区别仅仅在于最后一次归约的时候... return 和 rest 才有区别，虽然我以为 rest x 在解析不到的时候就 = return x 的... 所以不应该有区别

猜想一下，正确的答案是

(sub 3 (sub 2 3)) = (sub 3 -1) = 4
这是 return

parse 的时候，显然应该是这么规约的

scan @ "3 — 2 — 3"
return lhs=3 f=(—) rhs=scan <return (—) 3 (2 — 3)>
return lhs=2 f=(—) rhs=scan <return (—) 2 3>
return lhs=3 return 3

错误的是

(sub (sub 3 2) 3) = (sub 1 3) = -2
这是 rest...

3 »= rest f=(—) "2 — 3"
= 2 »= rest f=(—) "3"
= 3 »= return 3
rest (... 2) — 3
rest (3 — 2) — 3

... 我真的不知道是怎么 match 的，为啥可以这样，一直不懂

注，同样的输入真 chainl1 和伪 chainl1 是有区别的

chainl1:
[(3.0," 2 3"),(1.0," ** 3"),(-2.0,"")]
chainr1:
[(3.0," 2 3"),(1.0," ** 3"),(4.0,"")]
wrongChainr1:
[(3.0," 2 3"),(1.0," ** 3"),(4.0,""),(-2.0,"")]

chainl1p "3 - 2 - 3"
= 3 "- 2 - 3"
= 1 "- 3"
= -2

chainr1p "3 - 2 - 3"
= 3 - chainr1p "2 - 3"
= 2 - chainr1p "3"
= 3
-> -1
-> 4

—
chainr1w "3 - 2 - 3"
= rs@(rest $ p op rs) +++ return p
— {a '+'} b
rest $ 3 -
rest $ 2 -
return 3
=
<return>rest $ 3 - (<return>rest $ 2 - 3)

chainr1 有一次归约出了正确的结果，可不知为什么好像又在输入已为空时重新做了什么...
唯一的解释就是递归的方式不对...
突然想到，这好像是信息学问题

解析器的栈和系统栈加起来就是反的，所以系统栈本来应该是 O(1) 才对（尾递归的）
所以才两边 return，让做尾递归优化？

所以 foldl 这样的顺序才不会出错，否则顺着解析器的匹配，就像是顺序颠倒了一样?

rest $ 3 - （第三个匹配
rest $ 2 - （第二个匹配
return 3 （第一个匹配
= (3 - 2) - 3

... 真心糊涂了

可怜兮兮面向排错编程 #debug duangsuse... 😭

后来我看看，发现最后一次归约的时候（本来应该直接返回），居然没有停下，而是又解析了一遍...

最后一帧的情况就是绝对不该出现的，不可能有一个

chainr1.rest

出现 l = 1.0 / r = 2.0 的情况
输入可是 1 - 2 - 3，只能有 1 - (-1)
(1 - 2) - 3 这明显没有正常使用调用栈！

我收集了一下可以用于排错的信息：

Stopped in Main.chainr1.rest, BinOps.hs:197:7-22

_result :: ReadP Double = _
mid :: Double -> Double -> Double = _

l :: Double = 1.0
r :: Double = 2.0

l :: Double = 2.0
r :: Double = _

l :: Double = 1.0
r :: Double = _

l :: Double = -1.0
r :: Double = _

很奇怪，为啥有时候 r 是 _ 有时候是直接的结果？

推演一下，按照顺序

1 - 2 - 3
可能是 (1 - 2) -3 = -4 或者 1 - (2 - 3) = +2
[(1.0," - 2 - 3"),(-1.0," - 3"),(2.0,""),(-4.0,"")]

先算了 1 - 2 = -1
然后是 2 - ? （或许是 3？或许是 1？）
然后是 1 - ? （或许是 -1？）
然后是 -1 - ? （明显是 1 - 2 - 3 的错误结果）
结果居然是 -4？

#fix #haskell #fp #cs #wip #recommended #saved 这个问题，暂时就说到这里了

以后有机会我会跟冰封哥说... 看看他知不知道为什么
先做更有价值的事情

我也真是醉了，看了 #Monad Parser 是很迷啊

留影纪念，chainr1:rest 和 chainl1:rest 的区别只在 rhs 是 scan combine 自己还是 scan {+ 1} 这种

#tool 计算器最终版（

#Haskell #cs #pl #parser

duangsuse 的打算，从现在就开始做：

✅ Parser 写了不到一半，emitter 正在写，框架代码抄了正在研究是怎么工作的
1. Haskell 写 JSON 处理算法，还要把一个 Monad Parserc 框架的代码手动抄过来

1.5 抄！把某篇 Hindley-Milner 类型系统的推导算法教程里的 Haskell 代码抄下来！

2. 写 BinaryStreamIO

还要附带 Aapt 资源的 parser，因为找不到规范，直接抄 sdklite/aapt 的好了（炒鸡好看）
和 JVM / Dalvik 字节码处理框架，Yes

别人的巧克力重写了就是我做的巧克力（逃跑

3. 写 Java 8 的 TextCombinator 库，

还要附带 TrieTree、RangeMap、VersionizedMap、MultiMap 等算法
用来做 IDE 支持这样的工作

4. 写 Markdown 解析器

5. 练习 Qt 或者 Java Swing / AWT 的技术，反正就是 Desktop GUI 的技术...

6. 利用 TextCombinator 写一个 NaiveCat 的解释实现

NaiveCat 是简单版本的 Cat，后者比较详尽的定义已经在这里有几面了
NaiveCat 没有诸如 Coroutine、Lazy evaluation 这样的特性，算是半函数式半面向对象

配合新解析器框架刚刚好

然后我就是顺手用 readline 包完善了一下，然后发上了 GitHub... 求 star...（跑

看来第四条还真有点要命....
https://spec.commonmark.org/0.29/

有一个小细节： #pl #algorithm

提到 pretty，虽然我们可以把

Add
Rat 1
Rat 2

这样的树给安全地输出成 (1 + 2) 的形式，但是肯定还是有人嫌太长（括号根本不需要）

但是如果输出成 1 + 1 的形式呢，就会出现下面的问题

(2 + 1) * 2

本来是
Mul
Add
Rat 2
Rat 1
Rat 2

你这么一整，就成了
2 + 1 * 2 了
Add
Rat 2
Mul
Rat 1
Rat 2

语义不对。

有两种解决方案，一是对于每个二元子节点访问，dump 后再 parse 一遍，结果相同就返回无括号版本，否则返回有括号保险版
优点是肯定有效（而且不需要专门写解析器外的算法）
缺点... 我就不用说了，别说 Haskell 里那个 Text.ParserCombinator.ReadP Monad 解析组合子了，其他的非得再解析一遍，咸得🥚疼

还有一种方案可以处理这种问题（排除二元 / 一元在一起的坑爹情况，不过其实也都是一个道理，判断出要加括号的 case 加括号，不加的不用加）

要输出 (2 + 1) * 2 这个树，其实就是访问 Mul 节点的时候，判断一下子节点是否打破了运算符优先级

如果是正常情况，+ 的优先级没有 * 高，所以往往 * 是 + 的子节点，而不是上面这种情况

推广来说，就是发现自己左节点优先级没有自己高，就可以不带括号输出，相等则要看结合性情况（左结合右结合都要判左右手，判自己的就是左结合左手应该是自己、右结合右边应该是自己，否则就打破了结合性）

输出 (Mul (Add x y) y') 这种的，就给子节点加上括号再输出

"(" ++ dump x' ++ ") * " ++ dump y'

就不会有格式化错误的问题了


最后一段属于推销可以不看（

当然有没有第三种方法呢？档燃有啊！
就是使用 RangeMap 和 ReverseMap，在解析的时候就加上空格信息（当然也包括括号信息）喽！
然后保存这些信息，到时候如果要输出可以复用