译自 Markov Algorithm。除非特殊声明，下文中「我」指原文作者 Oleg Kiselyov。 如果问一个人知道什么计算模型，得到的常见答案可能是「图灵机」和「λ-演算」。也许有的人会说「寄存器机」，但应该不会有人说「Post 系统（Post System）」1或「Markov 算法（Markov Algorithm）」 。这洵为一件憾事，因为逻辑学和理论计算机科学中常见的推理规则就是 Post 系统的一种表现形式，模板引擎、EBNF 规则、XSLT 或宏也是如此。仔细研究这些系统及其令人惊讶的表现力或许会令人有所启发，毕竟，Chomsky 就受到了 Post 系统启发，他的上下文无关生成文法以及其他一些生成文法都受到了 Post 系统的影响。除了作为计算模型的理论意义外，Markov 算法的思想也启发了一种真正的编程语言：Refal。在模式匹配被推广到普通的编程语言之前，Refal 就已经基于模式匹配。「窥孔优化（peephole optimizer）」也是一种 Markov 算法。 Post 系统（试想生成文法）基于重复的，甚至可能是上下文相关的字符串替换，即用新的字符串替换一个原有字符串的子串。替换规则由一组有限的规则序列（文法生成规则）组成，可以用任意顺序应用替换规则。而「正规 Markov 算法（Normal Markov Algorithm）」，顾名思义，是这种基于规则的替换系统的一种受限的「正规」形式。在正规 Markov 算法中，替换是上下文无关的，同时按照严格定义的顺序进行。因此整个字符串替换过程具有确定性，可以通过一种简单的机制（即「机器」）完成。正规 Markov 算法才能称之为「算法」2（这其实是一个俄语中的文字游戏，「算法」在俄语中是「алгоритм」，而 Markov 称他的系统为「алгорифм」）。 由上可知，正规 Markov 算法是一种机器，根据一串重写规则序列，通过按顺序反复应用规则重写输入字符串。规则由源 src 和替换目标 rplc 一对字符串组成，两者都可为空字符串。有的规则被标记为「终止规则」。机器的工作循环是：按重写规则序列的顺序，依次尝试用每条规则的 src 匹配输入字符。如果有匹配的，那么就用对应的 rplc 替换输入字符串中最左侧匹配到的 src 。匹配结束后，如果这条规则是一条终止规则，那么就停机。否则把改写后的字符串作为新的输入，然后重新开始循环。当没有可用的规则时也停机。 举个例子，下面是一个 OCaml 数组形式编写的规则序列。它可以把一个大端序二进制数字（由 0 和 1 组成的字符串）转换为由 | 组成的一进制数字字符串。 let bin_to_unary = [| rule "1" "0|"; rule "|0" "0||"; rule "0" ""; |] 使用本文随附的代码运行 run bin_to_unary "110" 可以生成有六条杠的字符串 "||||||"。该代码还打印了重写过程中触发的所有规则以及对应生成的中间结果，以展示这一巧妙算法的工作原理。...

