提问人:Doubtful 提问时间:8/21/2023 更新时间:8/21/2023 访问量:57
为什么当我尝试使用 SKI-calculus 中的“S I I”实现递归时,Rust 会失败?
Why Rust fails when I try to implement recursion with "S I I" from SKI-calculus?
问:
注意:我从这里获取了定义:https://en.wikipedia.org/wiki/SKI_combinator_calculus#Informal_descriptionS
I
所以,或者在 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 x
x(x)
x
x
S 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 无法应对某些不可计算的类型。这是有道理的,但我在这里没有看到任何上述类型的例子。你能告诉我它发生在哪里(以及如何解决它,如果可能的话)?
答:
1赞
jthulhu
8/21/2023
#1
让我们试着写出 Rust 必须解决的类型方程,以了解出了什么问题。每个都有给定的类型。由于它们可以为每个独立选择,我将命名它们 和 。i
fn(X) -> X
X
i
X₁
X₂
X₃
- 第一个有类型,预期的类型是 ,所以通过统一,我们有(1)。
i
fn(X₁) -> X₁
fn(Z) -> fn(Y) -> X
Z = X₁ = fn(Y) -> X
- 第二个有类型,预期的类型是 ,所以通过统一,我们有(2)。
i
fn(X₂) -> X₂
fn(Z) -> Y
Z = X₂ = Y
- 第三种类型方程是(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 组合器,要么根本没有类型(“动态类型规则”),要么具有允许递归类型方程的静态类型系统。这是两个选择。(据我所知,我根本不是专家)。
评论