编程语言的表达能力是什么？第一部分

这是对经典论文 On the Expressive Power of Programming Languages 及其衍生思想的一份个人诠释。 原文如何将其对表达能力的定义严谨化、如何证明一门语言能/不能表达某项语言功能的思路也十分有趣，但在这里不会过多介绍。 因此，本文会不可避免地较为“不严谨”和掺杂个人观点。

本文旨在将编程语言理论研究中广为人知的一些结论和语言设计方法论，降低门槛后写成中文文本。因此会以例子为主。

编程语言的表达能力是什么？

在讨论编程语言时，关于 “表达能力” 的讨论比比皆是：

• 有时候人们会说 “X 语言的 A 功能比 Y 语言更有表达能力”，
• 有时候人们会说 “X 语言的 A 功能在 Y 语言中可以如此如此实现”,
• 有时候人们会说 “X 语言的 A 功能就是一个语法糖”。

但如果对 “表达能力” 没有一个共同的、尽可能严谨的定义，这样的讨论就是没有根基的。 本文讨论的正是一种广受认可的 “表达能力” 的定义方式。 在意义上，它比较接近平常所说的 “语法糖”。

我们想要什么样的定义？

在引入我们的定义之前，不妨先看几个不恰当的定义，以增加我们对 “表达能力是什么” 这个问题的理解。

A 能表达 B：B 的所有程序都能用 A 写出来

这是一个非常糟糕的定义，但恐怕也是许多人的第一反应。 那么，这个定义的问题是什么呢？ 我们知道：

• 所有能运行的编程语言都能翻译成 Brainfuck 语言，因为 Brainfuck 是图灵完备的
• 所有现存的编程语言都能写出 Brainfuck 的解释器，输入一个 Brainfuck 程序，然后输出结果 （哪怕那些不图灵完备的语言，例如 Coq、Agda、Idris 等，也可以描述出一个 Brainfuck 的解释器。只需在最终运行时解除停机检查的限制，它们也是图灵完备的）
• 因此，我们可以把 B 的任何程序翻译成 Brainfuck，然后喂给用 A 写的 Brainfuck 解释器
• 于是，任何两门编程语言的表达能力都是等价的了！

然而，用上述方法 “表达” 出来的程序非常糟糕。 它只是一个 Brainfuck 解释器和一段难以阅读和理解的 Brainfuck 程序。原程序的结构、目的在其中没有任何体现。 编程语言不只是拿来执行的。它还需要供人阅读、维护。 因此，当我们说 “语言 A 能表达语言 B 时”，我们不仅希望能将 B 中的程序翻译到 A，还希望翻译出来的程序是可读的、保留原程序结构的。 这一直觉正是接下来要介绍的定义的核心。

我们的定义：可以局部地用宏翻译

本文采用如下的 “表达能力” 的定义：

语言 A 能表达语言功能 X，意味着可以用宏将 X 翻译为 A 中的构造，而且这个翻译是局部的。这意味着：

• A 中本来就有的语言构造，不需要进行任何改动
• 翻译 X 时，翻译方式不受 X 的子表达式的影响
• 一个包含 X 的表达式的翻译方式，和它所处的上下文无关

直觉上，“A 能表达 X” 的含义比较接近我们平时所说的 “X 是一个语法糖”。 这个定义看上去也许还有些抽象。接下来我们用一些例子来演示它的意义。

例子：一些简单的语法糖

在有模式匹配的语言里，if/else 可以用模式匹配表达、做成语法糖。if e1 { e2 } else { e3 } 可以翻译为：

match e1 {
  true => e2
  false => e3
}

这个翻译是符合我们上面的定义的：它不需要修改 if/else 外的其他语言构造，不需要查看 e1、e2 和 e3 的内容， 并且某个 if/else 表达式的翻译方式和它所处的上下文无关。 事实上，Erlang 就是一门只有模式匹配而没有 if/else 的语言。

