注：这跟genetic programming毫无关系。 最近，我有一个任务：我要写一个Partial Evaluator。 更具体的，这是个Simply Typed Lambda Calculus加上Reference/ADT的Partial Evaluator（PE）。Lambda Calculus上的PE很多人都做过，但是加上Reference就不好办了。我找了很多Scheme/ML的PE的paper，但是在里面，很多都对Effect闭口不提。就算提Effect，也是‘遇到Effect不做PE，跳过就好’。 没办法，我只好自己设计。凭借着我对Partial Evaluation跟Staging的理解，我弄了一个这样的设计： 0：我们先写一个Definitional Interpreter。 1：我们reify the Store。 2：我们利用MetaOCaml式的LetList写一个ANF converter。 3：我们把Definitional Interpreter的Value lift上Partially Static Domain，然后跟ANF converter‘合并’- 这样，Partially Evaluated Code会生成ANF代码，于是就没有code duplication跟capture avoidance substitution的问题。 别急，我们来一步步来看这是啥意思。 0：我们先写一个Definitional Interpreter。 type ('a, 'b) sum = Left of 'a | Right of 'b type var = Var of int type term = | Let of (var * term * term) | FromVar of var | Abs of (var * term) | App of (term * term) | Unit | Int of int | Add of (term * term) | Mult of (term * term) | IfZero of (term * term * term) | MkProd of (term * term) | Zro of term | Fst of term | MkRef of term | SetRef of (term * term) | GetRef of term | TLeft of term | TRight of term | Match of term * term * term type 'a env = int -> 'a let emptyStore _ = raise Not_found let extend e v x = function i when i == v -> x | i -> e i let genCounter () = let cnt = ref 0 in let gen () = let ret = !...

（其实我倒数第三第四章跳了，实在看不动了。。。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认为“难的东西就是难的，无论如何修饰也是如此”导致的。。。

