计算机科学

今天想说一篇比较著名的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。。 这时候，最后的方案，真的比认真优化单核性能简单吗？

“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 - 根据这些规则，猜出一小段代码，这些代码会把这些空缺变得更小，然后我们不停进行这个操作，直到空缺消失。这时候，程序就编写完成了。...

最近电脑坏了，所以上周没法写文章，抱歉。 随着AWS Automated Reasoning Group的兴起，可以感受到了编程语言在工业界的影响力的加大（这不废话吗，这么多人都被吸过去了），顺带不久前看了github semantic的ICFP Experience Report，想了想可以写一写关于这些的内容。 这方面一写paper是(缩写C)，讲coverity的程序分析框架在应用的时候的问题，<Fusing Industry and Academia at GitHub (Experience Report)>(缩写G)讲github内部的程序分析框架semantic，还有(缩写A)，讲AWS如何利用SMT solver对云上控制权限的验证。 其实ACG三篇paper都有很多共通点，我觉得与其一篇篇介绍，不如对ACG做一些总结 为什么要整X? A:没说 C:我们一开始是为了publish paper，在几百万行代码上抓了很多错误，publish了paper以后，就觉得可以搞个大的。开家公司，请几个销售员躺着数钱钱，当然这考虑完全错误 G:做一个更好的，知道语义而不是只知道unstructured text的git diff 有没有遇到什么克苏鲁问题？ A:没有 C:好多，惨惨，哭哭。有一次我们跑用户的make，结果用户用了个奇奇怪怪的make语法写path，结果在蝴蝶效应下变成了rm -rf *。用户经常会给我们奇奇怪怪，不符合C语言标准的程序，然后因为各种原因无法改C编译器，最后要我们改自己的C parser。还有一次，给用户抓出use after free error，用户说free了以后还没malloc，所以freelist没有被复写，可以继续用，气死偶嘞！（整篇paper都是各种这些克苏鲁问题） G:没有，卧槽free了后依赖于没有malloc继续用也太克苏鲁了 有没有遇到什么不克苏鲁的问题？ A: 我们遇到的最大问题是只有很小一部分用户会写SMT Query或者First Order Logic。但是，AWS有一百万用户，没有办法教这一百万个用户都写SMT。所以，我们把问题反转过来 - 对于一个输入（系统设置），我们会返回所有的信息（对于所有最终用户X跟数据Y，X能不能访问Y）。这时候，AWS用户只需要检查这些访问权限报告，就知道行不行了。 我们遇到的另一个问题是，当我们升级我们的SMT solver的时候，有的时候以前能Solve的Query会timeout，于是对一些用户来说，以前行的东东就不行了。我们的解法是，弄一个大大的portfolio，各种solver version都丢进去。 C: 我们也一样有软件升级问题。当我们升级完我们的静态分析器的时候，我们往往能抓更多错误，但这是不好的！更准确的说，我们的PM往往都想要一个这样的故事：‘我们引入了静态分析器，然后发现了X个错误，然后在过去Y个月里面，我们把这X个错误一步步消除掉！现在，我们的程序没有错误了！’，然后当他们升级软件的时候，错误越来越多，就会很气气！ 另一个问题是，用户会不停提交代码，而如果你以前报过一次错误，同样的错误就不要再报了。我们写了一个错误database，然后会把所有分析出来的错误跟这个一一对比，只报告新的。 还有一个问题是，当我们报错误的时候，用户有时候看不懂，然后就会把我们的错误看成误报。当用户认为我们误报的时候，就会更不信任我们的工具，于是下次我们报错会更可能认为是误报。于是，我们需要很好的错误信息，并且对于一些复杂的静态分析，给出好错误信息更难，如果我们给不出好错误信息，我们宁愿不要这个分析。 G: 我们的新git diff能给出很有用的summary，于是得到了更多momentum（大概是有更多资源招程序员整这个）。但是用户不想安装跟用我们的新git diff。我们只好弃掉这个project。 更具体的说，我们不做git diff了，我们用我们整的静态分析工具弄一个Code Navigator，当你指定一个函数的时候，我们用静态分析找出这个函数用在那。 总结： 我觉得这三个工作都有一个共通点：如何包装销售自己的工作(Story)很重要。这里的销售并不是’口才很好‘的意思，而是’向谁卖什么‘。对于A用户来说，他们甚至不知道什么是SMT! 这时候，这整个工具就相当于’隐形‘的，需要跟用户打交道的地方小了很多（只剩下保证版本不会regress）。C用户会不停看到Coverity的工具，于是要求也最高。G也一样有这个问题，但是他们明白Story是可以改的，于是换了一个就好了。 当然，C的方法并不一定更’不好‘ - 在一些时候，这可以抓出’关键的错误‘，而semantic则做不到这个（因为已经包装成不是抓错误工具了）。更重要的是，C引入了一个叫’话语权‘的概念。当你的工具刚刚引入的时候，大家都不知道你的工具是做什么的，也不信任你的工具，于是会e.g.把错误看成误报，不看错误，或者就e.g.不会升级，或者买静态分析服务。所以这里有一个很典型的网络效应 - 在前期要给出很多精力去一个个服务用户，但是后面工具变出名了以后就不需要了。C也说了一句‘好日子在后头’之类的话：在以前静态分析没有C的时候这么流行，于是它的前辈要做的斗争更难。可以预想的是，很多这些都是‘一次性开销’，后续工具的应用会更简单。 另外，Github：Haskell真香，ICFP是我的秘密武器！

