类型检查 If 表达式

Posted on 2023-01-16

我有这个爱好项目，我已经研究了好几年了。这是一款奇幻游戏机，深受令人愉悦的PICO-8启发。和 PICO-8 一样，我的控制台有自己的内置脚本语言。因为我是我，所以我当然会借此机会设计一种全新的语言。

我对该项目的目标是构建小型 2D 游戏的有趣方式。我希望它的脚本语言具有足够的表现力以令人愉悦，但又足够小以至于您可以学习整个语言并且之后再也不需要查阅参考手册。我的梦想是一个愚蠢的小像素化 IDE，您可以在其中迷失自己的流动状态，而不必定期访问 StackOverflow，然后被 Internet 的奇迹/恐怖分散注意力。

我不知道我是否会成功，或者这种语言是否会面世，但这对我来说是一种有趣的治疗方法。

一种动态类型的脚本语言

为了创造一种适合你头脑（或者至少我的头脑，我的工作空间似乎每年都在变小）的语言，我需要尽可能多地放弃功能。我对一系列爱好和不太爱好的语言的经验是，静态类型大致增加了一个数量级的复杂性，因此类型是最先要做的事情之一。像大多数脚本语言一样，我使用了动态类型。

这是一个例子：

 def onTick () var d = 0 if buttonHeld ( 2 ) then d = d - 1 end if buttonHeld ( 3 ) then d = d + 1 end if d != 0 then h = h + d else if h > 0 then h = h - 0.5 else if h < 0 then h = h + 0.5 end if h < - 3.0 then h = - 3.0 end if h > 3.0 then h = 3.0 end x = x + h if y < 200 then v = v + 0.8 end y = y + v if y > 200 then y = 200 v = 0 end if buttonPressed ( 0 ) then if y == 200 then playSequence () v = - 10.0 end end end

我做的另一个简化是消除语句和表达式之间的区别。正如在 Ruby、Kotlin 和大多数函数式语言中一样，一切都是表达式。前面的链式if可以写成更明确的 expression-y 风格，例如：

 h = h + if d != 0 then d else if h > 0 then - 0.5 else if h < 0 then 0.5 end

统一语句和表达式意味着该语言不需要单独的if语句和条件表达式。另外，我不知道，我只是喜欢面向表达的语言。

命令式语言

即使该语言是面向表达式的，它也不是明确的函数式的。函数式语言很接近我的心，但这是一种游戏脚本语言。游戏世界基本上是一个不断更新的可变状态的大球。对于我心目中的那种程序和用户体验，我认为命令式、过程式的风格很容易学习，而且编程起来很有趣。我希望用户考虑他们的游戏，而不是单子和持久数据结构。

因此，虽然一切都是用我的语言表达的，但它一点也不回避副作用和命令式控制流。变量是可赋值的。字段是可设置的。有循环、中断和提前返回。所有这些都是自然而惯用的，就像它们在 C++、JavaScript、C# 或世界上大多数代码所用的任何其他语言中一样。

手工西雅图

去年秋天，我参加了精彩的西雅图手工制作会议。我与Devine Lu Linvega就他们的微型uxn VM 进行了一次特别鼓舞人心的对话。他们的想法是构建尽可能小的系统和编程语言供自己使用。然后他们用它重建了自己的个人工具——文本编辑器、音乐工具等等。

现在，UXN真的很小。我从汇编编程中获得了一定的满足感，但这不是我为了自己的乐趣而想使用的语言。但它确实让我重新考虑了我的幻想控制台的脚本语言。我选择了动态类型，因为它使语言更小，而且我认为它非常适合我的（此时完全假设的）用户。

但我想用它来制作小型 2D 视频游戏吗？我花最多时间破解的游戏是我的 roguelike Hauberk也是常年不完整的游戏。我已经多次重写它，但每次都使用静态类型语言：C++、C#、Java 和现在的 Dart。

我在 Hauberk 上工作最愉快的时光是在我重构时，类型系统会指导我清理剩下的东西。我真的很喜欢和类型打交道。 （如果你不这样做也没关系。正如我们的 Burger Sovereign 所说，随心所欲。）

