#life #dev duangsuse 落实 10:30 准时睡觉『政策』。 🐱

考虑到健康原因（不让自己的努力白费），每晚 10:30(h:m) 必须立即睡觉

== duangsuse::Echo 参考 #Telegram hashtags

duangsuse::Echo 常年利用 hastags 标记消息所含知识领域，并且，这也会为未来 Echo 频道进行简单准确的数据统计带来可能（不然，我也有其他手段，比如 NLP、统计预测）

以下是新的标签实例（不区分大小写、不能保证消息只含这些标签）：

== 消息平台部分
#Telegram #zhihu #Github #so #Coolapk #book #wiki

== 注释部分
#life #China #School #Statement #lib #recommended #low #fix
#project #blog #share #Learn #paper
#dev #tech #art #meetUp #conference
#Moha #Haha
#gnu
#Microsoft #Mozilla #WeChat #QQ #Weibo #Tencent #Baidu #Ali #Qihoo
#tools #code

== 程序设计语言部分
#Kotlin #Java #JavaScript #JavaScript_ES6 #TypeScript
#Rust #Go #Swift #Dart #Crystal
#Ruby #Python #Perl #Tcl #Lua #PHP
#C #D #Cplusplus #CSharp #Objc
#Pascal #Fortran #Delphi #Ada #Basic #VisualBasic
#Scheme #Haskell #Scala #Clojure
#TeX #Graphviz
#Octave #Matlab
#Shell
（有些写出来是为了鼓励我去写，其实不一定真的写过）

== 软件平台部分
#Android #Windows #Win32 #MacOS #Java #Java_JVM #CLR #Qt #GTK #Tk #WxWidgets
#CSS #XML #JSON #KDE #Postgres #dotnet

== 软件技术领域部分

#backend #sysadmin #frontend #sysadmin_net

#OI #CS #IT #Informatics

#stat #ann #ann_dnn #machl
#math #math_linearAlgebra #math_discrete
#se #se_dia #se_ci #se_ee
#comm #net #www #web #http #html #mail #wireless
#circuit #embedded #os #db #db_relAlgebra #SQL
#bin #encoding #encoding_audio #encoding_image #encoding_video #encoding_text
#hpc #parallelism #distributed #simd #gpgpu #crypto
#pl #pl_plt #ce_vee #ce #ce_optimize #fp_monad #fp_proof #fp #oop #oop_arch #sp #parser
#algorithm #struct #lists #maps #sets
#security #security_lowlevel
#signalProc #nlp #phonetic
#cg #cg_dip #cg_3d #cg_2d #cg_lowlevel
#gui #gui_animation #gui_layouts #cli #visualization

我正在使用 #Scala 重写 https://github.com/PinkD/CoolApkApiTokenGenerator/blob/master/CoolApkApiTokenGenerator.java

#Scala 真的是太棒了，在 JVM 上又找到了写 Haskell 的感觉！

#Scala 修复了一个弱智的问题（我以为是间接引用其实是拿到直接的引用了...）完成了.... 耗时三小时

我的第一个 #Scala 开源 repo！

第一次使用 #Scala sbt（死变态 emmm...

第一次使用 #Scala 的 experimental language feature: macros

顺便说一下为啥要进行 n 次，每次都要排序列表从 0 到 n - i -1 的项目，虽然我现在还没有证明为什么 bubble sort 输出的列表就一定是有序的的能力（归纳证明）

排序算法，就是给一个输入序列、一个测试函数『序(order)』，输出序列满足以下条件

forall i. list[i] `order` list[i+1]

比如 list=[3,2,1]; ord=(<) 简单的选择排序每次挑一个『最大』的元素出来（它满足 forall x in list. x <= it），复杂度是 O(n) 当然 n 是输入长度，线性复杂度，这也是必须的（显然得遍历一遍才能找出最大的），没得优化

max [] = undefined
max xs = let (maxidx, max) = (0, xs[0])
  in xs.with_index.forEach(cmpChg)

max

  where cmpChg = { |it, idx| if it > max then (maxidx, max) <- (idx, it) else Unit 

}


