编程语言

https://github.com/taimoon/scheme-compiler 关于一个业余如何另辟蹊径，作弊，逆练功法以及一些心得 前传 实际上，在真正写可以自举的编译器之前，我写了至少两个编译器，以及无数个解释器。 第一次，nand2tetris project写hack处理器汇编器，VM汇编器，Jack编译器。当时我还很懵懂，掌握不到其中的办法论。 第二次，IU Compiler课程学写python优化编译器，包括寄存器分配，尾递归，闭包。 这课程对我影响深远，让我找到适合我这种业余的办法论。 某天，看到某博客的编译器教学， https://generalproblem.net/lets_build_a_compiler/01-starting-out/。 得以让我可以不依赖教学提供的工具，写一个“hello world”式编译器来作为开头。誒，万事开头难啊。 可惜，那位博客并没有更新更多内容，不过博客主要参考Abdulaziz Ghuloum的“An Incremental Approach to Compiler Construction”论文，所以我以同样论文作为我主要参考，继续我的开发。 如果读者对其他语言编译器教学实现有兴趣，但又循序渐进式地实现，可以参考可自举C编译器实现 https://github.com/rui314/chibicc。 那位大大也有相关博客 https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days。 办法论 前提提要,前文说到IU Compiler课程对我影响深远是因为… 首先，IU Compiler课程设计继承至Abdulaziz Ghuloum的“An Incremental Approach to Compiler Construction”论文。 核心是incremental, 循序渐进式来学习编译器实现。 你的征程始于一个可以打印整数的编译器。 好了，你已经有了一个编译器，然后一点一点扩展你的编译器。 每一次的提交都要确保之前测试都能通过，还有新测试，以保证你的编译器可以work。 换一种说法就是你会写很多个编译器，厉害吧？给自己鼓掌；听懂，掌声！ 其次，IU Compiler课程采用对新手非常友好的nanopass架构。 在nanopass架构下，编译器会同过多个pass一步一步变换源码直到输出最后汇编，而每一个pass只做非常简单的事情。 比如一个pass来做free variable分析, 下一个pass才做闭包变换，然后下一个pass才限制函数参数。 这是一个很好办法论：如果一个编译步骤太难，就拆开成两个步骤。 可能有的同学会说，这不是会造成多次遍历，更长编译时间？ 新手嘛，更何况我一个业余，主打能work就可以，不寒碜。酷炫的东西比如SSA, 输出LLVM IR, 寄存器分配, 优化可以以后再打算。 不过，别灰心，nanopass被认可的工业优化编译器实现方式。 (详见:A nanopass framework for commercial compiler development) nanopass framework的chez scheme编译是可以非常快哒。传说，chez scheme几秒内就可以完成自身编译。 新手嘛，主打一个能work就好。 Parser generator我又不是很会，pratt parser, parser combinator, 就不明觉厉的感觉。 考虑到什么ambiguous grammar, associativity, precendence, 等等等， 让我手写parser可能会要我的命。 解析难的语言比如有layout syntax的haskell, python, 更不要说C++这种怪物， 自然不会是我考虑范围内。...