与 Devine 交谈后，我意识到如果我亲自为我制作这个幻想控制台，它的语言将被打字。所以在过去的几周里，我一直在草拟控制台脚本语言的静态类型变体。我不知道它是否真的会走到一起，但我认为写下探索可能会很有趣。

类型检查if表达式

我为我的语言拼凑了一个新的原型解释器。 （主要实现是 C++ 中的字节码 VM，速度非常快，但不太容易破解。）然后我尽职尽责地开始向它添加类型检查传递。我遇到的第一个挑战是如何输入 check if表达式。

正如标题所暗示的那样，这就是这篇文章的真正含义。因为事实证明，当涉及到类型检查时，拥有if表达式的同时还完全接受命令式风格会变得有点奇怪。

我将通过一系列示例来构建我已经确定的类型检查规则（至少到目前为止）。我们将从简单的开始：

 var love = if isFriday then "in love" else "not in love" end

我们需要if表达式的类型，以便我们可以推断变量love的类型。在这种情况下，类型显然是 String，因为 then 和 else 分支的计算结果都是字符串。

所以我们开始的基本规则是：一个if表达式的类型是分支的类型。

不同的分支类型

但是，如果它们的类型不同怎么办？关于什么：

 var love = if isFriday then "in love" else 0 end

在这里， love最终可能被初始化为String或Int 。现在我们选择什么类型？ Crystal 的答案是String | Int 。联合类型很酷，但对于我正在尝试制作的语言来说绝对太复杂了。

在也是类型化和面向表达式的 Kotlin 中，答案显然是{Comparable<CapturedType(*)> & java.io.Serializable} 。我不得不说这似乎并没有太大帮助。

我假设编译器会寻找两个分支类型 String 和 Int 的共享超类型。由于 String 和 Int 都碰巧实现了 Comparable（我猜是某种序列化接口），因此您将其作为通用超类型。

在具有子类型化且类型层次结构形成lattice的面向对象语言中，此公共超类型是最小上限，它是问题的自然答案。在对条件?:表达式和其他一些地方进行类型检查时，它会以其他语言出现。

它有效，但是，正如我们在此处的 Kotlin 示例中所见，它并不总是产生直观或有用的结果。更重要的是，我从我的脚本语言中放弃的其他功能之一是子类型化，因此 LUB 不在考虑之列。

如果没有子类型化，每种类型都是不相交的：一种类型的值永远不会是任何其他类型的值。这意味着如果if的两个分支具有不同的类型，那么我无法推断出包含它们所有值的可能类型。唯一的其他响应是使其成为类型错误。

那是下一条规则：如果分支有不同的类型，那就是编译错误。

命令式 ifs 和未使用的值

该规则确实有效：它基本上是 SML 的if表达式规则。但我希望我的脚本语言以命令式风格让用户感到熟悉。考虑：

 var daysNotInLove = 0 if isFriday then print ( "in love" ) else daysNotInLove = 1 end

在这里，两个分支具有不同的类型。 then 分支的类型为 String，因为在我的语言中， print()返回它的参数。 （这使得在表达式中间填充一些调试打印变得很方便。）else 分支具有 Int 类型，因为赋值表达式产生分配的值。

根据前面的规则，这是一个类型错误，因为我们不知道if表达式的计算结果是什么类型的值。

但这并不重要，因为无论如何都没有使用if的值。编译器不需要对你大喊大叫，这样的代码在实践中非常普遍。

为了解决这个问题，类型检查器考虑了一些周围的上下文。当if表达式出现在其值不会被使用的位置时，分支具有不同类型不再是错误。跟踪该上下文有多复杂？其实还不错。有几种情况：

  • 在具有一系列表达式的块或函数体中，结果是最后一个表达式的值。前面所有表达式的值都将被丢弃。所以在一个表达式序列中，除了最后一个表达式之外的所有表达式都在“值未使用”上下文中。

  • 与其他面向表达式的语言一样，我的语言中的函数隐式返回函数体表达式求得的值：

     def three () Int print ( "About to return three..." ) 3 end def onInit () print ( three ()) # Prints "About to return three..." then "3". end

    但如果一个函数没有返回类型（与其他语言中的void或 unit 相同），它就不会返回值。在这种情况下，即使正文中的最后一个表达式也是“未使用值”上下文。

  • 循环表达式不产生值，因此它们的主体始终是“未使用的值”上下文。 （我正在考虑允许break表达式从循环中产生一个值的想法，但现在还不行。）

  • 每当if或match表达式处于“值未使用”上下文中时，我们也会将该上下文推送到分支中。与and和or逻辑运算符的右侧类似，因为它们是控制流表达式。