想了想，最后还是觉得应该用这篇paper开头。 什么是Defunctionalization? 简单的来说，Defunctionalization是一个程序变换。更具体的说，Defunctionalization接受一个高阶编程语言的程序，输出一个一阶编程语言的程序。这通过一下变换完成。 创建一个代数数据类型，lam，跟创建一个函数apply: (lam * Any) -> Any（是的，naive的Defunctionalization并不类型安全） 对于所有a -> b类型作为一等公民（不是直接调用）出现的地方，把类型a -> b变换成lam。 对于所有构建闭包的地方，创建一个新的lam构造子。这个构造子的成员就是这个闭包捕获的变量。 同时，在apply函数内，给出该lam构造子的实现 - 而这实现照抄原closure的body。 对所有调用闭包f x的地方，改为apply (f, x)。 举个例子，假如我们有以下代码， (* aux : int * (int -> int) -> int *) fun aux (i, f) = f i (* main = fn : int * int list -> int list *) fun main (i, js) = let fun walk nil = nil | walk (j :: js) = (aux (i, fn i => i + j)) :: (walk js) in walk js end Defunctionalize后，会成为...

已经有很久没写文章了。 原因大概是，随着科研的进展，我看的paper，往往越来越冷门小众，也越来越‘高深’。 这时候，我对介绍这些paper动力越来越小 - 一方面，我自己都不能经常完全搞懂，那这时候我介绍效果会比原文差很多（甚至会出错！），而另一方面这些paper的受众也越来越小。 但这好像有点不对 - 如果人人都像我这样，那写文章的人岂不是都是公众号？ 所以我决定以后写一些CS里面浅显但有趣的知识，吸引读者关注各种领域，坚持一周一更 为啥要写一个公告而不是直接写捏？ 一个原因是，这样有个外部的deadline，鞭策鞭策自己 另一个原因是，尽管专栏好像不能投稿了，希望大家可以留言/私信我有趣的东东，这样我有更多写的材料 就这样。

