一位dalao说过，在神经网络架构中
神经网络就是一个含未知参数的程序
正向传播就是运行这个程序的过程
反向传播就是寻找最优的这些参数的过程

然后就要对权重w求导、梯度下降、可非线性逼近
还有什么J=E(J)的，不知道是啥玩意的公式，E(_)是能量？

神经网络就是由一堆抽象神经元构成的网络
神经元是一堆 y = f(wx+b)
递推计算公式是
y^{k} = f(\sum^n_{i=1} w^k_{i} * x^{k-1}_{i} + b^{k})
然后 k=0 是输入层

前馈好简单啊，隔壁的大佬10分钟不到就推完了前馈和CNN
Toeplitz matrix 是什么，relu 和 sigmoid 激活函数是怎么定义来着…… 数值稳定性怎么样……
Markov 链怎么实现一个……

最好还是结合数据分析和DIP来实现，才能做到效果
可是以我写一个 Montage.py 都拖了好久的速度是很难完成的！虽然我在学校里都设计半天了

隔壁的大佬开始谈起信号和噪声甚至能量了，好慌
感觉和知乎上就着1+1谈起范畴论的大佬有的一拼

自底向上构造解析结果的解析器看起来好麻烦啊，虽然各种parser compiler也不是很困难
但我还是觉得递归下降法最方便啊，因为可以直接用Kotlin写类似DSL的效果啊(EmbeddedDSL)，虽然基于LR的解析组合子也不是没有

有一天，他电话面了一下Facebook，电话面了15分钟后对方就放弃了，他受到了严重的打击。然后，他就开始找菲利宾人练英文口语了，我也让他做算法题，然后，他才发现，一道连算法都不是的纯编程题都提交几次都过不了，等他做完了Leetcode最初的那151道题后，整个人都改变了，写代码前认认真真地在纸上把程序的状态，处理时序以及可能遇到的一些条件先罗列出来，然后，进行逻辑设计后，再写

https://coolshell.cn/articles/20276.html

是啊，如果你不先想方设法设计好了再写，还能怎么写程序哩？
上手就是干，尽管比那些根本干不成的人强，但是能写的程序，也就是自然语言两句话说明白的东西而已，又有什么了不起？
好的程序员的重点永远不是在代码上，而是在『我要写什么』这件简单的事情上，所以才有代码可视化、代码质量、可移植性这一说。

虽然皓哥是架构师，但是你会发现他的观点真的是非常有理有据；尽管不一定都是高精尖，却能够鼓励更多人在日常的『小应用』『小平台』里干出更好的效果，这也是相当有价值的一件事

告诉大家一件很有意义的事：
我给 pr.py 加上了 --srand seed 和 --use-srand 选项
然后呢？我发现，由于不知道什么原因，即便 seed(a) 提供了一样的 random seed 也不能保证生成结果一致可重复。

而且由于它的代码过于繁复，连一点可维护性都没有，想分析和修改没有两把用IDE的刷子真是难上加难。
连修复都不可，因为不知道 import random 都是在哪里被使用的，
即便我能保证算法的随机性（非幂等）全由 random 库提供，不存在任何其他变数也还是不可。

所以不要再去写一些烂代码了，这是两次被烂代码搞崩溃的我的忠告。

这种代码毫无疑问是破烂代码，我们要以它这种脚本化的风格作自己的警醒，一定不能写出这样的烂代码来。

好吧，开个玩笑；不过还是要尽可能写好看点的，显然这样的逻辑过分密集、顺序依赖不够清晰，尚存改进空间。

#PLT 现在咱来讲讲过于中缀链解析的问题，然后我就只需要写Kotlin Parser和Binarie二进制组合解析库了……

（怎么觉得有点懒得讲）首先这个中缀链呢…… 就是 1 + 2 * 3
这里我们谈的是就解析传统的编程语言来的那个中缀链，所以不提及逆波兰记法(reverse polish notation)和前缀记法什么的。

尽管我们会谈及一些形式化文法方面的例子，但这里不是讨论解析算法的。本文使用的是传统的 recursive descent 递归下降自顶向下(top-down)解析。