然后每次找到这个最大的，忽略掉它（比如直接 delete），再把它 push 到期待的有序列表里，就成了升序(ascending) 序列（栈是 LIFO 的，collect 到列表后最后 push 进去的最小值成了第一项）

naiveSort xs = let result = []
in xs.length.times do
(maxidx, max) <- max xs
xs.delete(maxidx)
result.push(max)

当然我不知道有没有真正 Haskell 并且还好看的写法，或许依然要枚举索引... 也可以用链表和递归大概，但这里不讲它

对于 bubble sort，首先有一个过程，它遍历一遍所有 list[i] list[i+1]，假若 list[i] `ord` list[i+1] 不成立则交换（因为偏序关系有反对称性，所以这是正确的，可以向最终对输出全称量词(forall) 成立的方向演进）
（这里就隐式限定了 i < list.length-1-1 因为 list[?] 的 ? 必须 inbounds [0..list.length] 那这里 ? 的最大值是 i+1，最小值是 i）
给定 i+1 inbounds 0..list.length 推出（直接用加法的逆运算推导） i inbounds 0..list.length-1 转化为 Java 的布耳表达式就是 (0 <=i && i< list.length-1).

为什么 bubble sort 这种交换排序就需要再循环 n 次呢？而且为什么每一次排序的序列都可以是 [0..tailidx-i] 最后索引递减呢？

对于任何排序算法，都要做到一个最基本的东西：完成对偏序关系的传递
a R b ⇒ b R c ⇒ a R c
对于 R = (<) 的情况就是

a < b ⇒ b < c ⇒ a < c

这样的序列看起来像：

a < b < c

很简单吧
其中快速排序是基于 D&C （一种基于递归的）优雅算法，它对问题解决方式的表达很好地反映了这个道理

(Scala)

def qsort[T](xs: List[T])(implicit ord: Ordering[T]) = {...}

快速排序是一种基于交换的排序算法（这类算法一般都比较高效能，对于原表几乎不需要有任何概念上的数据复制），对问题的解决妙就妙在它把二元关系给“分治”到了二叉树上。
它的递归每层返回一个有序列表、基线是列表已经有序（长度 2 以下）

  if (xs.length <=2) { return xs }

找一个基线，作为交换的基点。

  val pivot: T = xs{xs.length /2}

[1,2,3,4] 基于快速排序它会被分成 [1,2] 和 [3,4] 两个子问题（理论上，其实实际使用了优化），
val lts = xs.filter(x => ord.lt(x, pivot))
val gts = xs.filter(x => ord.gt(x, pivot))

最后，返回一个有序的列表，这里用到了递归定义，因为我们不知道子列表是否已经有序，所以要递归下去拿到有序的列表

  return qsort(lts) ++ List(pivot) ++ qsort(gts)

想复制实现代码看这里

每个子问题只有一个子结果：一个有序的列表，实际上这样，它的每一个子问题就只有 O(log2 n) 的时间复杂度，它的传递方式就是『找出每个子树里最大的，然后把它和同层的其他子树做二元比较交换，再次找到最大的比较交换...』这样就在 O(n log2 n) （n 是平均情况下要解决子问题的个数，log2 n 是解决每层子问题二元比较的次数，因为它利用递归切分子问题和偏序的传递性，只需要很少的比较次数 log2 n 就可以得出正确的结果）

Question: 如果输入列表长度是单数(odd)岂不是无法切分为两个『子问题』？
Answer: 对于这种情况，设置一个递归分支 qsort [x] = [x] 就好了，这是应对单数输入的情况
此外 qsort [] = [] 也是一种递归中可能发生的情况

==
那现在问题来了，冒泡排序又是怎么完成这个偏序关系传递的呢？
因为冒泡排序比较不适合 Haskell 和 Scala 的风格，就用 Jawa 写好啦！

冒泡排序的思路就是，遍历交换遍历交换... 直到列表有序