译自 R-Techonology。除非特殊声明，下文中「我」指原文作者 Oleg Kiselyov。 「R-技术（R-Technology）」是一种设计和图形化表示程序的方法，由 V.M. Glushkov 领导的基辅控制论研究所开发。该技术是自 20 世纪 50 年代末及 60 年代初，苏联弹道导弹和后来的太空火箭的航空电子软件设计中发展起来的。（有趣的是，大约二十年后，David Harel 在担任以色列飞机工业公司航空电子软件工程顾问时，发明了一种相当类似的技术－－Harel 状态图。）Glushkov 研究所大量使用并推广 R-技术 ：据说他们在该领域发表了 600 多篇论文（大部份是俄语的），就这一主题举办了三次全联盟会议和一次国际会议。它们甚至把 R-技术 标准化了－－R-chart，ISO/IEC 8631。 20 世纪 80 年代初，我从控制论研究所研究人员出版的几本书和发表的几篇文章中了解到了 R-技术。Glushkov 研究所出版的所有东西都给人一种和 R-技术 有关的印象。我还记得当时看到了画在一张大纸上的完整 Pascal 编译器的图表（R-图表）。 R-技术 基于一种描绘程序控制流的图表。节点是程序的状态，有向边（弧）代表状态转换。弧的上下方都有文字或图形的注释，上方代表转移条件/守卫（guard），下方则描述了该弧将要执行的动作（action），弧是水平的线条。当程序处于特定状态时，我们从上到下查找对应转移条件为真的弧，并执行弧表示的操作，然后把程序状态更新为弧的目标节点。R-技术 与流程图密切相关，不过流程图中的一个节点在 R-技术 图表中是一条带有注释的弧（在 Harel 的状态图中也是如此）。我们称 R-技术 图表为 R-图表，它所描述的抽象机器/自动机则称为 R-机器 或者 R-tran（RTRAN）。 上面对 R-机器 的描述可能会令人联想到状态机。这种相似性并非偶然：Glushkov 是著名的自动机理论研究者，他第一个提出了把正则表达式转化为非确定性有限自动机的算法，还撰写了《Synthesis of Digital Automata》（该著作为他带来了列宁奖和苏联科学院院士资格）。与有限状态自动机不同的是，R-机器 转换状态的条件可以不只是对输入的测试，可以是任意复杂的。稍后可以看到一个例子：那 R-机器 名义上只有两个状态，但它还有可变状态，其动作会更新可变状态，因此实际状态的数量是无限制的。在我看来，R-机器 看起来总是像图灵机，但 R-机器「控制」实际事物，其动作不仅是读写和移动磁带。 通常把 R-技术 图表绘制成图像，因此也称该技术为可视化编程技术。不过，用（风格化的）纯文本表示图表也是可行的。我记得在某本书中看到表示 R-程序 的表格，看起来有点像 FORTRAN 或 COBOL 程序输入到打孔机上打孔的样子。表格有四列，分别是当前状态标签、转移条件、动作和目标状态标签。可以按以下方法输入 R-程序：...

我们在上一篇文章中，描述了一个通用的优化技术： 找到时间差，把数据分成已知跟未知，并且用代码表示后者。 但是，这种做法有两个问题： 0 - 你需要费时费力去整这个东东，而且不是所有时候都能刚刚好复用代码。 1 - 如果我们预先不知道应该怎么区分呢？甚至，如果这是动态的呢？假设我们先接受一半的数据，等一会，然后接受另一半，那我们如何用上述的技巧？难不成把所有可能的分法都预先写一遍？ 所以，我们希望把上述技术，staging，自动化掉，使得程序员不再需要去关心之。 我们应该怎么做呢? 我们先从最基本的开始，先决定要操作的语言吧： type expr = | Var of string | Int of int | Add of (expr * expr) | Mult of (expr * expr) 这个语言，简单到了极点，只剩下+跟*两个操作了。别担心，我们会一步步扩展这个语言。 module ENV = Map.Make(String) let rec eval (e : int ENV.t) : expr -> int = function | Var v -> ENV.find v e | Int i -> i | Add (x, y) -> eval e x + eval e y | Mult (x, y) -> eval e x * eval e y 这是一个标准的definitional interpreter实现，中规中矩，并没任何出彩的地方。...

我们先从一个很简单的算法，快速幂，开始看起吧： let rec quick_mod x y m = if y = 0 then 1 else if y mod 2 = 1 then (x * (quick_mod x (y - 1) m) mod m) else quick_mod ((x * x) mod m) (y / 2) m let example_0 = quick_mod 10 1000 3 显而易见，10的n次方除3都会余1： utop # example_0;; - : int = 1 这个算法试图在y很大的时候，算(x^y) mod m。 很明显，这个算法只会进行log y次’*然后mod’的操作 - 我们把这个操作定义为⊕吧。 我们去深入思考一下 - 为什么本来要进行y次⊕，现在，我们只需要进行log y次⊕？...

有趣的CS已经很久没动了。有外因跟内因。 外因是一直在忙，忙着准备OOPSLA的talk，忙着给talk，OOPSLA过后忙着做下一个project，就慢慢把这个忘了 内因是因为知识消耗得差不多了 - 有趣有用而且没基础本科生又能听懂的接近PL的内容。。。实在不怎么多 但是最近要给一些关于Partial Evaluation的talk，所以就随便写点吧。