原文标题：Higher-kinded bounded polymorphism 作者：Oleg Kiselyov 原文链接：Higher-kinded Bounded Polymorphism 为了表达数据集合上的泛型操作，或嵌入有类型的 DSL（尤其是在 tagless-final 方法中），经常需要对类型构造器［type constructor］进行抽象，然后在之后才为类型构造器提供参数。通常情况下，被抽象的类型构造函数不是任意的，而必须是实现了特定的接口（比如抽象序列）——这就是所谓有界多态［bounded polymorphism］。 OCaml 并不直接支持高种类多态［High-Kinded Polymorphism］：OCaml 的类型变量只能包含类型，不能包含类型构造函数；如果不给类型构造函数应用正确数量的参数，它就无法出现在类型表达式中。尽管如此，OCaml 还是可以表达高种类多态的——事实上，有几种或多或少比较麻烦的方式，其中的不那么麻烦的方式尤其鲜为人知，却又不断被重新发现。本文总结了表达（有些时候，是避免）高种类多态的不同方法。这些方法收集自多年以来的学术论文和 Caml-list 邮件列表上的信息，并根据文章的需要进行了调整和重新解释。 导言 Polymorphism abstracts types, just as functions abstract values. Higher-kinded polymorphism takes things a step further, abstracting both types and types constructors, just as higher-order functions abstract both first-order values and functions. 译：多态是类型的抽象，正如函数是值的抽象。而高种类多态则更进一步，它同时抽象了类型和类型构造函数——正如同高阶函数同时抽象了一阶值和函数。——Yallop 与 White（FLOPS 2014） 我们将进一步阐述这一非常精炼的总结，从而说明（有界的）高种类多态是如何产生的。这里介绍的例子将贯穿全文所有章节。 在实践中，经常会出现「对某些数字求和」的情况，对具体的数字类型进行抽象，就可以得到能在任意一个数字集合（列表）上执行的函数： let rec sumi : int list -> int = function [] -> 0 | h :: t -> h + sumi t 我们可以进一步抽象 0 和 + 运算，由于它们本身就是函数（也可以说是一个带参数的值），结果就会得到一个高阶函数：...

