使用反向箭头进行类型推断与类型收窄
本文阐述了 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 程序中找出确定的缺陷,而无需对代码做任何修改。一旦引入类型签名,同样的机制依然适用:签名越精确,收窄就越精确,误报也就越少。