Newshot

反向箭头的类型推断与类型收窄

Translation(model translation, not the source's own text)

使用反向箭头进行类型推断与类型收窄

本文阐述了 Elixir 如何利用反向箭头实现类型推断与类型收窄:它由一小组可组合的思想构成,而非将特例硬编码进类型检查器。

得益于这项工作,即将发布的 Elixir v1.21 通过了 Guo 等人提出的 If-T: Type Narrowing Benchmark 中的全部测试。这意味着 v1.21 能在现有 Elixir 程序中发现更多确定的缺陷;并且一旦引入类型签名,类型收窄将为我们带来更精确的类型和更少的误报。

该类型系统得以实现,得益于 CNRS 与 Remote 之间的合作。目前的开发工作由 Fresha、Supermethod 和 Dashbit 赞助。

类型推断

Elixir 通过细化动态类型来执行类型推断。这与大多数类型系统中实现推断和渐进类型的方式相当不同,所以我们来逐步拆解。

在许多渐进类型语言中,动态类型(通常称为 any)是一个“黑盒”,可以在任何上下文中使用。例如,设想下面这个 Elixir 函数,由于没有类型签名,x 一开始的类型是 dynamic():


        def using_x_as_number_and_binary(x) do
  IO.puts x * 2
  IO.puts byte_size(x)
  :ok
end
      

上面的程序既把 x 当作数字使用(更确切地说,在 x * 2 中当作 integer() 或 float()),又在 byte_size(x) 中把它当作位串使用。在某些渐进类型系统中,类型检查器会接受上面的程序,尽管它在运行时会崩溃,因为动态类型可以在任何上下文中使用。

然而,在 Elixir 中,dynamic() 类型可以被细化,上面的代码会报告如下类型违规:


        warning: incompatible types given to Kernel.byte_size/1:

byte_size(x)

given types:

dynamic(float() or integer())

but expected one of:

bitstring()

where "x" was given the type:

# type: dynamic(float() or integer())
    # from: iex:3
    x * 2

└─ iex:4: Foo.using_x_as_number_and_binary/1
      

正如你在错误信息中所见,Elixir 推断出,经过 x * 2 之后,x 的类型是 dynamic(float() or integer())。这意味着 x 可以被传给任何至少接受 float() 或 integer() 之一的函数。然而,由于 byte_size(x) 期望一个位串,我们便遇到了类型违规。

这之所以可行,是因为 Elixir 中的 dynamic() 实际上表示 dynamic(term()),其中 term() 是顶类型。随后,随着变量在代码中被使用,它的动态类型会通过与其所调用函数的参数类型求交来细化。换句话说,我们会经历以下步骤:

  • x 起初是 dynamic(term())
  • x 被传给 x 2。 的左操作数期望 integer() 或 float(),我们将其与 term() 求交,因此 x 获得类型 dynamic(integer() or float())
  • x 被传给 byte_size(x),它期望一个 bitstring。integer() 或 float() 与 bitstring() 的交集为空,这将导致类型违规

现在,我们来看这个程序:


        def using_x_as_integer(x) do
  IO.puts x * 2
  IO.puts rem(x, 2)
  :ok
end
      

这一次,我们把 x 传给求余函数 rem,它期望其所有输入都是整数。这意味着,在这个函数的末尾,Elixir 会正确地推断出 x 只能是整数,因为 x 从 dynamic(term()) 被细化为 dynamic(integer() or float()),然后仅细化为 dynamic(integer())。using_x_as_integer 的推断类型是一个函数,通常用箭头记法写作:dynamic(integer()) -> :ok。

最妙的是,Elixir 中所有动态类型都会被细化,因此类型系统始终在尽力发现缺陷,即使存在动态性也是如此。而且,得益于反向箭头,细化本身往往相当精确,接下来我们将探讨这一点。

反向箭头

用反向箭头进行类型推断和类型收窄

箭头是函数的类型:integer() -> boolean() 是一个箭头,表示“给定一个整数,此函数返回一个布尔值”。箭头左侧的类型是它的定义域(它接受什么),右侧的类型是它的陪域(它返回什么)。每个函数都有箭头,无论它们来自你编写的类型签名,还是由 Elixir 根据函数的各个子句推断而来。

Elixir 中的函数可以用多个箭头来标注类型。作为练习,让我们来看一个对数字取负的函数,比如 negate(1) 返回 -1:


        def negate(number) when is_integer(number), do: 0 - number
def negate(number) when is_float(number), do: 0.0 - number
      

你可以用单个箭头给它这样的类型签名:


        $ integer() or float() -> integer() or float()
def negate(number)
      

然而,这个类型表示,如果你给它一个整数,它可能返回一个浮点数,而实际情况从来不是这样!这个签名太宽泛了。相反,我们可以用两个箭头给它这样的签名:


        $ integer() -> integer()
$ float() -> float()
def negate(number)
      

这精确地表达了:如果你给它一个整数,它返回一个整数。如果你给它一个浮点数,它返回一个浮点数。多个箭头是为具有多个子句的函数标注类型的绝佳方式,这在 Erlang 和 Elixir 中都很常见。

考虑到这一点,并记住 rem 只对整数有效(它的类型是 integer(), integer() -> integer()),你认为下面函数中 x 的推断类型是什么?


        def negated_remainder(x), do: rem(negate(x), 2)
      

你可能会认为 x 是 dynamic(integer() or float()),因为那是 negate 的定义域。然而,x 会再次被推断为 dynamic(integer()),因为 Elixir 会反向沿着箭头传播类型:它从最外层调用所期望的类型开始,向内推进,从结果到参数,直到抵达变量。让我们逐步分析。

  • 我们开始对该函数进行类型检查,发现了 rem(negate(x), 2)。rem 只有一个箭头,integer(), integer() -> integer(),所以我们知道 negate(x) 必须返回 integer() 才能通过类型检查
  • 现在我们类型检查 negate(x)。negate 有两个箭头:integer() -> integer() 和 float() -> float()。由于它的结果必须是整数,我们可以丢弃 float() -> float() 箭头,因为它从不返回整数。剩下的唯一箭头是 integer() -> integer(),所以 negate 的参数必须是 integer()
  • 现在我们类型检查 x 本身。x 初始类型为 dynamic(term())。然后我们将它与 integer() 求交集,得到 dynamic(integer())

换句话说,推断有两个方向。正向,从参数到结果,箭头告诉我们每个调用返回什么。反向,从结果到参数,箭头告诉我们为了让调用产生预期结果,每个参数必须是什么。当我们用多个箭头为程序给出精确的类型签名时,类型系统将使用这些相同的箭头来推断精确的类型。正如我们接下来将了解到的,Elixir 使用这种技术从守卫中推断类型,并执行类型收窄(也称为出现类型)。

守卫

现在我们有了理解 Elixir 如何执行守卫类型推断的基础。看这个函数子句:


        def something(x, y) when is_integer(x) and is_bitstring(y) do
  ...
      

x 和 y 的初始类型都是 dynamic(term())。我们也知道守卫只有在返回 true 时才会成功,并且我们有如下类型签名(大致):


        $ true, true -> true
$ true, false -> false
$ false, true -> false
$ false, false -> false
def and(left, right)

$ integer() -> true
$ not integer() -> false
def is_integer(value)

$ bitstring() -> true
$ not bitstring() -> false
def is_bitstring(value)
      

因此,为了推断 when is_integer(x) and is_bitstring(y) 的类型,我们从 true 开始,这是守卫成功的唯一结果,并反向沿着箭头传播它:

  • and 中唯一能返回 true 的箭头是 true, true -> true,因此我们知道两个操作数都必须为 true
  • is_integer 中唯一能返回 true 的箭头是 integer() -> true,因此我们知道 x 必须是整数
  • is_bitstring 中唯一能返回 true 的箭头是 bitstring() -> true,因此我们知道 y 必须是 bitstring

如果有多个箭头能返回 true,我们只需对它们的定义域取并集。

值得强调的是,这一行为并不是硬编码在类型检查器所知的少数几个函数上。它对任何函数、在任何上下文中都有效。让我们看更多例子。

类型收窄(也称为 occurrence typing)

Occurrence typing 根据条件分支或模式匹配中所走的分支来细化变量和表达式的类型,因此同一个变量在不同分支中可能具有不同的类型。例如:


        if is_bitstring(x) do
  x #=> x has type: bitstring()
else
  x #=> x has type: not bitstring()
end
      

我们用来执行 occurrence typing 的机制与前几节中的机制非常相似。在 do 分支内,我们考虑 is_bitstring(x) 会返回 true 的场景。在 else 分支内,我们考虑它返回 false 的场景。

而且,由于我们的基础建立在反向箭头之上,收窄也适用于模式和 case 表达式!例如:


        def f(x) do
  case parse(x) do
    {:ok, _} -> ... # x is integer()
    :error -> ...   # x is bitstring()
  end
end

defp parse(x) when is_integer(x), do: {:ok, x}
defp parse(x) when is_bitstring(x), do: :error
      

在这里,parse 没有类型签名,但 Elixir 从它的子句中推断出箭头:integer() -> {:ok, integer()} 和 bitstring() -> :error。在第一个分支中,我们知道 parse(x) 返回了一个元组,而唯一返回元组的箭头以 integer() 为定义域,因此 x 必须是整数。

If-T 基准是一组测试场景,旨在评估类型收窄的精确性和可靠性。Elixir v1.20 已经处理了 13 个测试中的 12 个,但它无法为这个例子推断出正确的类型:


        y = is_integer(x)

if y do
  # y is true, x remains dynamic
else
  # y is false, x remains dynamic
end
      

要收窄 x,我们需要反转 is_integer(x) 的箭头。在 Elixir v1.20 中,我们只对直接传给 if 或 case 的表达式这样做。这里,传给 if 的表达式是变量 y。v1.20 对 y 的全部了解就是它是一个 boolean()。在 do 分支内,y 是 true,但此时 y 与 is_integer(x) 之间的联系已在赋值时丢失,因此没有箭头可以反转。

一旦我们加入类型签名,这会相当有害,因为这意味着诸如把表达式提取到变量中这类平凡的代码重构,可能会导致误报。

Elixir v1.21 通过跟踪每个变量被赋予的表达式解决了这个问题。现在,当 y 被收窄为 true 时,我们知道 y 来自 is_integer(x),因此我们继续让 true 反向沿 is_integer 的箭头传播,将 x 收窄为 integer()。这对任意数量的赋值都有效:


        y = is_integer(x)
z = not y

if z do
  # z is true, y is false, x is not integer()
else
  # z is false, y is true, x is integer()
end
      

我们的实现还以惰性方式执行收窄,将 if 和 case 表达式中的变量与每个子句中使用的变量相互对照,试图找出它们彼此共享的任何赋值。如果上面的子句不访问 z、y 或 x,则不执行收窄。

最后,由于 Elixir 为几乎所有操作定义了反向箭头,它可以细化目前在 TypeScript 中未被细化的表达式,例如数据构造器:


        def f(foo) when is_bitstring(foo) or is_integer(foo) do
  map = %{foo: foo}

if is_bitstring(map.foo) do
    byte_size(foo)
  else
    foo + 1
  end
end
      

文章标题:使用反向箭头进行类型推断与类型收窄

正文: 在上面的程序中,即使 foo 被设置为 map 的值,细化 map 仍然会细化原始变量。

总结

Elixir 的类型推断与类型收窄方法建立在几个能够良好组合的思路之上。动态类型会随着变量的使用而被细化,多重箭头为函数赋予精确的类型,而沿着这些箭头反向传播类型,使我们能够在条件分支、模式匹配和赋值之间推断并收窄类型,这一切都无需硬编码关于特定函数的知识。

在 Elixir v1.21 中,我们使用这些技术在现有 Elixir 程序中找出确定的缺陷,而无需对代码做任何修改。一旦引入类型签名,同样的机制依然适用:签名越精确,收窄就越精确,误报也就越少。

The translation is machine-generated and individual terms may be off. Nothing is rewritten or cut; the original is authoritative.

Published by Lobsters
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