首先我们看看Haskell人一般怎么处理……
先看看几个操作符：
+ foldl, foldr
+ chainl1, chainr1

foldl 呢，比方说，你想把 [1, 2, 3] 整成 [[[0, 1], 2], 3]，这很简单：

fl xs = foldl (\l x -> [l, x]) 0 xs

好吧，Haskell 不让你这么搞，因为没法描述 ……[[[[[[[a]]]]]]]……(无数个方括号) 的类型…… 尽管你可以用 Algebraic Data Types，无奈。
foldl1 实际上就是 \f xs -> foldl f (head xs) xs ……
那么如何把 [1, 2, 3] 整成 [1, [2, [3, 0]]] 呢？
fr xs = foldr (\x r -> [x, r]) 0 xs 就口以了
（当然，除非你用 Python 否则还是不行……我懒得再定义ADT了）

那么我在说什么呢？其实我是想让你理解结合性(associative)是啥意思。
+ (+) (-) (*) (/) 全都是『左结合』的，这意味着在不考虑优先级的情况下他们默认以 ((1 + 2) + 3) 的形式被解析
+ (=) 如果把它视作运算符，那它是右结合的，因为 a = b = c 这么写，实际上是表达 a, b 皆等于 c (a = (b = c))，不过这样赋值的操作就要有值了……
+ Java 里的 (.) 实际上是左结合的，要不然 user.name.charAt(0) 在没有 user 的值的情况下，何得 name？
一般来说 (**) 乘方运算也是右结合，不过我觉得这个不太自然所以没作例子。

那么这个玩意又有什么用呢？我们看看 chainl, chainr，当然定义就略过了
+ chainl1 op item 解析就是 chainl1 op item = item | (chainl1 op item) op item, 这个可以左递归（换成PLT的概念就是尾递归）优化
（从左往右扫描）它构造的就是所谓的 [[1, 2], 3]
+ chainr1 op item 解析就是 chainr1 op item = item | op item (chainr1 op item), 这个不可以左递归
它构造的就是 [1, [2, 3]], 什么？你问可不可以左递归地构造这样的结构？我不知道，但至少

foldl1 (\l x -> [x, r])

只能弄出 [[[0, 3], 2], 1] 这样的
+ 至于为什么 chain 还要有 "1" 这种情况，考虑一下 (1 + 2 * 3)，你会发现那个和 let c = 3 in (1 + 2 * (c)) 是一个意思，我是说 (? * _) 里的 ? 显然可能是 atom(也就是item) 或者另一个 (*) 是不是？
这也对应了二叉树的结构：要么然是叶子 (Leaf x)、要么然是根 (Branch a b)。

那么既然知道了Haskell里怎么做，我摘录一点基于 Haskell 解析组合子的代码自己思考：
https://github.com/duangsuse-valid-projects/BinOps/blob/master/BinOps/Parser.hs

-- Operators
-- + - * / ** mod
-- 下 equation 全都 :: ReadP Ast
exprP = ws0 >> addSubP
addSubP = chainl1 mulDivP (addOp +++ subOp)
mulDivP = chainl1 pwrModP (mulOp +++ divOp)
pwrModP = chainr1 unaryP (pwrOp +++ modOp)

