Flux 和静态分析

作者：Nathaniel Cook / 用例, 开发者, 产品
2020 年 6 月 1 日

导航至

当使用 Flux 代码编辑器时，您是否见过这种情况？

flux code editor

在编写代码时，能够从编辑器获得如此多的帮助，真是太棒了。

您是否曾想过这是如何工作的？今天，我将带您深入了解幕后，了解编辑器中实现这些自动完成功能的原理。

代码编辑器如何了解您编写的代码，从而为您提供帮助？

答案是一种叫做静态分析的技术，通过它可以分析 Flux 脚本，并在不实际运行代码的情况下了解代码的功能。我们不必运行代码就能了解它，这一点非常重要，因为作为代码的作者，您可能尚未准备好运行代码，因为它可能会编辑文件或将数据写入数据库。这就是为什么这项技术被称为静态分析；分析仅在静态输入（即 Flux 代码）上执行。

当我们分析代码时，我们想要了解代码的哪些信息？

当我们分析代码时，我们试图了解的主要信息是代码中表达式的类型。例如，如果您在代码中有这样一行 threshold = 42，我们了解到有一个名为 threshold 的变量，并且它的类型是整数。在上面的动画中，您可以看到编辑器能够建议 aggregateWindow 函数的参数。这是可能的，因为我们知道函数 aggregateWindow 的类型，并且该类型包括有关函数接受哪些参数的信息。

类型是一种指定哪些值在哪些上下文中才有意义的方式。因此，当您键入 aggregateWindow 时，我们知道名称 aggregateWindow 是程序作用域中的一个变量，它具有函数类型，因此我们可以为如何使用该类型完成代码的其余部分提供建议。

静态分析算法如何学习代码中表达式和变量的类型？

我们使用一种称为类型推断的静态分析技术，其思想是查看代码，您可以根据代码的使用方式推断出类型。例如，给定这段代码，您认为变量 m 的类型是什么？

m = "Hello World"
print(m)

变量 m 是一个字符串。即使代码中没有出现单词 string，但从代码中可以清楚地看出这一点。将该代码与等效的 Go 代码进行对比：

var string m = "Hello World"
print(m)

string 关键字告诉 Go 编译器变量 m 具有字符串类型。

类型推断的思想是，Flux 可以根据程序中值的使用上下文来推断值的类型。这意味着代码的作者无需在其代码中显式声明变量的类型。

如果您熟悉 Go，您可能会想到可以使用 := 语法代替。这是正确的，实际上也是 Go 中类型推断的一个有限的例子。

Flux 不需要代码中的类型注释，因为它可以在没有类型注释的情况下推断任何值的类型。

虽然上面的示例很容易推断类型，但总的来说，仅通过查看任意 Flux 脚本来确定其类型并不容易。为了始终如一且准确地确定任何 Flux 程序中的类型，我们需要一组规则（即算法）来定义如何推断类型。Flux 团队使用一种称为 Algorithm W 的特定算法进行类型推断。

Algorithm W 的具体细节非常细致，因此我们将忽略大部分细节。相反，我们将在此处仅介绍算法的原始结构。

为了理解 Algorithm W 的工作原理，让我们首先看一下您可能熟悉的另一个问题。还记得代数和求解方程组吗？那些问题是他们给出两个包含两个变量的方程，您必须求解这两个变量。这些问题的求解方式与 Flux 使用 Algorithm W 求解程序中类型的方式非常相似。例如，给定这两个包含变量 x 和 y 的方程，您可以求解这些变量。

2x + y = 5
y = 2 + x

求解这些变量的过程涉及将一个变量方程代入其他方程。我们有一个关于 y 等于什么的方程，因此我们可以将第一个方程中所有 y 的值替换为 y = 方程的右侧，如下所示：

2x + (2 + x) = 5

现在方程中只有一个变量 x，我们使用代数规则求解 x。以下是显式步骤：

2x + (2 + x) = 5
3x + 2 = 5
3x = 3
x = 1

我们已经求解了 x，并得知它的值为 1。现在我们可以使用 y 的方程来确定它的值。

y = 2 + x
y = 3

使用此过程，我们已求解了 x 和 y 的值。

类型推断与此类似，只不过我们求解的是关于类型的方程，而不是求解代数方程组。我们使用替换和类型规则来求解 Flux 程序中每个表达式的类型。

以下是流程概述：

  1. 为程序中的每个 Flux 表达式分配一个类型变量。
  2. 生成所有关于类型的方程。
  3. 求解该方程组。

首先，对于 Flux 脚本中的每个表达式，我们为其分配一个新的类型变量。（我们称它们为类型变量，因为它们代表类型；在我们求解它们之前，我们不知道是哪种类型。）

我们的目标是求解这些类型变量。为此，我们需要一些方程。我们通过查看每个类型变量在 Flux 程序中的使用方式来获得这些方程。

收集所有方程后，我们可以求解它们。我们使用与求解代数方程相同的方式来执行此操作，即根据规则重新排列方程，并使用替换来替换方程中的变量，直到我们得到一个简单的 X = Type 方程 для каждого типа переменной.

这是一个简单的 hello world Flux 程序，它将在通过 REPL 运行时打印“hello world”。

a = "hello "
b = "world"
a + b

我们可以按照类型推断所采用的过程来了解此程序中所有表达式的类型。我之所以选择这个示例，是因为此程序中的所有表达式都具有字符串类型，这使得我们很容易看到我们正在努力实现的解决方案，因为我们采取了每个步骤。