Rust 用于错误处理的 ? 运算符也是一个语法糖（Rust 的 ? 运算符可以操作在多个不同的类型上，这里我们只考虑它作用在 Result 类型上的版本）。 表达式 t? 可以翻译为：

match t {
  Ok(x) => x
  Error(err) => return Error(err)
}

例子：循环+break+continue 是语法糖吗？

函数式语言中，往往大量使用递归，而相对较少使用循环。一些语言如 Haskell 甚至没有任何循环构造。 那么，循环是语法糖吗？在没有 break 和 continue 和 return 的情况下，循环的确是递归的语法糖。 循环 while c { body } 可以翻译为：

fn loop() {
  if (c) {
    body;
    loop()
  }
}
loop()

然而，在有 return 的情况下，生成的函数 loop 会错误地捕获 body 中的 return，上面的翻译就是错误的了。 现在，我们假设语言中没有 return，但给循环加上 break 和 continue。 此时，循环+break+continue 还是递归的语法糖吗？答案是否定的。考虑下面的代码：

break;
f()

这段代码后面的 f() 永远不会被执行到，需要在翻译后被吞掉。但这就需要我们对顺序执行构造 ; 做修改， 从而违反了定义中，“不能修改现有语言构造的要求” （要严谨地证明某项语言功能不是语法糖，其实不能只否决掉标准的或某种特定的翻译方式, 还需要证明不可能存在任何其他满足要求的翻译方式。但如何证明这一点，这里暂不讨论。 这里只演示为何比较显然的翻译方式不存在/不满足要求）。

然而，如果语言中有异常，那么循环+break+continue 又可以做成语法糖了。 假设我们有两个异常分别名为 Break 和 Continue，那么 while c { body } 可以翻译成：

function loop() {
  if (c) {
    try {
      body;
    } catch Continue {
    };
    loop();
  }
}
try {
  loop()
} catch Break {
}

而 break 和 continue 分别翻译为 raise Break 和 raise Continue。 容易验证，这个翻译也是满足我们上面对 “表达”/语法糖的定义的。

例子：defer 是语法糖吗？

Go、Zig 等语言有一种 defer 块的构造，用于释放资源。 defer 块中的代码，会在当前语句块执行结束的时候被执行，用于自动释放资源。 那么 defer 块是一种语法糖吗？

当语言中没有 return 时，defer 其实是语法糖：

defer { defer_block }
...

可以翻译成（需要是 expression based 的语言才好翻译，所以这里用 Rust 语法）：

// Go 不是 expression based 的
let result = {
  ...
};
{
  defer_block
}
result

即使语言中有异常，defer 也依然可以写成语法糖（假设有一个特殊的异常叫作 ExceptionInDefer，在正常的代码中不会被抛出）：

// defer { defer_block }; ... 的翻译：
try {
  let result = {
    ...
  };
  // 要防止 defer 块中的异常被错误地捕获
  try {
    defer_block
  } catch err {
    throw ExceptionInDefer(err)
  };
} catch ExceptionInDefer(err) {
  // 来自 defer block 的异常，不做处理
  throw err;
} catch err {
  // 来自 ... 的异常，rethrow 前执行 defer block
  defer_block;
  throw err
}

然而，当语言中有 return 时，defer 就不是语法糖： 假如语言中有 return，那么仅仅只是在结尾拼接 defer 块的代码就不够了。 还需要找到 ... 中的每一处 return，并在 return 前也添加一份 defer 块的代码。 所以，这样的翻译就违反了上述定义中的第二条：翻译 defer 需要查看代码中哪里有 return。 因此，在有 return 的情况下，defer 不是语法糖。

（作为一个类似的例子/练习，读者可以思考，C 的 for 循环是 while 循环的语法糖吗？）

例子：重载是语法糖吗？

重载允许同一个函数有多个版本，通过类型决定调用哪个版本。 重载的翻译需要涉及类型。所以这个例子可以演示我们对 “表达能力” 的定义，如何处理和类型有关的语言。