原文标题：Algebra 作者：Oleg Kiselyov 原文链接：Algebra 代数式副作用（algebraic effects）和代数数据类型（algebraic data type）中的「代数」究竟是什么？哪些模块/对象的签名是「代数」的？「代数」到底是什么？自由代数（free algebra）的「自由」在哪里？初始代数（initial algebra）是什么，它有什么用，我们如何证明一个代数具有「初始性」？我们能准确地描述 tagless-final 式 DSL 嵌入，及其解释器的正确性吗？如果能描述，如何证明这种正确性？ 本文以讲义的形式展示了一些泛代数（Universal Algebra）领域的标准入门材料，旨在解答这一类问题。不过，这些材料是专门为程序员，尤其是那些对 tagless-final 方法感兴趣的程序员所挑选和安排的。我们只使用编程中遇到的例子，并尽可能使用具体的编程语言中的符号，而非数学符号。 导言 什么是代数（Algebra）？Garet Birkhoff 被现在的人们誉为「泛代数」领域的创始人，他是这么说的： By an `abstract algebra’ is meant, loosely speaking, any system of elements and operations such as a ring, a field, a group, or a Boolean algebra. 译：「抽象代数」泛指那些由元素和运算组成的系统：如环、域、群和布尔代数。（Birkhoff，1935） 随后，他又提出了一个「临时用的形式定义」，这一定义现在仍被人们使用（稍后会回顾这些形式定义）。 泛代数是数学的一个领域——关于泛代数的课程和教科书的很大一部分内容是格论（Lattice theory）和组合数学（Combinatorics）。看起来，这似乎与常见的编程任务没有太大联系。但世事无常，造化弄人，自动机（Automata）理论（有限状态机、Kleene 代数、正则表达式）是代数在计算机科学的最早应用之一。根据 Gougen 等人（1977）的说法：Burstall 和 Landin 共著的《Programs and their proofs: An algbraic approach》（1969）首次在编程语言语义学研究中使用了泛代数和（隐含的）代数初始性。F. L. Morris（《Correctness of translations of programming languages》斯坦福大学博士论文，1972 年）则引入了编程语言中最为常见的多类别代数。而在计算机科学中全面引入代数和范畴论技术，应归功于 ADJ 四人帮（J....

译自 Elementary Tutorial on Normalization-by-Evaluation。除非特殊声明，下文中「我」指原文作者 Oleg Kiselyov。 导言 本教程的初衷是为本科生提供一个五分钟快速入门通过求值进行归一（Normalization by Evaluation, NbE）技术的教程。因为是入门教程，所以只要求读者拥有小学或以上的数学背景知识，也无需拥有任何编程经验，读者可以一边在海边玩贝壳游戏一边进行学习。游戏的规则很基础，但游戏本身并不总是简单。在海边玩贝壳游戏可能是一个很好的契机，让你认识到：计算、规约、归一，以及证明游戏规则具有推进性和保持性的过程，都不过是一种玩弄符号的游戏。 但总有人试图超越符号的表象，将其视为真实事物的投影；在看似随意的规则背后寻找直觉，试图把握无脑游戏的意义。这样的人无疑会发现 NbE——就像人们在历史上多次重复发现的那样，本教程就是要指导读者重新发现 NbE。 游戏设置 让我们从一个游戏/谜题开始，它是许多小学练习的简化版本。玩这个游戏需要用到袋子、贝壳和橡皮筋。 袋子可以是空的，也可能内装有一个或多个贝壳 贝壳是一种游戏代币，彼此之间不作区别 「束」可以单指一个袋子，也可以通过用橡皮筋把另外两「束」扎起来作为一个新的束 我们将贝壳记作 #。在游戏中，两个「装有三个贝壳的袋子」可以视作同一个事物，并统一记作 [###]。而束的记法则是：把组成的两个束并排写在一起，中间用逗号隔开，然后两边加上圆括号。[##]，([##],[])，([##],([###],[#])) 都是合法的束，另外第一个例子也可以视为一个袋子。让我们较真一点：其他任何形式的记号都不是束（或者袋） ，像 [[]] 以及 (#, [&]) 就不是束，因为他们不是由方括号所包围的零个或多个 # 组成，也不是由圆括号包围的成对的方括号组成。 游戏的玩法是：给定一个束，找出一个「等价」或者说「相等」但更「简单」的束，并最终找到最简单的束——许多游戏甚至是学校里的练习题本质上都如此。例如，我们会得到一个形如 $5x-3=3x+7$ 的束，然后被要求找出与其等价且最简单的（在本例中，这样的束是 $x=5$）。 在开始游戏前，我们必须搞清楚两个束怎么才算「相等」，以及什么是「更简单」。 引用资料 我们的游戏实际上是 B. Pierce 所著的《Types and Programming Languages》中第 3 章内容的变体。这本书的本质是一些逐渐复杂化的玩弄符号的游戏的集合——尽管它自己没有如此声称。 相等 如何制定游戏规则，即定义束的「同一性」或者说「相等」完全取决于我们自己。我们可以一手指一个束然后声明它们相等，也可以把两个束分列 ~ 符号的两侧然后声明它们相等，如：([#],([##],[###])) ~ ([##],([#],[###]))。我们可能会声明很多类似这样的相等性，因此需要一种更简洁的写法。比如下面这样 首先，声明 ([], [S]) 等于 [S]，其中 S 代表包括 0 在内的任意数量的贝壳。 其次声明 ([#S],([T],[U])) ~ ([S],([#T],[U]))，其中 S、T 和 U 均代表任意数量的贝壳，而 #S 代表比 S 再多一个（#T 同理）。...

译自 Simplistic GADTs in OCaml。除非特殊声明，下文中「我」代指原文作者 Oleg Kiselyov From oleg at http://okmij.org Fri Jul 10 20:05:10 2009 To: caml-list@inria.fr Subject: GADTs in OCaml Message-Id: 20090711030510.49092176DE@Adric.metnet.navy.mil Date: Fri, 10 Jul 20091 20:05:10 -0700 (PDT) Status: RO 本文展示了一种 OCaml 中的简单、无副作用、且不需要魔法的实现 GADTs23 的方法。这种实现足以覆盖 GADTs 的许多常见应用：表达带有不变式（invariant）的数据结构、有类型的 printf/scanf、无标签（tagless）解释器等。本文提出的具体实现只是一个简单的 ML 模块，不需要修改 OCaml 系统本身。由于实现十分简单，理论上可以在任意 ML 系统上运行（不过，就如同嵌套数据类型一样，在不支持多态递归（polymorphic recursion）的 SML 上，GADT 也不是很有用）。 本文的例子涵盖了： 保障数据结构的不变式：静态地保证在一个表示某 HTML 文档的树结构中，一个链接节点不能为另一个链接节点的父节点。 有类型的 printf/scanf 实现，两个实现之间共享相同的格式化描述符。 带有常量和高阶抽象语法（High-Order Abstract Syntax）的简单有类型 $λ$-演算。我们所展示的其实就是奚宏伟等人（Xi et. al）的 POPL 2003 论文4中所展示的例子。 请移步 http://okmij....

译自 Having an Effect。除非特殊说明，下文中的『我』指原文作者 Oleg Kiselyov。 简介 本研究如同一次追寻表象之下草蛇灰线的旅程：Monad，Monad Transformer，Free Monad 以及可扩展副作用（Extensible Effects）的创始论文本质上都是关于所谓『可扩展解释器』问题的研究。一路走来，我们意识到表达式问题（expression problem），稳定指称问题，以及可扩展解释器问题都是同一事物的别称。最终我们找到了组织原则：交互－－客户端与服务器之间的交互、解释器与被解释代码之间的交互、表达式与其上下文之间的交互。 可能用『进程演算（process calculus）』能更好描述交互。而在各种序贯式的演算中，最早的把计算副作用视为交互，并且做出形式化表述的工作则是 Cartwright 与 Felleisen 发表的著作《Extensible Denotation Language Specifications》。 本文用现代的方法重构了 Cartwright 与 Felleisen 方法。得益于 tagless-final 形式，我们重构后的版本更简单，可以直接给计算机运行。 本文也在前人的工作之上做了进一步发展。本文令副作用处理程序变得模块化且可扩展－－它变成程序的一部分，而非永久独立于程序之外。这使得下面的做法成为可能。 尽管整数和一般的一阶子语言不需要变量和环境，Cartwright 与 Felleisen 的方法也必须将变量和环境融入基本语义框架；我们避免特殊对待可变环境和任意高阶编程特性，而是将 Lambda 与 State 一视同仁。动态绑定和词法绑定，以及各种调用约定（按值调用，按需求调用，按名调用）可以视为用不同方式解释副作用『解引用绑定变量』。 对研究领域溯本求源，寻回直达本质的洞见，发掘其沧海遗珠。这一探索过程有助于为我们为程序重新发明副作用。 本演讲稿于 2016 年 8 月 25 日在印第安纳大学信息与计算学院 (SoIC) 计算机科学研讨会上首次发表。我要感谢 Martin Berger 与我进行了许多令人受益匪浅的讨论，特别是解释了进程演算的起源。此外还要感谢穆信成与 Matthias Felleisen 提出的宝贵意见。 版本 当前版本为 2017 年 9 月版 引用资料 EDSLNG.hs 本文所使用的 Haskell 98 代码的完整版 edlsng.ml Cartwright-Felleisen 框架现代重构 OCaml 版本。附带全局状态、动态绑定、按值调用和按需求调 用的词法绑定示例...

译自：What are denotations, exactly? 。除非特殊声明，文中「我」指原文作者 Oleg Kiselyov。 指称语义通常被描述为：利用数学对象解释表达式（语法对象）。那么，所谓『数学对象』究竟是什么？OCaml 代码可以是数学对象吗？花些时间去思考到底什么是指称语义是值得的。 在最早一批的诸多『指称语义』的定义中，Landin 指出（Landin 1966，第 8 节） The commonplace expressions of arithmetic and algebra have a certain simplicity that most communications to computers lack. In particular, (a) each expression has a nesting subexpression structure, (b) each subexpression denotes something (usually a number, truth value or numerical function), (c) the thing an expression denotes, i.e., its `value’, depends only on the values of its subexpressions, not on other properties of them....

