#Algorithm 可算是让我给试出来了！

我以后再也不想用这种方式写代码了…… 它首先代表你对问题的理解很浅显和薄弱；其次显得你很辣鸡，因为你和那些脚本小子没有本质上的区别，都是依赖机器编程。

比如这个问题，有心的朋友会发现我上次写的 mid = end - begin / 2 (我还怀疑是不是取整的问题)，我努力地不去想之前在算法书，自己领悟（虽然我的数学不好，所以领悟的很片面，实际上，我举了几个例子，明白了 end - begin 实际上会让一切出现在列表的开始部分，所以首先，其次，end == begin 的时候 /2 也就是 begin，所以即便有向下取整也需要 size()-1）

其实这个算法，本来也应该是可以用 TreeSet 写的，就是要模式匹配到 right > v > min 的这种，不过太麻烦了，而且好像也没啥可用的（因为它好像速度不如直接列表）

import java.util.Arrays;

import static java.lang.System.*;

public class Main {
    public static void main(String... argv) {
        out.println(Lists.compare(1, 2));
        for (int i : new int[] {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}) {
            out.print(i);
            out.println(Lists.ascFirstLE(Arrays.asList(1, 2, 3, 7, 9, 13), i));
        }
    }
}

测试用 #Java 有了这个正确的实现，我就可以继续写 RangeMap 了

#task 现在我们知道衬衫的价格是十五便士，所以你选择 C 语言，并将国考的答案填涂在显示器上，鏂不 😐

这周到底是有啥好康的东西，呢，又有哪些东西，因为我的时间不够所以不得不暂时没份呢？
感兴趣的朋友可以看这里。

+ 小说《抓周》 Share/Zhuazhou 的修改（订正）和 NumPreety.js
因为作者暂时用不上这本小说了，而且 NumPreety.js 还莫名有点困难（因为作者的数学不好，我还以为现在有改进了呢……）所以暂时就不修改（我一点也不惋惜）
NumPreety.js 是什么呢……

然后我就可以 new Stream(titles).zipWith(titles.withIndex().map(it => fmt(numpreety.hanShow(it.index)) )) ((t, t_no) => t.innerText = t_no) 了
可是这个把 9 转化成 九、250 转化成 二百五十 的函数，还有点难写…… 何况我没时间，而且困难的算法对我来说太多了，所以就没多说……

+ Dokuss
Dokuss 的 Byte/Short ZExt 特性是要加上的，只剩下最后一个类，就可以框架式的读写东西了……

+ Parser.kt / Reflex
我就想早点写这个，不过现在看看（Parser.kt 目前有的一点代码其实急需重构，我之前写的时候觉得手酸果然是有原因的，一个该子类的逻辑放错位置了）
我打算拿 Java 重写，也正是因为打算（滚回去）用 Java 的缘故
本来我们 Parser.kt 可是相当优秀的，它是 Kotlin/Common 1.41…… 现在一巴掌打回 Java 8
不过不要紧，我相信为了这一点体积的问题，也不至于会难看非常

+ Montage.py / Badge.dex
montage 也是很有意思但也有点麻烦（主要是，我是第一次写）的 DIP 算法
实际上，每次我实现自己之前设计的那种东西，往往都会浪费很多时间
Badge.dex，就是那个可以用 builder pattern 的 Spannable 快捷方式了
现在想起来，我可以用 Lombok……

+ PL/0 的解析器（和编译器）
前几天看了从 USTC GitHub 分享那拿到的一些资料，和 LLVM Cookbook
我早就想实现一个编译器了
并且，为了实现它，我还特意思考了一整天那个 Lua 的跳转链表，最后终于搞懂了跳转链表是怎么一回事、嵌套内层跳外层还是怎么着，以及它的确需要 loc, succ 两个（而不是两者之一）来构造的事实……
至于那个 bp, sp, lr （一般 bp 上就存储上一个 bp 的 link……）什么的，不用担心我搞不懂这些
存储的层次差需要动态维护，我当然会啊，不就是生成几个循环减法加法……
解析器还要支持『自动处理错误』（镇定原则）…… 这个，我的 Parser.kt 没考虑太多（它只提醒错误，不可能无视错误填上几个 Token 继续，而且 PEG 解析器不存在什么 Terminator……）
if (succ == next.loc) succ = next.succ; fold right 就可以了。
我还想了个『面向对象』 poly(name, Variants, Fields); is(v, type) 宏…… （当然不能面向对象，只是 sum type 一样的而已）