（其实我倒数第三第四章跳了，实在看不动了。。。orz） 初看之下，这本书很逗比：身为一本算法书，只有十多个算法，一半的时间用来定义不知所云的奇葩语言，语言枯燥无比。。。简直什么鬼= = 如果你这样想，只能表明你完全没看进去：就跟Software Foundations是包着Coq皮（想歪的去面壁）的PL书一样，这本书比起纯正的算法书，更算得上是以算法之名，讲PL，讲如何编程，如果你只是来 看算法的话，你一定会失望。如果不是，你来对地方了：读完以后，你会对dijkstra 的The Humble Programmer之类的EWD有着更深的了解，会对computation 改变认识，知道该如何写代码，有一些reasoning/deduction的heuristic，也会感叹于dijkstra疯子般的radical reasoning下，就是不会学到什么算法（除非你算法跟我一样弱得过不去NOIP初赛） 前一半的不知道叫什么的语言已经是一绝了，我看之前完全无法想象跟while大同小异的一门语言能给我带来如此巨大的震撼-formalism跟minimalism尽管不是不可见，但是语言最核心是由nondeterminism construct构建起来的：你有没有考虑过其实你每天用的if语句其实是个败笔？该语言的variable设计也是神来之笔，我一开始看的时候也没明白为什么在极简主义的语言里面要引入如此复杂的东西，认为是画蛇添足，直到一遍又一遍的看，才领悟了精妙之处。。。完爆某另一个图灵奖得主写的算法书里面的不知所云的语言（ 后一半是利用这个语言解决各种问题，比如equivalence class，比如shortest spanning tree。。。一开始他是以极度formal的tone做这个的，proof什么的一个都不漏，到了后期你明白怎么搞了，由于篇幅关系，跳掉了一大部分formal proof，left as exercise，更着重于：我们如何解决这个问题？并给出了一定的example/heuristic，比如对intermediate step做出assumption，（shortest spanning tree中，assume已经决定的set of edge自己也是shortest spanning tree）（换句话说在什么时候需要加强induction hypothesis），比如当你代码钦定了什么的时候，利用之来优化（对一个naive 算法由3 pass改成2 pass，得出Rem’s algorithm），比如把计算从循环中往外拉，改为incrementally update之。。。 这本书其实绝大部分时候都在讲如何去对一个又一个的问题进行分析，分解，最后解决之-一开始的语言设计是如此，后面的算法也是如此，看这本书的过程，更多的像是跟dijkstra一起研究如何解决一个又一个的问题-从问题的定义下手，用直觉更heuristic找出可能有用的insight，并用之分解问题（算法设计），亦或者从现有的方案下手，质疑一切，找出问题，然后精简，或者去掉之（语言设计）。确实，Dijkstra 最后说了大概这样一段话：我们的确不太可能看完一本书，就明白该如何思考，但是我希望你读完这本书以后，能用seperation of concern之类的办法（没错，Dijkstra 发明了seperation of concern，还发明了pair programming，是软件工程中很重要的人（雾）），对一个复杂的问题，进行分解，导致不再复杂，是intellectually manageable的。 不过语言的确很枯燥，英文勉强的不用读了，这更多的我觉得是dijkstra认为“难的东西就是难的，无论如何修饰也是如此”导致的。。。

我想说一些旧闻。更准确的说，我收集了很多旧闻，想整理一下，变成一个没那么旧的旧闻。 0：对于很多编程语言，我们真能做到‘给出编程语言X跟Y，给X一步步加功能，修改下原本的功能，最后成为Y’。我们姑且叫这做计算力吧。这方面的Work数不胜数。 对于Effect，我们有： C is a purely functional language Dijkstra Monad（被EK吐槽就是hoare monad on continuation） Lazy Functional State Thread Lambda The Ultimate Imperative Gedanken 对于Subtyping，我们有： The Essence of Algol（这也应该算Effect的，但那边挤满了） A Semantics of Multiple Inheritance 至于Type？那就更多了 Untyped Program is unityped program Gradual Typing上的work，不太清楚 Well typed program cant be blamed Type System as Macro Semantic上面有Unified Theory of Programming 编译器上面某种意义上也符合这个样子，如Lambda The Ultimate Goto，Compiling With Continuation，就是在给你说‘你看，函数，高阶函数，其实还是goto那一套。’ 当然，LTU Goto严格来说不算Compiler，各种东西都算一点，但不放这一个Compiling With Continuation好孤单（ 最后，Prolog也能这样搞，Dijkstra老爷子厉害啊，一个小改动（GCL）竟然能影响到这 1：在PL以外，我们也能做到这点，有的时候还能直接unify出以前还没发现的东西 A Unifying theory of Garbage Collection - 你看看，各种GC算法都是一个路子的...

