最近计算机架构课组织了一次去Living Computers - Home的春游（误？），可惜迷路了，导致来晚，只看到一小半。 很好的一点是里面的计算机都是可远观而亦可亵玩 - 事实上我们的作业就是随便找台计算机在上面编程。 对于喜欢计算机历史的人来说很爽啊 - 从书上看着各种电脑各种OS是一码事，真正的看到，然后摸，还能用，感觉完全不一样。 尤其是还有Xerox Alto。还有个巨大的装着Smalltalk的盘盘。把老娘的爪爪放在圆圆的Smalltalk上然后插进Xerox Alto真是满足死我了。可惜不知道为啥Smalltalk跑不起来 - 放太久了？ 信仰++++。 然后Digi-Comp（见https://www.youtube.com/watch?v=_tZdE-3nR3w）也很好玩。 另：某Lisp厨失望了 - 没有Lisp Machine。 另另：有辛去的话，推荐下Pecos Pit Bar-B-Que，好好吃，实习以后大半年都没吃到这么辣的东西辣，sad

我最初学编程，应该也就是2010年左右的事情吧。 当时啥也不会，就会在C++吧水贴。 在那，听说过了有一个很厉害很潮流的东西，叫做C++11，有什么叫concept跟module的东西，好像挺厉害的样子。 当时，在clang上就可以用C++11了，只不过这两功能还没有，就有auto, lambda, constexpr 不知道有没有（记不清了），也很好了。 时间快进到现在，这两功能还是没加进去。 不过C++厨们可以稍稍放心，我今天不是来黑C++的。 这固然是C++的悲剧，不过也是所有语言的悲剧。 如果去看历史，去看看一个个语言的发展，我们会发现一个规律： 语言/语言家族的发展，是不停的扩大，直到无法支撑自身的重量而倒下为止。 让我们跳到1958。 ALGOL。 只要大家说计算机历史，就一定要说ALGOL。 因为这可以说是一切的开端。也是一门伟大的语言。 做Algol相关的work的图灵奖得主，足足有6个：John Backus，Alan Perlis，Peter Naur，John McCarthy，Edsger W. Dijkstra，Tony Hoare。还有无冕之王，Peter Landin跟John Reynold。 但是，为何这么成功的语言，却默默无名？因为错在了下一步。 在1960后，ALGOL推出了ALGOL 58，ALGOL 60，还有各种方言后，大家开始慢慢懂该怎么设计语言，实现编译器了。BNF，Recursion，Continuation，Stack，都慢慢被大家发明发现，慢慢熟悉。大家也开始发现了ALGOL 60没做好跟没有做的东西。 于是，1962起，大家开始发明一门新的，叫ALGOL X的语言，旨在把这些问题修好。从1962起讨论，一直到1965，变成一个draft。高兴的ALGOL厨把这叫做ALGOL W，并且等着用了。一切就差一些小修小补了。 就跟物理学大厦就剩下两朵乌云一样。 快进半年。另外一个ALGOL W的draft被奉上。情况不容乐观。 本来说好的三个月，跳票成了半年不说，draft变得更厚更长，问题反而越来越多。于是说在等三个月，我们再修修。 明明说三月，三月后又三月，三月后又三月，都快一年了。 拖了9个月后，在1968年尾，一个叫ALGOL W的，连设计者也不爱的怪兽产生了。 自此，ALGOL被命运之轮碾过。 故事的另一个主角，则知名得多。CPL。 这是1963，离悲剧还远得很，这时候大家都已自己是ALGOL方言为荣。 CPL就是一个ALGOL方言，旨在做更底层的ALGOL。 语言的设计也不算很复杂，唯一的问题就是不知道为啥，编译器死活写不出来。 于是，1967，有人在想，为何我们不把CPL简化点？这样就能做出编译器来了。 然后就出现了BCPL。同年，BCPL的编译器也被实现了。 两年后，为了把BCPL放上微型机，再次简化，出现了B。 同时间，B的一些问题被发现，效率也不够高，于是一个差不多的语言开始被设计，C。 而在C设计过程中，1970年，CPL的编译器终于面世。 命运之轮碾压过ALGOL，再碾压过CPL，碾压一次不够再碾压一次，BCPL，最后出了B，然后造就了C。最大赢家。 之后的，就是历史。 不过，这不是结束。也不是结束的开始。顶多是开始的结束。 还记得最开头的C++吗？没错，命运之轮怎么会放过C。 在C++后，为了简化，出现了JAVA，旨在消除C++的各种复杂性-比如不区分unsigned啊，自动管理内存啊，只有Class啊-只不过，到了最后，还是照样该变大变大。自动管理内存的确比手动简单，但是JVM确变成一个怪兽。就连unsigned这种小东西，也回到语言中了。屠龙的勇士，必成恶龙。 另外一边，PERL崩溃之后诞生的Python也一样，，不知道怎么的，就加入了optional static typing。。。说好的only one way呢？Simplicity呢？ 专门搞PL的人别偷笑，Scala就不说了，Haskell也一样，GHC无比复杂，连RecursiveDo都能水一篇170页的Paper，有一个minimal core，也不能解决这问题。也别以为Macro能解决问题-R6RS总共有187页，其中，有90页是语言定义。被称为怪兽的ALGOL W也就265页，实在差不了多少。ALGOL 60呢？17页。ALGOL 58则只有15页。不过R7RS倒是还行，只有77页。当然，这是以丢掉向后兼容性为代价的。 有没有语言试图挑战这命运之轮？ 有。Scheme，Python，都壮士断腕，丢掉了向后兼容性。自己不丢，别人就会给你丢。 Go也算是，Rob Pike活了60年，啥大风大浪没见过，尤其是Google的Build Server再也撑不起他们的C++，当然知道复杂度乃洪水猛兽-要不然为啥死撑不肯加generic。...