几天前，我的一个朋友给了我一个Haskell问题 Hey, MK，假设我有个BNF，并且我在Haskell中有个这个BNF的parser。 现在，我想给这个BNF改一行，有没有办法不用动这个BNF parser的代码（因为是其他人写的），而是对这parser进行扩展呢？ 这问题挺有趣的，也不算难。 这问题说是extensibility problem，其实有两个地方需要扩展。 0：Parser需要用open recursion之类的方法扩展 1：Parse出来的ADT也需要可扩展性 后半个需求见多了，Final Tagless，DTALC，Tree that grow，Recursion scheme style fix。。。于是放下不表，我们来处理前一个。 前半个。。Haskell’s Overlooked Object System就搞过，当然他们有点heavy weight，打算随手弄一个超级轻量级的：5行就够了，多一行是小莎莎。 Ready？ data Object x = MkObject (x -> x) 1。Inheritance is not subtyping式的Object=recursive type。为了简易性（反正也不需要多高的扩展性）就不model真。recursive type，而只有recursive dependency。 use :: Object x -> x use (MkObject x) = let res = x res in res 2。3。最典型的tying the knot。其实就是fix了。 我们想想，这个x是什么variant的呢？covariant还是contravariant？ inherit :: (a -> b) -> (b -> a) -> Object a -> Object b inherit ab ba (MkObject aa) = MkObject (ab ....

我想说一些旧闻。更准确的说，我收集了很多旧闻，想整理一下，变成一个没那么旧的旧闻。 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算法都是一个路子的...

什么是Tail Call？ Tail Call（尾调用）指，我们调用一个函数后，立刻返回。 def triple(x): # 返回的不是函数 return x * 3 def is_tail_call(x): # 是尾调用，因为我们调用后就返回了 return triple(x) def not_tail_call(x): # 不是尾调用，因为我们调用完还要1 + result return 1 + triple(x) def half_tail_call(x): # 外面的是尾调用，里面的不是 return triple(triple(x)) 在以上例子中，is_tail_call的triple，跟half_tail_call的外面的triple，是tail call。 为什么Tail Call很重要？ 因为Tail Call提供了很好的优化。 假设我们是register machine，return address存在一个register里面，如果我们tail call，我们需要：把argument放对位置，然后goto function就可以了！ 如果是non tail call，我们需要把argument放对位置，保存旧的return address（比如说塞上stack），设定return address为下一行，goto function，把旧的return address restore掉，然后该干啥干啥。 这样，我们额外的多做了一push一pop，space & time overhead一下子上来了，怪不得60~70年代的人不肯用函数。。 当我们递归的时候，不做这个优化导致了big O上的空间差距 - 一个要不停的push stack，一个说，stack是啥？ 另一点是，当递归的时候，argument的位置是对的，‘放对位置’这一步就没有了，于是就成为了一个goto self - 也就是loop。 尾递归优化，其实就是Tail Call Optimization在taill call self下的优化。（见Debunking the ‘Expensive Procedure Call’ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO）...

这是我接触Java的第二个星期（雾），大概是自己上手最快的语言了吧。 作为一个菜Haskeller，总想人肉将Haskell代码编译到Java上。 看了A little Java这本书，相比于Thinking in Java这些“传统”一点的书，觉得挺耳目一新的。 今天就把学到的东西记录一下——「利用Visitor Pattern模拟ML系语言的Pattern Matching」 当然，在OOP里面模拟Pattern Matching也是一件特别有成就感的事情，毕竟Pattern Matching这是一个特别好用的东西。 先看最简单的Maybe（写成Option）模式匹配的例子： data Option a = Some a | None getOrElse :: Option a -> a -> a getOrElse opt other = case opt of Some v -> v None -> other 然后再看看在Java里面如何表达。首先要定义等价的数据结构： abstract class Option<T> {} final class Some<T> extends Option<T> { private final T value; Some(T v) { value = v; } } final class None<T> extends Option<T> {} 可以将Java中抽象类表示一个Datatype，然后将继承这个抽象类的类作为这个Datatype的变体(variant)。然后如何模拟模式匹配呢？有请今天的主角：Visitor Pattern。用一个visitor来访问每个变体里的字段。...

各位国庆快乐！ 好久都没写东西了，就随便找个借口写点东西吧。 既然国庆放七天，我就随手推荐七篇paper吧，在脑袋里面找出来的，以前可能推荐过，不要见怪。 Generic Deriving of Generic Traversals - 好中规中矩的paper，就是说‘我用generics搞出了scrap your boilerplate without runtime type checking’，没有任何novelty。不过数字好漂亮啊！ Generic Programming of All Kinds - 靠De Bruijn Index跟各种扩展把True Sum of Product搞上gadt/constrainted/rankn等等等等。几天前当 @Felis sapiens 到西雅图来玩的时候曾经问他‘True Sum of Product跟Scrap Your Boilerplate你选那个’，结果他竟然给我说GHC.Generic！原因是TSOP/SYB等难以搞上复杂一点的类型（GADT/RankN）。现在看到这篇paper，越来越觉得有道理 - 这搞是搞上去了，不过好复杂，说不定反而比Generic用起来更麻烦呢。 Demystifying Differentiable Programming: Shift/Reset the Penultimate Backpropagator - 这是The paper on AD。曾经想过，其实只有两种AD算法，forward跟reverse，其他的一切ad算法都只是这两的变种（numerical ad是forward，但是不用infinitesmall，改某个足够小的值，symbolic也是forward，但是没有cse，同理，把wengert list变成runtime datastructure就是higher order reverse mode），然后写个blog。结果发现，这不就是这篇paper吗。结果竟然被ICFP拒了，什么鬼。 Beautiful differentiation - 这篇paper提出了differentiation tower，一次求出无数个导，挺漂亮的。另外也是conal照常的猫论时间。 Lightweight Static Capabilities - 教你怎么在不玩type level programming的情况下实现某种意义上的dependent type。 Ghosts of Departed Proofs - 上面内篇paper的扩展，变得更general了...

最近在群聊的时候，我们聊到了一个观点。 亚里士多德时代的科学不可能容许黑魔法，因为亚式科学的核心是 - 用直觉观察事物，得出物体的本质。黑魔法这种反常识的东西，只可能在可证伪科学体系下出现 - 这不你看，js就是现代产物（ 我的一个写C++的朋友趁机黑一把：‘函数式编程也是现代产物’。 我想了想，拿出了收藏已久的The Craft Of Programming。 为什么呢？很简单：这本书是本Gateway Drug。 这是第13页。很简单的Imperative程序，跟FP的学院派黑魔法正好形成鲜明对比。 17页开始教你怎么自顶向下写程序，很稳啊，一步一步来。 22页。给出程序的时候还加入了大量assertion，保证出错能debug到问题的那一行，很健壮啊。 这本书有400多页，太长了，我得加快进度。跳到了第44页，好像还行啊，这在说，假设满足P下运行程序S1，会满足Q，满足Q下运行S2，会满足R，满足P下运行S1后接S2会满足R。 直觉上还挺好理解的。。。不过为啥越来越学院派了？ 89页。我是在上逻辑学课程吗？ 95 97页。函数出来情有可原，为啥出现了交换图？喵喵喵？ 159页。be。。beta reduction？ 178页。有高阶函数已经算不了啥了。 206页。Environment跟Denotational Semantic都出来了。 到了这一步我们有啥？ program calculation（stepwise refinement) equivalence law type derivation simply typed lambda calculus environment denotational semantic 这跟SML还差啥？ HM？（我们可以写generic program，这些program等价于inline，然后因为是inline，所以有equivalence constraint。用这些constraint可以导致不需要写类型，可以去推导） ADT？（其实这门语言是Algol W，已经有ADT了） First Class Reference？（且不说Reference怎么算作函数式特性，这本书作者，John Reynold的Essence of Algol里面就很好的引入了Reference。） Garbage Collection?（试想象下C程序员指着Java程序员说你丫太学院派了） 所以说，你看看，Imperative Programming跟Functional Programming有啥本质区别呢？这些特性，每一个的加入都如此理所当然，但是那一步才算是一个‘函数式编程语言’？ 我们早就过了亚里士多德时代，发现了世界并没有这么多‘本质’。无论是那种语言，都是一步步从已有语言摸索出来的，只要你跟着，每次都学一个最小改动，到最后，你也会发现‘就这回事啊’。Lambda Cube是如此，Algol到Prolog是如此，Algol到Haskell更是如此。 既然编程语言之间并没有本质差别，那，什么是编程的流派？什么是面向对象/函数式/过程式？编译语言/解释语言/机器语言/电路描述语言？ 答：流派未月亭。没有打错。没有发疯。 在起初，John Mccarthy没搞懂Lambda Calculus，导致JMC Lisp并不对应Lambda Calculus，连Lexical Scope都没有。Lexical Scope是Algol加入的，而编程语言跟Lambda Calculus的对应是Landin发现的。但这不是跟ISWIM对应，是跟Algol！OOP的元老之一，Luca，做过ML Module的奠基性工作，另一个元老，Alan Kay，借助了FExpr（MACLISP）的概念。Backus写出了Fortran后广播了不朽的’Can Programming be liberated from Von Neumann Style?...