译自 Language for writing text adventure, er, online courses: glimpse into the computer-assisted education of the 1970s and 1980s。除非特殊声明，译文中「我」指原文作者 Oleg Kiselyov。 线上课程现在已经不是什么新奇事物了。一门典型的线上课程包含了一段教学视频和几个课程网页，以及由屏幕上的几道选择题组成的「小测」，完成小测后会显示正确答案并统计得分。然而，「计算机辅助教育」这一概念比互联网还要早几十年出现。那时人们就很快意识到，像上面描述那样的课程是非常枯燥乏味的。 一门引人入胜、富有成效的课程应更具互动性：讲解和提问应交织穿插在课程之中。提问之后当场就要判断学生的回答是否正确，如果回答错误，可以给他们另一次回答的机会或者一些提示。如果学生还是不能回答出正确答案，则启用备用课程，更慢地讲解课程主题。问题应该是多变的，最好具有不确定性。答案的形式也应该是自由的，学生的回答可以是任意数字或字符串，而非是单纯的选择题。总之，一门引人入胜的课程应该看起来像冒险游戏。 人们很早就意识到，编写一门好课程的脚本就像编写一款好游戏的脚本一样，是一种不同于编程的技能。让课程作者用 Fortran 或者汇编语言（当时的计算机编程语言）来写脚本是不合理的，他们需要更好的工具－－用于编写课程脚本的高级语言（游戏行业也意识到了这一点）。伊利诺伊大学在 20 世纪 60 年代末开发的 TUTOR 就是早期的课程脚本语言之一。 在苏联，有一种大型机上的 TUTOR 方言/实现，我在喀山大学学习和工作时就遇到过它。在大型机上学习计算机课程很不方便，因为一般很难接触到大型机。更何况，苏联的大型机经常坏掉。 个人计算机的横空出世为计算机辅助教学提供了更好的平台，至少个人机比大型机便宜得多。这就是当时我在个人机 BK-0010 上写一门 TUTOR 方言解释器的动机。个人机的硬件性能显然不如大型机，但我的实现比大型机上使用的实现还是有一些优势。 在原版 TUTOR 及其方言中，创建演示文稿首先要在屏幕上定位光标，然后再输入文本，而我的实现支持格式化输出文本或绘图。文本格式化模板中可以使用字符串或数字表达式插值，还可以包含用于实现颜色、黑白反转等一系列视觉效果的屏幕控制代码。此外还有一种绘制线条的特殊操作符。 这种脚本语言其实是一种包含了数值和字符串计算，以及字符串转换、编辑和匹配等功能的编程语言。由于学生可以按任意形式回答，为了判断学生回答是否正确，字符串匹配功能是必不可少的。该语言还支持 26 个整数变量以及 8 个字符串变量，以及分支判断、循环和子程序等特性。作为 TUTOR 的一门方言，它有专门的运算符实现下列功能：接受学生输入的答案、基于字符串模式匹配的结果跳转到不同分支、前进到下一课、回溯或切换到另一个教案。可以把几个课程脚本组成套装。课程脚本则用内置的全屏编辑器进行编辑。 解释器使用 PDP-11 汇编（MACRO-11）编写。解释器本身占用 3KB 内存，编辑器占用 1.5KB 内存，简单操作系统占用 2KB 内存。BK-0010 个人机主内存剩余的 9.5KB 空间可用于存放课程脚本和其他东西。用户写完课程后，可以删除掉编辑器以将其内存用于课程。 我现在才意识到，上面所描述的脚本语言足以用来编写文字冒险游戏（事实上不止文字，因为它支持绘图）。可惜当时我和我朋友都不知道「文字冒险游戏」这个概念。 当时我写了几个示例课程，并计划移植一些大学开发的现有 TUTOR 课程，但现在看来好像就剩下了解释器代码了，如下示。 几天前（2018 年 9 月），我参加了大学规定的一门关于个人信息处理的线上课程1，由一段视频和十多道选择题组成。我很遗憾地意识到，在 1988 年，在时钟速度只有 3MHz、总内存比现在的电脑小几百万倍的电脑上，我本应编写和学习一些更吸引人的课程。...