呃这里 (+++) 是下文 A / B 文法分支的意思
(p0 >> p1) 就是 Haskell 的 fmap 啦，这里是『解析完 p0 了再去解析 p1』的意思。 (比如 OOPS = kw "OO" >> kw "PS"……
当然Haskell作为Functor/Applicative/Monad纯函数语言是不会有太多Mutable数据的，那个解析器是基于backtrace和惰性链表弄的。

那么聪明的人显然会忍不住地想到PEG文法也是用左递归达到带优先级解析二元运算的效果的：
https://pegjs.org/online

Expr = Term (_ ("+" / "-") _ Term)*
Term = Factor (_ ("*" / "/") _ Factor)*
Factor = '(' _Expr_ ')'
  / Integer
Integer = [0-9]+
_ = [ \t\n\r]*

不过这个不一样：它只可以做到左结合，而且还是用 reduce 函数的（也就是说它没直接在解析器的层面做『结合』）：
[1,2,3].reduce((base, num) => [base, num])
你会收到 [[1,2], 3]。
那么它是怎么做到的呢？还是看看 (1 + 2 * 3)。

首先我们来解析它：
exprP 1 + 2 * 3
= addSubP 1 + 2 * 3
= ...n次递归alternate直到Literal解析器
= mulDiv (Literal 1 {...n次递归后}) (+ (Literal 2) ) * 3
= (Add (Literal 1) (Mul (Literal 2) (Literal 3))

好吧，其实不好说（因为每次递归选择的栈都太长了）
不过注意一点：

InfixC = Add
Add = Mul '+' Mul
Mul = Int '*' Int

重点是：
(0)一个注释：上面的PEG文法不是左递归而是直接循环了，所以不需要递归 Expr = Expr / Term (+/-) Term
实际上这也就相当于 Expr = (Term/Expr) (+/-) (Term/Expr)
不过前者不需要多层比较dummy的分支
(1)'+'在解析的时候给了Mul直接结合的一次机会，当然也给了下一个 '+' 结合到自己身上的机会
(2) 只要 (1 + ^2 * 3) 解析到 ^ 这里，很快你会发现它是一个 Mul，而不是一个 Add，所以高优先级的是作为被结合的项目放在 AST(Abstract Syntax Tree) 里面的
(3) 其他情况，或许 ^ 后是一个 1、一个 () 括号表达式（你可以认为它以 '(' 起始，然后把中缀链里到 ')' 的部分孤立了出来），都有可能。而被解析的Mul也会递归运行，只要程序的定义正确你不需要担心它不能正确解出文法结构。
(4) 如果是 (1 * 3 + 2) 这种呢？这就是属于解析器算法(LL(k)、递归下降、LR 什么的)问题了，是实现细节。

所以说了这么多，我们谈谈怎么用Kotlin写计算器吧……（也就是我要引入这次用小技巧来优化的递归算法）

计算器很简单：

Expr = AddSub
AddSub = MulDiv [+-] MulDiv
MulDiv = <int> [*/] <int>

这里为了方便我们不使用scannerless parsing的风格…… <int> 表示它是一个有状态存储的 Token 的意思，而 for、void 这种就是『无状态存储』的 Token。
（不知道是不是有点不良实践了，emmm）
Scanner: java.util.Scanner.

为了节省时间我只写一个复用抽提程度比较低的版本：

import java.lang.System
import java.util.Scanner as Lex

val input = Lex(System.`in`, "UTF8") //.useDelimiter("[\\+\\-\\*/]") // 好吧，我才知道delimiter不会next给你
//... 鉴于Java Scanner实在是太过弱鸡，暂时不支持不加空格的情况。

typealias Join = (Int, Int) -> Int
/** [prec]: Ascending order */
enum class Op(val prec: Int, val join: Join) {
  `*`(0, {a,b->a*b}), `$`(0, {a,b->a/b}),
  `+`(1, {a,b->a+b}), `-`(1, {a,b->a-b})
}
// 不准吐槽骚 Op 定义法…… 不过由于 `/` 这个名字依然是非法的（下文必须用到 Enum 类上自动生成的valueOf String），所以这里暂时通融一下，($)=(/)。

object Calculator {
  val terminateKw = "." //同样是一个通融，因为计算器很简单不好选择中缀链的终止符号(也可以选EOF但我不喜欢)，为了方便起见选择这个
  // 1 + 2 * 3 .
  @JvmStatic fun main(vararg arg: String) {
    scanInt().let(::infixChain).let(::println)
  }
  // 鉴于单纯LL1无法处理两个字符的中缀算符，
  // 为了优雅性不得不把上一次为了比较结合顺序的算符解析结果传来传去的
  // 不过如果没有也不影响
  private fun infixChain(base: Int, op_left: Op? = null): Int {
    val op1 = op_left ?: scanInfix() // '+'
    val rhs1 = scanInt()
    val op2 = scanInfix() // '*'
    return when {
      op1.prec <= op2.prec -> infixChain(op1.join(base, rhs1), op2) //(1+2)*3, 没事
      op1.prec  > op2.prec -> op1.join(base, infixChain(rhs1, op2)) //1+(2*3), 被人抢跑咯~
    }
  }
  private fun scanInt() = input.nextInt()
  private fun scanInfix() = Op.valueOf(input.next())
}

(大意，可编译版本过会发文件)

这里我们使用了『上下文相关』（个🍺）解析法…… 算了其实是无关，但是有这样的优化。
所谓的上下文就是 base, op1, rhs1, op2 啦，其实也不能算上下文，它就是见机行事好然解析过程更高效而已
这个解析算法算是经典的递归下降…… 不是很好理解吧？不如上面好理解吧？这就对了……
想想它是怎么解析 1 + 2 * 3 + 1 . 的，递归调用是这样，其他自己想吧：

scan(1, null) 

//op1=(+), rhs1=2, op2=(*)

  scan(2, `*`) 

//op1=(*), rhs1=3, op2=(+)

  scan(6, `+`) 

//op1=(+), rhs1=1, rhs2=[done]
//return (+) 6 1
//return (+) 1 7
就是这样，那么又有什么可以优化的呢？？？

不是能力下降……不是能力下降…… 是我的IDEA最近Tasks有点毛了，改代码总是忘记重新编译，造成各种古怪问题行号不对称后来才发现

最近手越来越生了，Peek(Iterator)里简单的时序都看不出来，consume()方法写错了，呵呵。

既然都这么弄了，还不如直接把优化写成代码算了……

这个是无优化版本的四则计算器

所以先梗概一下：其实这个所谓的优化就是显式的递归栈。

我们知道这个二元链解析器是这么工作的：

1+^2*3

每层我们都结合一个中缀[(a+b)什么的]。我们扫描到^的时候，会向前看一个中缀，目的是判断rhs1(这里的"2")该和谁结合
+ 如果 (+) 的优先级大，(1+2)
+ 否则(*)的优先级大，1+ (2*...)
注意上面的， (2 * ...) 这已经暴露了递归子程序需要的参数了：一个是 base (左边的那个表达式)、一个是 (*) 运算符
当它不是作为第一个解析器解析的时候，op_left 为空，就自动运行 scanInfix()，得到第一个 infix
当然也可能得不到，这是属于当前不是 infix 链的情况（一般所有的编程语言无论传统还是函数式还是啥子的，值基本都是表达式链表达的，所以也可能是一个单独的表达式）

在这个过程中，为了能够看到前面的一个op(op2)我们要多consume() 一个，但是这个很可能会失败。
举个例子，上面的 ...(2*3^) 扫描的时候就会找不到后面的op2，就必须返回 op1(base, rhs1) 的结果，而且你递归下去 infixChain(op1(base, rhs1)) 也不能少写这点代码，这是不可以省略的。

但是 rhs1 不可能失败，如果失败了就属于用户输入了 (1+) 这种不完整的中缀表达式。

所以怎么样呢？我想说，直接用数据栈而不是系统的调用栈建模递归会更高效一些。

比如说（当然是对于 1+(2*...) 这种等右结合的情况），这里我们为了保证递归回溯的时候能正常，不得不保留全部的栈帧变量：
+ base，op.join 的目标A
+ op1，op.join 的目标B
+ rhs1，这个已经非必须了
+ op2，这个也已经非必需了

其实这个栈帧的体积是可以缩小一半的（其实栈本来就应该是 [(1+), (2*3)] 这种形式）
然后我们利用面向对象的抽象，可以非常容易第弄出一个 Recursion<T> 数据结构，在上面用 mapTop 操作可以实现 tco、add 操作来增加入栈、reduce 来对 LIFO(LastInFirstOut) 进行归约就好了

return stack.reduce { x, r -> when (x) {
is Base -> x.expr
is Tail -> x.join(r)
} }
就可以鸟。