最近跟人聊天，他说物理学停歇不前，那像二战的黄金时代，产生了相对论跟量子力学。于是，我想起了去年刚学历史没多久的自己。。当时我觉得CS的黄金时代 - 1960~80已经过去，互联网，OS，GUI，Computer Architecture，等等，全部出自那个时代，而我们只是想方设法去monetize这些。唉。 现在看来，实在是有失偏颇。 要对历史/当下做评价的最主要的问题是，credit assignment实在太难做。 举个例子，大家是如何看待区块链的？ 我曾经问过我的PHD同事/朋友，他们的答案，除了一个就是搞区块链的，通通是‘敬而远之/bubble/pyramid scheme’。 而这的核心，是因为区块链‘没有现实价值’。 而1970年代的Xerox高层是怎么评价Xerox PARC的？ ‘没有用’‘白花钱’。 看出问题了吗？如果我们真穿越回1970，说不定我们会感叹着真是一代不如一代，老冯搞出了老冯架构，IBM搞出了计算机架构，海軍准將弄出了COBOL，一推人搞出了Algol，我们就有些民科般乱搞的人。 而他们也情有可原 - 1960~70出现了PC&GUI&Tablet/Smart Phone的概念，一直到90才步入大众（phone得到2010），而70年同时的出现的internet呢？Amazon在dot com bubble受到的影响一直到2010才恢复过来，这整整隔了40年。从一个东西被发明，到走到现实，往往需要很久的时间去降低成本/建立中层建筑/寻找应用。 而区块链只出现了10年，根据历史的发展，很可能30年后才兑现 - 现在评论区块链有没有用，实在太早。 但是，如果最近各个还在发展中的idea（block chain/deep learning/quantum computing），真在几十年后被发现是www级别的idea呢？ 那我们这就不止是第二春 - 黄金时代只是现在这时代的前传。 甚至，还有个更基本的问题 - internet固然是伟大的发明，bob taylor 当初也没有预料到会有 search engine存在啊。这credit多少得给Parc/Bob，多少Google？ 那，什么时代是最好的时代？ 杨过问道：“郭伯伯，你说襄阳守得住吗？”郭靖沉吟良久，手指西方郁郁苍苍的丘陵树木，说道：“襄阳古往今来最了不起的人物，自然是诸葛亮。此去以西二十里的隆中，便是他当年耕田隐居的地方。诸葛亮治国安民的才略，我们粗人也懂不了。他曾说只知道‘鞠躬尽瘁，死而後已’，至於最後成功失败，他也看不透了。我与你郭伯母谈论襄阳守得住、守不住，谈到後来，也总只是‘鞠躬尽瘁，死而後已’这八个字。” 我认为，学历史，是为了抓住&复现各种机会，而不是去怀古伤今或者轻议冢中人 - 那实在是太难了，谋事在人，成事在天就好。

You and Your Research如何做research One man’s view of computer scienceCS是啥，可以如何改革（图灵奖得主演讲） 另外膜一下bret victor，推上跟人聊天竟然可以用这个引经据典谈笑风生。。。 On the cruelty of really teaching computing science (EWD 1036) 同样是CS是啥，如何改革教育，我更喜欢这篇，很多很罕见的观点（类比之死，用CS做数学，反智的教育，徒劳无功的‘软件维护’，Characteristica universalis）等等 The Humble Programmer (EWD 340)这也可以看看

如果大家看过近期的文章，会发现有很多其他人写的文章，比如 @Canto Ostinato 的Stackage 镜像使用说明， @lotuc 的Programming Languages: Application and Interpretation【译6】，@Skillness 的C++模板元编程—lambda表达式简单实现， @品雪 的函数式编程的早期历史， @祖与占 的函数式又是函数式等等。 我认为这些文章都写得挺不错，于是决定开放投稿。 投稿的好处都有啥？你的文章会被更多人看见。 投稿话题偏向于（排在越前越代表同等质量下更大几率接纳）： 0：计算机科学，尤其是编程语言/人工智能相关的 1：数学，最好偏向CS（如离散数学） 2：偶尔会接受点娱乐向的，比如 @Canto Ostinato 的小说，跟车万。。。 如果你在你专栏/你的blog投过稿，你可以把该稿同样投放于此专栏。甚至，你可以在文章内连接自己的**专栏/个人主页，创造回流。 ** 另：如果你短时间内投了大量稿，为了防止刷屏，将会分批处理。 不过如果是1跟2，也请踊跃投稿-我希望专栏文章不要过于单一，如果全部都是haskell的blog的话会很单一的 内容包括但不限于 paper/project/书的广告 技巧/算法/工具/什么鬼的介绍 对啥啥啥的评价