最近电脑坏了，所以上周没法写文章，抱歉。 随着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是我的秘密武器！

几天前，有个人来找我，问我：‘我这语言语法设计得怎么样？’ 我连语法都没看，就问：‘你这语言的设计目的是什么？’ ‘我希望设计一个语言，融合FP跟OOP，这样我可以既有FP的表达力，也有OOP的易用性’ 我忍着吐槽的欲望，问：‘那你有继承吧？’ ‘有’ ‘那Subtyping呢？’ ‘当然也有’ ‘那你打算怎么做类型推导？’ ‘Algorithm W’ ‘你该知道，Algorithm W是靠unification做推导的，你如果有subtyping，跟Algorithm W不相容，你想好这么解了吗？’ ‘啊。。没有’ 其实如果答出来，还有很多相近的设计问题： OOP提倡extensibility，但是FP的ADT是封闭的，无法扩展新类型 - 而Class/Object无法在类型安全且不更改以前代码的前提下扩展新的method，这个语言该怎么提高扩展性？ Invariant/Covariant/Contravariant/Recursive Type/Existential Universal Quantification/Module的Subtyping怎么做？ Ad Hoc Polymorphism呢？如果靠Typeclass，这套东西怎么跟OOP的Class System整合？如果靠implicit Coherent问题怎么解决？ 这些问题不是不能解，毕竟融合FP跟OOP的语言一大推，OCaml跟Scala不说，往早说，Luca的一推paper全是这个套路，但是问题是，当你要设计语言的时候，这些东西要先考虑清楚，而不是先去考虑语法。比如说Subtyping可以看F<:跟MLSub，Extensibility可以看MLPolyR/Data a la carte/Object Algebra。 另一个我想吐槽的事情，就是‘超市买菜’模型。很多人在设计语言的时候，都会有如下的思路：‘X是好的，Y是好的，Z是好的，我也刚好都需要，所以我这个语言要有X, Y, Z。’,比如上面那个人，就认为‘FP是好的，OOP是好的，我都需要，于是我去设计语法去了’ 这样做的问题是完全没考虑到各种feature之间的互相影响-而这才是设计语言最麻烦的地方。 比如说，某个语言是Dynamically Typed的，但是有个叫Type Stability的概念：如果我能静态用Dataflow Analysis分析出类型，我就会用Type Directed Compilation做传统静态类型的优化。同时，我提供Type Annotation，所以如果分析不出来还可以手动加类型。 那好，这语言有Reference（指针），这再加上Higher Order Function，跟Dataflow Analysis很合不来，随便写点高阶的东西推不出，性能突然暴死怎么办？而Type Annotation则因为这个语言有Subtyping，同时Type Annotation选择会runtime check/convert的原因，导致没有Arrow Type，所以无法给高阶函数加Annotation，而这又恰巧是最需要的时候。。（Gradual Typing性能坑，而且他们还有Union Type，这下不止性能有问题，连做都不好做，见The root cause of blame: contracts for intersection and union types） IMO，如果设计语言，应该正好反过来：很多人都是先设计语法，然后再写实现，最后interaction管都不管听天由命的。如果是这个顺序： 先去考虑我这个语言的目的是什么（提示：如果你不是GRAIL，Scratch，APL，那答案不会是‘语法’）（提示：答案九成是‘我在设计这个领域的DSL’。） 然后去找可以实现目的的最小feature set-不可以被desugar的feature set越大，设计如上所说，越多坑，静态分析/类型推导/Partial Evaluation等操作也越难实现（要处理的case更多是一码事，不好处理的特性也是一码事（比如高阶语言不适合静态分析，指针不适合Partial Eval，Lambda Cube越往上爬越不好推类型，Subtyping更不好推等等）） 想想看自己要实现的Pass，脑袋里面建个大概的蓝图，想想要采用啥算法，看看有没有坑（要用Dataflow analysis做分析？跟高阶函数说再见吧。HM？Subtyping不相容。想在Effectful Language里面做Dead Code Elimination？你还是高阶的？好好想想Effect Analysis怎么设计吧） 如果上一步发现冲突，移除一定的Feature/Pass，看看能不能被啥弥补，或者直接不要，然后接着找冲突 好了，开始实现各种Pass吧 到了最后，才到实现Surface Language/Concrete Syntax/Parser/Pretty Printing/IDE Support这些外观上的东西的地步。 那才可以在第零时间发现这些特性/Pass interact的坑，也可以有个明确的目的，而不是看到啥好的特性，就往语言里面乱塞，最后做出一个跟C++一样复杂坑多又不好扩展的语言。