当涉及类型时，“表达能力” 的定义可以非常自然地拓展。 对于新增的类型，我们要求它也必须能用符合定义的方式翻译成现有的类型。 对于表达式的翻译，我们把它的类型看成一个 “子表达式”，并且也在翻译时禁止对它的分类讨论。 因此，所有类型制导的翻译都不是宏。

这样一来，按照定义，重载并不是一个语法糖。 因为一个重载的函数 f 的翻译，需要知道它所处的上下文（被提供了多少参数，参数的类型是什么）。 这违反了定义中的第三点。 这个结论也是非常合理的。因为即使是最基本的、仅允许按参数数量来进行重载的重载机制，也不是安全的。 下面我们会看到，“语法糖” 不会引入新的语言功能冲突。 然而，按参数数量的重载就会和变长参数函数冲突。所以，重载的确不是也不应该是一种语法糖。

我们对 “表达能力” 的定义描述不了什么

通过一些例子，我们演示了我们对 “表达能力” 的定义。 那么，这个 “表达能力” 的定义有什么用呢？ 在这个问题之前，不妨先看看这个定义描述不了什么：

• 它没有涉及任何性能和代码大小的考量。改变计算复杂度或是会导致代码大小指数膨胀的翻译也是被允许的
• 并不保证翻译出来的代码在美学上好看或可读

所以，一个语言功能可以做成语法糖，不代表我们就不应该引入它。 事实上，很多语法糖对于改善编程体验有极大的作用。 那么，我们定义出的 “表达能力” 有什么用呢？ 答案是，它能指导我们设计语言，给我们提供一种非常科学的设计编程语言的方法论：

用理论指导实践：设计语言功能的顺序

如果一个语言功能 X 可以表达为现有功能的语法糖， 那么可以知道一件事：它一定不会和其他语言功能产生新的冲突。 因为如果 X 引入了新的功能冲突，它又可以局部地翻译成其他语言功能， 那么其他语言功能之间肯定已经存在同样的冲突了。

利用这一点，我们可以以 “表达能力” 为依据，按如下的顺序设计/实现语言：

• 先确定那些会提升语言表达能力的功能，并理清楚它们之间的互动，确定没有行为冲突
• 在此基础上，可以放心地往语言里逐步添加不提升表达能力、但非常实用的功能

由于提升表达能力的语言功能也有重要性的不同， 这些 “核心功能” 也可以按重要性的顺序逐步添加， 这样一来，语言的设计就是一种树形的结构：主干是增加表达能力的核心功能，枝叶是实用的语法糖。 这种方法论能帮助语言设计者科学地设计语言，极大减轻添加新语言功能时，发现有不兼容之处、被迫打补丁或修改现有功能的风险。

下集预告

本文简短地介绍了经典论文 On the Expressive Power of Programming Languages 中， 比较语言功能的表达能力、严谨地定义“语法糖”这一概念的方式，以及由此衍生的设计新编程语言的方法论。 然而，本文只涉及了最基本的大体概念。很多更深入但非常有趣的问题并没有涉及到，例如：

• 如何严谨地真正证明某个语言功能不是语法糖（而不是只否定掉某种特定翻译方式）
• 一些更复杂的功能，例如 async/await，是语法糖吗

但这些更深入的问题超出了本文的范围，所以留待改日另写一篇文章讨论。 在最后，给读者留一个非常有趣的思考题。这道思考题可以展现出本文讨论的 “表达能力” 定义的强大威力：

• return 是异常的语法糖吗？
• 前面我们看到，有 return 时，循环不是递归的语法糖。然而，有异常时，循环是递归的语法糖。这是为什么？
• 如果 return 不是异常的语法糖，那么加入哪些额外的语言功能后，return 才能成为异常的语法糖？

读者不妨参照着本文定义的 “表达能力” 来思考这些问题。答案或许会马上自动浮现出来。