#defnie poly(name, Variants, Fields) \
typedef enum (Variants) name##Type;
typedef union (Fields) Poly##name;
typedef struct { name##Type type; Poly##name unwrap; } (name);
#define is(v, type) (v.type == type)

蛮没用，不过可以充当类似 sealed class 的东西，就是可以用来装 static Token 什么的
比 LLVM Cookbook 里面什么 type id，然后什么 string idVal; int intval; 啊强多了，那还能叫 scanner 模块么。
说心里话，我真的对代码有洁癖，所以我一点点不紧凑的代码也看不下去。

+ Java JNI 体验：TrieTree
因为我个人不经常写 C++（即便我的确是会写的，也会用 CMake, Qt 什么的），所以我还是打算用 C 写
这次我不觉得有时间可以实现了。（更不要说我开始计划的 byteTrie，还 8 bin(『散列』桶) 什么的……）
不过我还是很想把之前 CoolApk 的 liba 再蓐一把，体验一次 JNI 编程。（当然我也设计了很多方便使用的宏和代码风格，很甜）（内存管理么，首先部分程序员 C++ 内存泄漏很正常，其次不是有 shared_ptr, weak_ptr refcount 么

== 下面是真正意义上的骚操作，上周后来的时间我设计的

+ RangeMap，之前想了很久了，说白了就是一个有序表二分查找的简单算法数据结构（只不过之前我不懂得简化，所以一直眼高手低，在外围什么『区间冲突策略』的地方敲打）
显然，如果我们需要一个 Map<Int, V> （我指的是，你需要映射一大堆 key 的情况）的话肯定不能用 HashMap 吧（空间复杂度……）
可是线性查找又很慢
这样就有了省空间省时间的 RangeMap，缺点是因为 Java 的 Collection framework 没有 SortedList（而必须每次更新后，我也不想定义什么 SortedList，有它自己的原因）就必须每次去重新排序，不过基于增量排序算法的话不会有什么困难
排序问题是很经典的列表处理问题，已经有很多很成熟快速优雅的解决方案，在这里我不需要怀疑 Java 平台的能力。

+ DJD (duangsuse's Java Decompiler)
我这几天拿手画出来许多基于我基于 PL/0 处理机的汇编改造，然后又设计了一个能够侦测循环（我的方法是，每个 BasicBlock 我给一个 base，这样我就有机会检查控制流是否反在向跳转）的算法
然后我就有机会，基于抽象执行，(1) 把原来逆记法的二元链、方法调用折叠回表达式 (2) 而且还能提取出基本块

有了基本块就可以在上面进行进一步的模式匹配，然后就可以还原出 if () {} while () {} 这种高级结构了

当初我因为这个算法需要随机访问指令序列所以不能用 Feeder<E> 莫名伤心了很久，不过很不幸的是，（控制流分析过程中）为了能够判断 br 系指令是否跳转到了某个基本块中间（这样就必须 trunc 那个基本块了，因为基本块都是按顺序执行的，里面的指令不能有另外的前驱和后继）
，以及保证算法的优雅性，我必须使用 RangeMap 记录一个 ip （指令指针）位置属于哪个基本块

+ DiffAlgorithm #Algorithm
这个玩意包含两个项目： (1) DiffAlgorithm 的 Java 重写
(2) Java 的『状态机』（就是 onXsInput, onYsInput, onXsEnd, ……） 版本的重写
我都想好算法了，不过现在好像是没时间做了…… （因为事情比较多，而且不管怎么说，实现算法总是费时间）

+ 比较 TypeEqualizer 和传统的 instance check (operation model)
其实这也没啥，就是 TE 比别人『多』一个 toXXX() 转换而已
TypeEqualizer 是面向数值类型进行抽象建模、instance check 是面向操作进行抽象建模

所以他们之间有个明显的区别：如果要支持新的数值类型，则 TypeEqualizer 需要修改的代码少很多
如果需要支持新的操作，instance check 的版本方便不少

+ Trace.kt 没什么，我就是想让你们看看，天才写一遍和臭皮匠断断续续想一天能轻易拉开多大的差距

#CS #PLT #ce #Java 别捉 🐔，我先写个计算器再说……
这是一个普通的 Java 计算器，它支持 +-*/ 四则运算，Int/Long/Float/Double 四种类型。

关于如何实现 Number.plus(Number) 什么的，首先我们实现一个 (Int | Long).plus(Number)，然后直接利用它的定义，在 Number.plus(Number) 里判断第一个参数的类型（也就是说，我们可以确认接收者类型了）即可

类似这样：

Stmt = Expr
Expr = AddSub
AddSub = MulDiv
  / AddSub '+' AddSub
  / AddSub '-' AddSub
MulDiv = Atom
  / MulDiv '*' MulDiv
  / MulDiv '/' MulDiv
Atom = Literal | '(' Expr ')'

没学过形式化语言的：这么看

+ 你可以依据『规则』（它们的名字就是等号前面那个）推导匹配出某个『序列』里的数据
+ 可以被 (a / b / c), (a0 a1 a2) 这样的替换的，被我们称为『非终结符(non-terminal)』，因为遇到它们代表你要继续进行文法推导
+ 不能被其他规则替换的项，比如 'a', '.', '\n'，我们称之为『终结符』，因为推导到这里就代表当前项目已经结束

猪八戒 = '猪' '八' '戒'

< 猪八戒 +
猪n戒 = '猪' n@(八/九/十) '戒' where
八 = '八'; 九 = '九'; 十 = '十'
<猪八戒 + (n=八)
<猪九戒 + (n=九)
<猪十戒 + (n=十)
<猪一戒 -

在自顶向下（我们知道自己要推导规则『猪八戒』）推导过程中，我们把 (八/九/十) 尝试了一遍，并且找到了匹配的规则继续解析
这就是文法推导， (a / b / c) 这种规则被称为『分支』规则
(a0 a1 a2) 则是『按顺序解析』
([ a ]) 内部的是『可选项目』，也就是可能出现也可能不出现的项目
({ a }) 内部的项目可能重复，比如，
{'好'}
<好好好好 +

===
并且这个计算器会支持函数套用（过会再支持）
Stmt = ... | def Name [ LP ArgList RP ] '=' Expr BRK
ArgList = Name (',' Name)*
LP = '('; RP = ')'

BRK = '\n' | ';'

我给还不是很懂的萌新解释一下 MulDiv 和 AddSub 嵌套下面的项是怎么一回事：

(1 + 1)
Stmt -> Expr -> AddSub -> MulDiv -> Atom -> Paren -> ... 为什么需要这么长呢？是因为有些东西必须在前面。
1 - 2 + 3 * 2
我们知道，3*2 应该先结合，就是说它离语法树的根节点相对较远。
1 - 2 + (3 * 2)
在后序遍历过程中 (3*2) 最先被求值（因为这个加法依赖乘法的值），这就是所谓的『先算』（即便因为没有副作用的缘故，求值顺序不 matter）
所以我们就知道为什么要写成这种形式，为的是我们能：

(1 - 2)@AddSub + (3 * 2)@Atom:MulDiv

不过，这种写法可一点都不好看，而且很冗长（即便有点理论的优雅性）

因为这种做法不好看的缘故，我们使用另外一种好看的方法来利用递归下降法(recursive descent method)构造有优先级的表达式树。

首先我们得明白，一个表达式链有两种情况：

InfixChain = Atom / InfixChain BinaryOp InfixChain

举个例子，1 + 2 这是 Lit '+' Lit，我们知道 Lit 应该是一种 terminator 了（实际上这是一种 LL(1) 文法，呃…… 不要说那些没用的，只有字符本身是『终结符』！）
1 + 2 + 3 呢？
因为 (+) 法是左结合的（就是说，它出现在左边时的优先级比出现在右边时的优先级高，也就是 Lua 的 struct {int l,r;} precedence[] 实现）
我们知道解析构造的树是这样的： (1 + 2) + 3
它其实是 Add '+' Lit
所以，我们没有办法直接确定扫描的项目到底是 Lit 还是 BinaryOp, InfixChain 也应该囊括 Atom。

不管是在中缀解析器的层面，还是 AST 的层面，我们都知道，显然中缀链的项目可能是一种中缀或者是最终末端直接的『叶子』，要不然就没完没了了

data Ast = Add Ast Ast | Sub Ast Ast | Mul Ast Ast | Div Ast Ast | Lit Int

对应到 Haskell 代码上：上面的 Ast 数据，如果我们去掉它的 Lit :: Int -> Ast 架构器，则构造这种数据，实际上就变成了解答『先有鸡还是先有蛋』『先有 Ast 还是先有 Ast』这种问题，你怎么也无法够造出穷尽的 Ast 项。
（自然也无法实现有穷尽的 eval :: Ast -> Int 算法了）

所以我们使用一种扫描算法，首先它要从左到右(left-to-right)扫描输入流，其次是要能够处理 (a+b*c) (a*b+c) 的区别（乘法比加法先结合）

为了能够判断 + * 优先级的差别，它必须阅读两个项目、预取一个项目（rhs_op），而且必须能够把自己解析的结果『先结合』了，就是说它长这个样子：

Infix scanInfixChain(Infix base) {
  if (isEOF()) return base;

  InfixOp op = scanInfixOp(); // exp +
  Atom rhs = scanAtom(); // exp + 1
  InfixOp next_op = peekInfixOp(); // exp + 1 * ...
  switch (compare(op.left_prec, next_op.right_prec)) {
    case EQ: case GT: /*先结合*/ return scanInfixChain(op.fold(base, rhs))
    case LT: /*后结合*/ return op.fold(base, scanInfixChain(rhs)) //等于 next_op 「抢走」了自己的 rhs
  }
  return impossible();
}

如果不想用 peek，那第一次扫描的时候记下来，之后以参数的方式传递也行。

#life 唉，有时候会觉得一周最后放假的时候（虽然也就两天，当然正常高中生只有一个晚上）什么都没做到


有时候会感觉很累，不值得。
有时候会觉得自己菜，然后能够举出一大堆不太想通的代码证实。

有时候又认为做到了很不错的事情，超出预期。

也不知道到底是怎么样。

上面的计算器，我弄出来就结束了……
虽然没写几个测试，我也不清楚有没有 bug

好，那我说的已经完成了，我干别的去吧…… #Java #PL #PLT #CS

第一次玩 Kotlin/Java 混合开发
我也不是很确定是不是没有 bug，但我尽力了，这是我第二次写 Feeder（修好了第一次的不良实践，也推掉了一些特性）

理论上基于 Feeder 的解析器不应该使用子类的，不过我这次上了个『不良实践』…… 不过一切都好，二元操作链解析正常

我自己都觉得很奇怪，即便这不是什么稀奇的事情（函数式风格的解析器嘛……）

既然委托了 Kotlin，显然是不可能完全不用 stdlib.jar 的，不过我们可以用 proguard

这次的 Feeder 虽然支持（实验性地）MarkReset.Multi，也就是说，它能够用来给嵌套的 Branch 解析器喂东西，此外，它还使用了可以 Clone 的 Iterator（我是参考了 Haskell 的一切皆『复制』方案）
不过它不支持 Stream，也就是说，不能拿来做 REPL（所以你们看到，我是用 Scanner，而且 Java 的 lang.Character.isWhitespace 不知道哪个分支有毛病，不能自动跳过 '\n' 换行符，气死了
至于为什么不支持，其实支持起来也未必就非常复杂（就是一堆 buffer 有点绕而已）
是因为我不需要它来写 REPL……

就是这样了，那么告一段落，祝你们玩得开心，喵。 🐱
代码过会我会发上 GitHub

目前支持的中缀操作符

最后还是有点 bug，不过也有重构的部分

『我们保证以后不会往肉里打水了，我们欢迎你们来监督……』 — 《四十一炮》

暂时不发 GitHub 了，直接发文件算了 #Share #code #Java #Kotlin

其实，Lexer 是 LL-1（只用向前判断一个字符）的，但是 Parser 严格上来说它不能扩展自 Lexer
Parser 实际上也只是 Feeder<Character>，它的输入流支持 lookahead-1，可是那是字符层面的 lookahead，而 Parser 实际上只解析 token()

Lexer 的 token() 导致了看起来也该是基于 Feeder<Token> 的 Parser 实际上却是基于随机 mark()/reset()，你不得不在每次匹配失败的时候重置输入，免得下一次 token() 返回不同的结果（我们的子解析器不能保证，在 token() 一次的情况下总是可以成功，所以一旦遇到未预期的 token()，不得不『消耗』掉它，即便调用自己的解析器不希望那么做）

这种情况，其实应该使用解析组合子框架（当然过会我会弄一个的，早想好了）

所以我打算弄一个 StreamFeeder 和一个给 Java 的 Sequence（Sequence.OfProducer, 如果用 Kotlin 会缩减无数无聊的代码，可是我不知道 Kotlin 的 Sequence 有没有太大的体积问题……）
这样，我们的 Parser: StreamFeeder<Token> 里

constructor(String file, CharSequence code): super(file, Sequence(Lexer(file, code)::token))

再次强调，Feeder 本该是给组合函数式解析器喂 item 的（它就不应该 open），我会弄个 Delegate 把它的所有方法移到 AbstractFeeded 里
不过这样也就没法搞定 onItem, onEnd 的问题了……

剩下的部分我会继续使用 Kotlin/Java 混合编程，面向库使用者的部分我会用 Java，核心的部分我使用 Kotlin（真希望 Kotlin 不会往上加个几十兆……）

没什么目标，也只好信手去做……
我想把 Dokuss 完成，可是 Parser 也要写…… 而且 Dokuss 剩下的一个 Nat16, Nat8 的 ZExt （zero-extension）有点不好弄
zext 是因为 Nat16 其实是 kotlin.Short 实现的，它把高位的比特当作 sign 解释，.toInt() 的时候就会错误解释一个比特的信息
我们要先 toInt()，然后移位 bitwise or 操作把这个比特加回来
可是它不好测试

proguard -keep 'public class calc.inst.Main { public static void main(java.lang.String[]); }'
-injars calc.jar -out calc_out.jar
-libraryjars '/usr/lib/jvm/java-9/jmods/java.base.jmod(!**.jar;!module-info.class)'
-dontobfuscate -dontwarn
以后是 48K，我看看换成 Kotlin 的 collection 会不会加体积

开始试着习惯写测试了 #Java #Kotlin #dev

我现在才明白王垠的看法是片面的，像是这种情况，你标 return 是不对，这不是表达式的风格

我实在不敢再去想…… Linus 不是有一句话说，编程的两种方式一是认真思考，二是在无数个机器上测试，那我就多写点测试吧，真 TMD 太困难了！

最后一个 ++ 很是难理解，我都不知道自己是怎么写出来的…… 又搞不懂了，emm

Trace 还是不好写，不写了 #Algorithm #Kotlin