有一个基本子，它针对 list[0..ri] 线性（join 每两项，实际上最后真正比较的次数超乎你想象，它做到的『传递』几乎每轮只能增加一个项目... 而不是 i^2 个）排序一遍，这样我们实际上只能保证两边不存在偏序传播问题的项目是完全有序的，因为前面的其他项目的偏序关系全部都没有被传递而只是相邻两项之间有关系而已，(<), [3, 2, 1]，最后弄成 [2, 1, 3] 完全有可能，因为它交换 [3,1] 的时候看的是 2 < 3 但是不知道后面还有 2≮1, 和 qsort 基于栈存储的比较次数和每层输出一定有序的断言一比高下立判，优雅性也远远不及后者

private static <T extends Comparable<? super T>> void propagateOnce(List<T> xs, final int ri) {
  for (int i =ri -1; i >=0; i--) {
    T lhs = xs.get(i), rhs = xs.get(i+1);
    boolean ordered = lhs < rhs;
    if (!ordered) { // swap!
      xs.set(i, rhs); xs.set(i+1, lhs); }
  }
}

那既然无法保证 [3,2,1] (<) 之类在 propagateOnce 内 < 的传递性可以被尊重，怎么办？
有一个办法，就是循环 n 次，每次处理 [0..i] 的个子列表，因为虽然像是铁块上的石蜡一样偏序关系无法传递无法透过，边角上的 [2,1] 显然还是能保证顺序的（数学归纳法的基线）
这样处理 (n/2)*n 次过后，实际上就把最刁钻的关系传递到位了（比如 [5, 0, 0, 0, 0, -1] (<) 这个极端情况，会被切分成 5 个子序列从长到短依次串起来副作用排序，-1 会被不断当成边角被“冒泡”到第一个位置，这也是算法名字的来由）

public static <T extends Comparable<? super T>> List<T> bubbleSort(final List<T> xs) {
  List<T> output = xs.clone();

  for (int rlim =(xs.length-1); rlim >0; rlim--)
    { propagateOnce(output, rlim); }
  return output;
}

当然从左边递增切分子序列也是可以的，这里只是因为从右边更符合直觉

—
刚才看荔枝频道上那个基于遗传算法（物竞天择适者生存）的程序综合（program synthesis）机器人会自己生成排序算法，NB 啊。
是不是 Prolog, Coq 这类描述式编程语言也会这么做呢？ #Algorithm #Scala #Java #Haskell

#Haskell #Scheme #Scala #FP 支持一下其他内容维护发表一些文章分享，不过好像不是他的吧...

https://paste.ubuntu.com/p/FrGSNhphs4/ #plt 我也感觉奇怪，绝句设计时为了实践方便弄了个类似 by Delegate 的「类实例」语法，并且有了直接等价当前 receiver type 的类型变量「我类型」