大家520快乐！祝各位都能跟心仪的另一半进行crossover，产生fitness更高的后代哦~ 蛤？你没有另一半？没关系，本小编发现了一个库，用了这个库，你就能跟心仪的数据结构进行交合了哦~ 更厉害的是，交合对象跟你种类不一样也可以呢。甚至，多p交合也是小事一桩哦~ 你还在等什么，快来implement你内心深处的privateの梦吧！ http://okmij.org/ftp/Haskell/extensible/#crossover Extensible Effect旨在解决一个问题：如何Extensible的添加新Effect（这不废话吗） 我们的老朋友Data Type A La Carte酱尽管对Extensible挺能干的，但在这其实挺苦手的 - DTALC并不能Extensible的改变返回值，而每次新增Effect都需要这样做。 在Generic Crossover中，Oleg用Extensible Effect实现了一个State，一个Coroutine，然后就可以用两个effect来（加上SYB）作任意crossover 圆角骑士魔理沙：一招鲜，吃遍天 里面Session Type作法也很漂亮 - 更准确的说，看OK大法（final tagless，eff）的时候都会觉得像他那样做是正当作法，很trivial/natural，但是往往他本人也要一段时间才找得出来（可以看看eff的前身，当时还依赖奇奇怪怪的Request） 顺带一提，我很喜欢PL的原因是，概念是高度Composable的，新的概念往往可以用毫不相干的旧概念实现 - Generic Crossover用了Eff跟SYB，SYB自身又依赖于Typing Dynamic Typing这种做法，更极端的情况我觉得可以看EK这个comment： https://www.reddit.com/r/haskell/comments/387ex0/are_extensible_effects_a_complete_replacement_for/crt1pzm/ 更具体讲，一半lambda the ultimate一半growing a language呢。 http://library.readscheme.org/page1.html https://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf 另：The Reluctant Heroes莫名的好听 另另：知乎你们搞什么鬼，NLP做得这么烂，默认文章问题有生物学就算了，蔡英文跟马英九什么鬼，好歹要加入用户历史数据作prior啊

最近跟人聊天，他说物理学停歇不前，那像二战的黄金时代，产生了相对论跟量子力学。于是，我想起了去年刚学历史没多久的自己。。当时我觉得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？ 那，什么时代是最好的时代？ 杨过问道：“郭伯伯，你说襄阳守得住吗？”郭靖沉吟良久，手指西方郁郁苍苍的丘陵树木，说道：“襄阳古往今来最了不起的人物，自然是诸葛亮。此去以西二十里的隆中，便是他当年耕田隐居的地方。诸葛亮治国安民的才略，我们粗人也懂不了。他曾说只知道‘鞠躬尽瘁，死而後已’，至於最後成功失败，他也看不透了。我与你郭伯母谈论襄阳守得住、守不住，谈到後来，也总只是‘鞠躬尽瘁，死而後已’这八个字。” 我认为，学历史，是为了抓住&复现各种机会，而不是去怀古伤今或者轻议冢中人 - 那实在是太难了，谋事在人，成事在天就好。