为什么当我尝试使用 SKI-calculus 中的“S I I”实现递归时,Rust 会失败?

Why Rust fails when I try to implement recursion with "S I I" from SKI-calculus?

提问人:Doubtful 提问时间:8/21/2023 更新时间:8/21/2023 访问量:57

问:

注意:我从这里获取了定义:https://en.wikipedia.org/wiki/SKI_combinator_calculus#Informal_descriptionSI

所以,或者在 Rust 中:S xyz = xz(yz)

fn s <Z, Y, X> (
    x: fn(Z) -> fn(Y) -> X,
    y: fn(Z) -> Y,
    z: Z
) -> X
where Z: Copy
{
    x(z)(y(z))
}

我们再定义一个辅助:I x = x

fn i <X> (x: X) -> X { x }

我知道那是(我实际上试图解决的问题是找到一种适用于自己的类型),但是我们不要成为那个通用的rn并尝试使用。S I I xx(x)xxS I I I

明显地S I I I = I(I)(I(I)) = I(I) = I

let _ = s(i, i, i); // = i(i)(i(i)) = i(i) = i

这在我眼中是合法的,但在编译器中却不是:

error[E0308]: mismatched types
  --> src/main.rs:45:18
   |
45 |     let _ = s(i, i, i);
   |             -    ^ cyclic type of infinite size
   |             |
   |             arguments to this function are incorrect
   |
note: function defined here
  --> src/main.rs:32:4
   |
32 | fn s <Z, Y, X> (
   |    ^
33 |     x: fn(Z) -> fn(Y) -> X,
34 |     y: fn(Z) -> Y,
   |     -------------

我找到了一个“解释”,即发生此错误是因为 rustc 无法应对某些不可计算的类型。这是有道理的,但我在这里没有看到任何上述类型的例子。你能告诉我它发生在哪里(以及如何解决它,如果可能的话)?

递归 蚀 lambda-calculus

评论


答:

1赞 jthulhu 8/21/2023 #1

让我们试着写出 Rust 必须解决的类型方程,以了解出了什么问题。每个都有给定的类型。由于它们可以为每个独立选择,我将命名它们 和 。ifn(X) -> XXiX₁X₂X₃

  1. 第一个有类型,预期的类型是 ,所以通过统一,我们有(1)。ifn(X₁) -> X₁fn(Z) -> fn(Y) -> XZ = X₁ = fn(Y) -> X
  2. 第二个有类型,预期的类型是 ,所以通过统一,我们有(2)。ifn(X₂) -> X₂fn(Z) -> YZ = X₂ = Y
  3. 第三种类型方程是(3)。X₃ = Z

通过组合 (1) 和 (2),我们有 .这个类型方程是循环的:你永远不会找到一个有限类型(至少在 Rust 的类型系统中)可以满足这一点。Y = fn(Y) -> X

顺便说一句,如果你使用 -rectypes 显式打开递归类型,OCaml 可以对其进行类型检查:

# let s x y z = x z (y z) in s Fun.id Fun.id Fun.id;;
- : 'a -> 'a as 'a = <fun>
#

如果您正在探索 lambda 演算和朋友们,OCaml 可能是更好的选择。

至于 Rust,我认为没有任何类型友好的方法可以做到这一点。

评论

0赞 Doubtful 8/21/2023
好的,谢谢你的帮助,现在我明白了!我不确定带有递归类型的 OCaml 对我来说是否是一个合适的选择,因为任务是在强类型语言中实现 Y 组合器,因此递归类型看起来像作弊,因为如果我使用递归来实现递归......那不行:)
1赞 jthulhu 8/21/2023
@Doubtful我认为在不实现递归的类型系统中不可能实现 Y 组合器,但我不确定为什么。我本来打算添加一些与不可能像这样在 Rust 中嵌入 SKI 演算有关的东西,但我必须先考虑一下。当我发现有意义的东西时,我会编辑我的答案。
0赞 Doubtful 8/21/2023
IMO 这并不是说你不能在非递归上下文中实现 Y 梳,更像是这个上下文不应该施加某些类型限制。简单的例子:无循环的几乎无一切的 Javascript。这里可以定义 Y 梳(证明:benestudio.co/fixed-point-combinators-in-javascript),所以这都是关于类型的......
0赞 Will Ness 8/21/2023
@Doubtful,您要么想提前了解全部类型,要么不想。第一种称为静态类型规程,第二种称为动态类型规程。在静态类型规则中,所有类型必须彼此一致,这就是检测错误的方式。对于参数类型,这意味着求解类型方程组,例如,从 a=b 和 b=c 我们也得出 a=c。因此,当我们看到 a=b 和 a=b->c 时,我们必须得出 b=b->c 的结论,看看这是否自相矛盾。由于 B->C 涉及两个类型变量,因此我们查找它们的定义。c 没有,但 b 是 b->c,所以它必须保持
0赞 Will Ness 8/21/2023
...b=(b->c)->c=((b->c)->c)->c=...检查永不停止。或者我们可以在类型系统中添加一个功能,然后说,我们对这样的方程没问题,不要替我们检查它们,相信我们没关系。这些是递归类型。在语言中进行递归不是作弊,它仍然可以禁止它。类型是一个单独的领域。因此,要拥有非递归 Y 组合器,要么根本没有类型(“动态类型规则”),要么具有允许递归类型方程的静态类型系统。这是两个选择。(据我所知,我根本不是专家)。