第一步是将类型变量分配给表达式。此程序有三个表达式：每行一个。让我们为每行按顺序给这些类型变量命名为 X、Y 和 Z。

a = "hello " // X
b = "world"  // Y
a + b        // Z

请注意，我们正在讨论两种不同类型的变量：

  1. Flux 程序本身的变量，如 a 和 b
  2. 类型变量，如 X、 Y 和 Z

为了帮助区分两者，我将对类型变量使用大写字母，对程序变量使用小写字母。

接下来，我们需要收集所有我们知道的关于这些类型变量的方程。

首先，我们有类型变量 X，表达式为：

a = "hello "

由于我们看到只使用了字符串字面量，因此我们知道表达式必须具有字符串类型。我们可以为 X 写下一个方程，声明 X 必须等于类型 string。

X = string

我们还看到我们为程序变量 a 分配了一个值，因此我们写下与普通变量关联的类型变量，如下所示：

a -> X

我们跟踪程序变量与其对应的类型变量的关联，以便我们可以在其他表达式中使用它们时查找它们。

类型变量 Y 的下一个表达式是：

b = "world"

从类型的角度来看，这与 X 相同；因此，我们得到以下方程和类型变量关联。

Y = string
b -> Y

最后，我们需要为 Z 写下一个方程，记住它的表达式：

a + b

此表达式没有任何关于其类型的提示，因为仅使用了程序变量。但是，我们仍然可以从表达式中学到一些有用的东西。

我们知道 + 运算符的两边必须是相同的类型。这就是我们所说的使用类型规则：某些运算符必须以特定的方式使用，并且我们写下方程来捕获这些约束。

由于我们还不知道类型，因此我们创建一个新的类型变量 W 作为占位符。现在，我们可以使用 W 和 lookup 函数编写更多方程，以指示我们需要查找程序变量与其类型变量的关联。

W = lookup(a)
W = lookup(b)
Z = W

我们可以查找 a 和 b 的类型变量并更新方程。

W = X
W = Y
Z = W

现在我们已经检查了程序中的所有表达式，我们可以继续下一步来求解这些方程。此部分以与求解代数方程相同的方式进行。我们开始替换变量的方程，直到我们了解每个变量的类型。

以下是我们目前知道的所有方程：

X = string
Y = string
W = X
W = Y
Z = W

我们可以替换类型变量 X 和 Y 并获得这些简化的方程。

W = string
W = string
Z = W

现在我们知道了 W 的值，可以将其代入 Z 的方程，如下所示：

Z = string

我们现在有一组方程，并且已经求解了所有类型变量。

X = string
Y = string
Z = string
W = string

我们现在可以说 Flux 脚本中的所有表达式都是字符串，正如我们第一次看到程序时所预期的那样。

退后一步，我们可以开始了解如何系统地求解 Flux 程序中表达式的类型。我们还可以看到如何查找程序中的错误。例如，采用这个稍作修改的示例程序：

a = "hello "
b = 1
a + b

当为此程序创建类型方程时，我们将得到以下内容：

X = string
Y = integer
W = X
W = Y
Z = W

使用替换，我们将得到：

W = string
W = integer

此时，我们发现了一个类型错误，因为 W 不能既等于字符串又等于整数。当类型方程没有有效解时，程序中就会出现类型错误。此错误很有价值，因为它在运行程序之前告诉我们程序中的错误。

这就是类型推断的本质；根据表达式在 Flux 程序中的使用方式生成一堆方程，然后求解该方程组以获得所有类型变量。希望这能阐明我们如何执行静态分析（即类型推断）以了解 Flux 程序中的类型。掌握了类型知识后，编辑器就可以使用这些类型在开发 Flux 脚本时提供有用的建议和错误消息。

想了解更多关于类型推断的信息吗？

当然，类型推断在实践中更加复杂，因为即使简单的 Flux 程序也有很多表达式，因此也有很多方程需要求解。高效且准确地求解大量方程可能非常困难。想象一下尝试求解数百个代数方程组。这将非常乏味且容易出错。

此外，正如您可能从代数课上记得的那样，选择将哪些方程代入哪些其他方程可以使求解问题变得容易或极其困难。对于代数，这变成了一种有点直观的艺术，学生可以通过练习来掌握。不幸的是，计算机不擅长直觉。这就是 Algorithm W 的用武之地。它是一种用于高效且正确地生成和求解类型方程的特定算法。

如果您想了解更多信息，关于这些主题有数十年的研究和文献。以下是一些入门指南：

  • Algorithm W 是一类称为 Hindley-Milner 的类型推断算法。
  • 我们还使用 Algorithm W 的扩展来处理可扩展记录，请参阅论文。
  • 试用 SML 语言，它有一个基于 Hindley-Milner 的非常简单的类型系统，并且是一种可以快速学习的语言。它类似于 Haskel 和 OCaml，但学习起来更容易，理解起来更简单。
  • GitHub 存储库中有多种不同类型推断算法的实现及其研究。

我个人发现在尝试学习类型推断时没有捷径可走；大多数文献都假设对类型和计算理论的概念有一定的基本了解。我建议从 lambda 演算开始，因为所有关于 Hindley-Milner 的文献都假设熟悉 lambda 演算。然后进行实验并在您自己的部分进行练习。

此外，我还没有提到 Flux 语言服务器，它负责使用从静态分析中学习到的类型信息，并将其转换为编辑器可以呈现的建议。它是使这一切正常工作的关键部分。查看 GitHub 上的 Flux LSP 实现。

今天就到这里，感谢您的关注。