在Haskell等语言中，有datatype generic的概念：对于各种各样的ADT，都可以表示成一系列的Sum type 跟 Product type（因为这是ADT的定义），所以理论上，只要你能处理ADT的通用定义，你就能写一个对所有ADT适用的函数。其实这就是当你写deriving Show/Eq/Ord的时候发生的情况。generic，又称polytypic programming，就是把这理论变成现实的特性。注意这跟type generic是两码事。 这里面的Notable Work包括Scrap Your Boilerplate：把一定的类型信息塞到运行时，（Typable），然后就可以对某个类型做一种东西，而其他类型不变。然后可以写个高阶函数，对该类型做action，其他类型（wrapper，比如list/sum/either/whatever）就默认map进去，这样就可以给[Either [Double] Double]之类的type里面的所有Double翻倍，或者加起来返回。 GHC.generic做的是另外的东西，把一个类型表现成Sum type/Product type/Metadata（我们称作Rep），然后所有ADT都可以转化成这类型。然后加上把某类型变成它Rep的方法，就可以写function on all ADT，然后也可以写deriving等 True Sum Of Product就在GHC.generic上面做了层抽象，不用ADT来表示Rep，而是表示成[[*]] （类型的列表的列表）。然后有多参Product/Sum (可以想象成NProduct :: [*] -> *，其实具体情况复杂点），就可以直接组合/Map/Fold Product/Sum来完成generic programming，而无需在GHC.generic中递归，因为Sum type里面可能有Product type，然后里面再有Sum type。。。而这在True Sum Of Produt中不可能发生 然后还有Generic Generic Programming，因为有很多套Generic Library，每套都不一样，所以就搞出了个东西unify之。。。什么鬼 Generic Paper合集

我想给大家介绍一门语言。 C*。 C*有什么特点呢？很著名很流行。 我们可以看看TIOBE Index：到2017年12月，这门语言的rating达到了30.965%以上，比Java，下一个最热的语言，高了一倍有余。 这门语言被广泛使用于各种领域：操作系统（Linux, Windows），分布式（Spark），深度学习（部分tensorflow），区块链（bitcoin），游戏引擎（Unity）。 同时，C*的方言包含C, C++, Java, C#等知名语言。 我们先从语法开始介绍：C*的一个程序，由多个声明组成。其中，一些声明属于函数声明，而一个函数又由多条语句组成。。。 是不是觉得很荒谬？C没有Class, C++没有垃圾回收，Java跟C#水火不容，为什么被认作同一语言？ 而如果我告诉你，现实比这还魔幻呢？世界上有很多语言正被冠以‘C*’这样的名字，而这些语言中，毫无共通点？这些语言中，有的有静态类型，有的有动态类型，有的两个都有，有的GC，有的是为Arduino设计的，有的在JVM上，有的有Class，有的有Reflection，有的没有Assignment，有的基于Lambda Calculus，有的则不是，有的可以任意改自身语法，有的语法是二维的，是个表格，而不是线性的，而有的甚至自带GUI，是livecoding的鼻祖之一。。 而这些语言，通通被称作同一个语言：Lisp。 而更魔幻的在后面：于是，有很多人开始讨论，为啥这门语言没有取得主流化，为啥这门语言效率这么高。。。然后得出很多答案，其中一半的直接是错误的，如： Lisp是第二早的高级语言，所以XXX，所以效率很高 最早的编程语言Plankalkül，是1942到1945设计的，然后Fortran也比任何被称为Lisp的语言早。就算我们取最乐观的时间，1946到1955之间差了10年，里面出现了各种语言，AutoCode, ShortCode, Flow Chart, Haskell Curry的语言。。。 不过上述问题是技术错误，下面的论证则更离谱： Lisp社区很分裂，大家无法合作，所以没有流行 。。。Excuse Me？如果有一天，C, C++, Java, C#都衰落了，再也没有人用，是不是因为C*社区很分裂，C/C++/Java/C#，你任意选出一对，肯定在互捏？大家无法合作也是啊，Java自己有一套库，C#自己一套，C跟C++也是，这么分裂，不衰退才怪！ 欲加之罪，何患无辞啊！本来就不是同一个语言，为啥要放一起论证，然后去吐槽大家之间不兼容？ 在一推只是因为历史原因被称作一家族的语言之间，找共通点，然后去论证这些语言的兴衰，特性，适用范围。。。能找出啥有价值，nontrivial的insight才怪。 至于S表达式？Logo不用括号，Racket有2d syntax，也有infix expression, Common Lisp有reader macro。。。试问这些语言是不是Lisp?而JMC也说过我们应该往M表达式迁移，那是不是JMC 发现了Lisp的本质劣根性？我们也可以用argument by absurdity，论证C*这个词的合理性 - 有花括号跟分号的就是C*，C*成为世界上最主流语言，C*万岁！ ‘Lisp’，这个词，已经没有任何有价值的意义，早就该被废弃，或者仅仅指JMC在1950末造的一个语言。就如同C*这个词不应该被引入一样。 另：最后，我想吐槽小部分所谓的‘Lisp’ 厨。往往，当你问，‘Lisp有什么优势/值得学’的时候（我们先不吐槽这问题提得很糟糕，就如同你不会问为啥要学C*/C*有啥优势），会跳出大致如下的答案：‘大部分主流语言的特性，早在Lisp中存在。主流PL发展只不过是catch up 1960 Lisp。’ 这回答并很具误导性。 因为1960的时候，JMC 的确公开了一个语言，但是这个语言没有macro，是dynamic scope（读作：没有符合lambda calculus的first class function），连special form quote也没有（取而代之的是一个atom，换句话说你要quote compound expression得手动把(A B)转成(pair A B)）。在1967年，影响了Smalltalk跟无数学计算机人士的Logo出世，而在1970年，Scheme借鉴了Algol，修复了dynamic scope，也有macro跟continuation。Common Lisp在1984诞生，又在1990带来了Common Lisp Object System，跟metaobject protocol。1994，racket诞生，又在2002带来了composable & compilable macro。在今年，则出现了Collapsing Tower of Interpreter，实现了看上去有无数个interpreter，并且可以到达任何一个interpreter，更改语义，最后再运行普通的代码（并且看到更改语义带来的change），也出现了Type System as Macro，可以用宏代表静态类型。...

最近读了一篇paper，Duplication and Partial Evaluation，讲的是一门很。。奇怪的语言， 这门语言，可以大致想象是有无数个interpreter，一个stack着一个，interpret下一个，在最下，则是被解释的用户输入的代码。 你可以更改各种built in function，或者打印出来。比如说，你可以更改第1层（第0层为用户代码，第n+1层解释第n层代码）的apply，输入值print一次，输出值print一次，这样就实现了简陋debugger了。又或者对第二层解释器这样做，运行代码的时候就知道内部执行了啥 实现方法自然不能靠构造无限个interpreter，所以要先上laziness，按需增加，然后任何时刻，都有一个被解释的解释器去解释当下代码，然后有个被编译的解释器解释前一个解释器，这样就只有两轮。但是，这样，如果你更改n+2的代码，不会由n+1暴露到n层（换句话说n层看不出有啥区别），因为n层的时候，n+1层是被预编译的解释器执行，只有在n+1层看的到。这样，就顶多是两个编译器的开销。 ‘顶多’，双重编译很疼，于是用了下Partial Evaluation，手动优化成一个编译器。 什么鬼啊这是。 可以在The reflective language Black试试看。

今天发现了篇paper，http://brics.dk/RS/05/3/BRICS-RS-05-3.pdf 就是一个小trick，可以用于在2n pattern match下算出zip l (rev r) 看完以后觉得很简单啊，一点都不像某SM（Selection Monad（特大雾 不过为啥想不到呢，orz 最后：

这星期的文章是 http://cs.brynmawr.edu/~rae/papers/2012/singletons/paper.pdf。 这paper在codewars上，可以做做看：Singletons | Codewars 这文章在说两件事情： 0：用一种design pattern来做DT 1：这个design pattern可以用库automate一大部分 0： 假设我们有普普通通的data Nat = Z | S Nat。 首先，如果我们要把这用上type level（因为dependent type就是value可以在typelevel使用），我们需要额外的两个类型，一个ZType :: *，一个SType :: * -> *，来表示Nat的type level表示。然后，type level的Nat函数，可以用type family写出。 然后，可以用GADT表示inductive dependent type，比如Vec之类的。如果不支持GADT（什么鬼，不支持还想玩奇怪特性）可以考虑考虑用gadtless programming，换句话说用Leibniz Equality手动解constraint。。。 但是，由于parametricity，这无法做到：给入一个type level Nat，输出一个该长度的Vec。。。所以，做法是，再弄一个GADT inductive type，这个GADT的value是indexed on type level nat的。换言之，每一个type level nat，都能在这个GADT中找到一个unique的对应值。这就叫singleton 最后，很多时候singleton可以隐式推出，所以可以弄成一个constraint。 总结，一个datatype有4种做法：普通的，type level的，singleton，singleton变成constraint（换句话说，typeclass）。 1： type level的可以由GHC的DataKinds扩展自动生成。 singleton constraint可以统一到一个typeclass 由template haskell可以从普通函数生成singleton函数跟type level函数（type family） 最后：singleton constraint跟Data.Constraint有异曲同工之妙:) 还有，下期想看啥接着私信我。。。no monad tutorial，no 女装=/=

由于一直没找到好的并且能答得上的问题，以后打算时不时往这发点paper，然后对之进行一定的解释，练练手&降低阅读门槛（希望）。 这次的是 Embedded Probabilistic Programming 建议前置知识：Probability Distribution，Monad，Continuation P1-P6：我们想造一个编程语言，在这语言里面，所有变量都不是传统意义上的变量，而是Probability Distribution（PD）。 在本文中，一个a的PD可以看成一个List (probability, a)，其中，probability（简称prob）是double的别名，一个PD的元素，(probability, a)，代表在该概率下a的可能性是多小（这文章不考虑无限&连续的PD） 一个PD要满足两个条件：所有prob加起来是1，所有不同元素的a都不一样 在这定义下，我们可以定义多个PD下的函数：（此文皆为伪代码） return : a -> PD a，接受一个非随机的值，变成一个PD return x = [(1.0, x)] （这个随机变量只可能取一个值，就是传进来的那个） map : (a -> b) -> (PD a -> PD b)，把PD里的所有a 都变成b map f [] = [] map f ((prob, value):: rest) = (prob, f value):: map f rest join : PD (PD a) -> PD a，把一个概率分布的概率分布变成概率分布 join [] = [] join (prob_of_prob, prob_value): rest = loop prob_value ++join rest...

Proving Programs Correct Using Plain Old Java Types什么鬼。。。表示orz，应该重新去看看TAPL ，然后看看ATAPL

题图自如何解读杰洛说的「最短的捷径就是绕远路」？ - 知乎 最近在拜读History of Programming Language，有2K页，累&无聊死了，但有时候很有意思： The American side of the development of Algol - 几天后，Algol 58会议进入僵局 - 某欧洲佬拍桌而起：我永远不会把一个句号当小数点用！ 当晚，Wegstein 提出了一个建议：我们搞三个语言，一个标准语，只有AST，一个交流语，用于把程序写上书里面交流，一个机器语，代码怎么存机器里面是这解决的问题。 哎？这不就是non textual representation of code吗？学过smalltalk/lamdu/MPS，用structural editor的，都知道这个。对于不知道的，可以看看Why Concrete Syntax Doesnt Matter 然而，smalltalk是1972的，比这晚了整整14年，并且59年后（2017），这方法也没成主流。 是什么，使得Algol 58如此超越时代？很简单，因为当时5年后才有ASCII，Algol也是史上第零个有标准的语言。这导致没有一套能关照各硬件的字符集，也没有大量把concrete syntax，language reference弄一起的语言（当时语言就几个），就自然不会让人先入为主的产生‘编程语言就应该定义syntax’。 当然，还有那不知名的欧洲佬对美帝国主义的不妥协。 从这，可以得出一个principle of noncompromise： 一旦妥协，接受局限性，后人就会把局限性视为理所当然。而没有问题，那儿来的答案？跳出盒子思考的最好方式，就是一开始不弄个盒子。 无独有偶，几天前在参加lambdaconf，去听APL，讲师开发了个APL -> C with GPU的编译器，源代码为946行（最短时期750行）跑在GPU上的APL（这项目叫Co-dfns by arcfide）。 猜下是用什么开发的？两个记事本。一个屏幕分两半，左边一个，右边一个。没有scroll bar。代码文件则叫做a, b, c…简直是跟主流开发流程反着来！ 为什么？大体如下： “当我用着最糟糕的工具，有最严苛的字数限制，最没帮助的命名，我明白，代码必须写得最短最清晰，否则记事本的糟糕界面就会让我无法继续。这也是为什么我强烈反对IDE的原因。” 换句话说，这是principle of noncompromise的应用-把问题极端化，让之不得不被解决。 真微妙啊，完全相反的两种syntax处理方式，竟然可以由同一条principle激发出。