左结合：

总不可能这样来『兼容』嵌套的二元运算

add$2
  = num "+" num

add$3
  = num "+" num "+" num

add = add$2 | add$3

也不可能来这样

op = "+" | "-" | "*" | "/"
bin = num { op num }

为啥解析的时就能创建好的结构，非得解析完了再去创建？

当然可以这样

bin = (num|bin) op num

就是左递归，可是就不方便

然后介绍了一个 chainr1 和 chainr1，用来进行表达式树的左结合和右结合

+ 结合性、优先级

* 的优先级比 + 高，就是说 a + b * c 解析后乘法离根节点最远
(add a (mul b c))

+ 的优先级和 + 自己一样高，但是 a + b + c 是
(add (add a b) c)
或者说
(a + b) + c
而不是
(add (add a b) c)

就好像 Lambda calculus 里，默认也是左结合的

f g x 的意思是 ((f g) x) 而不是 (f (g x))
haskell 里也是一个样子，所以要 f $ g x，要不然会炸

+ 所以有啥关系

adds = chainl1 numberP addOp

其中 addOp 是一个 Parser，解析 "+" 返回 (+)
chainl1 会继续解析构造直到无法成功解析

然后就可以组织出这种东西：

1 + 2 + 3

(1 + 2) + 3

或者说，它先解析一个 num addOp num, 用存下来的 lhs (number) 构造出一个 Op 作为 lhs
然后继续往下解析 addOp num, 继续用存下来的东西构造 Op，结果就成了

o' = Add 1 2
o'' = Add o' 3

chainl1 p op = do
a <- p
rest a
where
rest a = (do
f <- op
b <- p
rest $ f a b) <|> return a — rest unmatched

3 + 2 + 1

a = 3
op = (+)
b = 2
a = (3 + 2)
op = (+)
b = 1
a = (3 + 2) + 1
return a

这样，看来我还不是特别理解递归..

最后附赠给大家一点小玩意，从 Ruby 那学的，Ruby 果然是比 Perl 强，后者真的是不规范绝了

dig :: [a] -> [Int] -> b
dig x [] = x 
dig xs (i : is) = dig (xs !! i) is

emmm... 我描述不出这个类型... 不会 Haskell。没想到是这样 😐
算了...