就是这样。在我想出这个规则之后，我四处寻找了一下，看起来 Kotlin 也做了类似的事情。它的框架是说当你使用if “作为表达式”时，两个分支必须具有相同的类型。这也是我在这里所做的大致区分：当if出现在其值被丢弃的类似语句的位置时，分支可能不同意。

缺少其他

这条规则允许我们支持命令式代码中常见的更重要的if表达式风格：那些没有else子句的表达式。在 SML 和其他一些函数式语言中，每个if表达式都必须有一个else子句，因为假定您将使用表达式产生的值，并且即使条件为假，您也需要一个值。

但是在命令式代码中，显然很常见if的主要目的是产生副作用并且不需要else子句。事实上，当我分析大量真实世界的 Dart 语料库时，我发现只有大约 20% 的if语句有else分支。

现在我们了解了if表达式何时处于未使用其值的上下文中，我们可以允许省略else分支。下一条规则是： if表达式在其值未被使用的上下文中可以省略 else 分支。

退出分支机构

我们快到了。开始感觉我们真的是在对一种命令式语言进行类型检查，而不是 BASIC 外衣中的 ML。我对此进行了编码并成功编写了一些小示例程序。它开始感觉像是一种真正的打字语言！

我可以在这里停下来，但是还有最后一点if表达式的类型检查逻辑。我还没有决定它是否值得保留。考虑：

 def onInit () var love = if isFriday then "in love" else return end end

当isFriday为真时，这将使用字符串“in love”初始化love 。当isFriday为 false 时， return将从函数中完全退出，因此love根本不会被初始化。因此，即使这些分支的计算结果不同， love也始终使用 String 进行初始化。这段代码应该没问题。

或者，至少，根据类型系统，它应该是合理的。这是否是好的风格绝对值得商榷。我可能不允许这样的代码。但我的默认立场是在不破坏稳健性的情况下尽可能宽容，这是我可以做的一个角落。

诀窍在于像break 、 return和throw这样的表达式是特殊的。虽然它们在语法上是表达式，但实际上并不计算值。如果你这样做：

 var x = return

x永远不会被初始化。 return表达式总是跳出周围的代码，而不是产生一个值。具有可以控制流的表达式的语言通过为这些表达式提供一种特殊类型来对此进行建模，这些特殊类型被称为“bottom”、 ⊥ （“up tack”）、 Never 、 noreturn等。这种类型意味着“你永远不会从我这里得到价值。”

在检查if表达式的两个分支时，如果一个分支具有该特殊类型（编译器现在称其为“无法访问”），那么我们只需使用另一个分支的类型作为if表达式的类型。这允许上面的例子工作。在我目前编写的示例代码中，它很少发挥作用。将控制流完全从if中提升通常更为惯用。但是我们可以轻松地对其进行类型检查，因此该语言可以让您做到这一点。

规则一应俱全

这就是我现在所处的位置。我花了几次迭代才达到我希望能够在我的示例程序中编写的所有if表达式实际上类型检查正确但现在看起来相当稳定。规则是：

  • 当if表达式处于未使用其值的上下文中时，分支可以具有的类型没有限制，我们就完成了。

  • 否则，必须有一个else分支并且：

  • 如果两个分支的类型都是“unreachable”，那么if表达式的类型也是“unreachable”。

  • 如果一个分支的类型为“unreachable”，那么if表达式的类型就是另一个分支的类型。

  • 否则，这两个分支必须具有相同的类型，并且if的类型就是该类型。

原文： http://journal.stuffwithstuff.com/2023/01/03/type-checking-if-expressions/