感觉类实例还是要学习一个，最开始只打算做隐式转换的没想到还有这茬……(其成员还要做成 extension fun 加入隐式转型才能直接调用， #Scala 一样)
若有 class C 和其 super P，面向对象 c+p is C 而 p+c is P ，没有理论优雅性，当然这个不重要能用就行
如果真的存在，我想肯定是取最精确的重载版本。

#functional #Scala https://github.com/Ray-Eldath/whatever/blob/master/main/src/main/scala/cats/Show.sc 范畴论实践，有 Boolean, Number 等

https://github.com/Ray-Eldath/whatever/blob/master/main/src/main/kotlin/ray/eldath/whatever/dsl/MeetingDSL.kt #Kotlin 新特性回顾，初入 Embed DSL

https://github.com/Ray-Eldath/whatever/blob/master/main/src/main/java/ray/eldath/whatever/LambdaBytecodeExampleJava.java#L26 #Java annotation 语法于数组的小细节 #PLT ，话说作者写好多 bytecode example... 编译看字节码的么

https://github.com/Ray-Eldath/whatever/blob/master/x86/protected_bubble_sort.asm#L52 #asm x86 冒泡排序， :internal 和 :external 是指 while {} 内外，后方可见 inc eax, cmp, jle 指令。

https://github.com/Ray-Eldath/whatever/blob/master/mips/fib.a#L40 #asm MIPS fib(n) 计算，话说 fib(n) = (n>0)? fib(n-1)+fib(n-2) : 0; 这种方法我之前都没用过，一直是 (n<=2)? n : recur(n) 的，思维定势

不过说起来也只有会写 C 的人能看汇编😋 GC 和 libc 用惯了会不知道栈空间 jal&j $ax、segment/mmap、interrupt/ivt 是干什么的说。
不过这么看 C 也解决了很严重的 sizeof 整数长度问题啊，这样代码就可移植了，虽然不能像 Java Python 去 Run Anywhere 。

作者在 test/kotlin 下也有写评测
还测了 IntRef+ parallelStream() forEach, reduce 的正确性🤔
当然也有 reflect MethodHandle 的测试代码
他真的对语言 Intrinsic 很了解啊

#PLT #Scala #Java #Ruby #Rust #learn https://ray-eldath.me/programming/thoughts-on-rust-1
总结几句：
Java 是主流的托管(managed) 语言，重量级的 GraalVM JS 甚至比 v8 更快，尽管有 valgrind, cppcheck 等工具， 90% 的 CVE 都是 #clang #cplusplus 内存不严谨导致的安全问题，所以托管更适合实际应用。

Scala 是重视语言特性可组合性的函数式语言，它连 enum class 都没有，而用 enum 的本质 newtype (受检的 typealise) 和直接的 extends 解决枚举类型；它的类型都是 higher kind 上的星号实现的，而构造函数类型的箭头是接收任意(包括函数)类型的二参操作符 #functional

Ruby 是一个灵活优雅的脚本语言，你可以 mokey patch Int.+ 运算符让 REPL 都爆炸，它也支持 case when guards
Ruby 的 {|x| x} closure 即闭包语法也被 Rust 使用，连 for 语法本质都是用 .each do 闭包，运行时很少阻止程序员执行能解释的代码（但没有 JS 的疯狂隐式转换）并且支持内省(introspect)

Rust 是 be explicit 的语言，它重视内存片的所有权等比 C 方便而失严谨的概念，但同时也加入了 format!() 等编译期 macro 的支持，也是一门重视严谨性、定义一致性的语言
Rust 的 Copy 和 Clone (深浅复制) 都是作为 trait 显式的，而浮点数判等 Math.EPSILON 也是应显式的

嘛，比起『子语言』我可能更倾向『语法集』『语言功能点语法集』这种更精确的描述

问题： 呃，今天才知道 Kotlin 的 Boolean 是 Comparable, true > false 。感觉有点坑啊

其实 Kt 的问题不少，比如 Common 改名 Multiplatform 还有些隐藏关键字(typeof..)，型参约束可以用 where，主要是太实验性，1.3 的时候字节码生成还有问题，不支持 j.l.invoke API
甚至一些?类型优化也有bug
但Kt确实是 #java JVM编程现阶段最好的选择，full interop ，完善带extfun OOP （只是Android上默认proguard规则还不够好什么的……

当你第一眼看某大佬的Kt 时着实被 let run constructor init companion 这些搞眼花了…… 一时觉得比Rust不明觉厉 🤪 Kotlin 初期的stdAPI命名 是个问题
>啥叫partition
school.partition(男女)

>不是有groupBy了吗
school.groupBy(领导教师学生)

那么 associate (toMap,还带 By-With介词) 和 all,any,none ("exists"=any,none=allnot) 也很容易忘，尽管相比JS和Scala 这是最好的

谈到Kt冷知识，我想再提 UnsafeVariance https://tttttt.me/dsuse/15959

(items[i] as IO<IN, in @UnsafeVariance T>).show(s, v)

这关于 IO<INPUT, T> 的定义，T 是 out 的，不然 Seq<Any>(io1:<String>,io2) 就会报错，如果要把 Reader 和 Writer 写在一起就会出问题，但代码复用偏偏必须写一起

我能断言指定 items: List<(IN)->R> 位置[i]的 show 可以接受(in) T ，因为它本来就是被取并集损失了精度的，于是写了这种代码，
其实它本身同时是 in, 但为了写存储的兼容被迫暂作 out 了而已。

然后匿名 object{} (即 new ArrayList(){{add(1)}} ,常量糖..)的IDE特性也很多，不过 inner class 才正常呢……

#recommend #kotlin #scala #reveng 关于coro底层的代码示例 https://tttttt.me/kotlin_cn/25062