{-# LANGUAGE RankNTypes #-}

printStringOrInt :: forall a. Show a => a -> IO ()
printStringOrInt x = putStrLn . show $ x

main = do
  printStringOrInt 1
  printStringOrInt "Hello"

直接写明 forall
可是不知道为什么，据说是因为有些平常的情况下可能需要 RankNTypes

https://en.wikibooks.org/wiki/Haskell/Polymorphism

foo :: (forall a. a -> a) -> (Char,Bool)
foo f = (f 'c', f True)

好像是可以这样

{-# LANGUAGE RankNTypes #-}

foo :: (forall a. Show a => a -> IO ()) -> IO ()
foo f = (f True) >> (f "String")

main = do
  foo $ putStrLn . show

就是说通过手动指定 Type variable 的 forall 可以使用 N 阶多态，而不是第一次 (f True) 确定了 f 是 Boolean -> IO () 就不允许再次判断了

https://en.wikibooks.org/wiki/Haskell/GADT #Haskell 啊...

辣鸡 Haskell，我还是回去用我的幼儿园 Java 好了

在提到如何解析有优先级和结合性处理的二元操作时，冰封哥也提到了左递归

首先，chainl1 的定义

chainl1 p o = do
  a <- p
  rest a
  where
    rest l = (do
      f <- o
      r <- p
      rest $ f l r) <|> return l

然后，chainr1 的定义，有点像 foldl 和 foldr 啊...
chainr1 就不能尾递归了

要构造 1 + (2 + 3) 这种程序结构，显然不能再『构造这一层，传给下一层组合之用』了，必须得『等待下一层解析完成』再规约到自己身上

chainr1 p o = scan
where
scan = do
l <- p
return $ f l (rest)
rest = (do
f <- o
r <- p
s <- scan
return s) <|> return f


... 好像是我自己写的时候理解不深刻弄错了？
这个是冰封贴的... 我方才才发现其实不必弄那么特殊，不就是保留个调用栈吗？

chainr1 p o = scan
  where
    scan = do
      l <- p
      rest l
    rest l = (do
      f <- o
      -- r <- p —开始我默写的时候多加了个这个... 居然也没觉出什么异常
      s <- scan
      return $ f l s) <|> return l

1+2+3 其实是要组成 1 + (2 + (3)) 的啊！

LLVM Cookbook 里面的递归下降解析器稍微搞基一点，支持自定义优先级，不过要支持的话理解了 chainl1 chainr1 的实现也不难操作，也就是个比大小而已

不过很幸运，要解析现在绝大部分编程语言都是不需要处理自定义优先级问题的，稍微难一点的也就是二维文法和 string interpolation，都不太需要递归

addP = chainl1 mulP $ binOp "+" $ \x y -> Op x "+" y
mulP = chainl1 oneP $ binOp "*" $ \x y -> Op x "*" y
oneP = numberP

对于右结合的例子：

pwrP = chainr1 numberP $ binOp "^" $ \x y -> Op x "^" y

像这样，就可以解析二元表达式了（包括类似 Java 里的 . 操作符）

以上是对使用 Haskell 编写灵活的 Parser （下）文章的简单解说。
感谢相关人员的学习和付出


至于为何左递归就能实现优先级了，我们来考虑一下：

1 + 2 * 3

如果我们完全用 chainl1 的话会被解析成 (1 + 2) * 3
但是我们这么解析

addP = chainr1 mulP $ binP "+" (+)
mulP = chainr1 numP $ binP "*" (*)
numP = satisfy isDigit

题外话，我连 compose 都差点不熟悉了...

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

isDigit :: Char -> Bool
satisfy :: (Char -> Bool) -> ReadP Char

不能是 satisfy . isDigit... 至少，就
b@satisfy = (Char -> Bool)
b@isDigit = Bool
是不匹配的...

回到无聊的正题...

正是因为 addP 的元素是 mulP，所以 + 的优先级就比 * 小（结合 *，但是求值的时候是后序遍历）
或者，如果不是也没有关系，反正可以堆砌很远（直到栈溢出，因为一般来说栈比较小容易溢出）

比如 1 + 2 * 3

先假设没有考虑优先级，仅仅左结合是什么样，方便参考
l = 1
P 1
o = (+)
r = 2
= P (1 + 2)
o = (*)
r = 3
= P (1 + 2) * 3

如果有呢？
l = mulP = numP
P 1
o = (+)
r = mulP
l = 2
o = (*)
r = 3
= P return
1 + (2 * 3)

如果有，而且没解析到 * 号呢？

l = 1
P 1
o = (+)
r = mulP = numP
P (1 + 2)
o = (+)
r = mulP = numP
return (1 + 2) + 3

就得到了正确的结果，因为 chainl1 chainr1 都会在解析不出来的时候（一个 atom，没有 operation）直接返回 atom
这也就是 chainl1 这个 1 的来历

所以 r 在不是 operation 的时候可以直接是 atom （Haskell 里 GADT 树的 Tip）
也就直接导致了合适情况下 mulP 等于 numP 等于正确的结果

data BinTree a = Node (BinTree a) a (BinTree a) | Tip a

Oh 开销...

岂止是『有点』.... emm

祝大家新年快乐（呃...）好吧（）晚安，希望我能恢复快点，不要长痘... 😕

#Haskell #code

这玩意的使用方法：

首先这玩意是个计算器，可以这么玩
Sigma 本来是想当 prompt 的，可惜好像缓冲区刷新有问题

[DuangSUSE@duangsuse]~/Projects% ./BinOps
1+1
Σ:: We got: 1+1
= Just (1.0 + 1.0)
= 2.0

这种。
下面的都是示例算式
Σ:: We got: 1+1*2
= Just (1.0 + (1.0 * 2.0))
= 3.0
Σ:: We got: (1+1)*2
= Just ((1.0 + 1.0) * 2.0)
= 4.0
Σ:: We got: 0xFF_FF_FF_FF
= Just 4.294967295e9
= 4.294967295e9
Σ:: We got: 0xFF
= Just 255.0
= 255.0
0.5*10
Σ:: We got: 0.5*10
= Just (0.5 * 10.0)
= 5.0
3 mod 10
Σ:: We got: 3 mod 10
= Just (3.0 mod 10.0)
= 3.0
2**8
Σ:: We got: 2**8
= Just (2.0 ** 8.0)
= 256.0
log2 16
Σ:: We got: log2 16
= Just log2 16.0
= 4.0
sin 3 + cos 3
Σ:: We got: sin 3 + cos 3
= Just (sin 3.0 + cos 3.0)
= -0.8488724885405782
Σ:: We got: (1+2) * 3 + 3 * log2 8
= Just (((1.0 + 2.0) * 3.0) + (3.0 * log2 8.0))
= 18.0
1/0
Σ:: We got: 1/0
= Just (1.0 / 0.0)
= Infinity

- 一元求逆运算解析我写错了，没法用（一元求逆和 Rat 的 -xxx 字面量语法混淆了，我不该这样的...），暂时算了
有好玩的玩法跟我说，原理上面也写了。

还蛮好玩的，可惜不完整

#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 的，为啥可以这样，一直不懂