假如我们有一段某种编程语言的 stack-based 字节码： const1 ; 将常量 1 压入栈顶 const3 add const3 mult halt 在一个经典的 C 编写的解释器中，我们可能会有一个用类似 switch 的东西实现的循环，来解释执行这段计算 (3 + 1) * 3 的字节码。 enum { OP_CONST1, OP_CONST2, OP_CONST3, OP_ADD, OP_MULT, OP_HALT, }; void interpret(uint8_t insn[], uint32_t stack[]) { int pc = 0; uint32_t *st = stack; next: switch (insn[pc++]) { case OP_CONST1: *st++ = 1; goto next; case OP_CONST2: *st++ = 2; goto next; case OP_CONST3: *st++ = 3; goto next; case OP_ADD: st[-2] = st[-1] + st[-2]; st--; goto next; case OP_MULT: st[-2] = st[-1] * st[-2]; st--; goto next; case OP_HALT: return; } } 有很多原因导致这段代码性能不佳：...

别急！ 别急！ 我们先别急着切入正文，而是先看看一道算法题： 圆角骑士魔理沙：数组多次取第X大元素 大家在评论区可以看到，这道题有一定的难度：不少人给出了错误，或者超时的答案。 尽管最高赞给出的答案的确是正确的，其实有一个简单很多的做法： 对N生成二叉搜索树，然后用M索引之。 等下，这不是O(n log n)的吗？ 所以才说别急！我们想一想，当M < N的时候，这个二叉树，并不是所有节点，都会被索引。 那，我们为什么要去把不会被用的二叉树部分构建出来捏？ 但是，我们怎么知道‘树的那一部分会被用上’？ 答案是，我们可以同时交叉构建树跟索引树的过程 - 默认情况下，树是没构建的。当我们索引没被构建过的树，我们会构建这里的最小一部分，然后保存下结果，再进行构建。 class LazyBST: def __init__(self, arr): self.constructed = False self.arr = arr self.size = len(arr) def idx(self, index): if not self.constructed: self.constructed = True self.head = self.arr[0] self.left = LazyBST([x for x in self.arr[1:] if x <= self.head]) self.right = LazyBST([x for x in self.arr[1:] if x > self.head]) if index < self....

今天想说一篇比较著名的paper：scalability! but at what cost? 这篇paper说的很简单： 以前，大家benchmark分布式框架(比如spark)比的是scalability，就是说看看1024个机器的spark比1个机器的spark快多少。但是，大家并没有比一个框架具体是多快！ 比如说，你可以想象我们给spark加入一些负优化，导致spark在一切任务一切机器配置上都要双倍时间。这时候，scalability是一样的！甚至，我们给计算加入负优化，而不动数据传输，这时候scalability甚至会变好！ 很明显，这是个发癫的metric。paper提出了另一个metric，COST，就是：我一台机器实现的代码，你们要开多少机器性能才追得上？ 有的时候，是100台机器！ 这paper的内容，其实到这就完结了。很明显，paper最重要的点是：谓，审稿人，别发电了，赶紧用一个正经点的metric。但很明显，改了metric以后这点就不需要再看了。 但我依旧认为这篇paper很有意义。 更具体的说，我们可以想象这样一个故事： 你是一个普通的Java程序员。有一天，你的程序跑得不够快，被PM要求加快速度。 这时候，你想：我应该上多线程！于是你看了看Java标准库的多线程怎么弄，怎么加锁，然后弄了弄，程序多线程以后快了点。 过了会，需求增长了，程序性能不够快了，但是你已经开了尽可能多的线程。这时候，你想：我用更多机器就好了！于是就弄上了spark，然后，请了些运维，弄了些机器连在一起。以后，当你计算力跟不上的时候，加机器就好了。 随着机器数量的增长，运维管得越来越麻烦，然后，你听说了一个叫做kubernetes的东东，可以自动跑你的计算，就不需要运维了。你弄了弄，花了不少时间弄各种配置。。。 但其实，是不是有另外一条路可以走？ 在最初，当你程序出现性能问题的时候，你可以看看如何进行算法或者实现上面的优化。但是你用了多线程。这时候，你要面对race condition，死锁，bottleneck，contention等等正确性上面或者性能上面的问题。 然后，你遇上了这些性能问题，认为可以上分布式解决，这时候要给出数据传输的开销，还要思考集群的拓扑架构，然后机子出问题了还要retry。 处理这些问题太麻烦，于是你用上了spark根k8s之类的。 这时候你看看，本来你遇上了一个性能问题，你选择使用一种新方法解决这个性能问题。但是，这个新方法需要很多心思才能优化好。你没花这些心思，于是依旧有性能问题。你于是继续找更新的方法去‘解决’之，etc。。 这时候，最后的方案，真的比认真优化单核性能简单吗？

