编程语言

注：这跟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 = !...

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

这是我接触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来访问每个变体里的字段。...

最近在群聊的时候，我们聊到了一个观点。 亚里士多德时代的科学不可能容许黑魔法，因为亚式科学的核心是 - 用直觉观察事物，得出物体的本质。黑魔法这种反常识的东西，只可能在可证伪科学体系下出现 - 这不你看，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?...

我最初学编程，应该也就是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。...

我想给大家介绍一门语言。 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试试看。

P.S. 这是写给想设计语言的人看的，如果你只是一个用户，不用看了，Syntax的确很重要。 假设你想写一门编程语言。 你想了一会语言大体有什么特性，然后写下一些展示这些特性的示例程序，并且注明它们的输出是啥。 错！绝大部分时候你不应该这样做！你的切入点应该是parser输出的中间结构（多为AST）入手，围绕这东西写各种evaluator/type checker/compiler等，以后再去搞Parser。 0.首先，无论如何，你最初设计的语法都会被你反复修改：注释能不能嵌套？用// /**/ 还是(**)还是#还是;还是;;？tab space有没有意义？def还是define? = 还是 := 还是 :- 还是 <-？这些东西都是互相不兼容的，你就这么多个符号，你选了=做赋值，=？做等价测试，过几天你觉得=?丑想用=做等价测试你就要选另一个东西给赋值。但是如果你是做语言其他方面，就没这么destructive（尽管feature有时候还是会冲突）：你今天写下Type Checking明天写个Compiler后天写GC过几天再写FFI，尽管你写一个东西的时候很可能要去改其他的，但是你是在不停的加东西，而不是单纯的换下一个改上另一个。 难。诚然，你可以手写LL Parser，折腾Parser Combinator，Parser Generator，几十行，大不了100行代码就够了。但是对比一个Simple Evaluator，比如SICP上的eval呢？一个要去折腾各种API，写至少几十行parser，然后再写几十行（很多时候还不到，比如UTLC with HOAS 10行足矣，untyped实现5行就够）Eval，另一个直接从Eval出发，rapid prototyping上讲高下立判。 不必要。除非你的语法真的真的很有特点，（图形化编程界面，APL，这里的标准是一个陌生人看到会不会说一句WTF），不然没有人会仅因你语法漂亮去用你语言。先把大部分精力花在更有意义的东西上，好好折腾有看点的特性，再去考虑语法。 更准确的说，我不是说Syntax不重要-有两种Syntax，Concrete Syntax，Abstract Syntax，Concrete Syntax是你看得见的东西，Abstract Syntax是Evaluator等东西接受的数据结构，举例来说，一个Parser接收Concrete Syntax（绝大部分时候为string）返回Abstract Syntax，然后由Evaluator执行（有的时候Parser直接Eval Concrete Syntax，在这说的不是这种）。Abstract Syntax是很重要的，（比如说Graph/Tree，Binding怎么表达，怎么搞得extensible，支不支持generic programming（见A Generic Abstract Syntax Model for Embedded Languages），是不是homoiconic的，有没有richly typed），搞得不好，自己用着不爽，性能不好，还甚至macro功能打折扣（homoiconicity） 好，你语言折腾得差不多了，其他人有兴趣，想用，（或者你自己开始在里面写很多程序），这时候你可以怎么搞？有一点：别以漂亮的名头把Syntax（含Abstract Syntax）搞的很复杂。或许你自己觉得反正自己只需要写一次，如果其他人用起来爽，就值得了。然而不是这么简单：还有人要去搞Syntax highlighting/Debugger/IDE support/Autocomplete/Static Analyzer这些乱七八糟的东西，搞得太麻烦的话你用户一想起你那麻烦的Syntax就打退堂鼓了（对，复杂如C艹一样这些东西应有尽有，但是C艹是在TIOBE上派前几的语言啊，开发团队，开发出来的受益人群，狂热粉（这些人才可能很抖M地单枪匹马写完整的Parser然后写奇怪的工具）数量都不是你一个没人知道的language能比的） 你也可以机智点，把parser暴露出来，这样写Analyzer/Optimizer的人就不需要自己再写一次了，如果要解放写Editor/Highlighting的人的生产力parser给AST加上奇怪的Annotation估计也可以 还有一个方法：直接不在语言中钦定任何最终用户Concrete Syntax，只钦定一个AST的Format（binary可以XML可以随便搞个Concrete Syntax也恶意）用于保存/交流，然后由各种用户的Editor等去渲染成代码。最好这些工具是可自定义的（或者，由于会有很多工具（比如git上看是一码事，emacs上看是一码事，xxx上看是一码事），这个自定义的东西本身也有一个配置文件标准），这样就从根本上断绝各种Syntax之争：如果你觉得XX更漂亮自己自定义下那些工具就是了，你折腾你的我折腾我的，井水不犯河水。并且这还能玩各种奇奇怪怪的东西：比如说Concrete Syntax没要求是String，这样可以搞Structural Editor/Graphical Editor给喜欢Structural Editing的人/初学者用。 注：456可以一起上 另：其实6在50多年前就提出了。。。历史里面真是有很多有意思的东西。 (The Next 700 PL) Revised Report on the Algorithmic Language Algol 60