koka 语言的卖点

2021-07-25

这个周末都在研究 koka 语言。准确来说，是读它背后的几篇 paper，有一些收获，也有一些心痛自己瞎 JB 点技能树，又浪费了一个周末。 先说结论，这个语言我觉得非常看好，所以来聊一聊它的卖点。

koka 没有追求特别 fancy 的 feature，所有这门语言用到的基本上都是理论比较成熟的，相对来说也只有 algebraic effect 是接受度尚低一点的。其它的都是一些函数式语言里面被广泛接受的概念，比如 first class 函数，polymorphic type。 它是编译成 C 的，并且我看了一下，对性能非常重视。从作者的背景看，应该微软搞的，所以不是那种纯学术领域的路子，是实战派。比较 amazing 的地方，它的内存管理选择的的是引用计数，而不是传统的 tracing 的垃圾回收。

引用计数是之前我没有特别重视的一个方向。近好些年来，干活一直都用的 Go，遇到垃圾回收相关的问题也是非常多。即便 Go 比较极致地优化 STW 的情况下，tracing 的 GC 还是有一些不可控的对业务层的延迟影响。 比如产生垃圾的速度太快，GC 的速度跟不上，那么 runtime 不可避免地需要让 mutator 慢下来，协助帮忙一起做 mark 或者 sweep。这些东西都不是特别可控，在性能要求高的场景还是需要做调优，从而对使用者带来一些心智负担。

rust 的出现让大家看到了另一个方向，由编译器在编译期推导对象的生命期。辅以语言层面做一些生命期的标注，没有引入 runtime 的 GC，又实现了自动内存管理。不过 rust 这门语言我实在喜欢不起来，它更像是 C艹的 feature 爆炸之后，做一个简化的版本，然后取一些有用的东西，再跟函数式语言那边“借”一些东西之后拼凑后的 bastard。这条路既然 rust 这边跑通了，那说么明在编译期去搞内存管理确实是一个可行的方向。

这跟引用计数有啥关系呢？其实要想不引入心智负担地用引用计数方式实现内存管理，是需要 runtime 跟编译期结合起来的。编译器必须去根据对象的分配，被引用和释放等过程去插入指令，修改引用计数，这个过程必须是在编译期完成，才能做到自动的内存管理。

我们先看一下传统的手动的引用计数的实现机制。比如说 C艹，对象出了生命期会自动调用析构函数，

void f() {
    Obj o;
	// exit function, destructor of o is called.
}

那我们利用这一点来管理自动释放内存

void f() {
	ptr = new XXX
	Obj o(ptr)
	// destructor function of o can reduce the ref count of ptr, and free it if ref count is 0
}

这种只能算奇技淫巧，因为它是会给使用者带来心智负担的，是手动的不是自动的。自动需要把编译器和 runtime 结合起来做，在编译器里面做控制流分析，从而知道具体每个对象的生存时间，然后再插入指令，到了执行的时候就会正确地增减引用和释放内存。这个叫 ARC 吧，自动的引用计数，好像流行一点的语言里面 Swift 是用自动引用计数的，python 据说也是，我不太确定。

相比于 tracing 的 GC，引用计数的优缺点是啥呢？ 总体来说，GC 的卡顿是一个很难以彻底解决掉的问题，优化了这么多年，其实都是无解的。因为记录的是所有活跃对象这种信息(所以叫 tracing)，必然会随便着对象越多，扫描的代价会越大。引用计数的方式，记录的是局部信息，不会扩展到全程序范围。一个对象，没有其它对象引用着它了，它就可以扔掉了。或者换句话说，引用计数只关心着它被引用了多少次，不关心它引用谁，或者谁引用着它，而 tracing 的 GC 是维护着“它引用着谁”，进而推导出“谁引用着它”，再然后去释放未被引用着的。引用计数的维护并不是没有代价，只是把代价放到每一次的操作里面了，因此相对来讲不会有长时间的卡顿。并且有说法是插入的增减引用计数的操作会破坏指令的 cache 友好性。GC 的方式把清理工作集中在一起做，有卡顿，但吞吐可能会更好一点。

这里纠正一个错误的谁知，引入计数就没有卡顿了。其实不是，比如举一个 case 吧，一个很长很长的链表，引用计数记录在头节点上面，然后代码是这样：

void drop(p *node) {
	if (p->count == 0) {
		for (iter = p->children(), !iter.end(); iter++) {
			drop(iter);
		}
		release(p);
	} else {
		p->count--
	}
}

假设这个链表很长，释放节点还是会卡顿的对吧。

koka 语言关于引用计数的主要是这篇论文：Perceus Reference Counting，传统的引用计数没有被广泛采用，有主要以下三个问题：