最近都在参加Splash/OOPSLA，就暂停了有趣的CS系列。 再过几天就回盐湖城了，今天也有点空，于是就写一写一些感想。 这某种意义上是我的第0个conference - 我以前参加过一次PLDI，但那是本科，也没给报告，也参加过一次ICLR，但那是virtual，而且给了报告，poster没啥人听，就相当于傻站了一个小时 我觉得最大感想，就是累 - 从离开盐湖城，到大概几天后回到盐湖城，我参加了几乎整整两周的会议+traveling。 travel的时候在飞机上或者在机场或者在车上，难以休息，到了会议早上要听报告听到黄昏，途中还穿插着社交 - 而社交很多时候都是一对一或者多对一交流工作跟idea，往往比单纯听报告还劳累。 不得不感叹，体力还是很重要的，而由于我太宅，体力好差，甚至怀疑比不上我认识的一个50多岁的教授，衰，希望可以慢慢锻炼改善。 另一个发现的短板是，口才不行。由于New Zeland（OOPSLA举行的地方）旁边就是ANU/Google Sydney，他们做的东东刚刚好也跟我做的有交集，所以我也过去宣传了一下我的工作。一般来说，我导师都会跟着去，跟其他人connect，也会帮忙回答各种问题。今天在Google Sydney宣传的时候导师在坐飞机，而且得到了一些关键问题，于是我就当机了，进入对对对模式，也可能会对后续落地有影响。如果有导师在解围，估计会好很多，但是这并不是知识差距 - 在project相关知识上我们俩知道的基本上一样，甚至我应该还多一些。这就是我没这个随机应变的能力。这就有点头疼，毕竟体力差可以去运动场找回来，但这样的报告机会差不多一年才有一次。 不过说点更正面的！我去了动物园！看到了kiwi！还有emu，摸起来毛茸茸的，也不知道躲！还摸了鳗鱼，很冷，所以就是冻鳗了！我从今以后，就是冻鳗高手了！！！ OK，说回正事，talk好像挺可以的，有很多人喜欢，而且结识了很多圈内人，好像都觉得工作挺有价值的。甚至，在visit ANU的时候，我们pair program成功在mmtk里面弄出了工作的hacky prototype。也跟做memory allocator的人讨论讨论了，可能可以用在这些地方。不得不说Steve的眼光真是毒辣，他arrange了一个跟allocator maintainer的meeting，说了下可能用得上，还真猜中了。 另一个重要的事情是，超人也会流血。在oopsla/澳大利亚，我近距离接触了一些以前只能在教科书跟经典paper上看到的人物，而这过程中我认为它们更像走在前面的前辈，是普普通通的人，而不是一种‘神话生物’。诚然，我能力跟各种做教授年龄比我存在年龄还大的人对比，有很大差距，但我认为这差距可以随时间缩小甚至填补。 甚至，我还看了一个著名教授做了一个。。。烂活。如果你挡着名字跟会议，我还会以为是各种奇怪workshop的新人论文。某种意义上，这反而很有价值（笑）。（当然，请大家别猜是谁，我还想活） 另外，跟各种教授还有工业界的人聊了聊以后，再去了次Google以后，对做教授或者去工业界的抗拒度降低了，其实还行，挺好的。当然，如果能被富婆包养就最好了，这样就可以一心做research，不考虑什么教书什么grant，也比工业界有更多自由，想做什么做什么。如果大家认识富婆，可以介绍介绍给我！ 至于看了什么talk? 跟人闲聊的时候学到了probabilistic separation logic，很漂亮。在普通的分离逻辑里面，magic wand代表的是两段内存没有交集，而在probabilistic separation logic里面，表示的是两个概率分布独立！ 而我认为最有意思的talk，是Deciding program properties via complete abstractions on bounded domains。简单的说，就是在一定条件下，有loop, ifelse, assignment的语言里面抽象解释可以是complete的，而且这个completeness是composable的 - 就是说只要对ifelse/assignment complete，也会自动对loop complete。以前没怎么见过这样的工作。 明天还有meeting跟socialize，睡觉。

“Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowchart; it’ll be obvious.” – Fred Brooks, The Mythical Man Month (1975) 吐槽一下，最近手指好疼，怀疑打字打太多了，等下有空看看医生，orz 我们先看这一个著名的笑话： 三个程序员被要求穿过一片田地，到达另一侧的房子。 菜鸟程序员目测了一下之间很短的距离，说：“不远！我只要十分钟。” 资深程序员看了一眼田地，想了一会，说：“我应该能在一天内过去。”菜鸟程序员很惊讶。 大神程序员看了一眼田地，说：“看起来要十分钟，但我觉得十五分钟应该够了。” 资深程序员冷笑了一声。 菜鸟程序员出发了，但只过了一会，地雷爆炸了，炸出了巨大的洞。这下他必须偏移预定的路线，原路返回，反复尝试穿过田地。最后他花了两天到达目的地，到的时候颤颤发抖，还受了伤。 资深程序员一出发就匍匐前进，仔细地拍打地面，寻找地雷，只有在安全的时候才前进。他在一天的时间内小心谨慎地缓慢爬过了这片地，只触发了几个地雷。 大神程序员出发之后径直穿过了田地，十分果断。他只用了十分钟就到了另一边。 “你是怎么做到的？”另外两个人问道，“那些地雷怎么没有伤到你？” “很简单，”他回答道，“我最初就没有埋地雷。” 一般来说，我们写程序，都是这样的步骤： 0：写出程序 1：写测试 2：通过测试查找错误，回到0修补，如果没发生问题就假装程序写好了 这时候有一个很大的问题：debug是一个很麻烦的过程，而且debug后不代表程序没有问题，只代表了程序在这些测试上没有问题（所以你还要牢费心力找测试）。更严重的问题是，在多线程或者分布式系统里面，同一段代码同一段输入，问题是概率性的：有可能会发生，也有可能不会发生。更更糟糕的一点 - 这些分布式代码，比如paxos的实现，往往是最核心的代码，当这些代码发生问题后，会带垮整个服务器集群，造成巨大的损失。 但是，为什么我们要劳心劳力的去debug？我们不把错误放进程序，不就好了？ 或者，我们更进一步，为什么要写程序？把程序种子埋土里，然后过几天等程序长大了，就收掉，不就行了？ 你先别笑，这的确是编写复杂程序的一个方法。 更具体的说，当我们程序运行到一半，假设我们随机修改一下变量的值，很明显程序不会没问题的继续运行下去。 比如说，如果我们在写一个二叉搜索树，当我们运行的时候，把一颗树的最左节点跟最右节点交换了，那接下来可能会找不到需要的值。 也就是说，我们的程序需要遵守一定的规则(invariant)。对于上面的例子来说，我们需要遵守的invariant是，一个二叉树的左边的所有节点小于等于自身，自身小于等于右边的所有节点。 所以，我们写程序的时候，要保证这些invariant的正确性。但是，我们可以反过来，从这些invariant，推导出一个程序！ 更具体的说，我们 0 - 写下程序输入跟输出符合的条件，一般来说，输入的条件并不等价于输出的条件，所以这时候，这两个条件之间，是有一个空缺的 1 - 根据这些规则，猜出一小段代码，这些代码会把这些空缺变得更小，然后我们不停进行这个操作，直到空缺消失。这时候，程序就编写完成了。...