先说成环，成环是最好理解的，a 引用 b b 引用 a 相互成环之后，引用计数永远无法减到零，然后内存泄漏。关于这一点，论文给出的方式是，不解决。在函数式语言里面，不像命令式语言那样 mutable 满天飞，于是函数式语言中成环的场景会相对比较少。然后作者提到，像 Swift 也没有解决成环的问题，然后实际生产上使用中也没啥大不了的事情，所以在函数式语言里面这就更不算个事了。

第三点多线程的问题是说引用计数在处理并发这一块比如难搞。多线程环境会同时访问对象，修改操作引用计数。文章里面是说了一些优化的，不过我没有太深入去研究。

重点说第二条，精度问题。传统的引用计数里面，生命期是靠变量的生命期来处理的。那么举个例子：

fun foo() {
	val xs = list(1,1000000)
	val ys = map(xs, inc)
	print(ys)
	drop(xs)
	drop(ys)
}

只有到出函数作用域的时候(stack unwinding)，才能判定对象 xs 的生命期结束，就会造成释放操作的延迟，运行时会占用更多的内存。而 koka 那篇论文里面，它会类似 rust 那种 ownership 的概念，有控制流信息精确知道，在 map 函数里面一边操作就可以一边释放了。ownership 会跟着函数调用传递。

然后论文里面有做一个特别有用的优化，重用分析。函数式语言里面会产生特别多的临时对象分配，好多都是用一次就扔。而 koka 对这一块的优化是，它在编译期做内联展开，之后可以分析哪些场景是分配，马上 drop 然后不再使用，它可以把对象重用起来，这样就消除掉了大部分的无效分配。我觉得这个优化非常棒，不过感觉似乎也比较难做，它要把内部表示转换成另外一种类似于 liner logic 的演算然后去处理。

关于引用计数这一块的点评，我觉得是一个新语言实现值得考虑的方向。另外我还有看到 Carp 这个 lisp 方言是用的引用计数来达成 no GC 的，不过 Carp 里面也类似 rust 需要一点标注信息，而 koka 则完全无需要用户来标注生命期。

algebraic effect

koka 语言的主要的一个卖点还是 algebraic effect 这个 feature。简单的理解，effect 可以看成是一个 try catch 的强化版本。它不仅可以 catch 异常，还可以在抛出异常的地方，resume！能够 resume 这一点非常牛B，相当于可以保存上下文，去执行其它的操作，再恢复上下文。由 algebraic effect 可以实现所有的控制流，像异常机制，generator，async/await，协程，通通都可以基于 algebraic effect 这个特性来实现。是不是觉得跟 callcc 一样的强大呢？ algebraic effect 很类似 delimited continuation，不过它有一些很好的特性，它是支持 type 的。

这东西这么好，怎么实现呢？具体到实现 koka 可能也有它自己的探索过程，从代码和 paper 上面看，都留下了不少演进的痕迹。

libhandle -> libmprompt -> compile to lambda calculus 大致是这样一条路径。

首先说这一篇，Implementing Algebraic Effects in C，这一篇它是用 C 实现的，方式是改 runtime。这个实现特别类似云风的 coroutine 那个库的实现，它先 setjmp，保留当前位置，然后到 handle effect 的时候，longjmp 回到之前的位置，如果只是实现异常，这就够了，但是需要实现 resume。关键点就是使用 stack copy。把从 throw 位置，到之前 setjmp 位置的那些函数栈 copy 出去，然后 handle 异常还是在原栈，handle 完全之后，把拷出去的栈再拷贝回来，再基于拷贝回来之后的栈执行。

这个算法在性能上有一点问题，栈拷贝是一块大头开销，另个寻找最近的 handler 的位置也是一个需要遍历的过程。

为了优化栈拷贝，还有另外一个实现，libmprompt。这一个实现没有对应的论文，看代码它的优化是用了特殊的 runtime 表示，让每一个 prompt 都有自己的栈了，这样初始的时候利用操作系统虚拟页的机制只有 4k 的栈，然后随着使用可以增大到最多 8M。 但是切换栈的操作是无法直接用 C 完成的，所以有一部分代码必须用汇编来写。性能好一点，通用性更差一点了，不是最终方案。

最终方案 koka 目前的实现是用了这一篇 paper，Generalized Evidence Passing for Effect Handlers。我没有读懂它具体怎么转的，但是它里面通过一系列的推导，最后让 effect 的代码可以直接转成 typed lambda，而不再信赖特定的 runtime。这个特别牛B，通用性非常强，可以在任何语言里面实现了，这是 koka 能编译到 c 的关键技术之一。